Pathfinding via precomputed tables

Authoring TADS
1

This comes out of a discussion with @inventor200.

T3 provides pathfind.t, which does provides simple pathfinding. This is almost certainly sufficient for most people and most IF games. But if you have a bunch of complex pathing problems, dynamic room topology, dynamic NPCs that move around a lot, or want to use pathfinding for things other than rooms, you will probably find yourself wanting something a little more feature-ful.

So here’s a T3 module containing a slightly cleaned-up version of some code for this I wrote: routeTable github repo. The module depends on the simpleGraph module.

Overview of what it does (just talking about room pathfinding):

  • Defines a PreinitObject that goes through every room and creates a next-hop table for each room
  • Provides routeTableRoom.findPath(), which has the same usage as BasePathFinder.findPath() but returns paths based on table lookups (from the tables created at compile time) instead of running Dijkstra at runtime
  • Allows subdividing the map into “zones” which a) reduce the size of the next-hop tables, and b) allow runtime re-computing of just specific sections of the map if necessary
  • Allows declaration of static routes, which are used when pathfinding would otherwise fail—if pathfinding to the inside of a castle would fail because the drawbridge is up, you can define a static route that tries to route to the drawbridge instead of the originally requested location

There are examples in the module source, but I’ll provide some here as well if there’s any interest.

I’m also planning on adding a lint/debugging utility for zone declarations…to help locate unreachable locations, identify poorly-defined zones, and so on.

5 Likes
2

Yessssss!

I know what I’ll be adding for post-comp!

2 Likes
3

Just curious, but what are the issues here? To my mind path-finding should be a relatively simple process of incrementally jumping to the location in a branching fashion until you hit the destination ( A* search algorithm). Can that not be done for each NPC each turn? That would seem to resolve issues with moving NPCs and dynamic rooms. Modern computers should easily be able to do that very fast, fast enough the player will not notice.

ETA: Or is the issue that T3 was designed for old computers, and your new system does more-or-less this?

2 Likes
4

If you have NPCs doing several pathing calculations to search for strategies, or if you need to process a path calculation a few different ways to customize the text output of something, then these calculations can start to add up. If it was just one pathing calculation per NPC per turn, to go from A to B, then it would probably be fine.

There have been plenty of calculations in old projects that should have been fast on modern hardware (specifically if I implemented it in Java), but it causes the game to pause for a second or two in TADS.

So this new system utilizes a bit more memory to make large groups of NPCs be able to perform very complex pathing calculations, strategies, and informed descriptions in extremely-little time.

2 Likes
5

Sounds cool! Now I want to write a game that requires complex pathfinding.

2 Likes
6

Well, like I said most people and most games won’t need more than what T3 gives you in pathfind.t.

But T3 is slow. That’s not going to be a problem if you’re never doing more than one or two pathfinding checks a turn, and if your map is relatively small and well-behaved. But as an example, in a simple map with twelve rooms and a longest path length of 10, the pathfinding in routeTable is around twenty times faster than the Dijkstra implementation in T3’s roomPathFinder. With a random 10x10 maze the speedup is more like a factor of 2000.

There are a couple of other things that routeTable does that general pathfinding stuff generally doesn’t do, like provide the ability to path “near” a requested destination when the destination itself is unreachable. This grew out of some pathfinding for fast travel stuff that I did before—if you’ve got a fast travel system and let the player >TRAVEL TO [wherever] then if they know that the hall of mirrors is in the carnival and they know where the carnival is, then if they try to >TRAVEL TO THE HALL OF MIRRORS then they should probably end up at the ticket booth even if the carnival is currently closed. Most pathfinding approaches are all-or-nothing, and if they player is in their bedroom and you did a roomPathFinder.findPath(me, bedroom, hallOfMirrors) and a path doesn’t exist, you get nothing. The pathfinding in routeTable allows you to define “static” connections between zones, so if you define the player’s house as a zone and the carnival as a zone and the town as a zone, and define the static connections between them, then routeTableRoomRouter.findPath(bedroom, hallOfMirrors) will path to the edge of the zone closest to the intended destination.

