Sign in to follow this  
Crayz92

Out of ideas for optimizing A* search, got any?

Recommended Posts

Here are the two main files:

Path: https://pastebin.com/ZkrbJ78t

AStar: https://pastebin.com/EVGazFtU

 

A few things I've done to optimize the search:

1. Rather than a dictionary to keep track of scores and parents, I use a 2d array of objects that are mapped to the grid i.e. [x,y] represents grid point (x,y).  Objects have F,G,H and Parent fields, these fields are reset to default values during each search.

2. Cheap weighted heuristic

3. Orthogonal neighbors (searching 4 neighbors rather than 8)

Paths don't have to be beautiful because the point reduction smooths them out quite nice. 

In Path.cs you can see the two functions to reduce points, Incremental and Stretch.  Stretch is much faster because it has the potential to reduce points all the way to the end right off the bat or early on thus reducing calls to the LineOfSight function, but it isn't so reliable around small areas/corners.  The incremental function is reliable but it calls to the LineOfSight function for each and every point along the path, this causes the path reduction to be just about as slow as calculating the path itself. 

Line of Sight is determined by getting all points between 2 points and checking that they are all flagged as Walkable.

 

My grid is dynamic and roughly 250x250.  I tried out Theta* and JPS, both were slower than my current A*.  I'm trying to avoid using a navmesh or worker thread, I suppose mostly just looking for ideas to tighten up my code :)

Edited by Crayz92

Share this post


Link to post
Share on other sites
50 minutes ago, ApochPiQ said:

Have you run a profiler against your code?

