Oops!

Looks like my little A* doesn’t always generate the shortest path if you are able to walk diagonally. (If your characters can only walk vertically/horizontally, you’re safe from potentially walking a few extra tiles!)

I’m using the Manhattan heuristic which is good if you can only move horizontal or vertical, but it’s double as large as what you would expect it to be if you can move diagonally. That means that sometimes, a shorter path will not be looked at, because the algorithm guesses that it would be a worse path than the current one.

The good news: it’s an easy fix. If by the time you are reading this v1.3 isn’t out yet:

In DataTiles.as, change the setH method:

public function setH(end:Point) : void
{
this.h = Math.abs(end.x - position.x) * _standardCost + Math.abs(end.y - position.y) * _standardCost;
this.f = this.h + this.g;
}

becomes

public function setH(end:Point) : void
{
this.h = Math.max(Math.abs(end.x - position.x), Math.abs(end.y - position.y)) * _standardCost;
this.f = this.h + this.g;
}

That is, of course, only if you are able to walk diagonally.

This will be fixed in v1.3.

3 Responses to “Oops!”


  1. 1 Guest

    This patch does not compile, because of unknown variable start.

  2. 2 Dauntless

    Thanks, you’re totally right. ‘start’ has to be ‘position’.

    I’ve fixed it above.

  3. 3 Ethan

    You’re doing great work. Thanks!

Leave a Reply

*