3 Likes
7

So how did you do that? In general terms, given I do not know TADS at all, like did you add a C library or something?

2 Likes
8

There’s demo code in the module (there are a couple of simple performance test cases), but the generation logic is pretty straightforward. Here’s a standalone example:

#charset "us-ascii"
#include <adv3.h>
#include <en_us.h>

class RandomRoom: Room desc = "This is a random room. ";

PreinitObject
        _rooms = nil

        execute() {
                local i, rm;

                _rooms = new Vector(100);

                for(i = 1; i <= 100; i++) {
                        rm = new RandomRoom();
                        rm.roomName = 'room' + toString(i);
                        _rooms.append(rm);
                }

                for(i = 1; i < 100; i++) {
                        if((i % 10) == 0) {
                                _connectRooms(i, i + 10, 'n');
                        } else if(i > 90) {
                                _connectRooms(i, i + 1, 'e');
                        } else {
                                if(rand(2) == 1)
                                        _connectRooms(i, i + 10, 'n');
                                else
                                        _connectRooms(i, i + 1, 'e');
                        }
                }

                me.moveInto(_rooms[1]);
        }
        _connectRooms(n0, n1, dir) {
                local rm0, rm1;

                rm0 = _rooms[n0];
                rm1 = _rooms[n1];

                switch(dir) {
                        case 'n':
                                rm0.north = rm1;
                                rm1.south = rm0;
                                break;
                        case 's':
                                rm0.south = rm1;
                                rm1.north = rm0;
                                break;
                        case 'e':
                                rm0.east = rm1;
                                rm1.west = rm0;
                                break;
                        case 'w':
                                rm0.west = rm1;
                                rm1.east = rm0;
                                break;
                }
        }
;
me: Actor;

versionInfo: GameID;
gameMain: GameMainDef initialPlayerChar = me;

We define a Room class, just so all the rooms get a description. They’ll all be the same, but this is just a demo.

Next, we define a PreinitObject to do the map generation. We use a very simple binary tree maze generation algorithm and regular 10x10 grid. The first room is in the southwest, the 100th is in the northeast. We just generate an array of room instances, and then go through each of them and add exactly one exit, randomly deciding whether to add it to the north or east. We also check if we’re along the north edge of the map (in which case the exit has to be to the east) or the east edge of the map (in which case the exit has to be to the north), and we never touch the 100th room (which is the only one on both the north and east edges). The generated exits are always reciprocal, so whenever we add an exit to the north or east on the room we’re working on, the appropriate neighbor gets the “return” exit to the south or west.

Finally, when we’re done we stuff the player into the first room. It’s guaranteed that they have a path to the 100th room.

That’s it.

The example code in the module does an intermediate step of creating a graph containing all the rooms, but that’s just because this is a simplified version of some more elaborate procgen map stuff I’ve been working on.

4 Likes
9

Thanks, but I was more interested in your code - how you got it to run so much faster.

Also, in your 10x10 maze, it might be useful to have a small chance of exits both north and east so there are some loops and alternative routes and just check it handles that okay.

2 Likes
10

Ah. That’s mostly just what it says in the thread title: it’s precomputed. Almost all of the heavy lifting happens in a PreinitObject, which in T3 means it’s executed at compile time instead of at run time (except in debugging builds).

So during a player turn, all that’s happening is some table lookups, basically nothing is ever computed except when a) a zone is flagged for re-evaluation, and b) when something fails for some reason (and I don’t think there are any non-bug cases where this’ll happen, but if it does it should fall back to “regular” pathfinding).

If you’re looking for more of the nuts and bolts, what happens under the hood is, basically:

  • The router iterates through all the rooms, identifying which zones have been declared. At the same time it adds a default zone identifier to any rooms that were declared without one.
  • The router then creates a graph in which each zone is a vertex and the edges are connections between pairs of rooms that aren’t in the same zone (one room is in one zone, the other is in a different zone). Call each such pair a bridge.
  • The router then goes through each declared zone, creating a graph of all of the rooms in the zone, and uses the graph to generate a next-hop table for every node in the zone in relation to every other node in the zone. That is, it loops through the rooms in the zone, and for each one it computes the path between the current room and every other room in the zone, and then it remembers just the next step in the path (after itself).

