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
____________________________
The Godkiller - Chapter 1 available now on Steam. It's a DROD-like puzzle adventure game.
dev journals |
twitch stream |
youtube archive (NSFW)
