diff options
Diffstat (limited to 'bin/ai/library/graph/aystar/main.nut')
-rw-r--r-- | bin/ai/library/graph/aystar/main.nut | 238 |
1 files changed, 0 insertions, 238 deletions
diff --git a/bin/ai/library/graph/aystar/main.nut b/bin/ai/library/graph/aystar/main.nut deleted file mode 100644 index 1999eab14..000000000 --- a/bin/ai/library/graph/aystar/main.nut +++ /dev/null @@ -1,238 +0,0 @@ -/* $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; } -}; |