0
\$\begingroup\$

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: enter image description here

It outputs: enter image description here

Which is less than Optimal?

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

Eventually I can get something like: enter image description here

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: enter image description here

Will expand way more nodes that necessary: enter image description here

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.

Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$
    – Elva
    Sep 13, 2015 at 15:58
  • \$\begingroup\$ @KevinvanderVelden It's Euclidean, the cost of a straight move is 1, the cost of a diagonal is 1.414214 \$\endgroup\$
    – mGuv
    Sep 13, 2015 at 16:03
  • \$\begingroup\$ That is indeed what it should be, I don't see that in your code however =p. \$\endgroup\$
    – Elva
    Sep 13, 2015 at 16:12
  • \$\begingroup\$ The cost functions are passed in as Method references, they reference the Distance function in the Vector2i.cs folder in the mGuv/Math namespace. \$\endgroup\$
    – mGuv
    Sep 13, 2015 at 16:29

1 Answer 1

Reset to default
0
\$\begingroup\$

Someone on Reddit sussed it. The issue was on line 136. When it updates a node's position in the Open Set, it never replaced the Parent node. Meaning, yes, the node was correctly reordered and used in the path finding but when it came to reverse traversing to build the path, it used the out dated, more expensive parent.

The fix was to simply update that nodes parent at the same time as updating its cost.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .