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.

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.

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.

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.  

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.

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.