I have.  The two biggest bottlenecks are in point reduction and the priority queue (using BlueRaja's which claims to be the fastest)

Here's a screenshot from the Unity profiler: f43ea1392f.png

Profiling alone adds a lot of overhead but I think it gives a good idea of where things sit.  I've never used a profile other than Unity's

Share this post


Link to post
Share on other sites

Actually, the profiler is showing you something slightly different.

Keep in mind that what you care about in this context is not the sum total cost of every call to a function - just the average cost of a single call. If you divide the time spent in a function by its call count, you'll see that the priority queue is dirt cheap per-call, you just call it a whole lot.

This is important data on two fronts. First, you should focus your effort on your algorithm primarily. Look for ways to avoid calling code that has no effect on the final results of the path search. Second, if you look at the actual places your code is burning a lot of time, you'll get much more visible performance wins.

 

Unity has a "deep" profiler option that you should also look into.

Share this post


Link to post
Share on other sites

I took a look at some of the code:

- Heuristic.  Is distance-squared admissible for A*?  I've never seen it used for A* before and that is a warning sign to me.

- FastPriorityQueue is being called an extremely high number of times, but each operation should be EXTREMELY short, so the profiler overhead is likely to be polluting the numbers to the point where you should no longer trust them.  You'll have to move your A* code into a standalone .Net project in order to use a sampling profiler with it, as far as I know.

- I looked at the github repo for FastPriorityQueue, and there are some obvious microoptimizations that can be made to it if you determine that it really is worth it.  Change the Node to a struct, change those properties to plain old fields, perhaps change the binary heap to a cache-friendly heap (after the first few layers of a binary heap you will cache miss on every single layer).

- JPS+ should be tremendously faster than A*, so if it wasn't then there's something significantly wrong with the implementation that you tried.

Edited by Nypyren

Share this post


Link to post
Share on other sites

I might be wrong here, but it looks like you might be enqueueing more nodes than you really ought to need to, unless you're hitting a really pathological layout.  250x250 is 62500 total nodes, and your profiler result is showing 59600 calls to Enqueue(), which appears to indicate that it is considering a pretty hefty fraction of the total nodes available.  Assuming no obstacles and an appropriate heuristic, A* ought to pretty much go in a straight line from the start to the goal, and only have to put the neighboring nodes of the ideal path on the open (priority queue) set.

You might want to try tweaking your code so that you can step through the algorithm one iteration at a time, and visualize how nodes are getting added to your open and closed sets at each step, so you can see if it is clearly doing something weird.  Five seconds is really far too long for this to take.

Where your connections all appear to be orthogonal, you might want to look at something like Manhattan Distance as a heuristic, which tends to work very well with A* in such situations.  That would tend to look something like this, lifted from my pathfinding code:

public static float ManhattanDistance(Point start, Point goal) {
  var dx = Math.Abs(start.X - goal.X);
  var dy = Math.Abs(start.Y - goal.Y);
  var h = dx + dy;

  return h;
}

 

Share this post


Link to post
Share on other sites
1 hour ago, Nypyren said:

I took a look at some of the code:

- Heuristic.  Is distance-squared admissible for A*?  I've never seen it used for A* before and that is a warning sign to me.

- FastPriorityQueue is being called an extremely high number of times, so the profiler overhead is likely to be polluting the numbers to the point where you should no longer trust them.  You'll have to move your A* code into a standalone .Net project in order to use a sampling profiler with it, as far as I know.

- I looked at the github repo for FastPriorityQueue, and there are some obvious microoptimizations that can be made to it if you determine that it really is worth it.  Change the Node to a struct, change those properties to plain old fields, perhaps change the binary heap to a cache-friendly heap (after the first few layers of a binary heap you will cache miss on every single layer).

- JPS+ should be tremendously faster than A*, so if it wasn't then there's something significantly wrong with the implementation that you tried.

I've played around with a variety of heuristics, this is the fastest I've come across and it produces acceptable results.  I'll give JPS another try, it's very possibly my implementation is messed up.

 

1 hour ago, ericrrichards22 said:

I might be wrong here, but it looks like you might be enqueueing more nodes than you really ought to need to, unless you're hitting a really pathological layout.  250x250 is 62500 total nodes, and your profiler result is showing 59600 calls to Enqueue(), which appears to indicate that it is considering a pretty hefty fraction of the total nodes available.  Assuming no obstacles and an appropriate heuristic, A* ought to pretty much go in a straight line from the start to the goal, and only have to put the neighboring nodes of the ideal path on the open (priority queue) set.

You might want to try tweaking your code so that you can step through the algorithm one iteration at a time, and visualize how nodes are getting added to your open and closed sets at each step, so you can see if it is clearly doing something weird.  Five seconds is really far too long for this to take.

Where your connections all appear to be orthogonal, you might want to look at something like Manhattan Distance as a heuristic, which tends to work very well with A* in such situations.  That would tend to look something like this, lifted from my pathfinding code:


public static float ManhattanDistance(Point start, Point goal) {
  var dx = Math.Abs(start.X - goal.X);
  var dy = Math.Abs(start.Y - goal.Y);
  var h = dx + dy;

  return h;
}

 

Ah I didn't mention that profiler screenshot is the result of 100 paths in a single frame.  Here's a better shot for a single path: 09008e6e1f.png

 

I fixed up some code and gave Manhattan distance a test run.  Here's a  comparison between my current heuristic & Manhattan

aba18466d2.jpg

6c1bbae0a0.jpg

 

Manhattan without weight puts it at about 2,200ms.  While Manhattan makes for a better looking path, post-processing takes care of that so I'm mostly interested in speed :)

Edited by Crayz92

Share this post


Link to post
Share on other sites

Use an instance of the Stopwatch class to time SetDestination with and without deep profiling enabled, and see how much it differs.  I still think the instrumenting profiler is causing too much overhead on the FastPriorityQueue and it would be good to find out how much there is.  It's the biggest offender if the profiler is telling the truth.

Share this post


Link to post
Share on other sites
3 minutes ago, Nypyren said:

Use an instance of the Stopwatch class to time SetDestination with and without deep profiling enabled, and see how much it differs.  I still think the instrumenting profiler is causing too much overhead on the FastPriorityQueue and it would be good to find out how much there is.  It's the biggest offender if the profiler is telling the truth.

I have my debug script set up just like that :)

179f97c661.png

 