Then at runtime any time there’s a pathfinding request:

  • The router makes the source endpoint the current node
  • It looks up the next hop between the current node and the destination endpoint
  • If the current node and the destination endpoint are in the same zone, then it looks up the next hop to the destination in the current node’s table, makes that the current node, and loops back to the second step
  • If the current node and the destination endpoint aren’t in the same zone, then it figures out which zone is the next step between the current zone and the zone the destination is in (this is cached in precisely the same way as room pathing is), and then it looks up the bridge between the current zone and the next zone
  • If the near side bridge location happens to be the current node, then the next hop is the “far side” location in the next zone, make it the current node and go back to step two
  • Otherwise we look up the next hop toward the near side bridge location, make it the current node, and go back to step two

This all happens in routeTableRouter.t, mostly in findpath(), which builds the return value containing the path:

        // Returns the path, if any, between the given two vertices.
        findPath(v0, v1) {
                local r, v;

                // A vector to hold the path.
                r = new Vector();

                // The first step on the path is always the starting vertex.
                v = v0;

                // We keep iterating until we get a nil vertex.
                while(v != nil) {
                        // First, add the vertex to our path.
                        r.append(v);

                        // If the current vertex is the destination vertex,
                        // the we're done.  Immediately return the path.
                        if(v == v1)
                                return(r);

                        // Get the next step in the path.
                        v = getRouteTableNextHop(v, v1);
                }

                // Return the path.  We only reach here if pathing failed.
                return(r);
        }

