equal
deleted
inserted
replaced
1 /* $Id$ */ |
1 /* $Id$ */ |
2 |
|
3 /* We need a Queue */ |
|
4 import("queue.binary_heap", "Queue", 1); |
|
5 |
2 |
6 /** |
3 /** |
7 * An AyStar implementation. |
4 * An AyStar implementation. |
8 * It solves graphs by finding the fastest route from one point to the other. |
5 * It solves graphs by finding the fastest route from one point to the other. |
9 */ |
6 */ |
10 class AyStar |
7 class AyStar |
11 { |
8 { |
|
9 _queue_class = import("queue.binary_heap", "", 1); |
12 _cost_callback = null; |
10 _cost_callback = null; |
13 _estimate_callback = null; |
11 _estimate_callback = null; |
14 _neighbours_callback = null; |
12 _neighbours_callback = null; |
15 _cost_callback_param = null; |
13 _cost_callback_param = null; |
16 _estimate_callback_param = null; |
14 _estimate_callback_param = null; |
83 function AyStar::InitializePath(sources, goals) |
81 function AyStar::InitializePath(sources, goals) |
84 { |
82 { |
85 if (typeof(sources) != "array" || sources.len() == 0) throw("sources has be a non-empty array."); |
83 if (typeof(sources) != "array" || sources.len() == 0) throw("sources has be a non-empty array."); |
86 if (typeof(goals) != "array" || goals.len() == 0) throw("goals has be a non-empty array."); |
84 if (typeof(goals) != "array" || goals.len() == 0) throw("goals has be a non-empty array."); |
87 |
85 |
88 this._open = Queue(); |
86 this._open = this._queue_class(); |
89 this._closed = AIList(); |
87 this._closed = AIList(); |
90 |
88 |
91 foreach (node in sources) { |
89 foreach (node in sources) { |
92 local new_path = this.Path(null, node, this._cost_callback, this._cost_callback_param); |
90 local new_path = this.Path(null, node, this._cost_callback, this._cost_callback_param); |
93 this._open.Insert(new_path, new_path.GetCost() + this._estimate_callback(node, goals, this._estimate_callback_param)); |
91 this._open.Insert(new_path, new_path.GetCost() + this._estimate_callback(node, goals, this._estimate_callback_param)); |