Pathfinding
Pathfinding is a rare feature found in a few IF games. Generically, the idea is to navigate one aspect of the game from its current state through a network of other states until a destination state is reached. This route through the network is usually called a path, and finding the shortest path, or at least the next step on the shortest path, is usually what pathfinding is all about.
In the diagram to the right, there are several paths from node A to H. Of the three possible adjacent nodes from node A—that is, nodes B, C, and D—a pathfinding algorithm should choose node B, since the path A-B-H is the shortest path.
If the nodes are or states that something can be in, or statuses that they have, then the connections between them are relationships between those states. Depending on the relationships involved, they may or may not be bidirectional.
Geographic pathfinding
The most obvious use of pathfinding in geographic. The author gives the player a new way to navigate the player character to other locations simply by telling the program where the PC should go to, e.g.: GO TO TOWN SQUARE instead of providing a specific direction to travel. It becomes the program's task to figure the best route to get there and take a step in the appropriate direction, moving the PC from the current location to an adjacent location that is closer to the destination.
Nightfall (Eric Eve; 2008) provides an example of geographic pathfinding. This game offers the player the following new commands:
- GO TO location.
- GO TO object. (The object must be something that the PC has previously seen and knows where it is now.)
- CONTINUE or C.
In each case, the effect is to move the PC one room closer towards the desired destination.
Conversational pathfinding
Pathfinding can also be used by an author to steer a conversation from the current topic to an unrelated topic via a chain of related topics. For example, one might go from talking about the weather, then to bad weather, flu, ill health, health of one's father, possible death of one's father, inheritance, money, etc.
Glass (Emily Short) provides an example of conversational pathfinding. The author can use pathfinding to have NPCs segue between topics with phrases like "Speaking of topic, have you heard about new topic..." or "All this talk about topic reminds me of new topic...".
Other possibilities
Pathfinding is still fairly new to IF authors that its possibilities have barely been explored at all. A game might attempt emotional pathfinding, where one might try to make an angry NPC into a curious and helpful one, for example. Or perhaps an ambitious author might try story pathfinding, where the author manipulates events until the PC's fate is finally resolved in a successful manner, regardless of what choices the player makes.
How to code pathfinding
