Techniques For Optimizing A* Path Finding 2D


#1

For reference I am use Unity as my game engine and the A* Pathfinding Project for path finding as there is no chance I would be able to create anything close to as performant as that in any reasonable amount of time.

So I am looking to build a game that is going to have a very similar style as Prison Architect / Rim World / SimAirport / etc. One of the things that I assume is going to effect performance is path finding. Decisions about the game I have already made that I think relate to this are:

  1. While I am going to be using Colliders, all of them will be trigger colliders so everything can pass through each other and I will not be use physics for anything else as it has no relevance for my game
  2. I am going to want to have a soft cap at the map size being 300x300 (90,000 tiles), I might allow bigger sizes but do something like Rim World does in warning the player about possible side effect (whether it be performance or gameplay)
  3. The map will be somewhat dynamic in that the user will be able to build / gather stuff from the map but outside of that, it should not change very much

Now I am going to build my game around the idea that users would be in control of no more than 50 pawns at any given time (which is something I can probably enforce through the game play) but I am also going to want to have number other pawns that are AI controlled on the map (NPCs, animals, etc.) that would also need path finding enabled. Now I did a basic test in which I have X number of pawns pick a random location in the 300 x 300 map. move towards it, and then change the location every 3-5 seconds. My initial test was pretty slow (not surprising as I was calculating the path every frame for each pawn) so I decided to cache the calculated path results and only update it ever 2 seconds which got me:

100 pawns: 250 - 450 FPS
150 pawns: 160 - 300 FPS
200 pawns: 90 - 150 FPS
250 pawns: 50 - 100 FPS

There is very little extra happening in the game outside of rendering the tilemap.

I would imagine the most pawns on the map at a given time that need path finding might be a 1000 (and I would probably be able to make due with like 500 - 600). Now obviously I would not need all the pawn to be calculation paths every 2 seconds nor would they need to be calculating paths that are so long but even at a 5 second path refresh rate and paths that are up to 10 tiles long, I am still only able to get to about 400 pawns before I start to see some big performance issues. The issue with reducing the refresh rate is that there are going to be cases where maybe a wall is built before the pawns path is refreshed having them walk through the wall but not sure if there is a clean way to update the path only when needed.

I am sure when I don’t run the game in the Unity editor I will see increase performance but I am just trying to figure out what things I could be doing to make sure path finding is as smaller of a performance hit as possible as there is a lot of other simulation stuff I am going to want to run on top of the path finding.


#2

Hi

First a few background questions:
What movement script are you using? Something you wrote yourself of one that is included in the package?
What version are you using?
Any rigidbodies/other interesting components on the AIs?


#3
  1. I am using a custom movement script as from my readings, the provided ones are not well suited for large number of agents and I also had issue related to physics I think where my sprites would rotate when they hit map colliders (I can provide a link to the code in about 10 - 12 hours)
  2. I am using the latest stable version from the asset store, also the pro version
  3. All the game objects that have path finding only have very basic scripts and colliders, nothing else. All colliders on agents will also be trigger colliders as agents should be able to go through each other

Let me know if any other information would be helpful


#4

Hi

  1. Nice. That’s a good idea.
  2. Okay. For faster graph updates you can download the latest beta. Shouldn’t be too important for prototyping though.
  3. Also good.

So a few things:

  • Make sure you are using multithreading (see A* inspector -> settings).
  • Avoid using any heavy modifiers (funnel, raycast, and simple smooth with a high number of iterations)
  • Make sure to profile the game. This is where you will get all the nice info.
  • Make sure you use path pooling in your custom script (mostly for reduced GC pressure though, not so much for performance), see https://arongranberg.com/astar/docs/pooling.html
  • Make sure you disable ‘Show Graphs’ in the unity editor while testing, drawing the graphs can be quite costly for larger graphs, especially when you update the graph.

You could make your movement script aware of which nodes it is going through (most likely you will want to just make it follow the list of nodes instead of a list of points then) and then every second or so check the next say 10 nodes ahead on the path and see if any of those nodes are blocked, and if so recalculate the path. Otherwise recalculate the path only every 5-10 seconds. That could drastically cut down on the number of path recalculations required, while still allowing for fast reaction times if the path of an agent is blocked (while not so fast reaction times if you open up a previously closed passage, however this is much less important usually).

Generally, the best advice is profile, profile, profile.


#5

Thanks for the advice, I thought of the idea of only checking the upcoming nodes instead of recalculating on my way home from work so it is good to know I am on the right path. I do have a question about the best way to implement that suggestion.

I have a basic implementation working but I feel there might be a better way that I am just not seeing in the documentation.

First I cache a copy of the grid graph here: https://github.com/ryanzec/gists/blob/master/Unity/Test/BasicAstarMovement.cs#L26

Then every so often I call a method to check the next X nodes ahead however since the cached nodes seem to always be walkable (which makes sense since there were walking when the path was first generated) I use the copy of the grid graph and pull the node from there using the position and check to see if that node is still walkable: https://github.com/ryanzec/gists/blob/master/Unity/Test/BasicAstarMovement.cs#L117

