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:
- Enemies do not seek the player's character
- However, some enemy units will wander
- Enemies will have a different movement speed depending on enemy type
- The player moves the avatar by clicking the destination (this initiates a walk)
- The player can start start running by double clicking a destination (this can happen in-between grid nodes)
- The player has allies that follow the avatar
- 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)
- 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!