(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

12 files changed, 1512 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; }
+};
diff --git a/bin/ai/library/pathfinder/rail/library.nut b/bin/ai/library/pathfinder/rail/library.nut
new file mode 100644
index 000000000..2d50557e2
--- /dev/null
+++ b/bin/ai/library/pathfinder/rail/library.nut
@@ -0,0 +1,12 @@
+/* $Id$ */
+
+class Rail extends AILibrary {
+	function GetAuthor()      { return "OpenTTD NoAI Developers Team"; }
+	function GetName()        { return "Rail"; }
+	function GetDescription() { return "An implementation of a rail pathfinder"; }
+	function GetVersion()     { return 1; }
+	function GetDate()        { return "2008-09-22"; }
+	function CreateInstance() { return "Rail"; }
+}
+
+RegisterLibrary(Rail());
diff --git a/bin/ai/library/pathfinder/rail/main.nut b/bin/ai/library/pathfinder/rail/main.nut
new file mode 100644
index 000000000..ad5a6664e
--- /dev/null
+++ b/bin/ai/library/pathfinder/rail/main.nut
@@ -0,0 +1,389 @@
+/* $Id$ */
+
+/**
+ * A Rail Pathfinder.
+ */
+class Rail
+{
+	_aystar_class = import("graph.aystar", "", 4);
+	_max_cost = null;              ///< The maximum cost for a route.
+	_cost_tile = null;             ///< The cost for a single tile.
+	_cost_diagonal_tile = null;    ///< The cost for a diagonal tile.
+	_cost_turn = null;             ///< The cost that is added to _cost_tile if the direction changes.
+	_cost_slope = null;            ///< The extra cost if a rail tile is sloped.
+	_cost_bridge_per_tile = null;  ///< The cost per tile of a new bridge, this is added to _cost_tile.
+	_cost_tunnel_per_tile = null;  ///< The cost per tile of a new tunnel, this is added to _cost_tile.
+	_cost_coast = null;            ///< The extra cost for a coast tile.
+	_pathfinder = null;            ///< A reference to the used AyStar object.
+	_max_bridge_length = null;     ///< The maximum length of a bridge that will be build.
+	_max_tunnel_length = null;     ///< The maximum length of a tunnel that will be build.
+
+	cost = null;                   ///< Used to change the costs.
+	_running = null;
+	_goals = null;
+
+	constructor()
+	{
+		this._max_cost = 10000000;
+		this._cost_tile = 100;
+		this._cost_diagonal_tile = 70;
+		this._cost_turn = 50;
+		this._cost_slope = 100;
+		this._cost_bridge_per_tile = 150;
+		this._cost_tunnel_per_tile = 120;
+		this._cost_coast = 20;
+		this._max_bridge_length = 6;
+		this._max_tunnel_length = 6;
+		this._pathfinder = this._aystar_class(this._Cost, this._Estimate, this._Neighbours, this._CheckDirection, this, this, this, this);
+
+		this.cost = this.Cost(this);
+		this._running = false;
+	}
+
+	/**
+	 * Initialize a path search between sources and goals.
+	 * @param sources The source tiles.
+	 * @param goals The target tiles.
+	 * @param ignored_tiles An array of tiles that cannot occur in the final path.
+	 * @see AyStar::InitializePath()
+	 */
+	function InitializePath(sources, goals, ignored_tiles = []) {
+		local nsources = [];
+
+		foreach (node in sources) {
+			local path = this._pathfinder.Path(null, node[1], 0xFF, this._Cost, this);
+			path = this._pathfinder.Path(path, node[0], 0xFF, this._Cost, this);
+			nsources.push(path);
+		}
+		this._goals = goals;
+		this._pathfinder.InitializePath(nsources, 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.
+	 * @see AyStar::FindPath()
+	 */
+	function FindPath(iterations);
+};
+
+class Rail.Cost
+{
+	_main = null;
+
+	function _set(idx, val)
+	{
+		if (this._main._running) throw("You are not allowed to change parameters of a running pathfinder.");
+
+		switch (idx) {
+			case "max_cost":          this._main._max_cost = val; break;
+			case "tile":              this._main._cost_tile = val; break;
+			case "diagonal_tile":     this._cost_diagonal_tile = val; break;
+			case "turn":              this._main._cost_turn = val; break;
+			case "slope":             this._main._cost_slope = val; break;
+			case "bridge_per_tile":   this._main._cost_bridge_per_tile = val; break;
+			case "tunnel_per_tile":   this._main._cost_tunnel_per_tile = val; break;
+			case "coast":             this._main._cost_coast = val; break;
+			case "max_bridge_length": this._main._max_bridge_length = val; break;
+			case "max_tunnel_length": this._main._max_tunnel_length = val; break;
+			default: throw("the index '" + idx + "' does not exist");
+		}
+
+		return val;
+	}
+
+	function _get(idx)
+	{
+		switch (idx) {
+			case "max_cost":          return this._main._max_cost;
+			case "tile":              return this._main._cost_tile;
+			case "diagonal_tile":     return this._cost_diagonal_tile;
+			case "turn":              return this._main._cost_turn;
+			case "slope":             return this._main._cost_slope;
+			case "bridge_per_tile":   return this._main._cost_bridge_per_tile;
+			case "tunnel_per_tile":   return this._main._cost_tunnel_per_tile;
+			case "coast":             return this._main._cost_coast;
+			case "max_bridge_length": return this._main._max_bridge_length;
+			case "max_tunnel_length": return this._main._max_tunnel_length;
+			default: throw("the index '" + idx + "' does not exist");
+		}
+	}
+
+	constructor(main)
+	{
+		this._main = main;
+	}
+};
+
+function Rail::FindPath(iterations)
+{
+	local test_mode = AITestMode();
+	local ret = this._pathfinder.FindPath(iterations);
+	this._running = (ret == false) ? true : false;
+	if (!this._running && ret != null) {
+		foreach (goal in this._goals) {
+			if (goal[0] == ret.GetTile()) {
+				return this._pathfinder.Path(ret, goal[1], 0, this._Cost, this);
+			}
+		}
+	}
+	return ret;
+}
+
+function Rail::_GetBridgeNumSlopes(end_a, end_b)
+{
+	local slopes = 0;
+	local direction = (end_b - end_a) / AIMap.DistanceManhattan(end_a, end_b);
+	local slope = AITile.GetSlope(end_a);
+	if (!((slope == AITile.SLOPE_NE && direction == 1) || (slope == AITile.SLOPE_SE && direction == -AIMap.GetMapSizeX()) ||
+		(slope == AITile.SLOPE_SW && direction == -1) || (slope == AITile.SLOPE_NW && direction == AIMap.GetMapSizeX()) ||
+		 slope == AITile.SLOPE_N || slope == AITile.SLOPE_E || slope == AITile.SLOPE_S || slope == AITile.SLOPE_W)) {
+		slopes++;
+	}
+
+	local slope = AITile.GetSlope(end_b);
+	direction = -direction;
+	if (!((slope == AITile.SLOPE_NE && direction == 1) || (slope == AITile.SLOPE_SE && direction == -AIMap.GetMapSizeX()) ||
+		(slope == AITile.SLOPE_SW && direction == -1) || (slope == AITile.SLOPE_NW && direction == AIMap.GetMapSizeX()) ||
+		 slope == AITile.SLOPE_N || slope == AITile.SLOPE_E || slope == AITile.SLOPE_S || slope == AITile.SLOPE_W)) {
+		slopes++;
+	}
+	return slopes;
+}
+
+function Rail::_nonzero(a, b)
+{
+	return a != 0 ? a : b;
+}
+
+function Rail::_Cost(path, new_tile, new_direction, self)
+{
+	/* path == null means this is the first node of a path, so the cost is 0. */
+	if (path == null) return 0;
+
+	local prev_tile = path.GetTile();
+
+	/* If the new tile is a bridge / tunnel tile, check whether we came from the other
+	 *  end of the bridge / tunnel or if we just entered the bridge / tunnel. */
+	if (AIBridge.IsBridgeTile(new_tile)) {
+		if (AIBridge.GetOtherBridgeEnd(new_tile) != prev_tile) {
+			local cost = path.GetCost() + self._cost_tile;
+			if (path.GetParent() != null && path.GetParent().GetTile() - prev_tile != prev_tile - new_tile) cost += self._cost_turn;
+			return cost;
+		}
+		return path.GetCost() + AIMap.DistanceManhattan(new_tile, prev_tile) * self._cost_tile + self._GetBridgeNumSlopes(new_tile, prev_tile) * self._cost_slope;
+	}
+	if (AITunnel.IsTunnelTile(new_tile)) {
+		if (AITunnel.GetOtherTunnelEnd(new_tile) != prev_tile) {
+			local cost = path.GetCost() + self._cost_tile;
+			if (path.GetParent() != null && path.GetParent().GetTile() - prev_tile != prev_tile - new_tile) cost += self._cost_turn;
+			return cost;
+		}
+		return path.GetCost() + AIMap.DistanceManhattan(new_tile, prev_tile) * self._cost_tile;
+	}
+
+	/* If the two tiles are more then 1 tile apart, the pathfinder wants a bridge or tunnel
+	 *  to be build. It isn't an existing bridge / tunnel, as that case is already handled. */
+	if (AIMap.DistanceManhattan(new_tile, prev_tile) > 1) {
+		/* Check if we should build a bridge or a tunnel. */
+		local cost = path.GetCost();
+		if (AITunnel.GetOtherTunnelEnd(new_tile) == prev_tile) {
+			cost += AIMap.DistanceManhattan(new_tile, prev_tile) * (self._cost_tile + self._cost_tunnel_per_tile);
+		} else {
+			cost += AIMap.DistanceManhattan(new_tile, prev_tile) * (self._cost_tile + self._cost_bridge_per_tile) + self._GetBridgeNumSlopes(new_tile, prev_tile) * self._cost_slope;
+		}
+		if (path.GetParent() != null && path.GetParent().GetParent() != null &&
+				path.GetParent().GetParent().GetTile() - path.GetParent().GetTile() != max(AIMap.GetTileX(prev_tile) - AIMap.GetTileX(new_tile), AIMap.GetTileY(prev_tile) - AIMap.GetTileY(new_tile)) / AIMap.DistanceManhattan(new_tile, prev_tile)) {
+			cost += self._cost_turn;
+		}
+		return cost;
+	}
+
+	/* Check for a turn. We do this by substracting the TileID of the current
+	 *  node from the TileID of the previous node and comparing that to the
+	 *  difference between the tile before the previous node and the node before
+	 *  that. */
+	local cost = self._cost_tile;
+	if (path.GetParent() != null && AIMap.DistanceManhattan(path.GetParent().GetTile(), prev_tile) == 1 && path.GetParent().GetTile() - prev_tile != prev_tile - new_tile) cost = self._cost_diagonal_tile;
+	if (path.GetParent() != null && path.GetParent().GetParent() != null &&
+			AIMap.DistanceManhattan(new_tile, path.GetParent().GetParent().GetTile()) == 3 &&
+			path.GetParent().GetParent().GetTile() - path.GetParent().GetTile() != prev_tile - new_tile) {
+		cost += self._cost_turn;
+	}
+
+	/* Check if the new tile is a coast tile. */
+	if (AITile.IsCoastTile(new_tile)) {
+		cost += self._cost_coast;
+	}
+
+	/* Check if the last tile was sloped. */
+	if (path.GetParent() != null && !AIBridge.IsBridgeTile(prev_tile) && !AITunnel.IsTunnelTile(prev_tile) &&
+			self._IsSlopedRail(path.GetParent().GetTile(), prev_tile, new_tile)) {
+		cost += self._cost_slope;
+	}
+
+	/* We don't use already existing rail, so the following code is unused. It
+	 *  assigns if no rail exists along the route. */
+	/*
+	if (path.GetParent() != null && !AIRail.AreTilesConnected(path.GetParent().GetTile(), prev_tile, new_tile)) {
+		cost += self._cost_no_existing_rail;
+	}
+	*/
+
+	return path.GetCost() + cost;
+}
+
+function Rail::_Estimate(cur_tile, cur_direction, goal_tiles, self)
+{
+	local min_cost = self._max_cost;
+	/* As estimate we multiply the lowest possible cost for a single tile with
+	 *  with the minimum number of tiles we need to traverse. */
+	foreach (tile in goal_tiles) {
+		local dx = abs(AIMap.GetTileX(cur_tile) - AIMap.GetTileX(tile[0]));
+		local dy = abs(AIMap.GetTileY(cur_tile) - AIMap.GetTileY(tile[0]));
+		min_cost = min(min_cost, min(dx, dy) * self._cost_diagonal_tile * 2 + (max(dx, dy) - min(dx, dy)) * self._cost_tile);
+	}
+	return min_cost;
+}
+
+function Rail::_Neighbours(path, cur_node, self)
+{
+	if (AITile.HasTransportType(cur_node, AITile.TRANSPORT_RAIL)) return [];
+	/* self._max_cost is the maximum path cost, if we go over it, the path isn't valid. */
+	if (path.GetCost() >= self._max_cost) return [];
+	local tiles = [];
+	local offsets = [AIMap.GetTileIndex(0, 1), AIMap.GetTileIndex(0, -1),
+	                 AIMap.GetTileIndex(1, 0), AIMap.GetTileIndex(-1, 0)];
+
+	/* Check if the current tile is part of a bridge or tunnel. */
+	if (AIBridge.IsBridgeTile(cur_node) || AITunnel.IsTunnelTile(cur_node)) {
+		/* We don't use existing rails, so neither existing bridges / tunnels. */
+	} else if (path.GetParent() != null && AIMap.DistanceManhattan(cur_node, path.GetParent().GetTile()) > 1) {
+		local other_end = path.GetParent().GetTile();
+		local next_tile = cur_node + (cur_node - other_end) / AIMap.DistanceManhattan(cur_node, other_end);
+		foreach (offset in offsets) {
+			if (AIRail.BuildRail(cur_node, next_tile, next_tile + offset)) {
+				tiles.push([next_tile, self._GetDirection(other_end, cur_node, next_tile, true)]);
+			}
+		}
+	} else {
+		/* Check all tiles adjacent to the current tile. */
+		foreach (offset in offsets) {
+			local next_tile = cur_node + offset;
+			/* Don't turn back */
+			if (path.GetParent() != null && next_tile == path.GetParent().GetTile()) continue;
+			/* Disallow 90 degree turns */
+			if (path.GetParent() != null && path.GetParent().GetParent() != null &&
+				next_tile - cur_node == path.GetParent().GetParent().GetTile() - path.GetParent().GetTile()) continue;
+			/* We add them to the to the neighbours-list if we can build a rail to
+			 *  them and no rail exists there. */
+			if ((path.GetParent() == null || AIRail.BuildRail(path.GetParent().GetTile(), cur_node, next_tile))) {
+				if (path.GetParent() != null) {
+					tiles.push([next_tile, self._GetDirection(path.GetParent().GetTile(), cur_node, next_tile, false)]);
+				} else {
+					tiles.push([next_tile, self._GetDirection(null, cur_node, next_tile, false)]);
+				}
+			}
+		}
+		if (path.GetParent() != null && path.GetParent().GetParent() != null) {
+			local bridges = self._GetTunnelsBridges(path.GetParent().GetTile(), cur_node, self._GetDirection(path.GetParent().GetParent().GetTile(), path.GetParent().GetTile(), cur_node, true));
+			foreach (tile in bridges) {
+				tiles.push(tile);
+			}
+		}
+	}
+	return tiles;
+}
+
+function Rail::_CheckDirection(tile, existing_direction, new_direction, self)
+{
+	return false;
+}
+
+function Rail::_dir(from, to)
+{
+	if (from - to == 1) return 0;
+	if (from - to == -1) return 1;
+	if (from - to == AIMap.GetMapSizeX()) return 2;
+	if (from - to == -AIMap.GetMapSizeX()) return 3;
+	throw("Shouldn't come here in _dir");
+}
+
+function Rail::_GetDirection(pre_from, from, to, is_bridge)
+{
+	if (is_bridge) {
+		if (from - to == 1) return 1;
+		if (from - to == -1) return 2;
+		if (from - to == AIMap.GetMapSizeX()) return 4;
+		if (from - to == -AIMap.GetMapSizeX()) return 8;
+	}
+	return 1 << (4 + (pre_from == null ? 0 : 4 * this._dir(pre_from, from)) + this._dir(from, to));
+}
+
+/**
+ * Get a list of all bridges and tunnels that can be build from the
+ *  current tile. Bridges will only be build starting on non-flat tiles
+ *  for performance reasons. Tunnels will only be build if no terraforming
+ *  is needed on both ends.
+ */
+function Rail::_GetTunnelsBridges(last_node, cur_node, bridge_dir)
+{
+	local slope = AITile.GetSlope(cur_node);
+	if (slope == AITile.SLOPE_FLAT && AITile.IsBuildable(cur_node + (cur_node - last_node))) return [];
+	local tiles = [];
+
+	for (local i = 2; i < this._max_bridge_length; i++) {
+		local bridge_list = AIBridgeList_Length(i + 1);
+		local target = cur_node + i * (cur_node - last_node);
+		if (!bridge_list.IsEmpty() && AIBridge.BuildBridge(AIVehicle.VEHICLE_RAIL, bridge_list.Begin(), cur_node, target)) {
+			tiles.push([target, bridge_dir]);
+		}
+	}
+
+	if (slope != AITile.SLOPE_SW && slope != AITile.SLOPE_NW && slope != AITile.SLOPE_SE && slope != AITile.SLOPE_NE) return tiles;
+	local other_tunnel_end = AITunnel.GetOtherTunnelEnd(cur_node);
+	if (!AIMap.IsValidTile(other_tunnel_end)) return tiles;
+
+	local tunnel_length = AIMap.DistanceManhattan(cur_node, other_tunnel_end);
+	local prev_tile = cur_node + (cur_node - other_tunnel_end) / tunnel_length;
+	if (AITunnel.GetOtherTunnelEnd(other_tunnel_end) == cur_node && tunnel_length >= 2 &&
+			prev_tile == last_node && tunnel_length < _max_tunnel_length && AITunnel.BuildTunnel(AIVehicle.VEHICLE_RAIL, cur_node)) {
+		tiles.push([other_tunnel_end, bridge_dir]);
+	}
+	return tiles;
+}
+
+function Rail::_IsSlopedRail(start, middle, end)
+{
+	local NW = 0; // Set to true if we want to build a rail to / from the north-west
+	local NE = 0; // Set to true if we want to build a rail to / from the north-east
+	local SW = 0; // Set to true if we want to build a rail to / from the south-west
+	local SE = 0; // Set to true if we want to build a rail to / from the south-east
+
+	if (middle - AIMap.GetMapSizeX() == start || middle - AIMap.GetMapSizeX() == end) NW = 1;
+	if (middle - 1 == start || middle - 1 == end) NE = 1;
+	if (middle + AIMap.GetMapSizeX() == start || middle + AIMap.GetMapSizeX() == end) SE = 1;
+	if (middle + 1 == start || middle + 1 == end) SW = 1;
+
+	/* If there is a turn in the current tile, it can't be sloped. */
+	if ((NW || SE) && (NE || SW)) return false;
+
+	local slope = AITile.GetSlope(middle);
+	/* A rail on a steep slope is always sloped. */
+	if (AITile.IsSteepSlope(slope)) return true;
+
+	/* If only one corner is raised, the rail is sloped. */
+	if (slope == AITile.SLOPE_N || slope == AITile.SLOPE_W) return true;
+	if (slope == AITile.SLOPE_S || slope == AITile.SLOPE_E) return true;
+
+	if (NW && (slope == AITile.SLOPE_NW || slope == AITile.SLOPE_SE)) return true;
+	if (NE && (slope == AITile.SLOPE_NE || slope == AITile.SLOPE_SW)) return true;
+
+	return false;
+}
diff --git a/bin/ai/library/pathfinder/road/library.nut b/bin/ai/library/pathfinder/road/library.nut
new file mode 100644
index 000000000..b3c6f1f54
--- /dev/null
+++ b/bin/ai/library/pathfinder/road/library.nut
@@ -0,0 +1,12 @@
+/* $Id$ */
+
+class Road extends AILibrary {
+	function GetAuthor()      { return "OpenTTD NoAI Developers Team"; }
+	function GetName()        { return "Road"; }
+	function GetDescription() { return "An implementation of a road pathfinder"; }
+	function GetVersion()     { return 3; }
+	function GetDate()        { return "2008-06-18"; }
+	function CreateInstance() { return "Road"; }
+}
+
+RegisterLibrary(Road());
diff --git a/bin/ai/library/pathfinder/road/main.nut b/bin/ai/library/pathfinder/road/main.nut
new file mode 100644
index 000000000..b33722369
--- /dev/null
+++ b/bin/ai/library/pathfinder/road/main.nut
@@ -0,0 +1,363 @@
+/* $Id$ */
+
+/**
+ * A Road Pathfinder.
+ *  This road pathfinder tries to find a buildable / existing route for
+ *  road vehicles. You can changes the costs below using for example
+ *  roadpf.cost.turn = 30. Note that it's not allowed to change the cost
+ *  between consecutive calls to FindPath. You can change the cost before
+ *  the first call to FindPath and after FindPath has returned an actual
+ *  route. To use only existing roads, set cost.no_existing_road to
+ *  cost.max_cost.
+ */
+class Road
+{
+	_aystar_class = import("graph.aystar", "", 4);
+	_max_cost = null;              ///< The maximum cost for a route.
+	_cost_tile = null;             ///< The cost for a single tile.
+	_cost_no_existing_road = null; ///< The cost that is added to _cost_tile if no road exists yet.
+	_cost_turn = null;             ///< The cost that is added to _cost_tile if the direction changes.
+	_cost_slope = null;            ///< The extra cost if a road tile is sloped.
+	_cost_bridge_per_tile = null;  ///< The cost per tile of a new bridge, this is added to _cost_tile.
+	_cost_tunnel_per_tile = null;  ///< The cost per tile of a new tunnel, this is added to _cost_tile.
+	_cost_coast = null;            ///< The extra cost for a coast tile.
+	_pathfinder = null;            ///< A reference to the used AyStar object.
+	_max_bridge_length = null;     ///< The maximum length of a bridge that will be build.
+	_max_tunnel_length = null;     ///< The maximum length of a tunnel that will be build.
+
+	cost = null;                   ///< Used to change the costs.
+	_running = null;
+
+	constructor()
+	{
+		this._max_cost = 10000000;
+		this._cost_tile = 100;
+		this._cost_no_existing_road = 40;
+		this._cost_turn = 100;
+		this._cost_slope = 200;
+		this._cost_bridge_per_tile = 150;
+		this._cost_tunnel_per_tile = 120;
+		this._cost_coast = 20;
+		this._max_bridge_length = 10;
+		this._max_tunnel_length = 20;
+		this._pathfinder = this._aystar_class(this._Cost, this._Estimate, this._Neighbours, this._CheckDirection, this, this, this, this);
+
+		this.cost = this.Cost(this);
+		this._running = false;
+	}
+
+	/**
+	 * Initialize a path search between sources and goals.
+	 * @param sources The source tiles.
+	 * @param goals The target tiles.
+	 * @see AyStar::InitializePath()
+	 */
+	function InitializePath(sources, goals) {
+		local nsources = [];
+
+		foreach (node in sources) {
+			nsources.push([node, 0xFF]);
+		}
+		this._pathfinder.InitializePath(nsources, 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.
+	 * @see AyStar::FindPath()
+	 */
+	function FindPath(iterations);
+};
+
+class Road.Cost
+{
+	_main = null;
+
+	function _set(idx, val)
+	{
+		if (this._main._running) throw("You are not allowed to change parameters of a running pathfinder.");
+
+		switch (idx) {
+			case "max_cost":          this._main._max_cost = val; break;
+			case "tile":              this._main._cost_tile = val; break;
+			case "no_existing_road":  this._main._cost_no_existing_road = val; break;
+			case "turn":              this._main._cost_turn = val; break;
+			case "slope":             this._main._cost_slope = val; break;
+			case "bridge_per_tile":   this._main._cost_bridge_per_tile = val; break;
+			case "tunnel_per_tile":   this._main._cost_tunnel_per_tile = val; break;
+			case "coast":             this._main._cost_coast = val; break;
+			case "max_bridge_length": this._main._max_bridge_length = val; break;
+			case "max_tunnel_length": this._main._max_tunnel_length = val; break;
+			default: throw("the index '" + idx + "' does not exist");
+		}
+
+		return val;
+	}
+
+	function _get(idx)
+	{
+		switch (idx) {
+			case "max_cost":          return this._main._max_cost;
+			case "tile":              return this._main._cost_tile;
+			case "no_existing_road":  return this._main._cost_no_existing_road;
+			case "turn":              return this._main._cost_turn;
+			case "slope":             return this._main._cost_slope;
+			case "bridge_per_tile":   return this._main._cost_bridge_per_tile;
+			case "tunnel_per_tile":   return this._main._cost_tunnel_per_tile;
+			case "coast":             return this._main._cost_coast;
+			case "max_bridge_length": return this._main._max_bridge_length;
+			case "max_tunnel_length": return this._main._max_tunnel_length;
+			default: throw("the index '" + idx + "' does not exist");
+		}
+	}
+
+	constructor(main)
+	{
+		this._main = main;
+	}
+};
+
+function Road::FindPath(iterations)
+{
+	local test_mode = AITestMode();
+	local ret = this._pathfinder.FindPath(iterations);
+	this._running = (ret == false) ? true : false;
+	return ret;
+}
+
+function Road::_GetBridgeNumSlopes(end_a, end_b)
+{
+	local slopes = 0;
+	local direction = (end_b - end_a) / AIMap.DistanceManhattan(end_a, end_b);
+	local slope = AITile.GetSlope(end_a);
+	if (!((slope == AITile.SLOPE_NE && direction == 1) || (slope == AITile.SLOPE_SE && direction == -AIMap.GetMapSizeX()) ||
+		(slope == AITile.SLOPE_SW && direction == -1) || (slope == AITile.SLOPE_NW && direction == AIMap.GetMapSizeX()) ||
+		 slope == AITile.SLOPE_N || slope == AITile.SLOPE_E || slope == AITile.SLOPE_S || slope == AITile.SLOPE_W)) {
+		slopes++;
+	}
+
+	local slope = AITile.GetSlope(end_b);
+	direction = -direction;
+	if (!((slope == AITile.SLOPE_NE && direction == 1) || (slope == AITile.SLOPE_SE && direction == -AIMap.GetMapSizeX()) ||
+		(slope == AITile.SLOPE_SW && direction == -1) || (slope == AITile.SLOPE_NW && direction == AIMap.GetMapSizeX()) ||
+		 slope == AITile.SLOPE_N || slope == AITile.SLOPE_E || slope == AITile.SLOPE_S || slope == AITile.SLOPE_W)) {
+		slopes++;
+	}
+	return slopes;
+}
+
+function Road::_Cost(path, new_tile, new_direction, self)
+{
+	/* path == null means this is the first node of a path, so the cost is 0. */
+	if (path == null) return 0;
+
+	local prev_tile = path.GetTile();
+
+	/* If the new tile is a bridge / tunnel tile, check whether we came from the other
+	 * end of the bridge / tunnel or if we just entered the bridge / tunnel. */
+	if (AIBridge.IsBridgeTile(new_tile)) {
+		if (AIBridge.GetOtherBridgeEnd(new_tile) != prev_tile) return path.GetCost() + self._cost_tile;
+		return path.GetCost() + AIMap.DistanceManhattan(new_tile, prev_tile) * self._cost_tile + self._GetBridgeNumSlopes(new_tile, prev_tile) * self._cost_slope;
+	}
+	if (AITunnel.IsTunnelTile(new_tile)) {
+		if (AITunnel.GetOtherTunnelEnd(new_tile) != prev_tile) return path.GetCost() + self._cost_tile;
+		return path.GetCost() + AIMap.DistanceManhattan(new_tile, prev_tile) * self._cost_tile;
+	}
+
+	/* If the two tiles are more then 1 tile apart, the pathfinder wants a bridge or tunnel
+	 * to be build. It isn't an existing bridge / tunnel, as that case is already handled. */
+	if (AIMap.DistanceManhattan(new_tile, prev_tile) > 1) {
+		/* Check if we should build a bridge or a tunnel. */
+		if (AITunnel.GetOtherTunnelEnd(new_tile) == prev_tile) {
+			return path.GetCost() + AIMap.DistanceManhattan(new_tile, prev_tile) * (self._cost_tile + self._cost_tunnel_per_tile);
+		} else {
+			return path.GetCost() + AIMap.DistanceManhattan(new_tile, prev_tile) * (self._cost_tile + self._cost_bridge_per_tile) + self._GetBridgeNumSlopes(new_tile, prev_tile) * self._cost_slope;
+		}
+	}
+
+	/* Check for a turn. We do this by substracting the TileID of the current node from
+	 * the TileID of the previous node and comparing that to the difference between the
+	 * previous node and the node before that. */
+	local cost = self._cost_tile;
+	if (path.GetParent() != null && (prev_tile - path.GetParent().GetTile()) != (new_tile - prev_tile) &&
+		AIMap.DistanceManhattan(path.GetParent().GetTile(), prev_tile) == 1) {
+		cost += self._cost_turn;
+	}
+
+	/* Check if the new tile is a coast tile. */
+	if (AITile.IsCoastTile(new_tile)) {
+		cost += self._cost_coast;
+	}
+
+	/* Check if the last tile was sloped. */
+	if (path.GetParent() != null && !AIBridge.IsBridgeTile(prev_tile) && !AITunnel.IsTunnelTile(prev_tile) &&
+	    self._IsSlopedRoad(path.GetParent().GetTile(), prev_tile, new_tile)) {
+		cost += self._cost_slope;
+	}
+
+	if (!AIRoad.AreRoadTilesConnected(prev_tile, new_tile)) {
+		cost += self._cost_no_existing_road;
+	}
+
+	return path.GetCost() + cost;
+}
+
+function Road::_Estimate(cur_tile, cur_direction, goal_tiles, self)
+{
+	local min_cost = self._max_cost;
+	/* As estimate we multiply the lowest possible cost for a single tile with
+	 * with the minimum number of tiles we need to traverse. */
+	foreach (tile in goal_tiles) {
+		min_cost = min(AIMap.DistanceManhattan(cur_tile, tile) * self._cost_tile, min_cost);
+	}
+	return min_cost;
+}
+
+function Road::_Neighbours(path, cur_node, self)
+{
+	/* self._max_cost is the maximum path cost, if we go over it, the path isn't valid. */
+	if (path.GetCost() >= self._max_cost) return [];
+	local tiles = [];
+
+	/* Check if the current tile is part of a bridge or tunnel. */
+	if ((AIBridge.IsBridgeTile(cur_node) || AITunnel.IsTunnelTile(cur_node)) &&
+	     AITile.HasTransportType(cur_node, AITile.TRANSPORT_ROAD)) {
+		local other_end = AIBridge.IsBridgeTile(cur_node) ? AIBridge.GetOtherBridgeEnd(cur_node) : AITunnel.GetOtherTunnelEnd(cur_node);
+		local next_tile = cur_node + (cur_node - other_end) / AIMap.DistanceManhattan(cur_node, other_end);
+		if (AIRoad.AreRoadTilesConnected(cur_node, next_tile) || AITile.IsBuildable(next_tile) || AIRoad.IsRoadTile(next_tile)) {
+			tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
+		}
+		/* The other end of the bridge / tunnel is a neighbour. */
+		tiles.push([other_end, self._GetDirection(next_tile, cur_node, true) << 4]);
+	} else if (path.GetParent() != null && AIMap.DistanceManhattan(cur_node, path.GetParent().GetTile()) > 1) {
+		local other_end = path.GetParent().GetTile();
+		local next_tile = cur_node + (cur_node - other_end) / AIMap.DistanceManhattan(cur_node, other_end);
+		if (AIRoad.AreRoadTilesConnected(cur_node, next_tile) || AIRoad.BuildRoad(cur_node, next_tile)) {
+			tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
+		}
+	} else {
+		local offsets = [AIMap.GetTileIndex(0, 1), AIMap.GetTileIndex(0, -1),
+		                 AIMap.GetTileIndex(1, 0), AIMap.GetTileIndex(-1, 0)];
+		/* Check all tiles adjacent to the current tile. */
+		foreach (offset in offsets) {
+			local next_tile = cur_node + offset;
+			/* We add them to the to the neighbours-list if one of the following applies:
+			 * 1) There already is a connections between the current tile and the next tile.
+			 * 2) We can build a road to the next tile.
+			 * 3) The next tile is the entrance of a tunnel / bridge in the correct direction. */
+			if (AIRoad.AreRoadTilesConnected(cur_node, next_tile)) {
+				tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
+			} else if ((AITile.IsBuildable(next_tile) || AIRoad.IsRoadTile(next_tile)) &&
+					(path.GetParent() == null || AIRoad.CanBuildConnectedRoadPartsHere(cur_node, path.GetParent().GetTile(), next_tile)) &&
+					AIRoad.BuildRoad(cur_node, next_tile)) {
+				tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
+			} else if (self._CheckTunnelBridge(cur_node, next_tile)) {
+				tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
+			}
+		}
+		if (path.GetParent() != null) {
+			local bridges = self._GetTunnelsBridges(path.GetParent().GetTile(), cur_node, self._GetDirection(path.GetParent().GetTile(), cur_node, true) << 4);
+			foreach (tile in bridges) {
+				tiles.push(tile);
+			}
+		}
+	}
+	return tiles;
+}
+
+function Road::_CheckDirection(tile, existing_direction, new_direction, self)
+{
+	return false;
+}
+
+function Road::_GetDirection(from, to, is_bridge)
+{
+	if (!is_bridge && AITile.GetSlope(to) == AITile.SLOPE_FLAT) return 0xFF;
+	if (from - to == 1) return 1;
+	if (from - to == -1) return 2;
+	if (from - to == AIMap.GetMapSizeX()) return 4;
+	if (from - to == -AIMap.GetMapSizeX()) return 8;
+}
+
+/**
+ * Get a list of all bridges and tunnels that can be build from the
+ * current tile. Bridges will only be build starting on non-flat tiles
+ * for performance reasons. Tunnels will only be build if no terraforming
+ * is needed on both ends.
+ */
+function Road::_GetTunnelsBridges(last_node, cur_node, bridge_dir)
+{
+	local slope = AITile.GetSlope(cur_node);
+	if (slope == AITile.SLOPE_FLAT) return [];
+	local tiles = [];
+
+	for (local i = 2; i < this._max_bridge_length; i++) {
+		local bridge_list = AIBridgeList_Length(i + 1);
+		local target = cur_node + i * (cur_node - last_node);
+		if (!bridge_list.IsEmpty() && AIBridge.BuildBridge(AIVehicle.VEHICLE_ROAD, bridge_list.Begin(), cur_node, target)) {
+			tiles.push([target, bridge_dir]);
+		}
+	}
+
+	if (slope != AITile.SLOPE_SW && slope != AITile.SLOPE_NW && slope != AITile.SLOPE_SE && slope != AITile.SLOPE_NE) return tiles;
+	local other_tunnel_end = AITunnel.GetOtherTunnelEnd(cur_node);
+	if (!AIMap.IsValidTile(other_tunnel_end)) return tiles;
+
+	local tunnel_length = AIMap.DistanceManhattan(cur_node, other_tunnel_end);
+	local prev_tile = cur_node + (cur_node - other_tunnel_end) / tunnel_length;
+	if (AITunnel.GetOtherTunnelEnd(other_tunnel_end) == cur_node && tunnel_length >= 2 &&
+			prev_tile == last_node && tunnel_length < _max_tunnel_length && AITunnel.BuildTunnel(AIVehicle.VEHICLE_ROAD, cur_node)) {
+		tiles.push([other_tunnel_end, bridge_dir]);
+	}
+	return tiles;
+}
+
+function Road::_IsSlopedRoad(start, middle, end)
+{
+	local NW = 0; //Set to true if we want to build a road to / from the north-west
+	local NE = 0; //Set to true if we want to build a road to / from the north-east
+	local SW = 0; //Set to true if we want to build a road to / from the south-west
+	local SE = 0; //Set to true if we want to build a road to / from the south-east
+
+	if (middle - AIMap.GetMapSizeX() == start || middle - AIMap.GetMapSizeX() == end) NW = 1;
+	if (middle - 1 == start || middle - 1 == end) NE = 1;
+	if (middle + AIMap.GetMapSizeX() == start || middle + AIMap.GetMapSizeX() == end) SE = 1;
+	if (middle + 1 == start || middle + 1 == end) SW = 1;
+
+	/* If there is a turn in the current tile, it can't be sloped. */
+	if ((NW || SE) && (NE || SW)) return false;
+
+	local slope = AITile.GetSlope(middle);
+	/* A road on a steep slope is always sloped. */
+	if (AITile.IsSteepSlope(slope)) return true;
+
+	/* If only one corner is raised, the road is sloped. */
+	if (slope == AITile.SLOPE_N || slope == AITile.SLOPE_W) return true;
+	if (slope == AITile.SLOPE_S || slope == AITile.SLOPE_E) return true;
+
+	if (NW && (slope == AITile.SLOPE_NW || slope == AITile.SLOPE_SE)) return true;
+	if (NE && (slope == AITile.SLOPE_NE || slope == AITile.SLOPE_SW)) return true;
+
+	return false;
+}
+
+function Road::_CheckTunnelBridge(current_tile, new_tile)
+{
+	if (!AIBridge.IsBridgeTile(new_tile) && !AITunnel.IsTunnelTile(new_tile)) return false;
+	local dir = new_tile - current_tile;
+	local other_end = AIBridge.IsBridgeTile(new_tile) ? AIBridge.GetOtherBridgeEnd(new_tile) : AITunnel.GetOtherTunnelEnd(new_tile);
+	local dir2 = other_end - new_tile;
+	if ((dir < 0 && dir2 > 0) || (dir > 0 && dir2 < 0)) return false;
+	dir = abs(dir);
+	dir2 = abs(dir2);
+	if ((dir >= AIMap.GetMapSizeX() && dir2 < AIMap.GetMapSizeX()) ||
+	    (dir < AIMap.GetMapSizeX() && dir2 >= AIMap.GetMapSizeX())) return false;
+
+	return true;
+}
diff --git a/bin/ai/library/queue/binary_heap/library.nut b/bin/ai/library/queue/binary_heap/library.nut
new file mode 100644
index 000000000..3a96617a9
--- /dev/null
+++ b/bin/ai/library/queue/binary_heap/library.nut
@@ -0,0 +1,12 @@
+/* $Id$ */
+
+class BinaryHeap extends AILibrary {
+	function GetAuthor()      { return "OpenTTD NoAI Developers Team"; }
+	function GetName()        { return "Binary Heap"; }
+	function GetDescription() { return "An implementation of a Binary Heap"; }
+	function GetVersion()     { return 1; }
+	function GetDate()        { return "2008-06-10"; }
+	function CreateInstance() { return "BinaryHeap"; }
+}
+
+RegisterLibrary(BinaryHeap());
diff --git a/bin/ai/library/queue/binary_heap/main.nut b/bin/ai/library/queue/binary_heap/main.nut
new file mode 100644
index 000000000..1bbb3914f
--- /dev/null
+++ b/bin/ai/library/queue/binary_heap/main.nut
@@ -0,0 +1,131 @@
+/* $Id$ */
+
+/**
+ * Binary Heap.
+ *  Peek and Pop always return the current lowest value in the list.
+ *  Sort is done on insertion and on deletion.
+ */
+class BinaryHeap
+{
+	_queue = null;
+	_count = 0;
+
+	constructor()
+	{
+		_queue = [];
+	}
+
+	/**
+	 * Insert a new entry in the list.
+	 *  The complexity of this operation is O(ln n).
+	 * @param item The item to add to the list.
+	 * @param priority The priority this item has.
+	 */
+	function Insert(item, priority);
+
+	/**
+	 * Pop the first entry of the list.
+	 *  This is always the item with the lowest priority.
+	 *  The complexity of this operation is O(ln n).
+	 * @return The item of the entry with the lowest priority.
+	 */
+	function Pop();
+
+	/**
+	 * Peek the first entry of the list.
+	 *  This is always the item with the lowest priority.
+	 *  The complexity of this operation is O(1).
+	 * @return The item of the entry with the lowest priority.
+	 */
+	function Peek();
+
+	/**
+	 * Get the amount of current items in the list.
+	 *  The complexity of this operation is O(1).
+	 * @return The amount of items currently in the list.
+	 */
+	function Count();
+
+	/**
+	 * Check if an item exists in the list.
+	 *  The complexity of this operation is O(n).
+	 * @param item The item to check for.
+	 * @return True if the item is already in the list.
+	 */
+	function Exists(item);
+};
+
+function BinaryHeap::Insert(item, priority)
+{
+	/* Append dummy entry */
+	_queue.append(0);
+	_count++;
+
+	local hole;
+	/* Find the point of insertion */
+	for (hole = _count - 1; hole > 0 && priority <= _queue[hole / 2][1]; hole /= 2)
+		_queue[hole] = _queue[hole / 2];
+	/* Insert new pair */
+	_queue[hole] = [item, priority];
+
+	return true;
+}
+
+function BinaryHeap::Pop()
+{
+	if (_count == 0) return null;
+
+	local node = _queue[0];
+	/* Remove the item from the list by putting the last value on top */
+	_queue[0] = _queue[_count - 1];
+	_queue.pop();
+	_count--;
+	/* Bubble down the last value to correct the tree again */
+	_BubbleDown();
+
+	return node[0];
+}
+
+function BinaryHeap::Peek()
+{
+	if (_count == 0) return null;
+
+	return _queue[0][0];
+}
+
+function BinaryHeap::Count()
+{
+	return _count;
+}
+
+function BinaryHeap::Exists(item)
+{
+	/* Brute-force find the item (there is no faster way, as we don't have the priority number) */
+	foreach (node in _queue) {
+		if (node[0] == item) return true;
+	}
+
+	return false;
+}
+
+
+
+function BinaryHeap::_BubbleDown()
+{
+	if (_count == 0) return;
+
+	local hole = 1;
+	local tmp = _queue[0];
+
+	/* Start switching parent and child until the tree is restored */
+	while (hole * 2 < _count + 1) {
+		local child = hole * 2;
+		if (child != _count && _queue[child][1] <= _queue[child - 1][1]) child++;
+		if (_queue[child - 1][1] > tmp[1]) break;
+
+		_queue[hole - 1] = _queue[child - 1];
+		hole = child;
+	}
+	/* The top value is now at his new place */
+	_queue[hole - 1] = tmp;
+}
diff --git a/bin/ai/library/queue/fibonacci_heap/library.nut b/bin/ai/library/queue/fibonacci_heap/library.nut
new file mode 100644
index 000000000..1ea7260e0
--- /dev/null
+++ b/bin/ai/library/queue/fibonacci_heap/library.nut
@@ -0,0 +1,12 @@
+/* $Id$ */
+
+class FibonacciHeap extends AILibrary {
+	function GetAuthor()      { return "OpenTTD NoAI Developers Team"; }
+	function GetName()        { return "Fibonacci Heap"; }
+	function GetDescription() { return "An implementation of a Fibonacci Heap"; }
+	function GetVersion()     { return 1; }
+	function GetDate()        { return "2008-08-22"; }
+	function CreateInstance() { return "FibonacciHeap"; }
+}
+
+RegisterLibrary(FibonacciHeap());
diff --git a/bin/ai/library/queue/fibonacci_heap/main.nut b/bin/ai/library/queue/fibonacci_heap/main.nut
new file mode 100644
index 000000000..7c6b3ece2
--- /dev/null
+++ b/bin/ai/library/queue/fibonacci_heap/main.nut
@@ -0,0 +1,204 @@
+/* $Id$ */
+
+/**
+ * Fibonacci heap.
+ *  This heap is heavily optimized for the Insert and Pop functions.
+ *  Peek and Pop always return the current lowest value in the list.
+ *  Insert is implemented as a lazy insert, as it will simply add the new
+ *  node to the root list. Sort is done on every Pop operation.
+ */
+class FibonacciHeap {
+	_min = null;
+	_min_index = 0;
+	_min_priority = 0;
+	_count = 0;
+	_root_list = null;
+
+	/**
+	 * Create a new fibonacci heap.
+	 * http://en.wikipedia.org/wiki/Fibonacci_heap
+	 */
+	constructor() {
+		_count = 0;
+		_min = Node();
+		_min.priority = 0x7FFFFFFF;
+		_min_index = 0;
+		_min_priority = 0x7FFFFFFF;
+		_root_list = [];
+	}
+
+	/**
+	 * Insert a new entry in the heap.
+	 *  The complexity of this operation is O(1).
+	 * @param item The item to add to the list.
+	 * @param priority The priority this item has.
+	 */
+	function Insert(item, priority);
+
+	/**
+	 * Pop the first entry of the list.
+	 *  This is always the item with the lowest priority.
+	 *  The complexity of this operation is O(ln n).
+	 * @return The item of the entry with the lowest priority.
+	 */
+	function Pop();
+
+	/**
+	 * Peek the first entry of the list.
+	 *  This is always the item with the lowest priority.
+	 *  The complexity of this operation is O(1).
+	 * @return The item of the entry with the lowest priority.
+	 */
+	function Peek();
+
+	/**
+	 * Get the amount of current items in the list.
+	 *  The complexity of this operation is O(1).
+	 * @return The amount of items currently in the list.
+	 */
+	function Count();
+
+	/**
+	 * Check if an item exists in the list.
+	 *  The complexity of this operation is O(n).
+	 * @param item The item to check for.
+	 * @return True if the item is already in the list.
+	 */
+	function Exists(item);
+};
+
+function FibonacciHeap::Insert(item, priority) {
+	/* Create a new node instance to add to the heap. */
+	local node = Node();
+	/* Changing params is faster than using constructor values */
+	node.item = item;
+	node.priority = priority;
+
+	/* Update the reference to the minimum node if this node has a
+	 * smaller priority. */
+	if (_min_priority > priority) {
+		_min = node;
+		_min_index = _root_list.len();
+		_min_priority = priority;
+	}
+
+	_root_list.append(node);
+	_count++;
+}
+
+function FibonacciHeap::Pop() {
+
+	if (_count == 0) return null;
+
+	/* Bring variables from the class scope to this scope explicitly to
+	 * optimize variable lookups by Squirrel. */
+	local z = _min;
+	local tmp_root_list = _root_list;
+
+	/* If there are any children, bring them all to the root level. */
+	tmp_root_list.extend(z.child);
+
+	/* Remove the minimum node from the rootList. */
+	tmp_root_list.remove(_min_index);
+	local root_cache = {};
+
+	/* Now we decrease the number of nodes on the root level by
+	 * merging nodes which have the same degree. The node with
+	 * the lowest priority value will become the parent. */
+	foreach(x in tmp_root_list) {
+		local y;
+
+		/* See if we encountered a node with the same degree already. */
+		while (y = root_cache.rawdelete(x.degree)) {
+			/* Check the priorities. */
+			if (x.priority > y.priority) {
+				local tmp = x;
+				x = y;
+				y = tmp;
+			}
+
+			/* Make y a child of x. */
+			x.child.append(y);
+			x.degree++;
+		}
+
+		root_cache[x.degree] <- x;
+	}
+
+	/* The root_cache contains all the nodes which will form the
+	 *  new rootList. We reset the priority to the maximum number
+	 *  for a 32 signed integer to find a new minumum. */
+	tmp_root_list.resize(root_cache.len());
+	local i = 0;
+	local tmp_min_priority = 0x7FFFFFFF;
+
+	/* Now we need to find the new minimum among the root nodes. */
+	foreach (val in root_cache) {
+		if (val.priority < tmp_min_priority) {
+			_min = val;
+			_min_index = i;
+			tmp_min_priority = val.priority;
+		}
+
+		tmp_root_list[i++] = val;
+	}
+
+	/* Update global variables. */
+	_min_priority = tmp_min_priority;
+
+	_count--;
+	return z.item;
+}
+
+function FibonacciHeap::Peek() {
+	if (_count == 0) return null;
+	return _min.item;
+}
+
+function FibonacciHeap::Count() {
+	return _count;
+}
+
+function FibonacciHeap::Exists(item) {
+	return ExistsIn(_root_list, item);
+}
+
+/**
+ * Auxilary function to search through the whole heap.
+ * @param list The list of nodes to look through.
+ * @param item The item to search for.
+ * @return True if the item is found, false otherwise.
+ */
+function FibonacciHeap::ExistsIn(list, item) {
+
+	foreach (val in list) {
+		if (val.item == item) {
+			return true;
+		}
+
+		foreach (c in val.child) {
+			if (ExistsIn(c, item)) {
+				return true;
+			}
+		}
+	}
+
+	/* No luck, item doesn't exists in the tree rooted under list. */
+	return false;
+}
+
+/**
+ * Basic class the fibonacci heap is composed of.
+ */
+class FibonacciHeap.Node {
+	degree = null;
+	child = null;
+
+	item = null;
+	priority = null;
+
+	constructor() {
+		child = [];
+		degree = 0;
+	}
+};
diff --git a/bin/ai/library/queue/priority_queue/library.nut b/bin/ai/library/queue/priority_queue/library.nut
new file mode 100644
index 000000000..a8c615ed1
--- /dev/null
+++ b/bin/ai/library/queue/priority_queue/library.nut
@@ -0,0 +1,12 @@
+/* $Id$ */
+
+class PriorityQueue extends AILibrary {
+	function GetAuthor()      { return "OpenTTD NoAI Developers Team"; }
+	function GetName()        { return "Priority Queue"; }
+	function GetDescription() { return "An implementation of a Priority Queue"; }
+	function GetVersion()     { return 2; }
+	function GetDate()        { return "2008-06-10"; }
+	function CreateInstance() { return "PriorityQueue"; }
+}
+
+RegisterLibrary(PriorityQueue());
diff --git a/bin/ai/library/queue/priority_queue/main.nut b/bin/ai/library/queue/priority_queue/main.nut
new file mode 100644
index 000000000..bafc93ac5
--- /dev/null
+++ b/bin/ai/library/queue/priority_queue/main.nut
@@ -0,0 +1,115 @@
+/* $Id$ */
+
+/**
+ * Priority Queue.
+ *  Peek and Pop always return the current lowest value in the list.
+ *  Sort is done on insertion only.
+ */
+class PriorityQueue
+{
+	_queue = null;
+	_count = 0;
+
+	constructor()
+	{
+		_count = 0;
+		_queue = [];
+	}
+
+	/**
+	 * Insert a new entry in the list.
+	 *  The complexity of this operation is O(n).
+	 * @param item The item to add to the list.
+	 * @param priority The priority this item has.
+	 */
+	function Insert(item, priority);
+
+	/**
+	 * Pop the first entry of the list.
+	 *  This is always the item with the lowest priority.
+	 *  The complexity of this operation is O(1).
+	 * @return The item of the entry with the lowest priority.
+	 */
+	function Pop();
+
+	/**
+	 * Peek the first entry of the list.
+	 *  This is always the item with the lowest priority.
+	 *  The complexity of this operation is O(1).
+	 * @return The item of the entry with the lowest priority.
+	 */
+	function Peek();
+
+	/**
+	 * Get the amount of current items in the list.
+	 *  The complexity of this operation is O(1).
+	 * @return The amount of items currently in the list.
+	 */
+	function Count();
+
+	/**
+	 * Check if an item exists in the list.
+	 *  The complexity of this operation is O(n).
+	 * @param item The item to check for.
+	 * @return True if the item is already in the list.
+	 */
+	function Exists(item);
+};
+
+function PriorityQueue::Insert(item, priority)
+{
+	/* Append dummy entry */
+	_queue.append(0);
+	_count++;
+
+	local i;
+	/* Find the point of insertion */
+	for (i = _count - 2; i >= 0; i--) {
+		if (priority > _queue[i][1]) {
+			/* All items bigger move one place to the right */
+			_queue[i + 1] = _queue[i];
+		} else if (item == _queue[i][0]) {
+			/* Same item, ignore insertion */
+			return false;
+		} else {
+			/* Found place to insert at */
+			break;
+		}
+	}
+	/* Insert new pair */
+	_queue[i + 1] = [item, priority];
+
+	return true;
+}
+
+function PriorityQueue::Pop()
+{
+	if (_count == 0) return null;
+
+	local node = _queue.pop();
+	_count--;
+
+	return node[0];
+}
+
+function PriorityQueue::Peek()
+{
+	if (_count == 0) return null;
+
+	return _queue[_count - 1][0];
+}
+
+function PriorityQueue::Count()
+{
+	return _count;
+}
+
+function PriorityQueue::Exists(item)
+{
+	/* Brute-force find the item (there is no faster way, as we don't have the priority number) */
+	foreach (node in _queue) {
+		if (node[0] == item) return true;
+	}
+
+	return false;
+}