diagonal cost isn't taken into account

[nojacko]

Hello

I've been using astar to make a game and I've discovered that diagonal movements are often favored although the route is longer.

From what I make out, weightings on diagonal movements should be slightly more than the given value as the diagonal distance across the sqaure is greater than up, down, left, right movements.

The solution (I think) would be to modify the node's cost to be: square root ( cost*cost + cost * cost).

However, I've not got this working correctly yet.

Does anyone have thoughts on this? Is it the correct thing to do? Is there a better solution?

[bgrins]

Good questions. Here is the heuristic we are using for cost calculation: https://github.com/bgrins/javascript-astar/blob/master/astar.js#L94.

It appears that we may want to use the "Diagonal Distance" heuristic instead: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html.

If you implemented a diagonal function following the algorithm on that site alongside the manhattan one then you should be able to just pass in astar.diagonal into the final parameter of the search function. If you get this working can you send a pull request over so we can include it in the implementation as I think this will come up again for others facing the same issue you are.

[nojacko]

Thanks for the pointers. I've been trying to implement this but I've struggled to get it working.

However, while doing this, it's become apparent to me that, for my needs, Dijkstra's algorithm is better.

[bgrins]

OK, you could easily turn this into Dijkstra's algorithm by coming up with a heuristic that always returns 0. That's really the only difference between the two.

[nojacko]

I've implement Dijkstra's (couldn't find any decent JavaScript implementation) so I thought I'd share, as you did with A*. Thanks.

https://github.com/nojacko/dijkstras-js

[kicktheken]

Here is the fix to diagonals:

https://github.com/bgrins/javascript-astar/blob/master/astar.js#L67

Instead of:

var gScore = currentNode.g + neighbor.cost;

use:

var gScore = currentNode.g + neighbor.cost * heuristic(currentNode.pos, neighbor.pos);

that way, if you use euclidean heuristic, it should always return the shortest path

[bgrins]

@kicktheken I see the reasoning there, and in the case of euclidean it should work but I think we should really have a costBetween function that returns the actual distance between the two nodes. The reasoning here is that the heuristic may not actually represent the true cost, rather be an estimate that takes other factors into consideration.

var gScore = currentNode.g + costBetween(currentNode, neighbor);

Then costBetween could return euclidean * neighbor.cost, or some other custom logic.

[gyril]

I added * heuristic(currentNode, neighbor) to L101 and it seems to work

[StanB123]

Maybe I'm silly. But wouldn't simply changing the getCost method into something like this do the trick in the current version?

GridNode.prototype.getCost = function(fromOther) {
    if (fromOther.x != this.x && fromOther.y != this.y)
        return this.weight * 1.42412;
    return this.weight;
};

Instead of the current version which doesn't seem to do anything with the parameter that is given to getCost on line 88?

[bgrins]

But wouldn't simply changing the getCost method into something like this do the trick in the current version?

@StanB123 Nice, I think that may work, since the fromOther is always going to be an adjacent neighbor. Any chance you could send over a PR with that change and a simple test?

[StanB123]

I'll try to find some time for that during the weekend :-)