…and the next hop selection happens in getRouteTableNextHop():

        // Get the next hop from the first vertex to the second.
        getRouteTableNextHop(v0, v1) {
                local b, p, l, o, v;

                _debug('computing next hop from <<v0.routeTableID>>
                        to <<v1.routeTableID>>');
                // If both rooms are the in same zone, just ask the
                // room what the next hop is (it should be precomputed).
                if(v0.routeTableZone == v1.routeTableZone) {
                        _debug('returning precomputed next hop');
                        o = getRouteTableZone(v0.routeTableZone);
                        v = o.getVertex(v0.routeTableID);
                        return(v.getRouteTableNextHop(v1.routeTableID));
                }

                // Get the path from the zone the source room is in to
                // the zone the destination room is in.
                l = getRouteTableZonePath(v0.routeTableZone, v1.routeTableZone);
                if((l == nil) || (l.length < 2)) {
                        _debug('no path between zones
                                <q><<v0.routeTableZone>></q>
                                and <q><<v1.routeTableZone>></q>');
                        return(nil);
                }

                _debug('next hop zone = <<l[2]>>');

                // Get the source zone.
                v = getRouteTableZone(v0.routeTableZone);

                // Look up the bridge between the zone we're in and the
                // next zone in the path.
                if((b = v.getRouteTableBridge(l[2])) == nil) {
                        // No bridge, so now we see if there's a static
                        // route defined.

                        // First we get the vertex for the source zone.
                        v = getVertex(v0.routeTableZone);

                        // We check to see if the source zone has a
                        // static route for the next zone in the path.
                        // If not, we're done, fail.
                        if((p = v.getRouteTableStatic(l[2])) == nil)
                                return(nil);

                        // We got a static route, so we try pathing
                        // from the source vertex to the static
                        // bridge vertex.
                        return(getRouteTableNextHop(v0, p));
                }

                // If there's only one bridge, we use it.  Otherwise
                // we check the path length through each bridge and
                // select the shortest.
                // In both cases p will contain a single bridge, which
                // is a two-element array:  first element is the near-side
                // vertex in the bridge, second element is the far-side
                // vertex.
                if(b.length == 1)
                        p = b[1];
                else
                        p = selectRouteTableBridge(v0, v1, b);


                // We couldn't figure anything out, fail.
                if(p == nil)
                        return(nil);

                // If the near-side bridge vertex is the source vertex,
                // then the next step is the far-side vertex.
                if(p[1] == v0)
                        return(p[2]);

                // We DIDN'T match any bridge endpoints, so instead
                // we path to a near-side bridge endpoint.
                _debug('pathing to near side of zone bridge');
                return(getRouteTableNextHop(v0, p[1]));
        }

This also includes a couple bits I didn’t describe above: the “static route” logic, which allows you to declare a place to route to in a source zone if a valid path to the requested destination doesn’t exist, and disambiguating if there are multiple bridges between zones.

This seems like it takes a bit of explaining, but the thing to note is that all of the computational stuff…under the hood it’s plain old Dijkstra…happens at compile time, and all the other stuff is just lookups, which happen pretty quick.

Like the resolution of a timestamp in T3 is around a millisecond, so in order to have pathfinding slow enough that the elapsed time is consistently recorded as more than zero, I have to run tests in batches of thousands of lookups. Doing the same for T3’s buildin roomPathFinder logic ends up taking tens of seconds.

5 Likes
11

I just pushed a substantial update to the repo. I think the only change that’s externally facing is that routeTableRoomRouter is now called just roomRouter. A bunch of other stuff has been shuffled around internally to allow method and variable names to be less verbose without causing any collisions (it would be nice if T3 supported plugins or namespaces or something like that)—but none of that would matter unless you’re tinkering around with the module internals.

The next hop caching also got pushed into the simpleGraph module, but it was already a dependency for routeTable.

The code reorganization/cleanup was preparation for implementing some meaningful static analysis tools for e.g. room graphs (things like identifying unreachable rooms) as well as things like identifying wonky zones, suggesting more efficient ways to partition the rooms into zones, and so on. So I’m hoping to knock that stuff out fairly soon.

3 Likes
12

Just pushed a commit that automagically munges any disconnected subgraphs in the default zone into their own zones.

If that doesn’t make sense: the module always goes through all the rooms to figure out which zones to create. If a room doesn’t have an explicit zone declaration, it gets added to a default zone (that only contains rooms with no declared zone).

The potential problem arises if the default zone ends up getting split into multiple “islands” by explicitly-declared zones. Imagine you’ve got three rooms: a front yard, a back yard, and a house in the middle. You can only get to the front yard to the back yard by passing through the house, and vice versa. If you don’t declare a zone on any of these locations, fine. They’ll all end up in the default zone and it’ll work with no problems. But if for some reason you decided to declare a zone definition on only the house, then the default zone would be split in half. This would break pathfinding, because the next hop logic assumes that all the locations in a zone are contiguous.

Anyway, that’s no longer a problem because now the logic by default checks for this sort of thing, and if it encounters disconnected subgraphs like this (isolated islands that aren’t contiguous with the rest of the zone) it’ll rebuild the default zone into however many distinct zones it needs. So in this case the front yard and back yard would end up being their own zones.

That’s the major usability “gotcha” taken care of. I’ll twiddle it some more later to diagnose problems with user-declared zones as well.

3 Likes
13

I am looking at your code and I am uncertain about this segment of code in routeTable.T.

selectBridge(v0, v1, b) {
		local len, path0, path1, r, t;

		// Best candidate path so far.
		r = nil;

		// Shortest path length so far.
		len = nil;

		// Go through all the bridges.
		b.forEach(function(o) {
			// Get the path from the source vertex and
			// the near-side bridge vertex.
			if((path0 = fetchNextHopWithBridges(v0, o[1])) == nil)
				return;

			// Get the path from the far-side bridge vertex
			// and the destination vertex.
			if((path1 = fetchNextHopWithBridges(o[2], v1)) == nil)
				return;
			
			// The total length of the path through this bridge.
			t = path0.length + path1.length;

			// If we don't have a candidate path yet, or the
			// path through this bridge is the shortest, remember
			// it.
			if((len == nil) || (t < len)) {
				len = t;
				r = o;
			}
		});

		return(r);
	}

	// Get the next hop from the first vertex to the second.
	fetchNextHopWithBridges(v0, v1) {
		local b, p, l, v, z;

		_debug('computing next hop from <<v0.routeTableID>>
			to <<v1.routeTableID>>');

		// If both rooms are the in same zone, just ask the
		// room what the next hop is (it should be precomputed).
		if(v0.routeTableZone == v1.routeTableZone) {
			if((z = getZone(v0.routeTableZone)) == nil) {
				_debug('failed to lookup zone
					<<v0.routeTableZone>>');
				return(nil);
			}

			if((v = z.getVertex(v0.routeTableID)) == nil) {
				_debug('failed to get vertex for
					<<v0.routeTableID>>');
				return(nil);
			}

			// Make sure we can get a next hop.
			if((v = v.getNextHop(v1.routeTableID)) == nil) {
				_debug('failed to get next hop from
					<<v0.routeTableID>> to
					<<v1.routeTableID>>');
				return(nil);
			}

			return(z.getNode(v.id));
		}

		// Get the path from the zone the source room is in to
		// the zone the destination room is in.
		l = getZonePath(v0.routeTableZone, v1.routeTableZone);
		if((l == nil) || (l.length < 2)) {
			_debug('no path between zones
				<q><<v0.routeTableZone>></q>
				and <q><<v1.routeTableZone>></q>');
			return(nil);
		}

		_debug('next hop zone = <<l[2].id>>');

		// Get the source zone.
		v = getZone(v0.routeTableZone);

		// Look up the bridge between the zone we're in and the
		// next zone in the path.
		if((b = v.getBridge(l[2].id)) == nil) {
			// No bridge, so now we see if there's a static
			// route defined.

			// First we get the source zone.
			z = getZone(v0.routeTableZone);

			// We check to see if the source zone has a
			// static route for the next zone in the path.
			// If not, we're done, fail.
			if((p = v.getStaticRoute(l[2].id)) == nil)
				return(nil);

			// We got a static route, so we try pathing
			// from the source vertex to the static
			// bridge vertex.
			return(fetchNextHopWithBridges(v0, p));
		}

		// If there's only one bridge, we use it.  Otherwise
		// we check the path length through each bridge and
		// select the shortest.
		// In both cases p will contain a single bridge, which
		// is a two-element array:  first element is the near-side
		// vertex in the bridge, second element is the far-side
		// vertex.
		if(b.length == 1)
			p = b[1];
		else
			p = selectBridge(v0, v1, b);


		// We couldn't figure anything out, fail.
		if(p == nil)
			return(nil);

		// If the near-side bridge vertex is the source vertex,
		// then the next step is the far-side vertex.
		if(p[1] == v0)
			return(p[2]);

		// We DIDN'T match any bridge endpoints, so instead
		// we path to a near-side bridge endpoint.
		_debug('pathing to near side of zone bridge');
		return(fetchNextHopWithBridges(v0, p[1]));
	}

I understand what this code is supposed to be doing. selectBridge cycles through the list of bridges presented selecting the quickest route. From the comments in this code I see you appear to be expecting a list from fetchNextHopWithBridges. From what I can tell, the code is only returning the next step in the path. Shouldn’t findPathWithBridges be the function called here?

If I am wrong, could you explain what I am missing? This is a very nice extension, it will help In a heavy NPC goals-seeking game I have in very early development.

3 Likes
14

Yep, that’s 100% a bug. The version you quote will chuck a wobbly when it tries to compute the path length (because neither of the paths will be Vectors, and therefore both of their length properties will be nil).

I’ve just pushed an update the fixes this, as well as a test case that exercises selectBridge().

Thanks for the bug report. Let me know if you find any more.

4 Likes
15

I just pushed a minor update that adds a debugVerifyPath() method to roomRouter. It takes three arguments: the first two are rooms, and the third is a Vector or List containing the expected path. The method returns boolean true if the computed path matches the third argument, nil otherwise. Just intended to make it a little easier to write test cases.

The bridgeTest.t demo code is now updated to use debugVerifyPath() and report success or failure, instead of just outputting the computed paths.

1 Like