Pathfinding!


Lui is heavily dependant on NPCs. What I'd like-- nay, what I've always wanted in a game-- is NPCs that are doing stuff off-screen, in a consistent way. Think majoras mask: you could follow the postman around, people had different things they did at different times of day and you could (at least in town) follow them around to see what they'd do. It was a great feeling, and fun to get inside everybody's daily routine.

So I coded a pathfinding algorithm, first for the screen. This was a bit tricky because the map is laid out in 3D (you can climb up stairs, etc.) but not as tricky as you might expect. Been a long time since I coded A*.

The next part of it was coding a "global" pathfinding map. This happens on two distinct levels:

First, each area (the game is divided into old-school "screens") has to be able to extract portals; these are areas along the edge where you can leave the screen (separated by boundaries) as well as any up-down (into the underworld) links. These two type of portals always link to another map. A third type of link is "local" to the area, and serves as a named, global destination point. For instance, the center of a grove might be "forest grove 1". Next, the area calculates all possible paths between all possible portals. So you get a list of nodes and a list of edges, some of the nodes which correspond directly to nodes in another area.

Second, we have a global map which can cleverly merge nodes from an area into a global list of nodes and edges. This is possible because of how the nodes are defined, the global map has always enough information to figure out which portals on which areas should line up with each other.

In the end we get a great big global graph that is automatically updated (except for destination portals) and lets us walk from any screen to any destination portal. This will let me program every NPC in the game (including all animals, etc.) in a very very awesome way, where they can walk anywhere at any time for any reason, and you can always follow them to see where they are goin. As well, they will periodically walk in and out of the gameplay screen.

Awesome!

2007-08-31


◀ Back