MicroPather is an AS3 port of Lee Thomason’s C++ A* solver.  The library focuses on being a path finding engine for video games but it is a generic A* solver. The main goals the library tries to meet are: an easy integration into games and other software, an easy to use and simple interface and performance (it has to be fast enough).

The library works by solving the path of a given object, which must implement the IGraph interface. That interface tells MicroPather how the map is organized, such as the cost of an edge. After it solves the path, the library returns a vector of points, each one representing a node of the route.

Sample

/*
Copyright (c) 2000-2005 Lee Thomason (www.grinninglizard.com)

Grinning Lizard Utilities.

This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any
damages arising from the use of this software.

Permission is granted to anyone to use this software for any
purpose, including commercial applications, and to alter it and
redistribute it freely, subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must
not claim that you wrote the original software. If you use this
software in a product, an acknowledgment in the product documentation
would be appreciated but is not required.

2. Altered source versions must be plainly marked as such, and
must not be misrepresented as being the original software.

3. This notice may not be removed or altered from any source
distribution.
*/

package demo {

import micropather.IGraph;
import micropather.MicroPather;

public class Dungeon extends Sprite implements IGraph {

    private const MAPX:int = 30;
    private const MAPY:int = 10;
    private const gMap:String =
        "     |      |                |" +
        "     |      |----+    |      +" +
        "---+ +---DD-+      +--+--+    " +
        "   |                     +-- +" +
        "        +----+  +---+         " +
        "---+ +  D    D            |   " +
        "   | |  +----+    +----+  +--+" +
        "   D |            |    |      " +
        "   | +-------+  +-+    |--+   " +
        "---+                   |     +";

    private var children :Vector.;
    private var pather :MicroPather;

    public var playerX :int = 0;
    public var playerY :int = 0;

    public function init (e :Event) :void {
        pather = new MicroPather( this );
    }

    public function Index( x:int, y:int ):int {
        return y*MAPX + x;
    }

    public function Encode( x:int, y:int ):int {
        return y*MAPX+x;
    }

    public function Decode( s:Object ):Point {
        var state :int = int(s);
        var y:int = state / MAPX;
        var x:int = state - y*MAPX;
        return new Point( x, y );
    }

    public function onMouseMoveEvent(event:MouseEvent):void {
        var dx:Number = stage.stageWidth/MAPX;
        var dy:Number = stage.stageHeight/MAPY;
        var x:int = event.stageX / dx;
        var y:int = event.stageY / dy;
        var index:int = y*MAPX+x;

        var ct:ColorTransform = new ColorTransform();
        //ct.blueOffset = 100;
        //ct.redOffset = 100;
        ct.greenOffset = 100;
        if ( selected )
            selected.transform.colorTransform = new ColorTransform();
        children[index].transform.colorTransform = ct;
        selected = children[index];
    }

    public function onMouseClickEvent(event:MouseEvent):void {
        var x:int = // destination X;
        var y:int = // destination Y;
        var solution :Vector.<Object> = new Vector.<Object>();

        pather.solve( Encode( playerX, playerY ), Encode( x, y ), solution );

        for( var i:int=1; i= 0 && nx < MAPX && ny >= 0 && ny < MAPY ) {
            var index:int = ny*MAPX+nx;
            var c:String = gMap.charAt( index );

            if ( c == ' ' )
                return 1;
            else if ( c == 'D' )
                return 2;
        }
        return 0;
    }

    public function leastCostEstimate( stateStart:Object, stateEnd:Object ):Number {
        var d0:Point = Decode( stateStart );
        var d1:Point = Decode( stateEnd );
        var dx:int = d0.x - d1.x;
        var dy:int = d0.y - d1.y;

        return Math.sqrt( dx*dx + dy*dy );
    }

    public function adjacentCost( node:Object, states:Vector.