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.

Flow fields generally are only used with one goal. It doesn't matter how many agents there are and whether or not they are clustered. The entire nature of flow fields (if we are using the same terminology here) is that you drop a vector towards where you need to head to get to the goal and then agents simply look at the vector near their feet (so to speak). If you have multiple goals, you would need multiple flow fields (e.g. via a separate 2D array of field vectors for each goal). If you did that, you could then have an agent know which goal it is going to and look up its vector from that layer. The trick then is assigning a goal to an agent -- which of course, could be done by some sort of clustering algorithm.

4 hours ago, IADaveMark said:

Flow fields generally are only used with one goal. It doesn't matter how many agents there are and whether or not they are clustered. The entire nature of flow fields (if we are using the same terminology here) is that you drop a vector towards where you need to head to get to the goal and then agents simply look at the vector near their feet (so to speak). If you have multiple goals, you would need multiple flow fields (e.g. via a separate 2D array of field vectors for each goal). If you did that, you could then have an agent know which goal it is going to and look up its vector from that layer. The trick then is assigning a goal to an agent -- which of course, could be done by some sort of clustering algorithm.

You are quite right, my apologies somewhere along writing all that my actual question got jumbled up. I am looking for advice in storing the flow fields, I am concerned with a situation where in a large map a user might decide to make numerous small unit moves that all need flow field data to navigate around obstacles. 

As I am quite new i am not quite sure what would be acceptable or unacceptable amount of Memory and CPU usage for pathfinding alone. Was wondering if there are any patterns or best practices for storing and maintaining a large amount of Flow Fields.

13 hours ago, IADaveMark said:

fields

So I'm currently implementing flowfield pathfinding on my game as well, although I have a slightly different problem (which i'll post in another thread. In terms of storing the flowfields, the way im doing it simply storing it in a hash indexed by goal target's id, which you kind of hinted on as well. And each unit/group has a goal stored internally, and it can easily query what flowfield it needs to use by looking up the hash. That doesnt really address your memory concern though. Memory wise, a potential solution is to not floodfill the whole map. Instead, you start at the goal, and then once it reaches your set of units, then you can stop the floodfill. Also, a single flowfield on a 31x31 sized tilemap taking 11mb of space sounds really inefficient. I think you can simplify the datastructure so that it takes less than 1mb. You really only need the (xy direction vector, distance, row, col) each can be 4 bytes max and 20 bytes total for a single flow information. So 31x31 flows can be around 20kb.

In terms or larger maps, I've seen resources online about how supreme commander 2 does it, where it uses a hybrid approach, where it uses a high level path finding first on a world grouped into navmeshes or sectors (where each sector contain many tiles), and then combines it with a low level flow-field based path-finding. Check out http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd_Pathfinding_and_Steering_Using_Flow_Field_Tiles.pdf and http://www2.cs.uregina.ca/~anima/408/Notes/Crowds/HybridVectorFieldPathfinding.htm
 

On 2/26/2019 at 6:51 PM, kuroro_san said:

And each unit/group has a goal stored internally, and it can easily query what flowfield it needs to use by looking up the hash.

Much appreciated, I will go round implementing this, seems my concerns were misplaced as I shouldn't do maths when tired. My Flowfields are not nearly as bad memory wise.

I think that a larger question here is why, in such a small environment, are you set on using flow fields? Sure, there is an advantage when all the units are going to the same spot (like in a desktop tower defense game) but it seems artificially limiting in an RTS game where, while admittedly you may have many units, you also may have many different goals.

Is there a reason you aren't using A*? If your mode is to select groups of units and give them a destination, you can even simply calc one path for the group rather than for each unit. That, of course, cuts down on the A* calls.

Just curious as to how you arrived at using flow fields.

On 2/26/2019 at 1:51 PM, kuroro_san said:

[...]Also, a single flowfield on a 31x31 sized tilemap taking 11mb of space sounds really inefficient. I think you can simplify the datastructure so that it takes less than 1mb. You really only need the (xy direction vector, distance, row, col) each can be 4 bytes max and 20 bytes total for a single flow information. So 31x31 flows can be around 20kb. 

Why would you use more than 4KBytes for a 31x31 tilemap? The only thing you need to store for each tile is the distance to the target.

Yeah. Alvaro is right. Its possible to store only the distance and lazily compute the direction vector when needed. Row, col could be omitted, but i personally stored it for debugging purposes. 

4 hours ago, IADaveMark said:

I think that a larger question here is why, in such a small environment, are you set on using flow fields? Sure, there is an advantage when all the units are going to the same spot (like in a desktop tower defense game) but it seems artificially limiting in an RTS game where, while admittedly you may have many units, you also may have many different goals.

Is there a reason you aren't using A*? If your mode is to select groups of units and give them a destination, you can even simply calc one path for the group rather than for each unit. That, of course, cuts down on the A* calls.

Just curious as to how you arrived at using flow fields.

 

The decision was based on some light research on large scale RTS pathfinding. It was a matter of slightly aiming for the final result which was to see as many agents as the system can possibly support. The concept is trying to see what a 2D RTS from 2002 would look like on modern tech, that game could support a 1000 units as a cap. I ran on the assumption that a modern system could pull off a much larger volume of units so thought of using some already established pathfinding algorithms for the purpose.

All in all, I do not have enough experience in alternative path finding methods, or that much experience in steering behaviour. So i mostly went off of research. From what I found, Flow Fields (or similar algorithms) would alleviate some of the issues that I could potentially run into if I hit that level of scale with A*. Also the 31x31 size limit at the moment is for testing purposes only as I am working on implementing the systems, I predict this will become much larger and would have to expand based on how many agents I would end up managing to fit in.

That said, I haven't solved a similar problem to this before and would gladly take some advice on any pathfinding techniques, especially if implementing A* would be sufficient or even better.

Watch the beginning of this one by James Anhalt (Blizzard) re the SC2 pathfinding.

https://www.gdcvault.com/play/1014514/AI-Navigation-It-s-Not

And this one:

https://www.gdcvault.com/play/1018262/The-Next-Vector-Improvements-in