🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Back to Artificial Intelligence

Flow Field Architecture Advice

Titas Kibas · 2019-03-04T12:16:10

Hello GameDevs, Context: I would consider myself a novice and am working on a RTS working project to practice my C++ and game programming skills. It is a tech demo to practice optimisation in the future, I am aiming to have it contain as many basic agents with rudimentary AI that can be controlled and optimising the system to allow for the most amount of these agents while still maintaining 60 FPS as a benchmark. Problem: I am aiming to implement Flow Fields for pathfinding and have managed a basic implementation with Flow Field follow and no steering behaviour as of yet. However, I have run into a design decision I am unsure of ,and was wondering if anyone could advise me of some potential architecture choices. When implementing Goal-Based Vector Field Pathfinding, what would be the most efficient way of keeping the flow field data when manipulating many clusters of agents? Current Thinking: It seems inefficient to recalculate per cluster of agents unless a new goal is set for them, so I would have to maintain the flow field at least up until the goal is met. I was considering creating a data structure like a map, that indexes each generated and maintained Flow Field based on whether some agent clusters are still trying to reach that goal, after which I would terminate. Then update each cluster every 1 to 2 seconds in order to not throttle the cpu. Currently the algorithm for updating the Flow Field is rudimentary and not optimised. Each Flow Field currently takes up about 11MB (31x31 for testing purposes) of memory and I am concerned that I could run into a scenario that could take up a lot of memory if enough particularly small clusters of agents are all trying to move across the map, especially when the map would be bigger. Question: Could you provide any advice on potential architecture choices that would be ideal in this Scenario or direct me to some implementations/papers? I have so far only managed to find implementations and demos of Flow Fields only with 1 goal and 1 cluster in mind, but not when put into practice in a real game with multiple clusters of units simultaneously moving around the map. Many thanks.

Artificial Intelligence Programming C++ Pathfinding 2D

Started by Satyrant February 25, 2019 10:34 PM

12 comments, last by LorenzoGatti 5 years, 3 months ago

LLachance

March 02, 2019 07:32 AM

Wow, such a small world,

I too was implementing flow-fields in my sfml game demo just last week. I have been able to make it on huge maze pretty fast. I did not encounter a problem with memory, but I always reuse the same node tree to recalculate the flow-field with others objectives.

Think about reusing data that you don't use anymore, maybe it will speed it up a bit, with less memory impact.

First time I checked but my 250*250 maze is 4,480,000 bytes. So each node is about 72 bytes.

I don't know what you did to get 11,000,000 bytes in 31*31 but it is huge.

Each of your node are 11,447 bytes. Your data structure need a major update.

Btw I can support up to 18,000 AI that follow my flow-fields at 70 fps. After that it start to do cache miss and all start to go wrong. My data structure rely a lot on the CPU cache.

My maze:

vector are going from green to red

LLachance

March 03, 2019 06:34 PM

Here is a working video !!!

2019-03-03_13-26-01.flv

LorenzoGatti

4,652

March 04, 2019 12:16 PM

For each tile, the flow field needs only 2 bits (go up/down/left/right), or 3 bits if allowing diagonal moves (4 additional directions). 1 MB of flow field (2^28 bits) should suffice for 2^25 map cells, e.g. 4096 by 8192.

In case you also need the distance to the target (e.g. for some AI decisions), with direction computed on demand, on a M by N tilemap it is an integer between 0 and M*N: a tiny 31 by 31 map needs 10 bits per cell, for a total of less than 4 KB.

Omae Wa Mou Shindeiru