The results in the two screenshots above are from this Stopwatch snippet with deep profile & profiler disabled completely

Share this post


Link to post
Share on other sites

Ok, so with profiling one call takes 31ms, and without you have 1-2ms.  Definitely too much overhead from Unity's instrumenting profiler.

If you can, take all of your pathfinding code and make a standalone .Net app out of it, and use a sampling profiler on it.  I think newer versions of Visual Studio should have a profiler built into them.  I can't tell if you're on Windows or not from the screenshots, though.  If not, there should also be some freely available profilers available that will run on other OSes.

Share this post


Link to post
Share on other sites

Just a handful of random suggestions:

  • Get your algorithm correct first. Micro-optimization is a waste of time if your code is solving the problem wrong.
  • In case you aren't already aware, benchmark in Release builds, not Debug builds. This can make a tremendous difference.
  • Your heuristic is not great. See this page for details.
  • Start with a tiny test case, like 10x10, and walk through the algorithm start to finish in a debugger. Pay attention to the behavior of the code. You will almost certainly find inefficiencies this way.

 

Share this post


Link to post
Share on other sites
On 9/9/2017 at 11:27 AM, ApochPiQ said:

Just a handful of random suggestions:

  • Get your algorithm correct first. Micro-optimization is a waste of time if your code is solving the problem wrong.
  • In case you aren't already aware, benchmark in Release builds, not Debug builds. This can make a tremendous difference.
  • Your heuristic is not great. See this page for details.
  • Start with a tiny test case, like 10x10, and walk through the algorithm start to finish in a debugger. Pay attention to the behavior of the code. You will almost certainly find inefficiencies this way.

 

I went over my code and found some issues - kind of funny how the heuristic I was using showed better performance with a bug in the A* algorithm.  It's overall better performance now using the diagonal distance heuristic.

 

On 9/9/2017 at 11:02 AM, Nypyren said:

Ok, so with profiling one call takes 31ms, and without you have 1-2ms.  Definitely too much overhead from Unity's instrumenting profiler.

If you can, take all of your pathfinding code and make a standalone .Net app out of it, and use a sampling profiler on it.  I think newer versions of Visual Studio should have a profiler built into them.  I can't tell if you're on Windows or not from the screenshots, though.  If not, there should also be some freely available profilers available that will run on other OSes.

Yea, definitely a lot of overhead from the profiler.  I use it just to get an idea of where things are at.  I am on Visual Studio, I wonder if its possible for it to hook into the Unity editor and profile that way?  I fixed up my JPS algorithm as well, it shows about 15-20% increased performance but in some cases performed much worse, so I'll have to do some more digging.

Share this post


Link to post
Share on other sites
1 hour ago, Crayz92 said:

Yea, definitely a lot of overhead from the profiler.  I use it just to get an idea of where things are at.  I am on Visual Studio, I wonder if its possible for it to hook into the Unity editor and profile that way?  I fixed up my JPS algorithm as well, it shows about 15-20% increased performance but in some cases performed much worse, so I'll have to do some more digging.

Unity's using a different .Net runtime (Mono) and I haven't been able to figure out how to get Visual Studio to profile that.

Share this post


Link to post
Share on other sites
On 9/9/2017 at 6:27 PM, ApochPiQ said:

Just a handful of random suggestions:

  • Get your algorithm correct first. Micro-optimization is a waste of time if your code is solving the problem wrong.
  • ...

Regarding correctness, if two heuristics give different results and not only different counts of expanded nodes it is crushing evidence there are bugs in the heuristics and/or in the A* search.
Judging from the screenshots the so-called "current" heuristic is inadmissible or worse and the Manhattan distance heuristic is OK.

Share this post


Link to post
Share on other sites

Manhattan distance is not an admissible heuristic if the character can move diagonally. It's not just sub-optimal, it's wrong. Same goes for distance-squared. Overestimating heuristics will give incorrect results. The direct straight-line distance is the best baseline heuristic for almost all applications, if you don't know for sure that you have a better one.

Share this post


Link to post
Share on other sites

