How to configure A* for large 2D Grid based pathfinding, where paths could be long or short?

I thought A* was Optimal, meaning I'd always get the quickest path.

I have written a generic Pathfinding implementation here: https://github.com/mGuv/mGuv/blob/PathPerformanceExperiment/mGuv/mGuv/Pathfinding/Pathfinder.cs

It's a bit messy/weird as I've branched off my original to fix some issues and experiment.

I wrote a testing class that can read in an image file that uses Black for Obstacles, Blue for start, Green for goal. It too is a little messy but I'm just debugging again.

http://hastebin.com/wikejexige.avrasm

So it uses Euclidean Distance and Orthogonal movement to attempt to path.

It then generates an output image, with Black for Obstacles, Blue for the Path found, Orange for the Nodes Expanded, and Cyan for the Open Set.

Given the input image:

It outputs:

Which is less than Optimal?

I've tried tweaking the cost/heuristic functions and their weighting.

Eventually I can get something like:

But now look at that open set, it's essentially turned in to Dijkstra's Algorithm.

I also believe I have the "Breaking the tie" problem, as an input like:

Will expand way more nodes that necessary:

I've tried to follow the Wikipedia article on A* to come up with better cost handling but most of those assume you know the estimated path length. Which is difficult for me as I will be using this to path find on giant (1024x1024+) grids that are dynamic. From tiny (<10 step paths) to huge (> 10000 step paths).

I'm a little lost now as to where I'm going wrong. I don't know if there's a bug or a misunderstanding. I apologise for the tiny images, it was just easier to work a pixel basis.

• In your code the weight for moving diagonally (which is one up and one down, for a length of sqrt(2)) is the same weight as moving straight, this is likely to be a large part of your issue.
– Elva
Sep 13, 2015 at 15:58
• @KevinvanderVelden It's Euclidean, the cost of a straight move is 1, the cost of a diagonal is 1.414214
– mGuv
Sep 13, 2015 at 16:03
• That is indeed what it should be, I don't see that in your code however =p.
– Elva
Sep 13, 2015 at 16:12
• The cost functions are passed in as Method references, they reference the Distance function in the Vector2i.cs folder in the mGuv/Math namespace.
– mGuv
Sep 13, 2015 at 16:29