Announcement: Be excellent to each other.


Caravel Forum : Caravel Boards : Development : The Old Movement Order Problem (Algorithmic thinking.)
New Topic New Poll Post Reply
Poster Message
ErikH2000
Level: Legendary Smitemaster
Avatar
Rank Points: 2462
Registered: 02-04-2003
IP: Logged
icon The Old Movement Order Problem (+4)  
So you know how when you move Beethro... and there's a bunch of roaches all together that should move towards Beethro as a group... but they end up having gaps in their formation?

I always wanted them to skitter neatly together--no gaps. And their irregular gaps led to a class of puzzles I really dislike--movement order puzzles. Roaches (or just monsters in general) that are earlier in the movement order will end up running into other monsters and not moving in a turn. While the monsters later in the movement order will successfully move into their destination squares.

Today, I was fooling around with some code and finally got the monsters to work well with each other. In my opinion, this will never go into DROD, because DROD now depends upon the movement order weirdness. But I still get large satisfaction from solving a 2-decade-old problem. (For me, anyhow. I'd be surprised if some CS/math pioneer didn't solve this before I was even born.)

But because I want an excuse to brag a little with people that might understand the problem, I'll post my algorithm here, which works quite well and makes me gleeful.

Definitions: we have a Room, which is a graph or grid of connected squares, and Monsters that are able to move within the Room in turns. Only one Monster may be in a square at one time, and on any turn, a Monster may move entirely out of its current square and into an adjacent square. Monsters determine for themselves what their goal squares are, and can move to them if no obstacle, which could be another Monster, is present within the goal square.

1.  Put all the Monsters into a LIFO queue (stack) called the Queue.
2.  While the Queue is not empty...
3.     Get the next Monster (Current Monster) from the Queue without popping it.
4.     If Current Monster can move to a goal square...
5.        Move Current Monster to goal square
6.        Pop Current Monster from the Queue
7.        Mark the Current Monster as "settled"
8.     Else If Current Monster was blocked by another Monster (Blocking Monster) and Blocking Monster is not marked "settled" and Blocking Monster did not previously block Current Monster...
9.        Track that that Current Monster was blocked by Blocking Monster (for later check of #8)
10.       Push Blocking Monster onto Queue
11.    Else...
12.       Mark Current Monster as "settled"
13.       Pop Current Monster from Queue.


And this will work with monsters that have paths running into each other too. Imagine a roach running towards Beethro and a roach queen running away, with the two of them blocking each other in a single-square corridor. The check on #8 keeps the loop from going infinite.

There must be some cases where the monsters give up too soon, but probably this covers most cases, and is compatible with varied goals, pathfinding, and obstacle checks for different types of monsters. And I think it avoids processing any single monster for movement more than twice.

-Erik

____________________________
Godkiller Gamedev streams (live sessions where I make a new puzzle game. NSFW, mature content)
youtube (archive of live streams, and some animated videos I made. Again, contains mature content.)
02-17-2019 at 05:10 AM
View Profile Send Email to User Show all user's posts This architect's holds Quote Reply
averagemoe
Level: Master Delver
Avatar
Rank Points: 274
Registered: 03-22-2012
IP: Logged
icon Re: The Old Movement Order Problem (+1)  
If I were to try to solve the problem, I'd probably make it so that a new movement order is generated each round, with monsters closest to Beethro going first.

____________________________
Black Lives Matter. And I don't mean that exclusively. Lives of all colors matter.
02-17-2019 at 05:44 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
mauvebutterfly
Level: Smitemaster
Rank Points: 507
Registered: 05-03-2015
IP: Logged
icon Re: The Old Movement Order Problem (0)  
Nice!

Although, if the goal is to avoid movement order puzzles, wouldn't this create an entirely different class of them? Consider the following:

B - Beethro, 0 - open space, R - roach, W - wall

BW0R
00R0
000R

Here if the middle roach moves first and slides along the wall the bottom roach will move into the space that the middle roach used to occupy, but if the bottom roach moves first it will slide up along the top roach. The top roach moving first will change where the middle roach moves.

____________________________
106th Skywatcher
02-17-2019 at 05:49 AM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
ErikH2000
Level: Legendary Smitemaster
Avatar
Rank Points: 2462
Registered: 02-04-2003
IP: Logged
icon Re: The Old Movement Order Problem (0)  
quote:
averagemoe wrote:
If I were to try to solve the problem, I'd probably make it so that a new movement order is generated each round, with monsters closest to Beethro going first.

I played with that notion, but I thought that the definition of “closest” would vary between different kinds of monsters. Or monsters might have different locations they are trying to reach.

I agree your algorithm should work well in some cases, and has advantages over mine. Right tool for the right job, I guess.

-Erik

____________________________
Godkiller Gamedev streams (live sessions where I make a new puzzle game. NSFW, mature content)
youtube (archive of live streams, and some animated videos I made. Again, contains mature content.)
02-17-2019 at 06:18 AM
View Profile Send Email to User Show all user's posts This architect's holds Quote Reply
ErikH2000
Level: Legendary Smitemaster
Avatar
Rank Points: 2462
Registered: 02-04-2003
IP: Logged
icon Re: The Old Movement Order Problem (+1)  
quote:
mauvebutterfly wrote:
Although, if the goal is to avoid movement order puzzles, wouldn't this create an entirely different class of them?

Yes, very hard to get rid of the consequences of movement order altogether. The remedies are making more rules, and just hoping those rules are intuitive for people to recognize as patterns,

I also set the movement order of monsters being fed into the alg above to be west-to-east, north-to-south, and those two things give it a predictable, ordered feel. Yet, always possible to find a little rule quirk.

-Erik

____________________________
Godkiller Gamedev streams (live sessions where I make a new puzzle game. NSFW, mature content)
youtube (archive of live streams, and some animated videos I made. Again, contains mature content.)
02-17-2019 at 06:32 AM
View Profile Send Email to User Show all user's posts This architect's holds Quote Reply
Dying Flutchman
Level: Smiter
Avatar
Rank Points: 397
Registered: 01-27-2017
IP: Logged
icon Re: The Old Movement Order Problem (+2)  
quote:
ErikH2000 wrote:
quote:
mauvebutterfly wrote:
...Yet, always possible to find a little rule quirk.

-Erik



I would propose to rephrase this as:

Naturally, architects will abuse these rules to build devious puzzles based on whatever quirks and edge-cases there could possibly be.

But OT: nice solution, although I am very happy with movement order.

Basically, there seems to be a general 'evolution' in drod puzzles.
1) New elements with new rules. Hurray!
2) Architects: let's build puzzles with those elements.
3) Players / architects: we have seen about every possible puzzle.
4) Smart architects: hey, look at this unintuitive side-effect/interaction/bug that we can turn into a puzzle.
5) Players: this is ridiculous.
6) Wait for a while
7) H&S forum discussions: "I see you were having trouble with that puzzle. You really need to know about this singular exploit. It has been around for a while now, but it still confuses the hell out of novice players. Sorry..."
8) New elements with new rules. Hurray!

