Flowfield pathfinding algorithm ?
Posted: 28 Aug 2016, 15:43
As far as I can tell Warzone pathfinding is using the A Star algorithm to plan unit movement. However they're often stuck since A Star doesn't take others unit into account.
Most RTS have been facing similar issues and a couple of them came with some solutions. For instance Starcraft 2 uses flocking which means every unit's movement is influenced by its immediate neighboors (see this http://gamedevelopment.tutsplus.com/tut ... medev-3444 ).
Supreme Commander 2 and Planetary Annihilation uses the Flowfield algorithm and it shows even more impressive results : https://www.youtube.com/watch?v=bovlsENv1g4 .
The idea behing flowfield is to model units as a fluid dynamic simulation. A cost field (= grid) is first computed with higher cost being discomfort zone. An integration field is then generated ; it represents the "time" needed for an unit close to the cell in the grid to reach the destination. This integration field uses unit density to add "time" in congestionned area.
The last step is to compute gradient over the field : it gives the direction a unit close to a cell should take to reach the goal.
Obviously the cost of this algorithm is higher than the classic A star one and need to be computed for every tick (to update unit density) and for every goal. I don't know what is the API handling pathfinding but maybe it should be possible to share pathfinding data for unit with the same destination goal ; it should make the algorithm practical.
Algorithm détails can be found here http://www.gameaipro.com/GameAIPro/Game ... _Tiles.pdf
Most RTS have been facing similar issues and a couple of them came with some solutions. For instance Starcraft 2 uses flocking which means every unit's movement is influenced by its immediate neighboors (see this http://gamedevelopment.tutsplus.com/tut ... medev-3444 ).
Supreme Commander 2 and Planetary Annihilation uses the Flowfield algorithm and it shows even more impressive results : https://www.youtube.com/watch?v=bovlsENv1g4 .
The idea behing flowfield is to model units as a fluid dynamic simulation. A cost field (= grid) is first computed with higher cost being discomfort zone. An integration field is then generated ; it represents the "time" needed for an unit close to the cell in the grid to reach the destination. This integration field uses unit density to add "time" in congestionned area.
The last step is to compute gradient over the field : it gives the direction a unit close to a cell should take to reach the goal.
Obviously the cost of this algorithm is higher than the classic A star one and need to be computed for every tick (to update unit density) and for every goal. I don't know what is the API handling pathfinding but maybe it should be possible to share pathfinding data for unit with the same destination goal ; it should make the algorithm practical.
Algorithm détails can be found here http://www.gameaipro.com/GameAIPro/Game ... _Tiles.pdf