Hello,
I’m struggling with implementing a flow field using ECS/DOTS.
A flow field itself is a 2D grid, where each cell contains a float2 vector, pointing to some goal point with considering to impassible grid cells. Generating a flow field is not a problem for me. The problem is choosing the correct data structures to store multiple flow fields.
As the flow field is a 2D grid, so it can be easily stored in NativeArray. But it’s for just one destination point. In a real game scenario, different units will have different destinations and I need to store all this NativeArray’s somewhere.
Naive approach would be something like that:
// Calculate new velocity for each unit that have a destination
Entities
.WithAll<Unit>()
.ForEach(
(ref Velocity velocity, in Translation translation, in WithDestination destination) =>
{
if (FlowFieldHashMap.TryGetValue(destination.Value, out NativeArray<float2> flowField))
{
velocity.Value = flowField[/*Conver translation.Value into grid int2 position*/];
}
else
{
// Request creating a new flow field for the unit's destination
}
})
.ScheduleParallel();
Where FlowFieldHashMap would be:
NativeHashMap<int2, NativeArray<float2>> FlowFieldHashMap = new NativeHashMap<int2, NativeArray<float2>>();
However as far as I know you can not create a native container of type of another native container.
How would I store multiple flow fields (NativeArrays) then?
Actually do you need a float2 as you could have 256 directions** with a byte?
This could massively reduce the memory footprint (in cache 1 byte vs 8 bytes for float2) and therefore speed of the system.
Could you not store the unused arrays in a list and only load the ones you need into a NativeArray, in theory you would not have to move the data as you are just specifying a block of memory*.
Not sure if C#/Unity has the capability to redefine blocks of memory as NativeArray/None Native?
** OK it would depend on the size of the cells in the grid as with large enough cells a > 1° direction vector could mean the Units do not follow the ideal path. On the flip side 4 bit / 8 direction vector could be enough for very small cells.
You are right, I don’t need a float2, in my gameObject version there are only 8 possible directions, so byte should be fine.
Regarding NativeArrays and stuff I’ll try to explain in more details what I want to do:
I want some kind of LRU cache to store last N flow fields
Then I want to use Entities.ForEach or custom Job to find all Unit entities that have a destination, check if there’s a flow field in the cache for this destination and get actual move direction from this flow field if it exists
If there’s no flow field for this destination, calculate it (or create a request to the system that does calculations) and store it in a cache
In our case, we just wrote our own native container which can store all flow fields, which can be accessed by some unique key (and flow field itself is another unsafe collection which used under the hood of top-level flow fields storage)
The easiest way to manage memory for it would be to store the flow field data as an IBufferElementData attached to the units. That way, once a unit is destroyed, the flow field goes with it and you don’t need to explicitly remove it from the hash map.
With 8 directions you only need 4 bits so that could half your data size again.
The thing is with flow fields then you would only need n! (factorial) where n is the number of corner/dead end regions on your map. As there would be a lot of overlap for linked regions.
No offence, but, to be honest, not a good solution for scale (even for not a big), as usually flow (potential) fields used for crowd pathfinding\navigation, which means a significant amount of agents (otherwise for small amount of agents using flow field is overhead and there is much more better approaches like regular grid\mesh A*, JPS, Greedy Best-First etc.), and if every agent will store flow field on its own it will be extremely memory wasteful and unnecessary data duplication, as in regular case flow field agents will share the same flow field, and with regions optimisation (simplified papers http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd_Pathfinding_and_Steering_Using_Flow_Field_Tiles.pdf, based on http://grail.cs.washington.edu/projects/crowd-flows/), they heavily will reuse big parts of traced path regions with fields and allow us very easily exclude further fields generation for big parts of map if they not changed (and if they change (like we built wall) in case of regions optimisation we will rebuild only small pieces). Moreover, this approach bad fills caching and reusability strategy of flow fields, as if they stored on every entity you can’t “reuse” it for others (well we can iterate every entity\or by spatial partitioning etc. and check if an entity has required for us flow field, but I think you see all stupidity of that idea ), the solution from links and part of implementation I described a bit in the previous post (and how we using that in our RTS (you can see in my sign or in a pinned thread in DOTS, which also in sign, and through the thread I described in details how we implemented that) where crowd pathfinding is one of the pillars) scales very well on big crowds (in our case pathfinding for 50k crowd extremely lightweight, and more you play - lighter it becomes (up to some point where we decide not waste memory and limit amount of cache) as we just reuse already generated fields for the most part of the path and only use merged Hierarchical A* on top regions level.
eizenhorn, thanks for sharing your thoughts! I’m also planning to use HPA* to be able to reuse already calculated flow fields for specific chunks and reduce the number of calculations overall. I’ll definitely take a look at the threads you mentioned!
), the solution from links and part of implementation I described a bit in the previous post (and how we using that in our RTS (you can see in my sign or in a pinned thread in DOTS, which also in sign, and through the thread I described in details how we implemented that) where crowd pathfinding is one of the pillars) scales very well on big crowds (in our case pathfinding for 50k crowd extremely lightweight, and more you play - lighter it becomes (up to some point where we decide not waste memory and limit amount of cache) as we just reuse already generated fields for the most part of the path and only use merged Hierarchical A* on top regions level.