/*
 *   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 <tads.h>


/* ------------------------------------------------------------------------ */
/*
 *   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_);
    }
;

