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.

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.

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.

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.

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.

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.

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.

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.