Maps can have a lot of shapes. You could have a node map, a rectangular grid, a hexagonal grid, etc. Each type of map would have its own definition for which tile is a neighbor of which tile, what the distance is between two tiles, etc. Astar uses the IMap interface to communicate with all these types of maps. The IMap has only three methods:

getNeighbours

This method should return all the neighboring tiles for the given tile. In a node map, this would be a list of all the nodes that share an edge with the given node. In a rectangular grid, this would be a list of all the tiles that are above/below/left/right of the given tile.

getHeuristic

Astar uses a heuristic to calculate which node to visit next. Every map should be able to provide a heuristic that tells how far you are probably away from reaching your goal. (More information about heuristics can be found on Wikipedia: Heuristic Function) One of the most important things to note is that your heuristic shouldn’t overestimate the actual cost. If you would do that, Astar isn’t guaranteed to give the best path.

getDistance()

This method returns the distance between two given tiles. This value is multiplied with a tiles cost to get the total cost from going to one tile to another. If two tiles in a rectangular grid have a common edge, it could return ‘1’ and if they only have a common corner (“going diagonally”), it could return 1.4 (sqrt(2)). If you don’t give diagonal moves a greater multiplier, you could get a path like this:

Crazy diagonal path

Default Map

A default 2D rectangular map can be found in be.dauntless.astar.basic2d. It provides two heuristic methods (Map.DIAGONAL_HEURISTIC and Map.MANHATTAN_HEURISTIC) which can be set with Map.setHeuristic.

You can also use “Map.NO_HEURISTIC” which will move the heuristic all together. You can find an example of why this is useful on the PathRequest page.

2 Responses to “Maps”


  1. 1 Bennett

    hi ~ thank you so much for provide this greate A* in as3.^ I don’t understand about MANHATTAN_HEURISTIC, could you explain it more specific ? Thank you~!!!

  2. 2 Dauntless

    Hi,

    The Manhattan heuristic is pretty famous and explained well on wikipedia: http://en.wikipedia.org/wiki/Manhattan_distance. It basically counts the number of tiles you would have to move horizontally and the amount of tiles you would have to move vertically and adds the two. This is probably the most basic heuristic if you can’t move diagonally.

Leave a Reply

*