diff options
author | truebrain <truebrain@openttd.org> | 2009-01-12 17:11:45 +0000 |
---|---|---|
committer | truebrain <truebrain@openttd.org> | 2009-01-12 17:11:45 +0000 |
commit | a3dd7506d377b1434f913bd65c019eed52b64b6e (patch) | |
tree | ced1a262eb143ad6e64ec02f4a4c89835c0c32fd /bin/ai/library/graph | |
parent | 9294f9616866b9778c22076c19b5a32b4f85f788 (diff) | |
download | openttd-a3dd7506d377b1434f913bd65c019eed52b64b6e.tar.xz |
(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
Diffstat (limited to 'bin/ai/library/graph')
-rw-r--r-- | bin/ai/library/graph/aystar/library.nut | 12 | ||||
-rw-r--r-- | bin/ai/library/graph/aystar/main.nut | 238 |
2 files changed, 250 insertions, 0 deletions
diff --git a/bin/ai/library/graph/aystar/library.nut b/bin/ai/library/graph/aystar/library.nut new file mode 100644 index 000000000..522760135 --- /dev/null +++ b/bin/ai/library/graph/aystar/library.nut @@ -0,0 +1,12 @@ +/* $Id$ */ + +class AyStar extends AILibrary { + function GetAuthor() { return "OpenTTD NoAI Developers Team"; } + function GetName() { return "AyStar"; } + function GetDescription() { return "An implementation of AyStar"; } + function GetVersion() { return 4; } + function GetDate() { return "2008-06-11"; } + function CreateInstance() { return "AyStar"; } +} + +RegisterLibrary(AyStar()); diff --git a/bin/ai/library/graph/aystar/main.nut b/bin/ai/library/graph/aystar/main.nut new file mode 100644 index 000000000..1999eab14 --- /dev/null +++ b/bin/ai/library/graph/aystar/main.nut @@ -0,0 +1,238 @@ +/* $Id$ */ + +/** + * An AyStar implementation. + * It solves graphs by finding the fastest route from one point to the other. + */ +class AyStar +{ + _queue_class = import("queue.binary_heap", "", 1); + _cost_callback = null; + _estimate_callback = null; + _neighbours_callback = null; + _check_direction_callback = null; + _cost_callback_param = null; + _estimate_callback_param = null; + _neighbours_callback_param = null; + _check_direction_callback_param = null; + _open = null; + _closed = null; + _goals = null; + + /** + * @param cost_callback A function that returns the cost of a path. It + * should accept four parameters, old_path, new_tile, new_direction and + * cost_callback_param. old_path is an instance of AyStar.Path, and + * new_node is the new node that is added to that path. It should return + * the cost of the path including new_node. + * @param estimate_callback A function that returns an estimate from a node + * to the goal node. It should accept four parameters, tile, direction, + * goal_nodes and estimate_callback_param. It should return an estimate to + * the cost from the lowest cost between node and any node out of goal_nodes. + * Note that this estimate is not allowed to be higher than the real cost + * between node and any of goal_nodes. A lower value is fine, however the + * closer it is to the real value, the better the performance. + * @param neighbours_callback A function that returns all neighbouring nodes + * from a given node. It should accept three parameters, current_path, node + * and neighbours_callback_param. It should return an array containing all + * neighbouring nodes, which are an array in the form [tile, direction]. + * @param check_direction_callback A function that returns either false or + * true. It should accept four parameters, tile, existing_direction, + * new_direction and check_direction_callback_param. It should check + * if both directions can go together on a single tile. + * @param cost_callback_param This parameters will be passed to cost_callback + * as fourth parameter. Useful to send is an instance of an object. + * @param estimate_callback_param This parameters will be passed to + * estimate_callback as fourth parameter. Useful to send is an instance of an + * object. + * @param neighbours_callback_param This parameters will be passed to + * neighbours_callback as third parameter. Useful to send is an instance of + * an object. + * @param check_direction_callback_param This parameters will be passed to + * check_direction_callback as fourth parameter. Useful to send is an + * instance of an object. + */ + constructor(cost_callback, estimate_callback, neighbours_callback, check_direction_callback, cost_callback_param = null, + estimate_callback_param = null, neighbours_callback_param = null, check_direction_callback_param = null) + { + if (typeof(cost_callback) != "function") throw("'cost_callback' has to be a function-pointer."); + if (typeof(estimate_callback) != "function") throw("'estimate_callback' has to be a function-pointer."); + if (typeof(neighbours_callback) != "function") throw("'neighbours_callback' has to be a function-pointer."); + if (typeof(check_direction_callback) != "function") throw("'check_direction_callback' has to be a function-pointer."); + + this._cost_callback = cost_callback; + this._estimate_callback = estimate_callback; + this._neighbours_callback = neighbours_callback; + this._check_direction_callback = check_direction_callback; + this._cost_callback_param = cost_callback_param; + this._estimate_callback_param = estimate_callback_param; + this._neighbours_callback_param = neighbours_callback_param; + this._check_direction_callback_param = check_direction_callback_param; + } + + /** + * Initialize a path search between sources and goals. + * @param sources The source nodes. This can an array of either [tile, direction]-pairs or AyStar.Path-instances. + * @param goals The target tiles. This can be an array of either tiles or [tile, next_tile]-pairs. + * @param ignored_tiles An array of tiles that cannot occur in the final path. + */ + function InitializePath(sources, goals, ignored_tiles = []); + + /** + * Try to find the path as indicated with InitializePath with the lowest cost. + * @param iterations After how many iterations it should abort for a moment. + * This value should either be -1 for infinite, or > 0. Any other value + * aborts immediatly and will never find a path. + * @return A route if one was found, or false if the amount of iterations was + * reached, or null if no path was found. + * You can call this function over and over as long as it returns false, + * which is an indication it is not yet done looking for a route. + */ + function FindPath(iterations); +}; + +function AyStar::InitializePath(sources, goals, ignored_tiles = []) +{ + if (typeof(sources) != "array" || sources.len() == 0) throw("sources has be a non-empty array."); + if (typeof(goals) != "array" || goals.len() == 0) throw("goals has be a non-empty array."); + + this._open = this._queue_class(); + this._closed = AIList(); + + foreach (node in sources) { + if (typeof(node) == "array") { + if (node[1] <= 0) throw("directional value should never be zero or negative."); + + local new_path = this.Path(null, node[0], node[1], this._cost_callback, this._cost_callback_param); + this._open.Insert(new_path, new_path.GetCost() + this._estimate_callback(node[0], node[1], goals, this._estimate_callback_param)); + } else { + this._open.Insert(node, node.GetCost()); + } + } + + this._goals = goals; + + foreach (tile in ignored_tiles) { + this._closed.AddItem(tile, ~0); + } +} + +function AyStar::FindPath(iterations) +{ + if (this._open == null) throw("can't execute over an uninitialized path"); + + while (this._open.Count() > 0 && (iterations == -1 || iterations-- > 0)) { + /* Get the path with the best score so far */ + local path = this._open.Pop(); + local cur_tile = path.GetTile(); + /* Make sure we didn't already passed it */ + if (this._closed.HasItem(cur_tile)) { + /* If the direction is already on the list, skip this entry */ + if ((this._closed.GetValue(cur_tile) & path.GetDirection()) != 0) continue; + + /* Scan the path for a possible collision */ + local scan_path = path.GetParent(); + + local mismatch = false; + while (scan_path != null) { + if (scan_path.GetTile() == cur_tile) { + if (!this._check_direction_callback(cur_tile, scan_path.GetDirection(), path.GetDirection(), this._check_direction_callback_param)) { + mismatch = true; + break; + } + } + scan_path = scan_path.GetParent(); + } + if (mismatch) continue; + + /* Add the new direction */ + this._closed.SetValue(cur_tile, this._closed.GetValue(cur_tile) | path.GetDirection()); + } else { + /* New entry, make sure we don't check it again */ + this._closed.AddItem(cur_tile, path.GetDirection()); + } + /* Check if we found the end */ + foreach (goal in this._goals) { + if (typeof(goal) == "array") { + if (cur_tile == goal[0]) { + local neighbours = this._neighbours_callback(path, cur_tile, this._neighbours_callback_param); + foreach (node in neighbours) { + if (node[0] == goal[1]) { + this._CleanPath(); + return path; + } + } + continue; + } + } else { + if (cur_tile == goal) { + this._CleanPath(); + return path; + } + } + } + /* Scan all neighbours */ + local neighbours = this._neighbours_callback(path, cur_tile, this._neighbours_callback_param); + foreach (node in neighbours) { + if (node[1] <= 0) throw("directional value should never be zero or negative."); + + if ((this._closed.GetValue(node[0]) & node[1]) != 0) continue; + /* Calculate the new paths and add them to the open list */ + local new_path = this.Path(path, node[0], node[1], this._cost_callback, this._cost_callback_param); + this._open.Insert(new_path, new_path.GetCost() + this._estimate_callback(node[0], node[1], this._goals, this._estimate_callback_param)); + } + } + + if (this._open.Count() > 0) return false; + this._CleanPath(); + return null; +} + +function AyStar::_CleanPath() +{ + this._closed = null; + this._open = null; + this._goals = null; +} + +/** + * The path of the AyStar algorithm. + * It is reversed, that is, the first entry is more close to the goal-nodes + * than his GetParent(). You can walk this list to find the whole path. + * The last entry has a GetParent() of null. + */ +class AyStar.Path +{ + _prev = null; + _tile = null; + _direction = null; + _cost = null; + + constructor(old_path, new_tile, new_direction, cost_callback, cost_callback_param) + { + this._prev = old_path; + this._tile = new_tile; + this._direction = new_direction; + this._cost = cost_callback(old_path, new_tile, new_direction, cost_callback_param); + }; + + /** + * Return the tile where this (partial-)path ends. + */ + function GetTile() { return this._tile; } + + /** + * Return the direction from which we entered the tile in this (partial-)path. + */ + function GetDirection() { return this._direction; } + + /** + * Return an instance of this class leading to the previous node. + */ + function GetParent() { return this._prev; } + + /** + * Return the cost of this (partial-)path from the beginning up to this node. + */ + function GetCost() { return this._cost; } +}; |