Honestly, I see all this rule-bending as a kind of collective learning process. The ridiculous rule-bending will stop at some point (e.g. magic sequence rooms depending on movement order), while the good (?) rule-bending will become a part of the standard toolbox of architects (e.g. mimics pushing Beethro across plates or traps wihtout activating, also basically using movement order).

____________________________
Autocorrect is not my friend. Apologies for the typos.

[Last edited by mrimer at 02-17-2019 03:47 PM]
02-17-2019 at 09:37 AM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
Actually Ed
Level: Goblin
Avatar
Rank Points: 22
Registered: 08-13-2018
IP: Logged
icon Re: The Old Movement Order Problem (+1)  
I wonder if "Movement Order Tokens" would work, or if that would be too weird and meta. Though that encourages what you were trying to avoid in the first place, which is movement order puzzles. Could just be something to confuse new people even more :fun
02-17-2019 at 08:54 PM
View Profile Send Private Message to User Show all user's posts High Scores Quote Reply
mauvebutterfly
Level: Smitemaster
Rank Points: 507
Registered: 05-03-2015
IP: Logged
icon Re: The Old Movement Order Problem (+1)  
quote:
Actually Ed wrote:
I wonder if "Movement Order Tokens" would work, or if that would be too weird and meta. Though that encourages what you were trying to avoid in the first place, which is movement order puzzles. Could just be something to confuse new people even more :fun


Actually, a "stalwart/soldier movement token" has been something we've discussed in chat as a way to make their pathfinding more predictable in new holds without invalidating old high scores.

____________________________
106th Skywatcher
02-17-2019 at 11:19 PM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
ErikH2000
Level: Legendary Smitemaster
Avatar
Rank Points: 2462
Registered: 02-04-2003
IP: Logged
icon Re: The Old Movement Order Problem (0)  
quote:
Actually Ed wrote:
I wonder if "Movement Order Tokens" would work, or if that would be too weird and meta.

Noooooooooo!

I should be more open-minded, I guess. I really like puzzles that are more intuitive than that.

-Erik

____________________________
Godkiller Gamedev streams (live sessions where I make a new puzzle game. NSFW, mature content)
youtube (archive of live streams, and some animated videos I made. Again, contains mature content.)
02-20-2019 at 02:53 AM
View Profile Send Email to User Show all user's posts This architect's holds Quote Reply
Pearls
Level: Smitemaster
Avatar
Rank Points: 747
Registered: 12-21-2009
IP: Logged
icon Re: The Old Movement Order Problem (+2)  
I'm pretty amused by this whole thread. Erik himself dislikes movement order puzzles, something that's become (definitely vexing at time) a staple of DRODery. By way of not solving a problem, yielded a tremendous amount of puzzle potential, tedious or otherwise. I feel like Erik has a knack for this kind of thing. Like, serpent movement. "How do I make these snakes be wiggly like snakes and go after beethro" -> tremendous puzzle potential. I love it.

Somewhere, Larry Murk weeps.

____________________________
Hey, w-wait, that's the guy who shamelessly promotes his own...

Click here to view the secret text

02-20-2019 at 04:21 PM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
ErikH2000
Level: Legendary Smitemaster
Avatar
Rank Points: 2462
Registered: 02-04-2003
IP: Logged
icon Re: The Old Movement Order Problem (+2)  
quote:
Pearls wrote:
I'm pretty amused by this whole thread. Erik himself dislikes movement order puzzles, something that's become (definitely vexing at time) a staple of DRODery.

I actually quite appreciate that the DROD community is large enough to have factions, camps, schools of thought.

Even now I'm still getting it clarified in my mind what puzzles are fun or not. Which means it's an elusive thing to chase.

-Erik

____________________________
Godkiller Gamedev streams (live sessions where I make a new puzzle game. NSFW, mature content)
youtube (archive of live streams, and some animated videos I made. Again, contains mature content.)
02-22-2019 at 10:47 PM
View Profile Send Email to User Show all user's posts This architect's holds Quote Reply
New Topic New Poll Post Reply
Caravel Forum : Caravel Boards : Development : The Old Movement Order Problem (Algorithmic thinking.)
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.8
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.