/*
* Copyright 2003, 2006 Michael J. Roberts
*
* Path Finder. This module provides a class that implements Dijkstra's
* Algorithm for finding the shortest path between two nodes in a graph.
* The basic path finder class makes no assumptions about the nature of
* the underlying graph; subclasses must provide the concrete details
* about the graph being traversed. We provide a subclass that finds
* paths in a game-world location map; this can be used for things like
* making an NPC find its own way to a destination.
*
* Everyone is granted permission to use and modify this file for any
* purpose, provided that the original author is credited.
*/
#include
/* ------------------------------------------------------------------------ */
/*
* The basic path finder class. This implements Dijkstra's algorithm to
* find the shortest path from one node to another in a graph. This base
* implementation doesn't make any assumptions about the nature of the
* underlying graph; each subclass must override one method to provide
* the concrete graph implementation.
*/
class BasePathFinder: object
/*
* Find the best path from 'fromNode' to 'toNode', which are nodes in
* the underlying graph. We'll return a vector consisting of graph
* nodes, in order, giving the shortest path between the nodes. Note
* that 'fromNode' and 'toNode' are included in the returned vector.
*
* If the two nodes 'fromNode' and 'toNode' aren't connected in the
* graph, we'll simply return nil.
*/
findPath(fromNode, toNode)
{
local i;
local len;
local cur;
local workingList;
local doneList;
local toEntry;
local ret;
/* start with set containing the initial node */
workingList = new Vector(32);
workingList.append(new PathFinderNode(fromNode));
/*
* Work through the list. For each item in the list, add all of
* the items adjacent to that item to the end of the list. Keep
* visiting new elements until we've visited everything in the
* list once.
*
* We'll only add an element to the list if it's not already in
* the list. This guarantees that the loop will converge (since
* the number of items in the graph must be finite).
*/
for (i = 1 ; i <= workingList.length() ; ++i)
{
/* add each adjacent item to the working list */
forEachAdjacent(workingList[i].graphNode,
new function(adj, dist)
{
/*
* add the adjacent node only if it's not already in the
* working list
*/
if (workingList.indexWhich({x: x.graphNode == adj}) == nil)
workingList.append(new PathFinderNode(adj));
});
}
/*
* if the destination isn't in the working list, then there's no
* hope of finding a path to it
*/
if (workingList.indexWhich({x: x.graphNode == toNode}) == nil)
return nil;
/* start with an empty "done" list */
doneList = new Vector(32);
/* we know the distance from the starting element to itself is zero */
cur = workingList[1];
cur.bestDist = 0;
cur.predNode = nil;
/* keep going while we have unresolved nodes */
while (workingList.length() != 0)
{
local minIdx;
local minDist;
/* find the working list element with the shortest distance */
minDist = nil;
minIdx = nil;
for (i = 1, len = workingList.length() ; i <= len ; ++i)
{
/* if this is the best so far, remember it */
cur = workingList[i];
if (cur.bestDist != nil
&& (minDist == nil || cur.bestDist < minDist))
{
/* this is the best so far */
minDist = cur.bestDist;
minIdx = i;
}
}
/* move the best one to the 'done' list */
cur = workingList[minIdx];
doneList.append(cur = workingList[minIdx]);
workingList.removeElementAt(minIdx);
/*
* update the best distance for everything adjacent to the
* one we just finished
*/
forEachAdjacent(cur.graphNode, new function(adj, dist)
{
local newDist;
local entry;
/*
* Find the working list entry from the adjacent room.
* If there's no working list entry, there's nothing we
* need to do here, since we must already be finished
* with it.
*/
entry = workingList.valWhich({x: x.graphNode == adj});
if (entry == nil)
return;
/*
* calculate the new distance to the adjacent room, if
* we were to take a path from the room we just finished
* - this is simply the path distance to the
* just-finished room plus the distance from that room
* to the adjacent room (i.e., 'dist')
*/
newDist = cur.bestDist + dist;
/*
* If this is better than the best estimate for the
* adjacent room so far, assume we'll use this path.
* Note that if the best estimate so far is nil, it
* means we haven't found any path to the adjacent node
* yet, so this new distance is definitely the best so
* far.
*/
if (entry.bestDist == nil
|| newDist < entry.bestDist)
{
/* it's the best so far - remember it */
entry.bestDist = newDist;
entry.predNode = cur;
}
});
}
/*
* We've exhausted the working list, so we know the best path to
* every node. Now all that's left is to generate the list of
* nodes that takes us from here to there.
*
* The information we have in the 'done' list is in reverse
* order, because it tells us the predecessor for each node.
* So, first find out how long the path is by traversing the
* predecessor list from the ending point to the starting point.
* Note that the predecessor of the starting element is nil, so
* we can simply keep going until we reach a nil predecessor.
*/
toEntry = doneList.valWhich({x: x.graphNode == toNode});
for (cur = toEntry, len = 0 ; cur != nil ;
cur = cur.predNode, ++len) ;
/* create the vector that represents the path */
ret = new Vector(len);
/*
* Traverse the predecessor list again, filling in the vector.
* Since the predecessor list gives us the path in the reverse
* of the order we want, fill in the vector from the last
* element backwards, so that the vector ends up in the order we
* want. In the return vector, store the nodes from the
* underlying graph (rather than our internal tracking entries).
*/
for (cur = toEntry, i = len ; cur != nil ; cur = cur.predNode, --i)
ret[i] = cur.graphNode;
/* that's it - return the path */
return ret;
}
/*
* Iterate over everything adjacent to the given node in the
* underlying graph. This routine must simply invoke the given
* callback function once for each graph node adjacent to the given
* graph node.
*
* The callback takes two arguments: the adjacent node, and the
* distance from 'node' to the adjacent node. Note that the distance
* must be a positive number, as Dijkstra's algorithm depends on
* positive distances. If the graph isn't weighted by distance,
* simply use 1 for all distances.
*
* This method isn't implemented in the base class, since we don't
* make any assumptions about the underlying graph. Subclasses must
* provide concrete implementations of this routine to define the
* underlying graph.
*/
forEachAdjacent(node, func) { /* subclasses must override */ }
;
/*
* A node entry for the path finder - this encapsulates the node in the
* underlying graph, along with the "label" information in the algorithm.
* Note that this is NOT a node in the underlying graph; rather, this is
* an internal data structure that we use in the path finder to keep
* track of the underlying nodes and their status in the work queue.
*/
class PathFinderNode: object
construct(node)
{
/* remember the underlying node */
graphNode = node;
}
/* the underlying node in the graph */
graphNode = nil
/*
* The best estimate of the shortest distance from the starting
* point. We use nil to represent infinity here.
*/
bestDist = nil
/* the best-path predecessor for this path element */
predNode = nil
;
/*
* Room path finder. This is a concrete implementation of the path
* finder that finds a path from one Room to another in the game-world
* map.
*
* This implementation traverses rooms based on the actual connections in
* the game map. Note that this isn't appropriate for all purposes,
* since it doesn't take into account what the actor knows about the game
* map. This "omniscient" implementation is suitable for situations
* where the actor's knowledge isn't relevant and we just want the actual
* best path between the locations.
*/
roomPathFinder: BasePathFinder
/* find the path for a given actor from one room to another */
findPath(actor, fromLoc, toLoc)
{
/* remember the actor */
actor_ = actor;
/* run the normal algorithm */
return inherited(fromLoc, toLoc);
}
/*
* iterate over the nodes adjacent in the underlying graph to the
* given node
*/
forEachAdjacent(loc, func)
{
/*
* run through the directions, and add the apparent destination
* for each one
*/
foreach (local dir in Direction.allDirections)
{
local conn;
local dest;
/*
* if there's a connector, and it has an apparent
* destination, then the apparent destination is the
* adjacent node
*/
if ((conn = loc.getTravelConnector(dir, actor_)) != nil
&& (dest = getDestination(loc, dir, conn)) != nil
&& includeRoom(dest))
{
/*
* This one seems to go somewhere - process the
* destination. The standard room map has no concept of
* distance, so use equal weightings of 1 for all
* inter-room distances.
*/
(func)(dest, 1);
}
}
}
/*
* Get the location adjacent to the given location, for the purposes
* of finding the path. By default, we return the actual
* destination, but subclasses might want to use other algorithms.
* For example, if a subclass's goal is to make an NPC find its own
* way from one location to another, then it should use the APPARENT
* destination, from the NPC's perspective, rather than the actual
* destination, since we'd want to construct the path based on the
* NPC's knowledge of the map.
*/
getDestination(loc, dir, conn)
{
/* return the actual destination for the connector */
return conn.getDestination(loc, actor_);
}
/*
* For easier customization, this method allows the map that we
* search to be filtered so that it only includes a particular
* subset of the map. This returns true if a given room is to be
* included in the search, nil if not. By default, we include all
* rooms. Note that this is only called to begin with for rooms
* that have apparent connections to the starting room, so there's
* no need to filter out areas of the map that aren't connected at
* all to the starting search location.
*/
includeRoom(loc) { return true; }
/* the actor who's finding the path */
actor_ = nil
;
/*
* An NPC goal-seeking path finder. This is a subclass of the basic room
* path finder that
*/
npcRoomPathFinder: roomPathFinder
/*
* Get the destination. Unlike the base class implementation, we
* take into the NPC's knowledge of the map by only using connector
* destinations that are APPARENT to the NPC.
*/
getDestination(loc, dir, conn)
{
/* return the apparent destination of the connector */
return conn.getApparentDestination(loc, actor_);
}
;