Flowfield pathfinding algorithm ?

For code related discussions and questions

Flowfield pathfinding algorithm ?

Postby Vincent » 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
Vincent
Trained
Trained
 
Posts: 64
Joined: 06 Aug 2016, 17:24

Re: Flowfield pathfinding algorithm ?

Postby Cyp » 28 Aug 2016, 19:32

Yes, it's A*. The pathfinding is done from destination to source, and if another unit pathfinds to the same destination at the same time, the A* search for that destination is reused with the new source.

Think people have suggested various things, think flowfield was one of them.

The pathfinding system should probably be rewritten with something smarter and more efficient, but noone has done it yet (despite one or more people saying they would).
Cyp
Evitcani
Evitcani
 
Posts: 677
Joined: 17 Jan 2010, 23:35

Re: Flowfield pathfinding algorithm ?

Postby Vincent » 29 Aug 2016, 19:22

By the way looking at the code is the threading really improving performance ?
Apparently the critical section includes a call to fpathExecute (in fpathThreadFunc). fpathRoute which is used to retrieve the result from the main thread or submit job request a lock on fpathmutex. This means that the main thread may be stalled when the fpath thread is doing work which may happens when moving several droids at the same time.

I think fpathExecute should be removed from the critical section but my early tests seem to hint that it can introduce race condition.
Vincent
Trained
Trained
 
Posts: 64
Joined: 06 Aug 2016, 17:24

Re: Flowfield pathfinding algorithm ?

Postby Cyp » 29 Aug 2016, 20:29

Uh, apparently the code has been practically single-threaded since 4986580f0845f47553713c2b3afbdfa82296d12a, so no, it probably doesn't improve performance much if at all.

The issue it was supposed to fix might be fixed by 297b3e43bf389c89acf7881741c1eaed0139bc41, so reverting 4986580f0845f47553713c2b3afbdfa82296d12a might not break anything.
Cyp
Evitcani
Evitcani
 
Posts: 677
Joined: 17 Jan 2010, 23:35


Return to Coding