/* Copyright (c) 2001 by Kevin Forchione. All Rights Reserved. */
/*
* TADS ADV.T/STD.T LIBRARY EXTENSION
* TRACKACTOR.T
* Version 3.0
*
* THE TRAVEL GRAPH
*
* The travel graph is a multi-graph of weighted directed
* edges, that may contain self-loops. To simplify the automation
* process only travel properties that resolve to property types
* of _object_ are used to build adjacent vertex and adjacent edge
* lists.
*
* Multiple edges between a given pair of vertices are flattened
* out by resolving the traversal between the two vertices as
* passable if any of the edges is found to be passable, and
* impassable otherwise. This allows for simple paths to be
* computed by dijkstra's shortest paths algorithm.
*
* Weighting of edges between vertices is based upon the
* actor's ability to pass all of the obstacles that may
* lie along the given edge. Impassable edges are given a
* weight of INFINITY, while edges for which passage is
* possible are give a weight of 1. The edge weights are
* maintained through all path computations for a given
* station (see below), and re-adjudicated only when the
* next station is being considered.
*
* If a passable edge has been found for the two vertices
* then the adjacent vertex itself is examined to determine
* if it is accessible to the actor. Inaccessible vertices
* are temporarily removed from path computations. After a
* new path has been computed the bias against the
* inaccessible vertex is removed.
*
* STATIONS
*
* TrackActor class allows the author to set stations as
* points of travelling preference along the graph. Stations
* are used to form the destinations of simple paths computed
* by dijkstra's algorithm.
*
* When a path to a station has been found to be impassable,
* the trackActorDaemon() will remove the impassable vertex
* or edge from its new path computation and attempt to
* traverse this new path. This strategy is continued until
* either a path to the station has been successfully
* traversed; or all possible paths to the station are
* exhausted. If all paths have been exhausted the station
* is abandonned and we proceed to calculate a path from
* the actor's location to the next station in the list.
*
* TRAVERSAL STYLE
*
* In this way, stations are run in sequence as they appear
* in the actor's station list until the end of the list is
* reached. At that point the traversal style used to set
* the station list will determine what happens next. The
* pattern of this sequence can be any of three traversal
* styles:
*
* pathTraversal: the station list is processed once only.
* cycleTraversal: the station list is processed once, returning
* the actor to the first station when the end has
* been reached.
* continuousTraversal: the station list is processed as a continuous
* loop from beginning to end.
*
* EXAMPLE
*
* setStation( [loc1, loc2, loc3], continuousTraversal );
*
* The above statement tells TrackActor to set its station
* list to [loc1, loc2, loc3] and its traversal style to
* continuousTraversal. The actor's destination will be
* set to loc1and a path computed from the actor's location
* to loc1.
*
* The actor will then follow the computed path (track list)
* until it completes it or finds an edge or vertex it cannot
* pass. If this is the case then a new path to its destination
* is computed, eliminating the obstructing edge or vertex from
* the calculation.
*
* After the actor has arrived at loc1 (or it has been
* determined that this no paths to the destination exist)
* a new path starting from the actor's location to loc2
* will be computed; the process repeated for loc3 and
* the whole cycle starts over again by the actor returning
* from loc3 to loc1.
*
*----------------------------------------------------------------------
* REQUIREMENTS
*
* + HTML TADS 2.2.6 or later
* + Should be #included after ADV.T and STD.T
* + Requires dijkstra.t
*
*----------------------------------------------------------------------
* IMPORTANT LIBRARY INTERFACE AND MODIFICATION
*
* + Overrides preinit()
*
*----------------------------------------------------------------------
* COPYRIGHT NOTICE
*
* You may modify and use this file in any way you want, provided that
* if you redistribute modified copies of this file in source form, the
* copies must include the original copyright notice (including this
* paragraph), and must be clearly marked as modified from the original
* version.
*
*------------------------------------------------------------------------------
* REVISION HISTORY
*
* 28-Jan-01: Creation.
* 06-Feb-01: Major restructuring!
*/
/*
* Stations are vertices within the game world multi-graph which
* form the destinations for the tracks the actor must traverse.
* This method sets the actor in motion by setting its station
* list, calculating the track list for the first station, and
* notifying the trackActorDaemon.
*/
setStation( vertexList, type ) = {
self.stationList = [];
self.traversalStyle = type;
/*
* Creates the track list for the destination. Track lists are
* computed using dijkstra's shortest paths algorithm.
*/
setPath( start, dest ) = {
self.trackPos = 1;
self.destination = dest;
self.trackList = Path.shortestPathVertices(start, dest);
}
trackActorDaemon = {
local cur, nxt, edge, povSave;
if ( !self.isActive ) return;
/* set the point of view to this actor */
povStack.push(self);
/* Reset movement count */
self.movementCount = 0;
while( self.hasMore )
{
/* Get the actor's current and next locations */
cur = self.location;
nxt = self.trackList[ self.trackPos ];
/*
* Retrieve a passable edge for the current and next
* vertices.
*/
edge = self.getEdge( cur, nxt );
if ( edge != nil )
{
if ( self.canMoveToVertex( nxt ) )
{
/*
* We remove the nxt vertice from the failed
* station list, if it has been added from an
* earlier iteration.
*/
if ( nxt == self.destination )
self.failedStationList -= nxt;
self.traverseEdge( edge );
break;
}
/*
* If this vertex is temporarily blocked to the actor we
* need to recalculate the path, eliminating this vertex
* from our calculations -- temporarily.
*/
if ( nxt != self.destination )
{
self.failedVertexList += nxt;
self.setPath( cur, self.destination );
self.handleInvalidVertex( nxt );
continue;
}
}
/*
* The actor's current location is the next location in the
* track list. We simply increment the track position and start
* the process over. This is checked after edge and vertice
* validation to allow for graph self-loops.
*/
if ( cur == nxt )
continue;
/*
* This route is blocked to the actor. We need to recalculate
* the path, eliminating the failed edge list from our
* calculations.
*/
self.setPath( cur, self.destination );
if ( length(self.stationList - self.failedStationList) == 0)
{
/*
* Dijkstra didn't compute a path for any of the stations,
* so shut the actor down.
*/
self.handleNoValidStations;
return nil;
}
/*
* When we reach the end of the track list we check to see if
* we need to stop or go to the next station.
*/
if ( length(self.trackList) < self.trackPos )
{
/* Ask traversal style is we should stop moving */
if ( self.traversalStyle.trackListCompleted(self,
self.stationListCycles) )
return nil;
/* increment the station position */
++self.stationPos;
/*
* If we've reached the end of the station list we need to
* determine if we should stop or recycle through the list.
*/
if ( length(self.stationList) < self.stationPos )
{
/* Ask traversal style is we should stop moving */
if ( self.traversalStyle.stationListCompleted(self) )
return nil;
/*
* Increment the number of times we've been thru the
* station cycle list.
*/
++self.stationListCycles;
/* set the station position back to 1 */
self.stationPos = 1;
}
/* Reset the failed vertex and edge lists */
self.failedVertexList = [];
self.failedEdgeList = [];
/* Compute the track list for the new station */
self.setPath( self.location, self.stationList[
self.stationPos ] );
}
return true;
}
getEdge( cur, nxt ) = {
local i, len, edge, obsList;
local edgeList = [], obstacleEdgeList = [];
/*
* Create an edge list containing each edge object that matches
* the actor's current and next locations. Build a separate
* list from the edge list that contains all edges that have
* obstacles.
*/
len = length( cur.adjacentEdgeList );
for ( i = 1; i <= len; ++i )
{
edge = cur.adjacentEdgeList[ i ];
if ( edge.vertexFrom == cur && edge.vertexTo == nxt )
{
edgeList += edge;
if ( length( edge.obstacleList ) > 0 )
{
obstacleEdgeList += edge;
}
}
}
/* remove all edges with obstacles from the edge list */
edgeList -= obstacleEdgeList;
/* Set edge to nil */
edge = nil;
if ( length( edgeList ) > 0 )
{
/* we have at least 1 passable edge */
edge = randomElement( edgeList );
return edge;
}
/*
* All edges have obstacles. Check each edge to see if the
* actor can pass all of the obstacles for the given edge. If
* the actor can pass all of the obstacles then travel to the
* first obstacle.
*/
len = length( obstacleEdgeList );
for ( i = 1; i <= len; ++i )
{
obsList = obstacleEdgeList[ i ].obstacleList;
if ( self.canPassEdge( obsList ) )
{
edge = obstacleEdgeList[ i ];
return edge;
}
}
/* Add the obstacle edge list to the failed edge list */
self.failedEdgeList += obstacleEdgeList;
return nil;
}
/*
* Test whether the actor can pass all of the obstacles for a
* given edge. Returns true if the actor can; otherwise returns
* nil.
*/
canPassEdge( obstacleList ) = {
local i, len, o;
len = length( obstacleList );
for ( i = 1; i <= len; ++i )
{
o = obstacleList[i];
if ( !self.canPassObstacle( o ) )
{
/* we can't pass the obstacle */
return nil;
}
}
/* No obstacle has stopped passage */
return true;
}
/*
* Test whether the actor can pass the specified obstacles for
* a given edge. The method should return true if passage is
* allowed; nil otherwise. The default simply tests to see
* if the obstacle is closed and locked or not auto open.
*/
canPassObstacle( o ) = {
if ( !o.isopen
&& ( o.islocked || o.noAutoOpen ) )
{
/* we can't pass the obstacle */
return nil;
}
/* The obstacle has not stopped passage */
return true;
}
/*
* This method is used to determine if the vertex
* is, for some reason, off-limits to the actor.
*/
canMoveToVertex( v ) = {
return true;
}
// move to a new location, notifying player of coming and going
traverseEdge( edge ) = {
local old_loc_visible;
local new_loc_visible;
local room, obs;
obs = car(edge.obstacleList);
if ( obs )
room = obs;
else
room = edge.vertexTo;
/* if it's an obstacle, travel to the obstacle instead */
while( room != nil && room.isobstacle )
room = room.destination;
/* do nothing if going nowhere */
if ( room == nil )
return;
/* note whether the actor was previously visible */
old_loc_visible = (self.location != nil
&& parserGetMe().isVisible(self.location));
/* note whether the actor will be visible in the new location */
new_loc_visible = parserGetMe().isVisible(room);
/*
* if I'm leaving the player's location, and I was previously
* visible, and I'm not going to be visible after the move, and
* the player's location isn't dark, show the "leaving" message
*/
if (parserGetMe().location != nil
&& parserGetMe().location.islit
&& old_loc_visible
&& !new_loc_visible)
self.sayLeaving( edge.dirPtr );
/* move to my new location */
self.moveInto( room );
/*
* if I'm visible to the player at the new location, and I
* wasn't previously visible, and it's not dark, show the
* "arriving" message
*/
if (parserGetMe().location != nil
&& parserGetMe().location.islit
&& new_loc_visible
&& !old_loc_visible)
self.sayArriving( edge.dirPtr );
}
// sayLeaving and sayArriving announce the actor's departure and arrival
// in the same room as the player.
sayLeaving( dirPtr ) = {
self.location.dispParagraph;
"\^<<self.thedesc>> leaves";
switch( dirPtr )
{
case &up:
case &down:
case &in:
case &out:
" the area. ";
break;
default:
" to the <<sayDirName( dirPtr )>>. ";
}
}
sayArriving( dirPtr ) = {
self.location.dispParagraph;
"\^<<self.thedesc>> enters ";
switch( dirPtr )
{
case &up:
case &down:
case &in:
case &out:
" the area. ";
break;
default:
" from the <<sayDirName( dirPtr )>>. ";
}
}
// Hooks for special transition handling
/*
* This method is called when no valid edges have been found and
* after a new path has been calculated weighting the edges between
* cur and nxt at INFINITY.
*/
handleNoValidEdges( cur, nxt ) = {}
/*
* This method is called when the next vertex is found to be
* impassable to the actor and after a new path has been calculated
* by removing the vertex from dijkstra's considerations. By
* default we remove the vertex from the failed vertex list.
*/
handleInvalidVertex( nxt ) = {
self.failedVertexList -= nxt;
}
/*
* This method is called when all of the stations in the actor's
* station list have been added to the failed station list. This
* means that the actor has failed to find paths for all of the
* stations. By default we stop the actor's attempts to move.
*/
handleNoValidStations = {
self.isActive = nil;
}
/*
* This method is called when the traversal style is cycleTraversal
* and the cycle has been completed. By default we stop the actor's
* attempts to move.
*/
handleCompletedCycle = {
self.isActive = nil;
}
/*
* This method is called when the traversal style is pathTraversal
* and the path has been completed. By default we stop the actor's
* attempts to move.
*/
handleCompletedPath = {
self.isActive = nil;
}
;
/*
* TraversalStyle indicates whether movement is to stop
* at the points when the end of the track list or station
* list has been reached.
*/
class TraversalStyle: object
trackListCompleted(actor, stationListCycles) = { return nil; }
stationListCompleted(actor) = { return nil; }
;
pathTraversal: TraversalStyle
/* movement stops when we reach the end of the station list */
stationListCompleted(actor) = {
actor.handleCompletedPath;
return true;
}
;
cycleTraversal: TraversalStyle
/* movement stops when we've cycled around the station list once */
trackListCompleted(actor, stationListCycles) = {
if ( stationListCycles > 0 )
{
actor.handleCompletedCycle;
return true;
}
return nil;
}
;
/*
* Modify Path to weight edges that are found to be unpassable to the
* track actor. If we find a corresponding edge for v & w we return a
* value that will compute to INFINITY for comparison of the edge
* between the two vertices. If we don't find an edge in the track
* actor's failed edge list then we return 1.
*/
modify Path
computeEdge( v, w ) = {
local i, len, e;
local edgeList = [];
edgeList = povStack.currentPov.failedEdgeList;
len = length( edgeList );
for ( i = 1; i <= len; ++i )
{
e = edgeList[ i ];
if ( v.vertex == e.vertexFrom && w.vertex == e.vertexTo )
return INFINITY;
}
