--- a/bin/ai/library/graph/aystar/library.nut	Wed Jun 11 12:13:22 2008 +0000
+++ b/bin/ai/library/graph/aystar/library.nut	Wed Jun 11 13:04:27 2008 +0000
@@ -4,7 +4,7 @@
 	function GetAuthor()      { return "OpenTTD NoAI Developers Team"; }
 	function GetName()        { return "AyStar"; }
 	function GetDescription() { return "An implementation of AyStar"; }
-	function GetVersion()     { return 1; }
+	function GetVersion()     { return 2; }
 	function GetDate()        { return "2008-06-11"; }
 	function CreateInstance() { return "AyStar"; }
 }

--- a/bin/ai/library/graph/aystar/main.nut	Wed Jun 11 12:13:22 2008 +0000
+++ b/bin/ai/library/graph/aystar/main.nut	Wed Jun 11 13:04:27 2008 +0000
@@ -9,88 +9,147 @@
  */
 class AyStar
 {
+	_cost_callback = null;
+	_estimate_callback = null;
+	_neighbours_callback = null;
+	_open = null;
+	_closed = null;
+	_goals = null;
+
 	/**
-	 * 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.
+	 *  should accept 2 parameters, old_path and new_node. old_path is an
+	 *  instance of AyStar.Path, and new_node is the new node that is added to
+	 *  that path. It should return the cost of the path including new_node.
+	 * @param estimate_callback A function that returns an estimate from a node
+	 *  to the goal node. It should accept two parameters, node and goal_nodes.
 	 *  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
+	 *  node and any node out of goal_nodes. Note that this estimate is not
+	 *  allowed to be higher than the real cost between node and any of
+	 *  goal_nodes. 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.
+	 * @param neighbours_callback A function that returns all neighbouring nodes
+	 *  from a given node. It should accept two parameters, current_path and node,
+	 *  and return an array containing all neighbouring nodes.
 	 */
-	function FindPath(sources, goals, cost_callback, estimate_callback, neighbours_callback);
+	constructor(cost_callback, estimate_callback, neighbours_callback)
+	{
+		if (typeof(cost_callback) != "function") throw("'cost_callback' has be a function-pointer.");
+		if (typeof(estimate_callback) != "function") throw("'estimate_callback' has be a function-pointer.");
+		if (typeof(neighbours_callback) != "function") throw("'neighbours_callback' has be a function-pointer.");
+
+		this._cost_callback = cost_callback;
+		this._estimate_callback = estimate_callback;
+		this._neighbours_callback = neighbours_callback;
+	}
+
+	/**
+	 * Initialize a path search between sources and goals.
+	 * @param sources The source nodes.
+	 * @param goals The target nodes.
+	 */
+	function InitializePath(sources, goals);
+
+	/**
+	 * Try to find the path as indicated with InitializePath with the lowest cost.
+	 * @param iterations After how many iterations it should abort for a moment.
+	 *  This value should either be -1 for infinite, or > 0. Any other value
+	 *  aborts immediatly and will never find a path.
+	 * @return A route if one was found, or false if the amount of iterations was
+	 *  reached, or null if no path was found.
+	 *  You can call this function over and over as long as it returns false,
+	 *  which is an indication it is not yet done looking for a route.
+	 */
+	function FindPath(iterations);
 }
 
