2
* Copyright 2003, 2006 Michael J. Roberts
4
* Path Finder. This module provides a class that implements Dijkstra's
5
* Algorithm for finding the shortest path between two nodes in a graph.
6
* The basic path finder class makes no assumptions about the nature of
7
* the underlying graph; subclasses must provide the concrete details
8
* about the graph being traversed. We provide a subclass that finds
9
* paths in a game-world location map; this can be used for things like
10
* making an NPC find its own way to a destination.
12
* Everyone is granted permission to use and modify this file for any
13
* purpose, provided that the original author is credited.
19
/* ------------------------------------------------------------------------ */
21
* The basic path finder class. This implements Dijkstra's algorithm to
22
* find the shortest path from one node to another in a graph. This base
23
* implementation doesn't make any assumptions about the nature of the
24
* underlying graph; each subclass must override one method to provide
25
* the concrete graph implementation.
27
class BasePathFinder: object
29
* Find the best path from 'fromNode' to 'toNode', which are nodes in
30
* the underlying graph. We'll return a vector consisting of graph
31
* nodes, in order, giving the shortest path between the nodes. Note
32
* that 'fromNode' and 'toNode' are included in the returned vector.
34
* If the two nodes 'fromNode' and 'toNode' aren't connected in the
35
* graph, we'll simply return nil.
37
findPath(fromNode, toNode)
47
/* start with set containing the initial node */
48
workingList = new Vector(32);
49
workingList.append(new PathFinderNode(fromNode));
52
* Work through the list. For each item in the list, add all of
53
* the items adjacent to that item to the end of the list. Keep
54
* visiting new elements until we've visited everything in the
57
* We'll only add an element to the list if it's not already in
58
* the list. This guarantees that the loop will converge (since
59
* the number of items in the graph must be finite).
61
for (i = 1 ; i <= workingList.length() ; ++i)
63
/* add each adjacent item to the working list */
64
forEachAdjacent(workingList[i].graphNode,
65
new function(adj, dist)
68
* add the adjacent node only if it's not already in the
71
if (workingList.indexWhich({x: x.graphNode == adj}) == nil)
72
workingList.append(new PathFinderNode(adj));
77
* if the destination isn't in the working list, then there's no
78
* hope of finding a path to it
80
if (workingList.indexWhich({x: x.graphNode == toNode}) == nil)
83
/* start with an empty "done" list */
84
doneList = new Vector(32);
86
/* we know the distance from the starting element to itself is zero */
91
/* keep going while we have unresolved nodes */
92
while (workingList.length() != 0)
97
/* find the working list element with the shortest distance */
100
for (i = 1, len = workingList.length() ; i <= len ; ++i)
102
/* if this is the best so far, remember it */
103
cur = workingList[i];
104
if (cur.bestDist != nil
105
&& (minDist == nil || cur.bestDist < minDist))
107
/* this is the best so far */
108
minDist = cur.bestDist;
113
/* move the best one to the 'done' list */
114
cur = workingList[minIdx];
115
doneList.append(cur = workingList[minIdx]);
116
workingList.removeElementAt(minIdx);
119
* update the best distance for everything adjacent to the
120
* one we just finished
122
forEachAdjacent(cur.graphNode, new function(adj, dist)
128
* Find the working list entry from the adjacent room.
129
* If there's no working list entry, there's nothing we
130
* need to do here, since we must already be finished
133
entry = workingList.valWhich({x: x.graphNode == adj});
138
* calculate the new distance to the adjacent room, if
139
* we were to take a path from the room we just finished
140
* - this is simply the path distance to the
141
* just-finished room plus the distance from that room
142
* to the adjacent room (i.e., 'dist')
144
newDist = cur.bestDist + dist;
147
* If this is better than the best estimate for the
148
* adjacent room so far, assume we'll use this path.
149
* Note that if the best estimate so far is nil, it
150
* means we haven't found any path to the adjacent node
151
* yet, so this new distance is definitely the best so
154
if (entry.bestDist == nil
155
|| newDist < entry.bestDist)
157
/* it's the best so far - remember it */
158
entry.bestDist = newDist;
159
entry.predNode = cur;
165
* We've exhausted the working list, so we know the best path to
166
* every node. Now all that's left is to generate the list of
167
* nodes that takes us from here to there.
169
* The information we have in the 'done' list is in reverse
170
* order, because it tells us the predecessor for each node.
171
* So, first find out how long the path is by traversing the
172
* predecessor list from the ending point to the starting point.
173
* Note that the predecessor of the starting element is nil, so
174
* we can simply keep going until we reach a nil predecessor.
176
toEntry = doneList.valWhich({x: x.graphNode == toNode});
177
for (cur = toEntry, len = 0 ; cur != nil ;
178
cur = cur.predNode, ++len) ;
180
/* create the vector that represents the path */
181
ret = new Vector(len);
184
* Traverse the predecessor list again, filling in the vector.
185
* Since the predecessor list gives us the path in the reverse
186
* of the order we want, fill in the vector from the last
187
* element backwards, so that the vector ends up in the order we
188
* want. In the return vector, store the nodes from the
189
* underlying graph (rather than our internal tracking entries).
191
for (cur = toEntry, i = len ; cur != nil ; cur = cur.predNode, --i)
192
ret[i] = cur.graphNode;
194
/* that's it - return the path */
199
* Iterate over everything adjacent to the given node in the
200
* underlying graph. This routine must simply invoke the given
201
* callback function once for each graph node adjacent to the given
204
* The callback takes two arguments: the adjacent node, and the
205
* distance from 'node' to the adjacent node. Note that the distance
206
* must be a positive number, as Dijkstra's algorithm depends on
207
* positive distances. If the graph isn't weighted by distance,
208
* simply use 1 for all distances.
210
* This method isn't implemented in the base class, since we don't
211
* make any assumptions about the underlying graph. Subclasses must
212
* provide concrete implementations of this routine to define the
215
forEachAdjacent(node, func) { /* subclasses must override */ }
219
* A node entry for the path finder - this encapsulates the node in the
220
* underlying graph, along with the "label" information in the algorithm.
221
* Note that this is NOT a node in the underlying graph; rather, this is
222
* an internal data structure that we use in the path finder to keep
223
* track of the underlying nodes and their status in the work queue.
225
class PathFinderNode: object
228
/* remember the underlying node */
232
/* the underlying node in the graph */
236
* The best estimate of the shortest distance from the starting
237
* point. We use nil to represent infinity here.
241
/* the best-path predecessor for this path element */
246
* Room path finder. This is a concrete implementation of the path
247
* finder that finds a path from one Room to another in the game-world
250
* This implementation traverses rooms based on the actual connections in
251
* the game map. Note that this isn't appropriate for all purposes,
252
* since it doesn't take into account what the actor knows about the game
253
* map. This "omniscient" implementation is suitable for situations
254
* where the actor's knowledge isn't relevant and we just want the actual
255
* best path between the locations.
257
roomPathFinder: BasePathFinder
258
/* find the path for a given actor from one room to another */
259
findPath(actor, fromLoc, toLoc)
261
/* remember the actor */
264
/* run the normal algorithm */
265
return inherited(fromLoc, toLoc);
269
* iterate over the nodes adjacent in the underlying graph to the
272
forEachAdjacent(loc, func)
275
* run through the directions, and add the apparent destination
278
foreach (local dir in Direction.allDirections)
284
* if there's a connector, and it has an apparent
285
* destination, then the apparent destination is the
288
if ((conn = loc.getTravelConnector(dir, actor_)) != nil
289
&& (dest = getDestination(loc, dir, conn)) != nil
290
&& includeRoom(dest))
293
* This one seems to go somewhere - process the
294
* destination. The standard room map has no concept of
295
* distance, so use equal weightings of 1 for all
296
* inter-room distances.
304
* Get the location adjacent to the given location, for the purposes
305
* of finding the path. By default, we return the actual
306
* destination, but subclasses might want to use other algorithms.
307
* For example, if a subclass's goal is to make an NPC find its own
308
* way from one location to another, then it should use the APPARENT
309
* destination, from the NPC's perspective, rather than the actual
310
* destination, since we'd want to construct the path based on the
311
* NPC's knowledge of the map.
313
getDestination(loc, dir, conn)
315
/* return the actual destination for the connector */
316
return conn.getDestination(loc, actor_);
320
* For easier customization, this method allows the map that we
321
* search to be filtered so that it only includes a particular
322
* subset of the map. This returns true if a given room is to be
323
* included in the search, nil if not. By default, we include all
324
* rooms. Note that this is only called to begin with for rooms
325
* that have apparent connections to the starting room, so there's
326
* no need to filter out areas of the map that aren't connected at
327
* all to the starting search location.
329
includeRoom(loc) { return true; }
331
/* the actor who's finding the path */
336
* An NPC goal-seeking path finder. This is a subclass of the basic room
339
npcRoomPathFinder: roomPathFinder
341
* Get the destination. Unlike the base class implementation, we
342
* take into the NPC's knowledge of the map by only using connector
343
* destinations that are APPARENT to the NPC.
345
getDestination(loc, dir, conn)
347
/* return the apparent destination of the connector */
348
return conn.getApparentDestination(loc, actor_);
added
removed
tads/tads3/lib/extensions/pathfind.t
