1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
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; }
};
|
