From a3dd7506d377b1434f913bd65c019eed52b64b6e Mon Sep 17 00:00:00 2001 From: truebrain Date: Mon, 12 Jan 2009 17:11:45 +0000 Subject: (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 --- bin/ai/library/graph/aystar/library.nut | 12 + bin/ai/library/graph/aystar/main.nut | 238 +++++++++++++++ bin/ai/library/pathfinder/rail/library.nut | 12 + bin/ai/library/pathfinder/rail/main.nut | 389 ++++++++++++++++++++++++ bin/ai/library/pathfinder/road/library.nut | 12 + bin/ai/library/pathfinder/road/main.nut | 363 ++++++++++++++++++++++ bin/ai/library/queue/binary_heap/library.nut | 12 + bin/ai/library/queue/binary_heap/main.nut | 131 ++++++++ bin/ai/library/queue/fibonacci_heap/library.nut | 12 + bin/ai/library/queue/fibonacci_heap/main.nut | 204 +++++++++++++ bin/ai/library/queue/priority_queue/library.nut | 12 + bin/ai/library/queue/priority_queue/main.nut | 115 +++++++ 12 files changed, 1512 insertions(+) create mode 100644 bin/ai/library/graph/aystar/library.nut create mode 100644 bin/ai/library/graph/aystar/main.nut create mode 100644 bin/ai/library/pathfinder/rail/library.nut create mode 100644 bin/ai/library/pathfinder/rail/main.nut create mode 100644 bin/ai/library/pathfinder/road/library.nut create mode 100644 bin/ai/library/pathfinder/road/main.nut create mode 100644 bin/ai/library/queue/binary_heap/library.nut create mode 100644 bin/ai/library/queue/binary_heap/main.nut create mode 100644 bin/ai/library/queue/fibonacci_heap/library.nut create mode 100644 bin/ai/library/queue/fibonacci_heap/main.nut create mode 100644 bin/ai/library/queue/priority_queue/library.nut create mode 100644 bin/ai/library/queue/priority_queue/main.nut (limited to 'bin/ai/library') 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; +} -- cgit v1.2.3-54-g00ecf