Announcing the new fastPath module.
This is a refactor of the old routeTable module.
Purpose
This is an alternative to the pathfinder provideded by adv3 that precomputes pathfinding information (by default during preinit) for much faster (by multiple orders of magnitude) runtime performance.
The present module also allows you to declare and use multiple pathfinder instances, for maintaining cached pathfinding data for multiple actors, for example.
Basic Usage
First off, for most purposes just adding something like this somewhere in the game’s source will be sufficient:
pathfinder: RoomPathfinder;
This will create a pathfinder that:
- uses
gameMain.initialPlayerCharfor determining what travel connectors are and are not traversable - will generate the cache during preinit
- will automagically handle changes to pathfinding triggered by the status of
Lockabletravel connectors changing
Having declared a RoomPathfinder instance you can then compute a path via:
local path = pathfinder.findPath(room1, room2);
…where room1 and room1 are Room instances.
Tweaking Pathfinder Instances
There’s more complete API information in the module’s README, but the customizations you’re most likely to need are:
fastPathActor
Property onRoomPathfinderthat determines what actor is used to determine what’s reachable.updatePathfinder(obj)
Method onRoomPathfinderthat updates the pathfinder cache as necessary. The argument can be aThing(like a magic portal being opened) or aRoom(the place where the change occurred).
Note that you don’t have to do this for “normal” lockable doors, which will automagically update the pathfinder themselves.gUpdateFastPath(obj)
Macro that works the same as above, but updates allRoomPathfinderinstances. Only useful if you have several.
Under the Hood
The module consists of several sub-modules:
fastPathGraph
ExtendsGraph,Vertex, andEdgefrom thedataTypesmodule to do cached pathfinding. ProvidesFastPathGraph,FastPathVertex, andFastPathEdge.fastPathZone
Extends thefastPathGraphstuff above to include “zones”. A zone in this context is a subgraph in which each vertex is reachable from each other vertex without leaving the zone. That is, a path exists between the two vertices, they don’t need to be directly connected.
ProvidesFastPathMap(the overall graph),FastPathZone(for individual zones), andFastPathGateway(which enumerates the connections between zones).fastPathRoom
ExtendsfastPathZoneto work specifically withRoominstances in the gameworld instead of abstractVertexinstances.
Automagically handles figuring out which parts of the map are reachable from other parts, creating zones as necessary.
ProvidesRoomPathfinder(subclass ofFastPathMap, and usually what you want to interact with for most purposes).
This is just a quick summary; the classes and methods are more exhaustively documented in the module’s README.
Optimizing
For most games the stock behavior will probably be fine, assuming the game map isn’t particularly huge and isn’t pathological in some way I haven’t thought of. For reference, I test against a gameworld consisting of a 400 room random maze with 400 NPCs chasing each other around it. My assumption is that that’s worse than anything most people are going to try to put into a real game.
That said, it’s generally better to have larger numbers of smaller zones compared to smaller numbers of larger zones.
For example, with 400 rooms divided into four zones (in a 2x2 grid) each containing 100 rooms (in a 10x10 square) each turn takes ~0.25 seconds on my desktop, and updating zones (because some doors connecting zones became locked and some became unlocked) extends that to ~0.75 seconds. For comparison, with the stock adv3 pathfinder the same test case takes ~7-8 seconds per turn (whether or not any doors were updated).
On the other hand with 400 rooms divided into 25 zones (in a 5x5 grid) each consisting of 16 rooms (in a 4x4 square) each turn still takes ~0.25 seconds (most of this time is adv3 updating all of the moved objects, not the pathfinding itself) but on an update turn it’s only ~0.3 seconds (slightly variable because in the test case more zones means more doors opening and closing randomly, which is probably not relevant to most “real” games).
The point being that you might want to “manually” identify zones in your gameworld and mark them via declaring:
fastPathZone = 'someZoneID'
on Room instances (or subclasses).
Note that the pathfinder will still automatically “fix” zones and re-assign zone IDs if it has to. For example, say your gameworld is a house and the surrounding yard. You declare fastPathZone = 'house' on all the rooms in the house, and fastPathZone = 'yard' on all the rooms in the yard. But if the front yard is only reachable from the back yard by going through the house, then you have a zone (yard) where some parts aren’t reachable from other parts. The pathfinder will automatically, during preinit, spilt the yard zone into two zones, called something like yard-1 and yard-2.
Examples
The module includes a bunch of demos, including:
basicTest.t
Implements a simple chunk of Zork I-ish gameworld including multiple doors and one-way passages. Provides a>PATHFINDaction to illustrate asymmetric pathfinding (that is, that the path from A to B is not necessarily just the path from B to A in reverse order).
Intended to illustrate basic pathfinding (without any fancy optimizations) in a non-trivial gameworld.worstCaseTest.t
The 400 room, 400 actor test case.
Intended to be, as the name suggests, a worst case stress test.zoneTest.t
A example of non-room zone-based pathfinding.
Intended to illustrate the how to use pathfinding for things other than rooms (in my WIP I’m using this for NPC goalseeking behaviors, for example)
That’s just a couple of them, there are several others intended to test individual functions provided by the module but those probably aren’t of general interest.