ATTENTION: the V2 release comes with breaking changes. Starting with V2, this library will no longer be limited to 2D maps and will support solving any generic graph. The existing usage for 2D maps will still be available as a built-in option, but the user will also be able to define his own.

• Framework-agnostic A* solver for any graph.
• Comes with a built-in implementation for 2D maps.
• Supports caching for significant speedups when searching through overlapping sub-paths.
• Efficient implementation, with object pooling and minimal run-time allocations.

Installation

haxelib install astar

Basic usage - 2D map

import astar.map2d.Map2D;

First initialize a Map2D object.

// Dimensions of the world in tiles.
var worldWidth = 10;
var worldHeight = 10;

// Movement directions possible on the grid.
var movementDirection = FourWay;

var map2d: Map2D = new Map2D(worldWidth, worldHeight, movementDirection);

Load the world grid into the graph.

var world: Array<Int> = [
// x 0  1  2  3  4  5  6  7  8  9     y
     0, 0, 0, 0, 0, 0, 0, 0, 1, 0, // 0
     1, 1, 1, 1, 1, 1, 1, 0, 1, 1, // 1
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 2
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 3
     0, 0, 0, 2, 2, 0, 1, 1, 1, 1, // 4
     0, 0, 0, 2, 2, 0, 1, 0, 0, 0, // 5
     0, 0, 0, 0, 0, 0, 1, 0, 1, 0, // 6
     0, 0, 1, 0, 0, 0, 1, 0, 1, 0, // 7
     0, 0, 1, 0, 0, 0, 1, 0, 1, 0, // 8
     0, 0, 1, 0, 0, 0, 0, 0, 1, 0, // 9
];

map2d.setMap(world);

The array should have widthxheight elements, which contain the grid packed row by row. So the first element is the cell 0x0, the second element is the cell 1x0 and so on.

The values in the cells of the grid are arbitrary, and shall be chosen by the user to represent the various types of tiles present in the world, which are differentiated by different passability and/or traversal costs.

A cost is defined for traversal into a tile.

Set the costs of movement

var costs = [
    // 0 is our ground, with a cost of 1 to move lateraly.
    // also: 0 => Map2D.defaultCosts,
    0 => [ N => 1, S => 1, W => 1, E => 1 ],

    // 2 is harsh terrain, slower to move into.
    2 => [ N => 1.5, S => 1.5, W => 1.5, E => 1.5 ]

    // 1 is wall tiles
    // without any cost specified, they are impassable
];

map2d.setCosts(costs);

Solve for a path

// Starting point
var startX = 3;
var startY = 3;

// End point
var endX = 7;
var endY = 9;

var result: SearchResult2D = map2d.solve(startX, startY, endX, endY);

// Check if a solution was found
if (result.result == Solved)
{
    // Total cost of the path
    var totalCost: Float = result.cost;

    // Go through the resulting path
    // (the first element is the starting point)
    for (point in result.path)
    {
        trace('${point.x}, ${point.y}');
    }
}

Caching paths

Caching can be enabled, which can offer a significant speedup for multiple searches on the same paths or sub-paths.

// Enable the cache, with a capacity of 512 paths.
map2d.configureCache(true, 512);

The main method graph.solve() will then automatically query the cache to construct paths, as well as update it with paths that are solved.

The cache is always reset when updating the graph through the setWorld(), setCosts() and setHeuristicFunction(). In addition to that it can also be reset manually.

map2d.resetCache();

Heuristics

The built-in Map2D implementation comes with three heuristics under the astar.map2d.heuristics package.

• ManhattanDistance: The default heuristic for a four-way movement grid. Details can be found here.
• DiagonalDistance: The default heuristic for an eight-way movement grid. Details can be found here.
• EuclideanDistance: This is the typical geographical distance between two points. It should be used if movement is possible at any angle, instead of grid directions. Details can be found here.

One of these, or any custom heuristic implementing the HeuristicFunction interface, can be configured for the graph using the setHeuristic method.

map2d.setHeuristic(new EuclideanDistance());

Advanced usage - custom graphs

States

Graph nodes are uniquely identified by a single state integer. This means that two different nodes must always have different state, and that the same node must never change its state.

How states are defined for a graph is up to the user and depends on the kind of graph. For example, this state might be a unique ID, or a hash of a node's coordinates, and so on.

In Haxe, the Int type typically represents a 32-bit integer, so currently this library does not support graphs with more than 2³² nodes.

Implementation

To run the A* solver on a custom graph, it is necessary to implement a class that extends Graph. In said class, it is necessary to implement the following methods.

import astar.Graph;
import astar.types.NextNodeCallback;

class MyGraph extends Graph
{
    public function getNextNodes(state: Int, callback: NextNodeCallback): Void
    {
        /**
         * This method takes a node's state number, and must return all of the other node
         * states that are reachable from it.
         */
        for (neighbor in neighborsOf(state))
        {
            var cost: Float = costToMoveInto(neighbor);
            callback(neighbor, cost);
        }
    }

    public function getHeuristicCost(from: Int, to: Int): Float
    {
        // this method should return the heuristic cost estimate from one state to another
        return to - from;
    }
}

The parent Graph class keeps a reference to an Astar object, which can then be used to run the algorithm. For example, an additional method could be added to the MyGraph class, which will encapsulate a call to astar.solve(), while also converting between A* states, and useful nodes for the application.

The following excerpt is similar to what is done in Map2D to showcase how this might be implemented.

class MyGraph extends Graph
{
    public function getShortestPath(startX: Int, startY: Int, goalX: Int, goalY: Int, ?maxCost: Float): SearchResult2D
    {
        var start: Int = xyToNode(startX, startY);
        var goal: Int = xyToNode(goalX, goalY);
        var res: SearchResult = astar.solve(start, goal, maxCost);

        return {
            result: res.result,
            cost: res.cost,
            path: res.path == null ? null : res.path.map(s ->
            {
                x: nodeToX(s),
                y: nodeToY(s)
            })
        };
    }
}

Finally, if the Graph instance is reused and the cache is enabled, the user should not forget to call the resetCache() method whenever any change occurs to the graph or traversal costs.

Keeping track of transitions between states

By default, the SearchResult.path that is returned by Astar.solve() is just an ordered list of the states that make up the shortest path. If it's necessary to also track exactly which transition was used to traverse from one state to the other, a unique transition identifier can be passed to the getNextNodes callback.

public function getNextNodes(state: Int, callback: NextNodeCallback): Void
{
    /**
     * In this example it is important to know not only what next state was reachable, but also
     * the transition that took us to that state.
     */
    for (action in possibleActions)
    {
        var nextState: Int = action.applyTo(state);
        callback(nextState, action.cost, action.id);
    }
}

Then the field SearchResult.transitions can be used to check which transition was used to traverse to each node in the graph.

var res: SearchResult = astar.solve(start, goal);

for (i in 0...res.path.length)
{
    var node: Int = res.path[i];
    var action = getActionById(res.transitions[i]);

    // now we also know which action was used in getNextNodes to reach this node!
}

Note that res.transitions[0] will always be 0, since res.path[0] holds the starting state.