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.
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.
Which is less than Optimal?
I've tried tweaking the cost/heuristic functions and their weighting.
But now look at that open set, it's essentially turned in to Dijkstra's Algorithm.
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.