# pathfind.t | documentation

    #charset "us-ascii"
    #include "advlite.h"

    /* Abstract pathfinder */
    class Pathfinder: object

        /*
         *   When populated the pathsFound will contain a Vector of path Vectors,
         *   each path Vector comprising a series of two element lists, the first
         *   element describing the route taken and the second the destination
         *   arrived at (e.g. [northDir, hall] meaning go north to reach the hall).
         */

        pathsFound = nil

        /*
         *   The number of steps we have tried so far. We start with 1, being the
         *   null step to our starting point.
         */
        steps = 1

        /*
         *   A Vector containing all the nodes we have visited so far in our attempt
         *   to find a route. This enables us to cull paths that lead somewhere
         *   we've already been.
         */

        nodesVisited = nil

        findPath(start, target)
        {
            /*
             *   Initiate the search by setting up the Vectors we need and
             *   populating them with the null route to our starting point.
             */

            cachedRoute = nil;
            currentDestination = target;

            pathsFound = new Vector(20);
            nodesVisited = new Vector(20);
            local newPath = new Vector(2);
            newPath.append([nil, start]);
            pathsFound.append(newPath);
            nodesVisited.append(start);
            steps = 1;
            if(start == target)
                return newPath;

            /*
             *   To find the path we take a step out from our starting point through
             *   all available routes. We note the route we took and where we
             *   arrived at as a set of new paths building on our existing paths. We
             *   then discard all paths that are shorter than the number of steps we
             *   have now taken and look for one among the remainder that arrives at
             *   our target destination. If we find one, we return it. If not, we
             *   remove all paths that lead to destinations we have visited before,
             *   and then try taking another step, noting the destinations to which
             *   it leads. Repeat until we either find a path to our target or we
             *   run out of new paths to try.
             */

            while(pathsFound.length > 0)
            {
                takeOneStep();

                /* cull all paths that are shorter than steps long */

                pathsFound = pathsFound.subset({x: x.length == steps});

                /* see if any of the paths we've found lead to our target */
                local pathFound = pathsFound.valWhich({x: x[steps][2] == target} );
                if(pathFound != nil)
                {
                    cachedRoute = pathFound;
                    return pathFound;
                }

                /* remove all paths that end in nodes we've already visited */
                pathsFound = pathsFound.subset({x: nodesVisited.indexOf(x[steps][2])
                                               == nil});

                    /* note which nodes have now been visited */

                foreach(local cur in pathsFound)
                    nodesVisited.append(cur[steps][2]);

             }

            return nil;
        }

        takeOneStep()
        {
            /* Note that we've taken another step out from our starting point */
            steps ++;

            /*
             *   Copy the existing paths into a temporary Vector, since we're about
             *   to add to them and we only want to iterate over the existing list.
             */
            local temp = new Vector(pathsFound);

            /*
             *   For each existing route, see what happens if we advance one more
             *   step in every available direction and add the new routes to our
             *   list of paths.
             */
            foreach(local cur in temp)
                findDestinations(cur);
        }

        /* Find all the destinations one step away from cur */
        findDestinations(cur)
        {
            /* Specific instances must define how this is done */
        }

        /* The most recently calculated route */
        cachedRoute = nil

        /* The destination of the most recently calculated route. */
        currentDestination = nil

    ;

    /*
     *   A Pathfinder specialized for finding a route through the game map. Note
     *   that this can only find a route through TravelConnector objects (which
     *   includes direction properties attached to Rooms, Doors and other
     *   TravelConnectors).
     */
    routeFinder: Pathfinder

        findDestinations(cur)
        {
            /* Note the location our current path leads to */
            local loc = cur[steps - 1][2];

            /* See what leads in every available direction from this location */
            for(local dir = firstObj(Direction); dir != nil ; dir = nextObj(dir,
                Direction))
            {
                local newPath = new Vector(cur);

                /*
                 *   If the direction property points to an object, see if it points
                 *   to a valid path.
                 */
                if(loc.propType(dir.dirProp) == TypeObject)
                {
                    local obj = loc.(dir.dirProp);

                    /*
                     *   if the object is a locked door and we want to exclude
                     *   locked doors, or if there's some other reason the actor
                     *   cannot pass this way, we can't use this path.
                     */

                    if(excludeLockedDoors &&
                        (obj.isLocked
                          || obj.canTravelerPass(gActor) == nil
                          || valToList(obj.travelBarriers).indexWhich(
                              { b: !b.canTravelerPass(gActor, obj)}) != nil))
                        return;

                    /*
                     *   If it leads to a non-nil destination note the path to this
                     *   object. This will be the path that got us to this location
                     *   plus the one additional step.
                     */
                    local dest = loc.(dir.dirProp).getDestination(loc);
                    if(dest != nil)
                    {
                        newPath.append([dir, dest]);
                        pathsFound.append(newPath);
                    }
                }

                /*
                 *   if the direction property points to code, see if it provides a
                 *   valid path.
                 */

                if(loc.propType(dir.dirProp) == TypeCode)
                {
                    /* first look up the destination this code takes the actor to */
                    local dest = libGlobal.extraDestInfo[[loc, dir]];

                    /*
                     *   the destination is only of interest if it's not nowhere,
                     *   the default unknown destination, or the location we're
                     *   trying to leave.
                     *
                     *
                     *   if it's none of these, add it to the list of possible paths
                     *
                     */
                    if(dest not in (nil, loc, unknownDest_, varDest_))
                    {
                        newPath.append([dir, dest]);
                        pathsFound.append(newPath);
                    }

                }

            }
        }

        excludeLockedDoors = true
    ;

    /*
     *   The pcRouteFinder works exactly the same as the more general routeFinder
     *   except that it finds routes only through TravelConnectors whose
     *   destinations are known.
     */
    pcRouteFinder: Pathfinder
        findDestinations(cur)
        {
            /* Note the location our current path leads to */
            local loc = cur[steps - 1][2];

            /* See what leads in every available direction from this location */
            for(local dir = firstObj(Direction); dir != nil ; dir = nextObj(dir,
                Direction))
            {
                local newPath = new Vector(cur);

                /*
                 *   If the direction property points to an object, see if it points
                 *   to a valid path.
                 */
                if(loc.propType(dir.dirProp) == TypeObject)
                {
                    local conn = loc.(dir.dirProp);

                    /*
                     *   If it leads to a non-nil destination that the pc knowns,
                     *   note the path to this object. This will be the path that
                     *   got us to this location plus the one additional step.
                     */
                    local dest = conn.getDestination(loc);

                    /*
                     *   if both the location (loc) and the destination (dest) lie
                     *   in the same familiar region, then assume the pc knows
                     *   his/her way between the two rooms and so set
                     *   isDestinationKnown to true
                     */

                    if(!conn.isDestinationKnown &&
                       loc.regionsInCommonWith(dest).indexWhich(
                           {x: x.isFamiliar(gPlayerChar.knownProp)}) != nil)//
                        conn.isDestinationKnown = true;

                    /*
                     *   if the connector leads to a known destination then add the
                     *   direction and its destination to a new path
                     */

                    if(dest != nil && conn.isDestinationKnown)
                    {
                        newPath.append([dir, dest]);
                        pathsFound.append(newPath);
                    }
                }
                /*
                 *   if the direction property points to code, see if it provides a
                 *   valid path.
                 */

                if(loc.propType(dir.dirProp) == TypeCode)
                {
                    /* first look up the destination this code takes the actor to */
                    local dest = libGlobal.extraDestInfo[[loc, dir]];

                    /*
                     *   the destination is only of interest if it's not nowhere,
                     *   the default unknown destination, or the location we're
                     *   trying to leave.
                     *
                     *
                     *   if it's none of these, add it to the list of possible paths
                     *   (The fact that it's none of these implies that the
                     *   destination is known so we don't need to apply any further
                     *   tests to check that).
                     *
                     */
                    if(dest not in (nil, loc, unknownDest_, varDest_))
                    {
                        newPath.append([dir, dest]);
                        pathsFound.append(newPath);
                    }
                }
            }

        }
    ;

    /*
     *   An AskConnector is a specialized TravelConnector that leads to more than one possible
     *   destination (e.g., two doors that lie to the east) which player needs to choose between when
     *   trying to travel in the relevant direction. If routefinding finds a route through an
     *   AskConnector, the choice will be made on the player's behalf when executing a GO TO or CONTINUE
     *   commsnd.
     */
    class AskConnector: TravelConnector

        /*
         *   The list of conectore (doors, passages, stairways or whatever) that lie in the direction
         *   this AskConnector leads. There should be at least two items in this list.
         */
        options = []

        /*
         *   Our notional destination (which code may fall back on if all else fails). By default we use
         *   the first item in our options list.
         */
        destination = options[1]

        /*   Our effective location is the room we lead from. */
        effectiveLocation = lexicalParent ?? location

        /*
         *   The travel action to be used if when we ask the player to choose one of our options. This
         *   defaults to TravelVia, which is suitable for just about anything, but could be overriden to
         *   GoThrough or Enter if they seen a better choice in any given case.
         */
        travelAction = TravelVia

        /*
         *   Our destination normally depends on which of our options the player chooses, but if a route
         *   finder is trying to find a route for us, our destination needs to be whichever of our
         *   options leads to the player's desired destinations. Note that the value returned by this
         *   mathod is relevant only to the poRouteFinder when it's trying to find a path or to the exit
         *   lister when deciding how to colour exits.
         */
        getDestination(origin)
        {
             /* Cache a list of the rooms our options lead to. */
            local dests = getDestinations(origin);

            /*
             *   If the last command wasn't GO TO we're not trying to find a path. The exit lister may
             *   be trying to use us to see if the room we lead to has been visited, so return any
             *   unvisited room if we have one (so the exit lister will show there are still rooms to
             *   visit through us) or else just return the value of our destination property.
             */
            if(gAction != GoTo)
            {
                local dest = dests.valWhich({x:!x.visited});

                return dest ?? destination;
            }

            /*
             *   If we haven't already got a destination table, create it, and populate with the rooms
             *   our options immediately lead to.
             */
            if(destTab == nil)
            {
                destTab = new LookupTable();

                foreach(local dest in dests)
                    destTab[dest] = dest;
            }

            /*
             *   Note out target destionation, the room the player is trying to reach via the GO TO
             *   commasnd just issued.
             */
            local target = gDobj.getOutermostRoom;

            /*
             *   If there's already a destination (for this AskConnector) in our destination table for
             *   this target, simply return it.
             */
            local dest = destTab[target];

            if(dest)
                return dest;

            /*
             *   Otherwise recursively run through all the destinations we immediately lead to in order
             *   to establich whether any of them lies on a path to our target. If we find one, return
             *   it.
             */
            foreach(dest in dests)
            {
                local res = findDestFor(dest, target, dest);
                if(res)
                    return res;
            }

            /*
             *   If we reach here, none of our destinations is on a path to our target, so simply return
             *   the value of our destination property (which should be irrelevant to the pathfinder's
             *   calculation.
             */
            return destination;
        }

        /*
         *   Find which of the destinations led to by our options list would be on the route to target
         *   from loc and add any we find to our destTab tablle.
         */
        findDestFor(loc, target, origin)
        {
            for(local dir = firstObj(Direction); dir != nil ; dir = nextObj(dir,
                Direction))
            {
                local dests = new Vector();

                /*
                 *   If the direction property points to an object, see if it points
                 *   to a valid path.
                 */
                if(loc.propType(dir.dirProp) == TypeObject)
                {
                    local conn = loc.(dir.dirProp);

                    /*
                     *   If it leads to a non-nil destination that the pc knows, note what that
                     *   destination is.
                     *
                     */
                    local dest = conn.getDestination(loc);

                    /*
                     *   if both the location (loc) and the destination (dest) lie
                     *   in the same familiar region, then assume the pc knows
                     *   his/her way between the two rooms and so set
                     *   isDestinationKnown to true
                     */

                    if(!conn.isDestinationKnown &&
                       loc.regionsInCommonWith(dest).indexWhich(
                           {x: x.isFamiliar(gPlayerChar.knownProp)}) != nil)//
                        conn.isDestinationKnown = true;

                    /*
                     *   if the connector leads to a known destination that we haven't yet stored in our
                     *   destTab table, then add it to the destTab table (which notes that this dest can
                     *   be reached from origin, which should be one of the destinations led to by the
                     *   connectors in our options list) and append it to the list of destinations that
                     *   could be reached from loc.
                     */

                    if(dest != nil && destTab[dest] == nil && conn.isDestinationKnown)
                    {
                        destTab[dest] = origin;
                        dests.append(dest);

                        /*
                         *   If this destination is the target we're trying to reach, then return the
                         *   origin room we started out from.
                         */
                        if(dest == target)
                            return origin;

                    }
                }
                /*
                 *   if the direction property points to code, see if it provides a
                 *   valid path.
                 */

                if(loc.propType(dir.dirProp) == TypeCode)
                {
                    /* first look up the destination this code takes the actor to */
                    local dest = libGlobal.extraDestInfo[[loc, dir]];

                    /*
                     *   the destination is only of interest if it's not nowhere, the default unknown
                     *   destination, the location we're working out from, the origin we started from or
                     *   the room this AskConnector leads from.
                     *
                     *
                     *   If it's none of these, add it to the list of possible paths (The fact that it's
                     *   none of these implies that the destination is known so we don't need to apply
                     *   any further tests to check that).
                     *
                     */
                    if(dest not in (nil, loc, unknownDest_, varDest_, origin, effectiveLocation))
                    {
                        /*
                         *   If this destination has not yet been noted in out destTab, then add it to
                         *   the destTab and append it to the list of destinations directly accessible
                         *   from this location.
                         */
                        if(destTab[dest] == nil)
                        {
                            destTab[dest] = origin;
                            dests.append(dest);
                        }

                        /*
                         *   If this is our target destination, then return the origin room we started
                         *   out from (which will be one of the rooms the travel connectors in our
                         *   options list lead to.
                         */
                        if(dest == target)
                            return origin;
                    }
                }

                /*
                 *   If the list of (hopefully unvisited) destinations immediatlel leading off from this
                 *   location is greater than zero, then iterate through them calling this method
                 *   recursively.
                 */
                if(dests.length > 0)
                {
                    foreach(local dest in dests)
                    {
                        /*
                         *   We're not interested in iterating back out to the room this AskConnector
                         *   leads from, so we exclude that, but otherwise we see if we can reach our
                         *   target destination from any of the rooms in the dests list; if we return
                         *   the original room (one of those led to by one of the connectors in our
                         *   options list) to our caller.
                         */
                        if(dest != effectiveLocation)
                        {
                            local res =  findDestFor(dest, target, origin);
                            if(res)
                                return res;
                        }
                    }
                }

            }

            /*
             *   If we reach here we haven't found a path from out origin room to our destination room,
             *   so we return nil to our caller to signal our failure.
             */
            return nil;
        }

        /* Return a list of the rooms the connections listed in our options property lead to, */
        getDestinations(origin)
        {
            return options.mapAll({x: x.getDestination(origin)});
        }

        /*
         *   To execute our travel we first see if the player character is making the next move in
         *   response to a GOTO or CONTINUE command. If so then we select whichever of our options leads
         *   to a room on the way to our destination and choose that, executing its travelVia() method
         *   without any further intervention if we find a suitable choice. Otherwise we display a
         *   message listing our options and ask the player to choose which one to use.
         */
        execTravel(actor, traveler, conn)
        {
            /*
             *   If we have an options property, list the options it contains (e.g., 'that wat lies the
             *   red door and the blue door') and ask the player to specify which one to go through.
             */
            if(gActionIn(GoTo, Continue))
            {
                /* Get a list of rooms along our route. */
                local rooms = pcRouteFinder.cachedRoute.mapAll({x: x[2]});

                /* Restrict this to the list that starts from the actor's room */
                local ri = rooms.indexOf(gActor.getOutermostRoom);
                if(ri)
                    rooms = rooms.toList().sublist(ri);

                /*
                 *   The connector we want to use is the one among our options whose destination is one
                 *   of the rooms along our route.
                 */

                local connToUse
                    = options.valWhich({x: rooms.indexOf(x.getDestination(effectiveLocation))});

                /*
                 *   If we find one, then use its travelVia() method to move the actor, then return,
                 *   because we'll be done.
                 */
                if(connToUse)
                {
                    connToUse.travelVia(actor);
                    return;
                }
            }

            /* Otherwise ask the player which connector to use. */
            DMsg(multi destination, 'That way {plural}{lie} {1}. ',  makeListStr(options, &theName));
            askForDobjX(travelAction);
            return;
        }

        /*
         *   A LookUp table to cache which of our options' immediate destinations this AskConnector
         *   notionally leads to when we're on a path to any given to anu given target destination.
         */
        destTab = nil

    ;

Adv3Lite Library Reference Manual
Generated on 13/06/2025 from adv3Lite version 2.2.1