/* 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!
 */


#ifndef _TRACK_ACTOR_T_
#define _TRACK_ACTOR_T_

#include <dijkstra.t>

#pragma C+

sayDirName: function;
randomElement: function;

TrackActor: object
    isActive            = nil
    traversalStyle	    = nil
    destination 	    = nil
    movementCount       = 0
    stationPos		    = 1
    trackPos 		    = 1
    stationList		    = []
    trackList		    = []
    failedVertexList    = []
    failedEdgeList      = []
    failedStationList   = []

    /*
     *  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;
        
	    if (length( vertexList ) == 1
	    && self.traversalStyle != pathTraversal )
	        self.stationList    += self.location; 

	    self.stationList        += vertexList;
	        
	    self.stationPos		    = 1;
	    self.stationListCycles  = 0;
     	povStack.push(self);
    	self.isActive 		    = true;
	    self.failedVertexList 	= [];
	    self.failedEdgeList     = [];
	    self.setPath( self.location, self.stationList[ self.stationPos ] );
	    povStack.pop;
    }

    /*
     *  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 ( nxt == self.destination
            && length( self.trackList ) == 0 )
            {
                local tmp = [ nxt ];
	        	self.failedStationList += (tmp - self.failedStationList);
            }
            self.handleNoValidEdges( cur, nxt );
        }
        
        /* Reset the pov */
        povStack.pop;
    }
    
    hasMore = {
        ++self.trackPos;

        ++self.movementCount;
        
        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;
    }

    isFirstPass = { return (self.movementCount == 1); }
    
    // 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;
    }
;

continuousTraversal: TraversalStyle
;

class Edge: object
    vertexFrom      = nil
    vertexTo        = nil
    dirPtr          = nil
    obstacleList    = []

    instantiate( vf, vt, d, o ) = {
        local e = new Edge;

        e.vertexFrom    = vf;
        e.vertexTo      = vt;
        e.dirPtr        = d;
        e.obstacleList  = o;

        return e;
    }
;

/*
 *  Say the direction name for the direction pointer.
 */
sayDirName: function( dirPtr )
{
    switch( dirPtr )
    {
        case &north:
            "north";
            break;
            
        case &ne:
            "northeast";
            break;
            
        case &nw:
            "northwest";
            break;
            
        case &south:
            "south";
            break;
      
        case &se: 
            "southeast";
            break;
            
        case &sw:
            "southwest";
            break;
            
        case &east:
            "east";
            break;
            
        case &west:
            "west";
            break;
            
        case &up:
            "up";
            break;
            
        case &down:
            "down";
            break;
            
        case &in:
            "in";
            break;
            
        case &out:
            "out";
            break;
    }
}

/*
 *  Returns an element of the list selected at random.
 */
randomElement: function( lst ) {
	local r, len = length( lst );
	
	if ( len == 1 )
	    r = 1;
	else
	    r = _rand( len );

	return lst[ r ];
}

povStack: object
    povList     = []
    currentPov  = nil
    
    push( val ) = {
        local tmpList   = self.povList;
        
        self.currentPov = val;
        self.povList    = [ val ] + tmpList;
    }
    
    pop = {
        local cp, val;
        
        val = car(self.povList);
        if ( val == nil ) {
            val = parserGetMe();
            self.currentPov = val;
        }
        else
        {
            self.povList = cdr(self.povList);
        
            cp = car(self.povList);
            if ( cp == nil )
                self.currentPov = parserGetMe();
            else
                self.currentPov = cp;
        }
        
        return val;
    }
;

/*
 *  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;
        }
        
        return 1;
    }
;

modify room
    adjacentVertexList  = []
    adjacentEdgeList    = []
    
    setAdjacentVertices = {
        local i, dPtr, w, len, e, obsList;
        local dirList = [ &north, &south, &east, &west, &ne, &nw, &se,
            &sw, &up, &down, &in, &out ];

        len = length( dirList );
        for ( i = 1; i <= len; ++i )
        {
            if ( proptype( self, dirList[ i ] ) == DTY_OBJECT )
            {
                dPtr = dirList[i];
                w = self.(dPtr);

                /* build a list of all obstacles */
                obsList = [];
                while( w != nil && isclass(w, obstacle) )
                {
                    obsList += w;
                    w = w.doordest;
                }

                e = Edge.instantiate(self, w, dPtr, obsList);
                self.adjacentEdgeList += e;

                /* Ensure that the adjacent vertex list is unique */
                w = [ w ];
                self.adjacentVertexList += (w - self.adjacentVertexList);
            }
        }
    }
    
    getAdjacentVertices = {
        return (self.adjacentVertexList - 
            povStack.currentPov.failedVertexList);
    }
;

initTravelGraph: function {
    local o;

    o = firstobj(room);
    while( o != nil )
    {
        o.setAdjacentVertices;
        o = nextobj( o, room );
    }
    povStack.push(parserGetMe());
}

replace preinit: function
{
    local o;

    global.lamplist = [];
    o = firstobj();
    while(o != nil)
    {
        if (o.islamp)
            global.lamplist = global.lamplist + o;
        o = nextobj(o);
    }
    initSearch();
    initTravelGraph();
}

#pragma C-

#endif  /* _TRACK_ACTOR_T_ */