Is this the best way to do this or is there a better API I am missing for doing something like this?


#6

Hi

So some comments.
When you say you cache a copy of the grid graph, that’s not actually what happens. You just keep a reference to the grid graph. If the grid graph is updated, then all node and grid references you have will also be updated.
Secondly, you are calling BlockUntilCalculated. This will force the path to be calculated synchronously immediately when you call that function, this will cause all your paths to be calculated in the main thread, and they won’t even be time sliced over multiple frames if they they take a long time to calculate. Most likely this would kill your performance if you have that many agents. You should avoid that method and use asynchronous path requests instead (see https://arongranberg.com/astar/docs/callingpathfinding.html).

In your HasBlockingNodeAhead method, you can just use the reference you already have. So something like this would work:

public bool HasBlockingNodeAhead() {
    for (int i = 0; i < NodesToCheckAheadForBlocking && i < CachedNodes.Count; i++) {
      if (!CachedNodes[i].Walkable) return false;
    }
}

Also note that things like GetRange and foreach allocate memory behind the scenes (though foreach might not do so with the new .net 4.x backend), so in performance sensitive code it is usually best to avoid them.


#7

Thanks for the info, not sure why I was doing the block node check the way I was.

One issue however is that when I turned that off and set the threads in the settings to 1, with 100 agents changing direction every ten seconds, I starterd to get “no new paths are accepted” error and eventually all my agents stopped moving. I tried to look here : https://arongranberg.com/astar/docs/errormessages.html : for the message but did not see it.

Any idea on why this would be happening? Is my stress test case just an unrealistic use case to support?

My updated movement script can be found here: https://github.com/ryanzec/gists/blob/master/Unity/Test/BasicAstarMovement.cs


#8

Hi

The No New Paths Are Accepted error is only logged if the A* object has been destroyed or the pathfinding has failed with some internal error (if that is the case you should see that further up the log). Are you sure you are not seeing any of this?


#9

The astar game object looks fine in the scene, there are some error in the log that related to the astar code that don’t make a whole lot of sense to me:

I had logging at heavy for this, does this make any sense to you? Let me know if you need anymore information.

Also incase this matters, I am running the latest beta version of Unity (since I just started to prototype this game in the past week, I want to be able to use the new prefabs workflow with it).


#10

Hi

That ArgumentOutOfRange exception looks very important. Would you mind posting the full stack trace for it?


#11
ArgumentOutOfRangeException: Index was out of range. Must be non-negative and less than the size of the collection.
Parameter name: index
System.ThrowHelper.ThrowArgumentOutOfRangeException (System.ExceptionArgument argument, System.ExceptionResource resource) (at <ac823e2bb42b41bda67924a45a0173c3>:0)
System.ThrowHelper.ThrowArgumentOutOfRangeException () (at <ac823e2bb42b41bda67924a45a0173c3>:0)
System.Collections.Generic.List`1[T].get_Item (System.Int32 index) (at <ac823e2bb42b41bda67924a45a0173c3>:0)
Pathfinding.Path.Trace (Pathfinding.PathNode from) (at Assets/AstarPathfindingProject/Core/Path.cs:666)
Pathfinding.ABPath.CalculateStep (System.Int64 targetTick) (at Assets/AstarPathfindingProject/Pathfinders/ABPath.cs:596)
Pathfinding.Path.Pathfinding.IPathInternals.CalculateStep (System.Int64 targetTick) (at Assets/AstarPathfindingProject/Core/Path.cs:787)
Pathfinding.PathProcessor.CalculatePathsThreaded (Pathfinding.PathHandler pathHandler) (at Assets/AstarPathfindingProject/Core/Misc/PathProcessor.cs:329)
UnityEngine.Debug:LogException(Exception)
Pathfinding.PathProcessor:CalculatePathsThreaded(PathHandler) (at Assets/AstarPathfindingProject/Core/Misc/PathProcessor.cs:383)
Pathfinding.<>c__DisplayClass23_0:<.ctor>b__0() (at Assets/AstarPathfindingProject/Core/Misc/PathProcessor.cs:95)
System.Threading.ThreadHelper:ThreadStart()

#12

Hm… That actually looks like a bug.
You have encountered a race condition which can happen very rarely when you use the Path.CompleteState property to check if the path has been calculated and then modify the node list. Veeery few people do this which is probably why this has gone undetected for several years. Until it is fixed you can as a workaround try to use the more common ways to be notified of when a path has been calculated (e.g using a callback or using a coroutine), see: https://arongranberg.com/astar/docs/callingpathfinding.html


#13

Yup, that fixed the issue, was able to get 2200 agents running without the error happening for several minutes. The callback / coroutine is ultimately a cleaner solution I think but I am glad I was able to uncover a possible bug for you.

Thanks for your help.