(svn r15027) -Merge: tomatos and bananas left to be, here is NoAI for all to see.

  NoAI is an API (a framework) to build your own AIs in. See:
   http://wiki.openttd.org/wiki/index.php/AI:Main_Page
 With many thanks to:
  - glx and Rubidium for their syncing, feedback and hard work
  - Yexo for his feedback, patches, and AIs which tested the system very deep
  - Morloth for his feedback and patches
  - TJIP for hosting a challenge which kept NoAI on track
  - All AI authors for testing our AI API, and all other people who helped in one way or another
-Remove: all old AIs and their cheats/hacks

2 files changed, 250 insertions, 0 deletions

diff --git a/bin/ai/library/graph/aystar/library.nut b/bin/ai/library/graph/aystar/library.nut
new file mode 100644
index 000000000..522760135
--- /dev/null
+++ b/bin/ai/library/graph/aystar/library.nut
@@ -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 4; }
+	function GetDate()        { return "2008-06-11"; }
+	function CreateInstance() { return "AyStar"; }
+}
+
+RegisterLibrary(AyStar());
diff --git a/bin/ai/library/graph/aystar/main.nut b/bin/ai/library/graph/aystar/main.nut
new file mode 100644
index 000000000..1999eab14
--- /dev/null
+++ b/bin/ai/library/graph/aystar/main.nut
@@ -0,0 +1,238 @@
+/* $Id$ */
+
+/**
+ * An AyStar implementation.
+ *  It solves graphs by finding the fastest route from one point to the other.
+ */
+class AyStar
+{
+	_queue_class = import("queue.binary_heap", "", 1);
+	_cost_callback = null;
+	_estimate_callback = null;
+	_neighbours_callback = null;
+	_check_direction_callback = null;
+	_cost_callback_param = null;
+	_estimate_callback_param = null;
+	_neighbours_callback_param = null;
+	_check_direction_callback_param = null;
+	_open = null;
+	_closed = null;
+	_goals = null;
+
+	/**
+	 * @param cost_callback A function that returns the cost of a path. It
+	 *  should accept four parameters, old_path, new_tile, new_direction and
+	 *  cost_callback_param. 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 four parameters, tile, direction,
+	 *  goal_nodes and estimate_callback_param. It should return an estimate to
+	 *  the cost from the lowest cost between 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 nodes
+	 *  from a given node. It should accept three parameters, current_path, node
+	 *  and neighbours_callback_param. It should return an array containing all
+	 *  neighbouring nodes, which are an array in the form [tile, direction].
+	 * @param check_direction_callback A function that returns either false or
+	 *  true. It should accept four parameters, tile, existing_direction,
+	 *  new_direction and check_direction_callback_param. It should check
+	 *  if both directions can go together on a single tile.
+	 * @param cost_callback_param This parameters will be passed to cost_callback
+	 *  as fourth parameter. Useful to send is an instance of an object.
+	 * @param estimate_callback_param This parameters will be passed to
+	 *  estimate_callback as fourth parameter. Useful to send is an instance of an
+	 *  object.
+	 * @param neighbours_callback_param This parameters will be passed to
+	 *  neighbours_callback as third parameter. Useful to send is an instance of
+	 *  an object.
+	 * @param check_direction_callback_param This parameters will be passed to
+	 *  check_direction_callback as fourth parameter. Useful to send is an
+	 *  instance of an object.
+	 */
+	constructor(cost_callback, estimate_callback, neighbours_callback, check_direction_callback, cost_callback_param = null,
+	            estimate_callback_param = null, neighbours_callback_param = null, check_direction_callback_param = null)
+	{
+		if (typeof(cost_callback) != "function") throw("'cost_callback' has to be a function-pointer.");
+		if (typeof(estimate_callback) != "function") throw("'estimate_callback' has to be a function-pointer.");
+		if (typeof(neighbours_callback) != "function") throw("'neighbours_callback' has to be a function-pointer.");
+		if (typeof(check_direction_callback) != "function") throw("'check_direction_callback' has to be a function-pointer.");
+
+		this._cost_callback = cost_callback;
+		this._estimate_callback = estimate_callback;
+		this._neighbours_callback = neighbours_callback;
+		this._check_direction_callback = check_direction_callback;
+		this._cost_callback_param = cost_callback_param;
+		this._estimate_callback_param = estimate_callback_param;
+		this._neighbours_callback_param = neighbours_callback_param;
+		this._check_direction_callback_param = check_direction_callback_param;
+	}
+
+	/**
+	 * Initialize a path search between sources and goals.
+	 * @param sources The source nodes. This can an array of either [tile, direction]-pairs or AyStar.Path-instances.
+	 * @param goals The target tiles. This can be an array of either tiles or [tile, next_tile]-pairs.
+	 * @param ignored_tiles An array of tiles that cannot occur in the final path.
+	 */
+	function InitializePath(sources, goals, ignored_tiles = []);
+
+	/**
+	 * 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::InitializePath(sources, goals, ignored_tiles = [])
+{
+	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 = this._queue_class();
+	this._closed = AIList();
+
+	foreach (node in sources) {
+		if (typeof(node) == "array") {
+			if (node[1] <= 0) throw("directional value should never be zero or negative.");
+
+			local new_path = this.Path(null, node[0], node[1], this._cost_callback, this._cost_callback_param);
+			this._open.Insert(new_path, new_path.GetCost() + this._estimate_callback(node[0], node[1], goals, this._estimate_callback_param));
+		} else {
+			this._open.Insert(node, node.GetCost());
+		}
+	}
+
+	this._goals = goals;
+
+	foreach (tile in ignored_tiles) {
+		this._closed.AddItem(tile, ~0);
+	}
+}
+
+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 = this._open.Pop();
+		local cur_tile = path.GetTile();
+		/* Make sure we didn't already passed it */
+		if (this._closed.HasItem(cur_tile)) {
+			/* If the direction is already on the list, skip this entry */
+			if ((this._closed.GetValue(cur_tile) & path.GetDirection()) != 0) continue;
+
+			/* Scan the path for a possible collision */
+			local scan_path = path.GetParent();
+
+			local mismatch = false;
+			while (scan_path != null) {
+				if (scan_path.GetTile() == cur_tile) {
+					if (!this._check_direction_callback(cur_tile, scan_path.GetDirection(), path.GetDirection(), this._check_direction_callback_param)) {
+						mismatch = true;
+						break;
+					}
+				}
+				scan_path = scan_path.GetParent();
+			}
+			if (mismatch) continue;
+
+			/* Add the new direction */
+			this._closed.SetValue(cur_tile, this._closed.GetValue(cur_tile) | path.GetDirection());
+		} else {
+			/* New entry, make sure we don't check it again */
+			this._closed.AddItem(cur_tile, path.GetDirection());
+		}
+		/* Check if we found the end */
+		foreach (goal in this._goals) {
+			if (typeof(goal) == "array") {
+				if (cur_tile == goal[0]) {
+					local neighbours = this._neighbours_callback(path, cur_tile, this._neighbours_callback_param);
+					foreach (node in neighbours) {
+						if (node[0] == goal[1]) {
+							this._CleanPath();
+							return path;
+						}
+					}
+					continue;
+				}
+			} else {
+				if (cur_tile == goal) {
+					this._CleanPath();
+					return path;
+				}
+			}
+		}
+		/* Scan all neighbours */
+		local neighbours = this._neighbours_callback(path, cur_tile, this._neighbours_callback_param);
+		foreach (node in neighbours) {
+			if (node[1] <= 0) throw("directional value should never be zero or negative.");
+
+			if ((this._closed.GetValue(node[0]) & node[1]) != 0) continue;
+			/* Calculate the new paths and add them to the open list */
+			local new_path = this.Path(path, node[0], node[1], this._cost_callback, this._cost_callback_param);
+			this._open.Insert(new_path, new_path.GetCost() + this._estimate_callback(node[0], node[1], this._goals, this._estimate_callback_param));
+		}
+	}
+
+	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;
+	_direction = null;
+	_cost = null;
+
+	constructor(old_path, new_tile, new_direction, cost_callback, cost_callback_param)
+	{
+		this._prev = old_path;
+		this._tile = new_tile;
+		this._direction = new_direction;
+		this._cost = cost_callback(old_path, new_tile, new_direction, cost_callback_param);
+	};
+
+	/**
+	 * Return the tile where this (partial-)path ends.
+	 */
+	function GetTile() { return this._tile; }
+
+	/**
+	 * Return the direction from which we entered the tile in this (partial-)path.
+	 */
+	function GetDirection() { return this._direction; }
+
+	/**
+	 * 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 node.
+	 */
+	function GetCost() { return this._cost; }
+};