Searching large numbers of graphs

Hi,

I have a need to use an arbitrary number of graphs. The actual number is determined by the limitations of the hardware. A hard cap is fine as long as the system is maxed out before then.

I’m getting conflicting information from posts and documentation about the built-in limit. I see 3 and 16 referenced, and the MaxGraphIndex says 255, but an int mask is used for searching which would limit it to 32.


Questions

  1. How easy would it be (for me) to push this limit to say, 2000?
  2. What are the reasons for the limitation besides the bit mask? (A: I see, you try to store everything in the flags property.)
  3. Are there any performance costs for having a lot of (masked) graphs?
  4. What’s the approximate RAM usage of a 300x300 grid running on a separate thread?

I went ahead and replaced graphMask with an int[]. Thankfully pretty simple.

I’m currently poking around GraphIndex, and man, did you pack these bits.

I’m thinking the thing to do is just replace the GraphIndex definition with the default get; set; and set MaxGraphIndex to int.MaxValue.

Does that sound like all that needs to happen?

Hi

Sorry for the late answer.
Replacing the graphMask with an int[] and replacing the GraphIndex definition should be the only things that need doing I think.

4: Approximate RAM usage for one node is approximately
32 bytes + 32 bytes per thread in raw storage for a 64-bit machine. However if we take into account metadata (I think it is 8 bytes per class in C# on 64-bit, might be 12 or 16) and some references it is probably more like 48 bytes + 48 bytes per thread.

This is with ASTAR_GRID_NO_CUSTOM_CONNECTIONS enabled (see Optimizations tab), otherwise there is an additional 16 bytes per node (not per thread though). You can further reduce the constant memory usage per node by 4 bytes by enabling ASTAR_NO_PENALTY.

So for 300*300 nodes * (48 bytes + 48 bytes per thread) = 90000 * 48 + 90000 * 48 ≈ 4.1 MiB + 4.1 MiB per thread on a 64 bit machine.

3: When searching for the closest node to a position, it will walk through all graphs and try to find the closest one. If you have AstarPath.fullGetNearestSearch enabled (the default) this operation can be quite expensive, but you can disable it to make it faster. Also graph updates that require a flood fill of the graphs will likely be very slow.

Q: Why do you need so many graphs? Usually I recommend using only a single graph since there are so many edge cases involved when trying to link multiple graphs together.

Thanks for the reply.

First, let me say, your code is amazingly well written. I’ve had a ton of (usually foreign) code bases dumped on me at my previous job, and I wish they were all written half as well as this.

Anyway, I’m integrating your pathfinder into my server backend. Running an instance of Unity per room is way too memory intensive, so I’ll be instantiating up to (ideally) 100 rooms per Unity instance. Each room has its own unique level, and is bound to a 2000x2000 section of space on the server.

I’m planning on having 2 graphs per room, since the rooms shouldn’t interact, and need to be created and destroyed whenever. One of the graphs will be identical across rooms (an outpost in the middle). I was thinking it would be a manually created point graph. The other is the changing grid graph for the rest of the world. So maybe 200 graphs at most.


Wouldn’t the search early out because of the graph mask?

I’m not sure what a flood fill is, I haven’t gotten to the update portion yet. I was thinking of using UpdateGraphs(Bounds) for any changes, and the graphs won’t overlap. I would assume that a quick bounds check would ignore irrelevant graphs. That might be too expensive still, so I might extend it to take a graph index. I’ll have to look at how complicated it is.

I had to change my grid size to 525, so by my estimates, I’ll use about 3 gigs of graphs per instance. I might need to look at reducing that when it comes time to stress test.

Hi

I see.
Ah, forgot about the graph mask. Yes when searching for the nearest node those other graphs will be skipped.

First, let me say, your code is amazingly well written.

Thank you! That is very nice to hear :smile:

When a search is requested between two nodes that have no possible path between them, normal A* would just search and search until it had searched everything it could reach. This is pretty slow, so to prevent that the script calculates different areas (these are the different colours of the nodes that you can see in the scene view) using a flood fill. When a graph is updated these areas need to be recalculated. I am sketching on a way to do this by repairing the area information instead of recalculating it completely (which would be a lot faster for most cases), however that is not implemented yet. So to avoid doing this recalculation for all graphs (which would be extremely expensive) you can either: a. Disable areas completely, which can be useful if you know that your graphs will not be divided into multiple areas (or at least only very seldom). Essentially put a return at the top of the Floodfill methods in the AstarPath class or b. You can make sure that when graphs are updated, they only flood fill the graphs that need updating (would involve some tweaking in the AstarPath.ProcessGraphUpdates method).

I would assume that a quick bounds check would ignore irrelevant graphs. That might be too expensive still, so I might extend it to take a graph index. I’ll have to look at how complicated it is.

You can use the UpdateGraphs(GraphUpdateObject) instead of the UpdateGraphs(bounds) method. That contains an NNConstraint field which has a graphMask variable (which you might have swapped out for an int).

Keep in mind that with 200 graphs, you will use quite a lot of RAM, so GC pauses will be horrible. This is not too bad since it is on a server, but it is still good to keep in mind.

PS: When you have used the system for a while. A rating and/or a review in the Unity Asset Store really helps the project.