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

Here is a working video !!!

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.