Astar Pathfinding

[Jono]

@Roquen

Why bother with sqrt or max/min? Euclidean distance squared is an equivalent metric to euclidean distance. (if aa > bb, then |a| > |b|)

The problem is that you actually need to combine the results of the heuristic with the cost so far. So if just using the square of the heuristic you’d have f(x) = g(x) + h(x)*h(x), which for heuristic values greater than 1 would make the search tend to a best-first (and the heuristic is non-admissible).

Taking the square of the cost so far doesn’t fix it either, because g(x)*g(x) + h(x)*h(x) still doesn’t have the same metric properties as g(x) + h(x).

[Demonpants]

@pjt33

@Eli Delventhal

So yeah, in your case a Euclidean heuristic is necessary.

There are other admissible heuristics. E.g. max(abs(x - x0), abs(y - y0)).

Edit: or

int dx = x - x0; if (dx < 0) dx = -dx;
int dy = y - y0; if (dy < 0) dy = -dy;
int max = dx > dy ? dx : dy;
int heuristic = max + (dx + dy - max) / (2 * max);

Yes, I should have clarified, I meant between Manhattan and Euclidean distances.

In my game Sinuosity because it’s a maze where you can never go diagonally Manhattan distance works excellently. I would imagine that if you allowed diagonals you could just do a smarter version of Manhattan where you use sqrt(2) for the diagonals and 1 for direct angles. That is, if you consider a diagonal to cost more than u/d/l/r, considering it is in fact a longer distance.

[appel]

Few years ago I worked on a pathfinder project.

If you’re interested you can see it here: http://gamadu.com/temp/stuff/Pathfinder.zip

[martin]

Hi,
When running the applet from the browser, the path does not start after the two clicks.
When building and running from sources, the pathfind returns a null path at the following call

GridPath aPath = pathfinding.getPath(mouse.getStart(), mouse.getEnd(), draw.getMap());

Any suggestion to have the demo running?! It seems great!
Cheers
Martin

[Gudradain]

Just test it and it still work fine. You need to do a right click and a left click and you need to click on empty space.

[martin]

That’s what I did
I will tell you if I find the reason.
Cheers,
Martin