--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/bin/ai/library/graph/aystar/library.nut	Tue Jun 10 23:30:02 2008 +0000
@@ -0,0 +1,12 @@
+/* $Id$ */
+
+class AyStar extends AILibrary {
+	function GetAuthor()      { return "OpenTTD NoAI Developers Team"; }
+	function GetName()        { return "AyStar"; }
+	function GetDescription() { return "An implementation of AyStar"; }
+	function GetVersion()     { return 1; }
+	function GetDate()        { return "2008-06-11"; }
+	function CreateInstance() { return "AyStar"; }
+}
+
+RegisterLibrary(AyStar());

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/bin/ai/library/graph/aystar/main.nut	Tue Jun 10 23:30:02 2008 +0000
@@ -0,0 +1,96 @@
+/* $Id$ */
+
+/* We need a Queue */
+import("queue.binary_heap", "Queue", 1);
+
+/**
+ * An AyStar implementation.
+ *  It solves graphs by finding the fastest route from one point to the other.
+ */
+class AyStar
+{
+	/**
+	 * Find a single path between sources and goals with the lowest cost.
+	 * @param sources The source tiles.
+	 * @param goals The target tiles.
+	 * @param cost_callback A function that returns the cost of a path. It
+	 *  should accept 2 parameters, old_path and new_tile. old_path is an
+	 *  instance of AyStar.Path, and new_tile is the new tile that is added to
+	 *  that path. It should return the cost of the path including new_tile.
+	 * @param estimate_callback A function that returns an estimate from a tile
+	 *  to the goal tile. It should accept two parameters, tile and goal_tiles.
+	 *  It should return an estimate to the cost from the lowest cost between
+	 *  tile and any tile out of goal_tiles. Note that this estimate is not
+	 *  allowed to be higher than the real cost between tile and any of
+	 *  goal_tiles. A lower value is fine, however the closer it is to the real
+	 *  value, the better the performance.
+	 * @param neighbours_callback A function that returns all neighbouring tiles
+	 *  from a given tile. It should accept two parameters, current_path and tile,
+	 *  and return an array containing all neighbouring tiles.
+	 * @return A route to from an element of sources to an element of goals or
+	 *  null if there is no route.
+	 */
+	function FindPath(sources, goals, cost_callback, estimate_callback, neighbours_callback);
+}
+
+function AyStar::FindPath(sources, goals, cost_callback, estimate_callback, neighbours_callback)
+{
+	local closed = AIList();
+	local open = Queue();
+	/* Create the initial open list */
+	foreach (tile in sources) {
+		local new_path = AyStar.Path(null, tile, cost_callback);
+		open.Insert(new_path, new_path.GetCost() + estimate_callback(tile, goals));
+	}
+	while (open.Count() > 0) {
+		/* Get the path with the best score so far */
+		local path = open.Pop();
+		local cur_tile = path.GetTile();
+		/* Make sure we didn't already passed it */
+		if (closed.HasItem(cur_tile)) continue;
+		/* Check if we found the end */
+		foreach (tile in goals) {
+			if (cur_tile == tile) return path;
+		}
+		closed.AddItem(cur_tile, 0);
+		/* Scan all neighbours */
+		local neighbours = neighbours_callback(path, cur_tile);
+		foreach (tile in neighbours) {
+			if (closed.HasItem(tile)) continue;
+			/* Calculate the new paths and add them to the open list */
+			local new_path = AyStar.Path(path, tile, cost_callback);
+			open.Insert(new_path, new_path.GetCost() + estimate_callback(tile, goals));
+		}
+	}
+
+	return null;
+}
+
+class AyStar.Path
+{
+	_prev = null;
+	_tile = null;
+	_cost = null;
+
+	constructor(old_path, new_tile, cost_callback)
+	{
+		this._prev = old_path;
+		this._tile = new_tile;
+		this._cost = cost_callback(old_path, new_tile);
+	};
+
+	/**
+	 * Return the tile where this (partial-)path ends.
+	 */
+	function GetTile() { return this._tile; }
+
+	/**
+	 * Return an instance of this class leading to the previous tile.
+	 */
+	function GetParent() { return this._prev; }
+
+	/**
+	 * Return the cost of this (partial-)path from the beginning up to this tile.
+	 */
+	function GetCost() { return this._cost; }
+}