Implementing David Silver's Cooperative Pathfinding in Real-Time

Question

I'm currently implementing David Silver's Cooperative Pathfinding algorithm for a 2D game with grid-based movement (all eight directions).

The issue I'm having trouble wrapping my mind around is the Reservation Table with respect to real-time. I've fully implemented the algorithm in its own testbed; however, my implementation is turn-based where everybody is moving at the same speed.

The game I'm trying to integrate the group pathfinding into has real-time movement with units having different speeds.

---

I've compiled a few considerations I need to take into account and some that could help me implement this:

1. Enemies do not seek the player's character
2. However, some enemy units will wander
3. Enemies will have a different movement speed depending on enemy type
4. The player moves the avatar by clicking the destination (this initiates a walk)
5. The player can start start running by double clicking a destination (this can happen in-between grid nodes)
6. The player has allies that follow the avatar
7. Allies will run to keep up with the avatar if too far away and start walking again if close enough (this can also happen in-between grid nodes)
8. Speeds are not perfect multiples of each other

---

With those in consideration, my current partial solution consists of the following:

• Because of consideration 1 and 2, enemies will share reservation tables since I can have them move on the same intervals so their times will match up
• Because of considerations 3 and 8, the enemies' reservation tables will differ by movement speeds. I am thinking of doing it this way because I'm not sure how to use one reservation table for all of them if their speeds are not perfect multiples of each other.
• Because of the speed-change considerations of 4, 5, 7, and 8, the player's and allies' paths will be recalculated whenever they start walking or start running since that will affect path coordination.
• Because paths can be recalculated for the player avatar on the fly, I will need to have two reservation tables specifically for the player (one for walk, one for run). I would also possibly need to have two reservation tables for the allies to share (one for walk, one for run).
• Because of the fact that paths can be recalculated in-between nodes, I believe I will have to limit changes of speed to only occur when a unit is directly on a node rather than being able to change speeds in-between nodes as it currently works. Otherwise, I believe I would have to calculated the time it will take to reach the next node and then track that in the reservation table as well somehow.

---

Finally, here are things I'm wondering about:

• I must be not understanding the Reservation Table completely if coordinating units is this difficult. How do I define the time of a node in the Space-Time map if not by how long it takes one unit to get from one node to another?
• Is diagonal movement going to be an issue when defining the time of a node in the Space-Time map?
• Is there an easier way to handle implementing this short of implementing a different group pathfinding algorithm?
• If there is another pathfinding algorithm you recommend, I am all ears, but at this point in development, there most likely isn't any time to implement something new unless coding it as well as integrating it into the game would take less time than jamming the already-coded algorithm into the game.

---

Feel free to suggest ways of slightly altering how enemies, the player, and the allies move if that will make implementing this significantly easier. I appreciate any help you feel like offering. Thanks for your time!

Answer 1

Not being familiar with this approach prior to reading the linked document, it seems like the confusion comes from using multiple reservation tables. That would be missing the point of having a reservation table. You could prevent collisions between units of the same type, but a fast unit and a slow unit trying to cross the same space could still end up in a collision reaction dance as they attempt to move through each other. Further, page 11 of the linked pdf addresses that specific issue stating they are expected to share a reservation table.

If your design calls for a friendly unit to be able to run past a group of enemy units, allies and enemies will share a reservation table as well. If you specifically want them to do a collision dance when they're close together, maybe you could use separate tables for each group, but I would still think it's preferable to keep all their pathing on the same reservation table and rely on behavioral logic to determine if they stop to interact, or continue moving. By which I mean you could hack some of your logic by intentionally pooching the pathfinding, but I very strongly recommend against it.

I think I see where the uncertainty is coming in for diagonal moves, or different speed multiples, but again the pdf would indicate continuing to use the same reservation table, and reserving a larger space for units whose movement speeds do not fit cleanly into the interval established by the table. If a unit is moving diagonally and will partially occupy multiple tiles during some portion of the reservation table, reserve all those tiles for that interval. If, x seconds from now, a faster or slower unit will be partially in one tile and partially in another due to moving at a speed that is not a clean multiple of the interval used in the table, reserve both tiles.

Finally, a change in unit speed from running to walking should not generate a second reservation table, it should refresh that unit's path along the one reservation table all units share.

The only case where I would think it to be appropriate to have multiple reservation tables is if you have different movement elevations (in a 2D game, or 3D rendered game where movement is restricted to 2D planes) where flying units can pass over the heads of ground units without colliding. In a full 3D game, you would use a 4D reservation table.

It might help to do some reading into animation. Conceptually, the reservation table shares (in my mind) some elements with animating a vertex that is expected to move from this point to that, starting at this time, ending at this time, while the game clock is all but guaranteed to not update perfectly in time with the model's keyframe intervals.