Note that inadmissible heuristics are totally fine, as long as you want "a" path rather than "the best" path.

Sometimes, inadmissible heuristics will be just the ticket to make pathfinding run well.

In this particular case, I'd first look at why PathQuery.LineOfSight() takes so much time. A simple greedy path simplification algorithm should basically run in linear time. Then, I'd look at whether there are calls to functions that don't need to be made. Then, I'd look at functions that are virtual, and see if they could be made non-virtual. Or maybe even inline.

If all of that still doesn't work, then also look at whether you can re-use previous path finding from other entities, whether you can remember cached segments and re-use them, and whether you can implement a hierarchical finder. Split the 256 grid in 16x16 cells, and classify connectivity between edges as a pre-processing step. Run pathfinding through this coarse grid. Once that works, you can run a single refine step on the found path, and end up with a fine result.

Or you can build passable segments by "inflating" interior geometry (boxes, or spheres) until they hit non-passable areas, and know which pieces connect to which other pieces, and just path-find between pieces rather than cells. Again, a final pass of smoothing will fix up the path.

Share this post


Link to post
Share on other sites
On 9/8/2017 at 5:21 PM, Crayz92 said:

Here's a screenshot from the Unity profiler

Since you seem to be using Unity, is there a reason you aren't using Unity's own navmesh functionality instead of re-inventing the thing?  It's auto-generated navmeshes are pretty good, and you can create your own to fine-tune anything you need.  

Share this post


Link to post
Share on other sites
4 hours ago, frob said:

Since you seem to be using Unity, is there a reason you aren't using Unity's own navmesh functionality instead of re-inventing the thing?  It's auto-generated navmeshes are pretty good, and you can create your own to fine-tune anything you need.  

I decided early on to avoid Unity as much as possible and keep all my game's logic within its own boundaries.  Reason for it is so that my server can run headless and/or standalone with no dependencies to Unity.  And reinventing the wheel isn't such a bad thing, if I had decided to stick to Unity's physics and pathfinding I would only have a little bit more knowledge about Unity and a lot less knowledge about pathfinding and physics.

Share this post


Link to post
Share on other sites

Try having your "result" debug tool (the one showing the path line) also show each grid node that became opened during the search, and colour each node by a function of its (best found) G cost, so you can visually track the open set and the best path found to each cell in the open set. Like others are saying, after reviewing your code, I think you're massively over-opening the search space.

Share this post


Link to post
Share on other sites

If you want 8 direction movement, your heuristic should support that. Creating an "8 direction manhattan style estimate" between two points should be no big deal. (dist = min(xDiff, yDiff) * sqrt(2) + abs(xDiff - yDiff))

 

Now to make A* really lightning fast there is an counter intuitive tip: Make the heuristic under/overestimate the distance to the target so it doesn't backtrack as much to go around an obstacle. This is exactly what everyone says the A* heuristic must never do, because now it will no longer be guaranteed to calculate a correct shortest path at all. But usually in games you don't care about the path being 100% the shortest one.

The upside are crazy performance gains up to a factor 10! In extreme cases like labyrinth style maps the results can be very wrong though.

You'll have to experiment a little as I did that a long time ago and don't remember what the best factor was exactly. You'll know when you've hit the sweet spot. CPU time will drop like a stone and the paths should still look mostly optimal.

Hope this helps :-)

Edit: Postprocessing/smoothing a found path can reduce the introduced error, especially in the more obvious suboptimal cases like running into a dead end.

Edited by ntroPi

Share this post


Link to post
Share on other sites
On 9/19/2017 at 4:26 PM, ntroPi said:

Creating an "8 direction manhattan style estimate" between two points should be no big deal. (dist = min(xDiff, yDiff) * sqrt(2) + abs(xDiff - yDiff))

This can't be right, xDiff=0, yDiff=-200 gives a path -200 * sqrt(2) + 200 is about -200 * 0.4

Share this post


Link to post
Share on other sites

I should have written explicitly, that the diffs are supposed to be absolute values. Wanted to keep it short, as it is only a minor point of my post.

