A* Pathfinding Project

How to disable flood fill for a grid graph version 4.2.2 Pro


#1

Hello, we are making a mobile game with a huge world. We are using multiple grid graphs as a solution (There are multiple reasons we are selected grid graph). Huge problem I am facing now is unacceptably slow deserialization of a grid graph. One of the biggest reasons is the flood fill. In the docs there is a case for it in the procedural world example, it says disable floodFill field, but there is no floodFill field in the ProceduralGridMover example, to see how floodFill is disabled in the script. As far as I understood documentation is out of date. How can I disable FloodFill in 4.2.2 pro.


#2

Hi

Ah, yeah that looks out of date. The flood fill field was removed from the ProceduralGridMover script because it is handled automatically behind the scenes in a more efficient way now anyway.

I’m not quite sure what you are asking. You seem to be using both the ProceduralGridMover script and deserializing grid graphs on the fly? Usually you do one or the other, but not both?

Also, could you post a screenshot of the unity profiler when this happens?


#3

No, I am not using ProceduralGridMover, I mentioned it because it was only part in the documentation related to my problem. Neither I am using Included deserialization (it is very slow for realtime on mobile) I am writing my own serialization / deserialization using AddWorkingItem to rebuild grid after serialized data is loaded, main idea is to distribute calculations over multiple frames.

Here is the profiler screenshot (from Editor, it is much worse on mobile)

Every spike is located after working item is complete
Screenshot_3


#4

Hi

Hmm… Well, if that overhead is unacceptable I suppose you could disable flood filling.

This can be done by adding a return as the first line of the HierarchicalGraph.cs -> RecalculateIfNecessary method. Note however that if you ever try to search for a path to a point which is not reachable (but still walkable) it will have no choice but to search the entire graph before it stops. This can be quite slow. Methods such as PathUtilities.IsPathPossible will also no longer work.


#5

Thank you!
This spikes are 400 - 800 ms on our low end target devices. And it happens very often, every time player moves to other chunk.
If it is possible to serialize HierarchicalGraph data for each grid separately I could just save this data with grid data, I guess loading calculated data for HierarchicalGraph would be much faster than recalculating it.


#6

400-800 ms!? Wow. That’s more than 100 times slower than on your PC! Are you sure it’s the same cause? Can you run the profiler on the target device?


#7

Yes, this is a main cause.Spikes disapeared when I deleted EnsureValidFloodFill line.
400-800 is a worst case, for example if device is heated.


#8

I’m not sure what could cause it to be that slow… But in any case you could try the above suggestion to disable the flood fill completely.