10 class AyStar |
10 class AyStar |
11 { |
11 { |
12 _cost_callback = null; |
12 _cost_callback = null; |
13 _estimate_callback = null; |
13 _estimate_callback = null; |
14 _neighbours_callback = null; |
14 _neighbours_callback = null; |
|
15 _cost_callback_param = null; |
|
16 _estimate_callback_param = null; |
|
17 _neighbours_callback_param = null; |
15 _open = null; |
18 _open = null; |
16 _closed = null; |
19 _closed = null; |
17 _goals = null; |
20 _goals = null; |
18 |
21 |
19 /** |
22 /** |
20 * @param cost_callback A function that returns the cost of a path. It |
23 * @param cost_callback A function that returns the cost of a path. It |
21 * should accept 2 parameters, old_path and new_node. old_path is an |
24 * should accept three parameters, old_path, new_node and |
22 * instance of AyStar.Path, and new_node is the new node that is added to |
25 * cost_callback_param. old_path is an instance of AyStar.Path, and |
23 * that path. It should return the cost of the path including new_node. |
26 * new_node is the new node that is added to that path. It should return |
|
27 * the cost of the path including new_node. |
24 * @param estimate_callback A function that returns an estimate from a node |
28 * @param estimate_callback A function that returns an estimate from a node |
25 * to the goal node. It should accept two parameters, node and goal_nodes. |
29 * to the goal node. It should accept three parameters, node, goal_nodes and |
26 * It should return an estimate to the cost from the lowest cost between |
30 * estimate_callback_param. It should return an estimate to the cost from |
27 * node and any node out of goal_nodes. Note that this estimate is not |
31 * the lowest cost between node and any node out of goal_nodes. Note that |
28 * allowed to be higher than the real cost between node and any of |
32 * this estimate is not allowed to be higher than the real cost between node |
29 * goal_nodes. A lower value is fine, however the closer it is to the real |
33 * and any of goal_nodes. A lower value is fine, however the closer it is to |
30 * value, the better the performance. |
34 * the real value, the better the performance. |
31 * @param neighbours_callback A function that returns all neighbouring nodes |
35 * @param neighbours_callback A function that returns all neighbouring nodes |
32 * from a given node. It should accept two parameters, current_path and node, |
36 * from a given node. It should accept three parameters, current_path, node |
33 * and return an array containing all neighbouring nodes. |
37 * and neighbours_callback_param. It should return an array containing all |
|
38 * neighbouring nodes. |
|
39 * @param cost_callback_param This parameters will be passed to cost_callback |
|
40 * as third parameter. Useful to send is an instance of an object. |
|
41 * @param estimate_callback_param This parameters will be passed to |
|
42 * estimate_callback as third parameter. Useful to send is an instance of an |
|
43 * object. |
|
44 * @param neighbours_callback_param This parameters will be passed to |
|
45 * neighbours_callback as third parameter. Useful to send is an instance of |
|
46 * an object. |
34 */ |
47 */ |
35 constructor(cost_callback, estimate_callback, neighbours_callback) |
48 constructor(cost_callback, estimate_callback, neighbours_callback, cost_callback_param = null, |
|
49 estimate_callback_param = null, neighbours_callback_param = null) |
36 { |
50 { |
37 if (typeof(cost_callback) != "function") throw("'cost_callback' has be a function-pointer."); |
51 if (typeof(cost_callback) != "function") throw("'cost_callback' has be a function-pointer."); |
38 if (typeof(estimate_callback) != "function") throw("'estimate_callback' has be a function-pointer."); |
52 if (typeof(estimate_callback) != "function") throw("'estimate_callback' has be a function-pointer."); |
39 if (typeof(neighbours_callback) != "function") throw("'neighbours_callback' has be a function-pointer."); |
53 if (typeof(neighbours_callback) != "function") throw("'neighbours_callback' has be a function-pointer."); |
40 |
54 |
41 this._cost_callback = cost_callback; |
55 this._cost_callback = cost_callback; |
42 this._estimate_callback = estimate_callback; |
56 this._estimate_callback = estimate_callback; |
43 this._neighbours_callback = neighbours_callback; |
57 this._neighbours_callback = neighbours_callback; |
|
58 this._cost_callback_param = cost_callback_param; |
|
59 this._estimate_callback_param = estimate_callback_param; |
|
60 this._neighbours_callback_param = neighbours_callback_param; |
44 } |
61 } |
45 |
62 |
46 /** |
63 /** |
47 * Initialize a path search between sources and goals. |
64 * Initialize a path search between sources and goals. |
48 * @param sources The source nodes. |
65 * @param sources The source nodes. |
96 return path; |
113 return path; |
97 } |
114 } |
98 } |
115 } |
99 this._closed.AddItem(cur_node, 0); |
116 this._closed.AddItem(cur_node, 0); |
100 /* Scan all neighbours */ |
117 /* Scan all neighbours */ |
101 local neighbours = this._neighbours_callback(path, cur_node); |
118 local neighbours = this._neighbours_callback(path, cur_node, this._neighbours_callback_param); |
102 foreach (node in neighbours) { |
119 foreach (node in neighbours) { |
103 if (this._closed.HasItem(node)) continue; |
120 if (this._closed.HasItem(node)) continue; |
104 /* Calculate the new paths and add them to the open list */ |
121 /* Calculate the new paths and add them to the open list */ |
105 local new_path = this.Path(path, node, this._cost_callback); |
122 local new_path = this.Path(path, node, this._cost_callback, this._cost_callback_param); |
106 this._open.Insert(new_path, new_path.GetCost() + this._estimate_callback(node, this._goals)); |
123 this._open.Insert(new_path, new_path.GetCost() + this._estimate_callback(node, this._goals, this._estimate_callback_param)); |
107 } |
124 } |
108 } |
125 } |
109 |
126 |
110 if (this._open.Count() > 0) return false; |
127 if (this._open.Count() > 0) return false; |
111 this._CleanPath(); |
128 this._CleanPath(); |