Manhattan_8(Point P1, Point P2)
{
	xDiff = abs(P1.x - P2.x);
	yDiff = abs(P1.y - P2.y);
	return min(xDiff, yDiff) * sqrt(2) + abs(xDiff - yDiff);
}

So it would come out to xDiff = 0, yDiff = 200 in your example, which gives the expected result (200).

Thx for the feedback :-)

Edited by ntroPi
Added code for convenience.

Share this post


Link to post
Share on other sites

What does your GridNode look like?  You might try to shrink it down as much as possible.  You might even get a benefit from pulling out the visited index to its own array.

GetNeighbors, is that doing a copy?  That could potentially be doing some goofiness.

You also have a minor potential bug, as you never check for overflow in your searchindex.  (Shouldn't happen that often, but it's not a tough fix.)

 

I'm also curious if rewriting the whole thing in C++ and importing that into Unity would be faster still.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Announcements

  • Forum Statistics

    • Total Topics
      628383
    • Total Posts
      2982384
  • Similar Content

    • By lucky6969b
      I am not sure I can ask questions about a specific library here, but if you haven't already. I'd like to tag some polys in a navigation mesh that correspond to grass or road etc, I can give an extent to do so, or in another way, I can directly feed a geometry in and the polys are tagged this way. But I am looking into alternative ways such as allowing the user to tag the polys using a text file or bitmap file (like the way heightfields are done).. If I define a area map which is a grayscale  image, and the values range from 0-255, and for example, if the value of the first char is 0, then I can map this index to certain place in the navigation mesh, and say this is a walkable ground etc, unlike heightfields, where you define an image and the resultant thing is some terrain, but when you start off with a bitmap for area map, you end up with what? you see, I had the geometry already, the area map probably doesn't make sense here, same way as the text file thing....
      Any ideas?
      Jack
    • By Luqman Ibrahim
      Hello guys, I just registered this site and heard from my lecturer that this a good site to talk about certain topics since my research topic are mostly programmer who are experienced with AI can answer the survey.
       
      The reason of the survey below is to understand which is suitable solution for 2d platformer pathfinding for AI and which one is easier to implement for 2D platformer. 
       
      I would appreciate if you guys give your responses for the survey link shared and thank you for spending time answering the survey. Sorry if the survey is a bit hard to understand, I tried to make it understandable as best as I can. Again, thank you!
       
      https://goo.gl/forms/S0etAlAAHL6S5kTI2
    • By baabaa
      Hello hello. I'm in the preliminary design phase for a space based game, and I need some advice on how to approach the AI side of things.
      Here's the situation in a nutshell. Say I'm a space explorer with a spaceship, and I am competing with other space explorers to be the first one to discover things. I have a procedurally generated 2D top-down solar system, and to make things a little simpler, let's say all the planets in the system are static, meaning they are not orbiting their sun. But they all have their gravity wells of varying strength. As a player I have to negotiate newtonian physics around these planets, using engine thrust at the right amounts and timing, to get to where I want. That part is not a problem. I'm also willing to assume non-newtonian rotation so that AI and player do not need to account for appyling torque to get a correct bearing.
      So far I have not mentioned whether this is real-time or turn-based and that's because of my uncertainty around AI.
      Problem is I'm not sure how to approach the AI side of things either way. Ideally I'd like to have an AI that can optimize trajectory for speed and/or fuel efficiency, but I have been able to find precious little on the topic on the interwebs. The best I've found so far is the following article from a decade ago, and it does not really point to a solution: http://playtechs.blogspot.ca/2007/05/pathfinding-in-space.html
      If I can find a good resource on how to pull this off in realtime, I'd like to go that route. At the moment my fallback is using a turn based system for exploration and visualizing the system as a hex grid. Then using A* I could get AI agents to naively assume use of thrust to come to a stand still each time they want to change trajectory, and then add extra thrust to move in the next direction, but I'm worried this would be extremely under-optimized in terms of fuel efficiency and the reach of rival ships as a result. I could also factor in the AI ship's current velocity into the graph search, which would likely greatly increase the search space for pathfinding, but I haven't experimented with it yet to be able to say whether it's viable.
      Any thoughts?
    • By povilaslt2
      Hello, I'm trying to implement enemy pathfinding algorihtm, but i have problem with empty tile collision when moving enemy to node.
       
      For example this image shows how it should move like shown in example:

      But it stucks at last tile:

       
      It happens because enemy collides with right side of "air" tile and then it removes from node list because it "collided", but it works with not "air" tiles of course. How do fix this problem?
      Code:
      void Enemy::generateMoveToNode(AStar::Vec2i lastNode) { auto lastSave = AStar::Vec2i{ 0.0f, 0.0f }; while (!target.empty()) { if (target.back().y == lastNode.y) { lastSave = target.back(); target.pop_back(); } else { moveToNodes.push_back(lastSave); moveToNodes.push_back(target.back()); generateMoveToNode(target.back()); return; } } moveToNodes.push_back(lastSave); } void Enemy::updateTarget(std::shared_ptr<InputManager> inputManager) { if (moveToNodes.empty()) return; // Calculate half sizes. float halfWidthA = getSize(0) / 2.0f; float halfHeightA = getSize(1) / 2.0f; float halfWidthB = 32.0f / 2.0f; float halfHeightB = 32.0f / 2.0f; // Calculate centers. auto centerA = glm::vec2(getPosition(0) + halfWidthA, getPosition(1) + halfHeightA); auto centerB = glm::vec2((moveToNodes.front().x * 32.0f) + halfWidthB, (moveToNodes.front().y * 32.0f) + halfHeightB); // Calculate current and minimum-non-intersecting distances between centers. float distanceX = centerA.x - centerB.x; float distanceY = centerA.y - centerB.y; float minDistanceX = halfWidthA + halfWidthB; float minDistanceY = halfHeightA + halfHeightB; setKey(inputManager->getKeyBinding("Move Left"), false); setKey(inputManager->getKeyBinding("Move Right"), false); setKey(inputManager->getKeyBinding("Jump"), false); setKey(inputManager->getKeyBinding("Duck"), false); // If we are not intersecting at all, return (0, 0). if (abs(distanceX) >= minDistanceX || abs(distanceY) >= minDistanceY) { if (moveToNodes.front().y > ceil(getPosition(1) / 32.0f)) setKey(inputManager->getKeyBinding("Jump"), true); else if (moveToNodes.front().y < ceil(getPosition(1) / 32.0f)) { if (getCanClimb()) setKey(inputManager->getKeyBinding("Duck"), true); } else { if (moveToNodes.front().x < ceil(getPosition(0) / 32.0f)) setKey(inputManager->getKeyBinding("Move Left"), true); else if (moveToNodes.front().x > floor(getPosition(0) / 32.0f)) setKey(inputManager->getKeyBinding("Move Right"), true); } updateInput(inputManager); return; } // Calculate and return intersection depths. float depthX = distanceX > 0 ? minDistanceX - distanceX : -minDistanceX - distanceX; float depthY = distanceY > 0 ? minDistanceY - distanceY : -minDistanceY - distanceY; updateInput(inputManager); moveToNodes.erase(moveToNodes.begin()); } generateMoveToNode: recursive function to generate all nodes.
      updateTarget: updates enemy every frame to check if it hits node and then removes it from list and checks next till no nodes left.
    • By lucky6969b
      When my program was generating navigation meshes for my geometry, and the extent is 5000x5000 (m), with a cell size of 5.0 meters, it has to generate 250,000 cells, which makes my computer halt, the target object is a truck, which has a radius of about 20 meters, should I give the cell size a value of 20, because I don't really want to use this navigation mesh on one type of vehicle only. I want to use it for vehicles like cars, which has only about 5 meters in radius... the generation speed is a problem while the memory consumption is another.
      Any ideas how to improve this?
      Thanks
      Jack
  • Popular Now