Notifications
Article
Multi-Threaded Flow Field AI Pathing
Updated 7 months ago
83
0
Using multi-threading to generate a Flow Field that allows infinite amount of enemies to chase a player in a 2D grid environment.

What is this?

This algorithm creates a 10 x 10 (range is specifically made for my game) Vector Flow Field for every tile possible. In addition it splits the work into other threads while main thread creates fields for the player's current position. This allows players to interact with the game and enemies without having to wait for the level to be finished. This is useful for multiple objects frequently chasing a target.

What is a Flow Field

It is an algorithm using a modified Dijkstra's Algorithm to create a grid with each point having a direction towards its parent until it reaches the target. Objects on this field can use the point's direction to move towards the target. Additionally, it's a simple algorithm with low computation but still very effective. Unlike A* which finds the absolute shortest path, Flow Fields find all possible paths to a location.

How I Made It Special

Instead of constantly computing a field, I instead computed a 10 x 10 tile field for every possible tile in a game map, and stored them into a dictionary. The dictionary is then accessed using the player's position. Dictionary<Vector2Int, List<VectorTile>> Where the Vector2Int is the player's position, and List<VectorTile> is the flow field. Furthermore, I use multiple threads to compute the flow field for each chunk of the map. However, using thread.Join() on the main thread causes Unity to stop all processes until this Algorithm is done, so I had to create a thread that creates other threads and joins them.

Unity-ized

Unity's Tilemap currently is currently limited with how you can interact with it, but is extremely use full for quick map generation. What I did was create a custom class VectorTile to store custom data for each tile in a Tilemap and worked with those. This allows me to build a map in Unity using the Tilemap, without having to worry.

Tests

These tests are done with Unity's Profiler and with 1 thread setting up 4 worker threads, as using thread.Join() on side of the setup thread will cause unity to freeze all other operations. Cpu: Intel i7 - 7700 Hz @ 2.8 Gz Ram: 16 GB

While player standing still

This is a rare scenario of the player not moving for an average 4,320 milliseconds. The spike at the end is the Unity's console log







While player is moving

The spikes are the player's movement and the path being calculated for that tile. The lag is bearable and only lasts for an average of 4,083 milliseconds.






Threads joined is called on main thread

Calling thread.Join() on the main thread causes all other processes to halt, meaning the profiler can not capture what is happening. However, this led to an astounding performance increase. The average time taken to run 900 calculations is 3,214 milliseconds.




Conclusion

This was an amazing experiment that let me explore and learn more about AI pathing and multi threading. My code is up on my github and I am open to all criticisms. https://github.com/Gismar/FlowFieldPathing#flow-field-ai-pathing
I will be using this on my actual project and I hope this helps other people with theirs.
GH
Gismar Horsch
2
Comments