-function AyStar::FindPath(sources, goals, cost_callback, estimate_callback, neighbours_callback)
+function AyStar::InitializePath(sources, goals)
 {
-	local closed = AIList();
-	local open = Queue();
-	/* Create the initial open list */
-	foreach (tile in sources) {
-		local new_path = this.Path(null, tile, cost_callback);
-		open.Insert(new_path, new_path.GetCost() + estimate_callback(tile, goals));
+	if (typeof(sources) != "array" || sources.len() == 0) throw("sources has be a non-empty array.");
+	if (typeof(goals) != "array" || goals.len() == 0) throw("goals has be a non-empty array.");
+
+	this._open = Queue();
+	this._closed = AIList();
+
+	foreach (node in sources) {
+		local new_path = this.Path(null, node, this._cost_callback);
+		this._open.Insert(new_path, new_path.GetCost() + this._estimate_callback(node, goals));
 	}
-	while (open.Count() > 0) {
+
+	this._goals = goals;
+}
+
+function AyStar::FindPath(iterations)
+{
+	if (this._open == null) throw("can't execute over an uninitialized path");
+
+	while (this._open.Count() > 0 && (iterations == -1 || iterations-- > 0)) {
 		/* Get the path with the best score so far */
-		local path = open.Pop();
-		local cur_tile = path.GetTile();
+		local path = this._open.Pop();
+		local cur_node = path.GetNode();
 		/* Make sure we didn't already passed it */
-		if (closed.HasItem(cur_tile)) continue;
+		if (this._closed.HasItem(cur_node)) continue;
 		/* Check if we found the end */
-		foreach (tile in goals) {
-			if (cur_tile == tile) return path;
+		foreach (node in this._goals) {
+			if (cur_node == node) {
+				this._CleanPath();
+				return path;
+			}
 		}
-		closed.AddItem(cur_tile, 0);
+		this._closed.AddItem(cur_node, 0);
 		/* Scan all neighbours */
-		local neighbours = neighbours_callback(path, cur_tile);
-		foreach (tile in neighbours) {
-			if (closed.HasItem(tile)) continue;
+		local neighbours = this._neighbours_callback(path, cur_node);
+		foreach (node in neighbours) {
+			if (this._closed.HasItem(node)) continue;
 			/* Calculate the new paths and add them to the open list */
-			local new_path = this.Path(path, tile, cost_callback);
-			open.Insert(new_path, new_path.GetCost() + estimate_callback(tile, goals));
+			local new_path = this.Path(path, node, this._cost_callback);
+			this._open.Insert(new_path, new_path.GetCost() + this._estimate_callback(node, this._goals));
 		}
 	}
 
+	if (this._open.Count() > 0) return false;
+	this._CleanPath();
 	return null;
 }
 
+function AyStar::_CleanPath()
+{
+	this._closed = null;
+	this._open = null;
+	this._goals = null;
+}
+
+/**
+ * The path of the AyStar algorithm.
+ *  It is reversed, that is, the first entry is more close to the goal-nodes
+ *  than his GetParent(). You can walk this list to find the whole path.
+ *  The last entry has a GetParent() of null.
+ */
 class AyStar.Path
 {
 	_prev = null;
-	_tile = null;
+	_node = null;
 	_cost = null;
 
-	constructor(old_path, new_tile, cost_callback)
+	constructor(old_path, new_node, cost_callback)
 	{
 		this._prev = old_path;
-		this._tile = new_tile;
-		this._cost = cost_callback(old_path, new_tile);
+		this._node = new_node;
+		this._cost = cost_callback(old_path, new_node);
 	};
 
 	/**
-	 * Return the tile where this (partial-)path ends.
+	 * Return the node where this (partial-)path ends.
 	 */
-	function GetTile() { return this._tile; }
+	function GetNode() { return this._node; }
 
 	/**
-	 * Return an instance of this class leading to the previous tile.
+	 * Return an instance of this class leading to the previous node.
 	 */
 	function GetParent() { return this._prev; }
 
 	/**
-	 * Return the cost of this (partial-)path from the beginning up to this tile.
+	 * Return the cost of this (partial-)path from the beginning up to this node.
 	 */
 	function GetCost() { return this._cost; }
 }

--- a/bin/ai/regression/regression.nut	Wed Jun 11 12:13:22 2008 +0000
+++ b/bin/ai/regression/regression.nut	Wed Jun 11 13:04:27 2008 +0000
@@ -1,6 +1,6 @@
 import("queue.priority_queue", "PQ", 2);
 import("queue.binary_heap", "BH", 1);
-import("graph.aystar", "AS", 1);
+import("graph.aystar", "AS", 2);
 
 class Regression extends AIController {
 	function Start();
@@ -380,10 +380,14 @@
 {
 	print("--AyStar--");
 	print("  Fastest path:");
-	local as = AS();
-	local path = as.FindPath([1], [10], cost_callback, estimate_callback, neighbours_callback);
+	local as = AS(cost_callback, estimate_callback, neighbours_callback);
+
+	local path = false;
+	as.InitializePath([1], [10]);
+	while (path == false) path = as.FindPath(5);
+
 	while (path != null) {
-		print("    Tile " + path.GetTile());
+		print("    Tile " + path.GetNode());
 		path = path.GetParent();
 	}
 }