Posted on April 6, 2017
2d polygon pathfinding.
Welcome to the first post in the dev blog for Cascade Quest! You can expect semi-regular posts about behind-the-scenes implementation details, new artwork, or any other interesting updates. Let’s get started on the first topic: pathfinding!
In the original Sierra games (AGI, and early pre-VGA SCI), movement was accomplished by moving the player along straight lines: either with arrow keys, or by click-to-move with the mouse.
The character’s walkable boundaries were defined by a bitmap that indicated which pixels were walkable and which were not.
Later Sierra games (VGA SCI and up) and LucasArts’s SCUMM engine used more intelligent pathfinding to automatically route the player around obstacles. As these games were primarily played with the mouse, this more complicated implementation made sense.
Up to now, the Cascade Quest code had used the old system – only direct lines were supported. It was up to the user to move the player’s character around obstacles manually. This sort of made sense, as the keyboard is the primary input mechanism in this parser-based game.
There are problems with this though. During cutscenes, it is necessary to move the player’s character (or NPCs) to specific locations. To do so, I either need to disable collision checking for the actors, or be absolutely certain they are in a good position to reach the destination without bumping into something. Both these things are error-prone. They can result in bugs where the actor never reaches the destination and cutscene is blocked – or, in the best case, I detect this and continue the cutscene in a visually broken manner where the actor is not in a location that makes sense.
So I decided I needed to implement proper pathfinding. While back during the early Sierra days this may have been quite a magical feat (in fact, Sierra has a patent on the algorithm they use), today it’s a commonplace “solved” problem. Make a graph that connects adjacent walkable areas and run an A* algorithm over it.
A* is the easy part. Defining the walkable areas and the connections between them is the more challenging bit. Navmeshes are commonly used in 3d (or pseudo-3d) games. The latest version of Unity that I’m using supports runtime navmesh generation (and pathfinding on that navmesh), but it isn’t really suitable for me. It still requires 3d geometry (meshes or physics colliders). My source material is simply a 2d image with polygon boundaries:
A further complication is that Unity’s navmesh generation requires knowing the agent size (the radius of the character moving through the environment). So the agent’s “footprint” must be a circle. In Cascade Quest though, the characters’ footprints are wide and narrow (generally only 2 pixels high).
So basically I would rather just take my simple polygonal shapes (a collection of “barred” and “allowable” non-convex polygons) and generate a connectivity graph. One possibility is to generate a traditional navmesh by decomposing the polygon into triangles.
Another possibility is to use the concave vertices of a polygon. David Gouveia has a good article on this. Basically, by determining the interior line-of-sight connections between the concave vertices, you have all you need for pathfinding. Your start and end points (as long as they are within bounds) are guaranteed to connect to one of the concave vertices.
Here’s what this would look like for the screenshot above:
From there it’s a simple matter of determining the connection between the start/end points and the concave vertices, and then running A* over the graph nodes.
My background image editor (and engine) support three types of polygons:
- Polygons that dictate where actors can be
- Polygons that dictate where actors can’t be (these may appear inside the above polygons – for example the tree and sign-in box in the screenshots).
- Polygons where an actor can be only if the start or end point is within them (used to navigate around dangerous areas (or areas where something might be accidentally triggered)).
For the purposes of the algorithm, type 3 can be considered like type 2 if the actor is outside of them (otherwise they are ignored).
So we basically have “yes, you can be here” and “no, you can’t be here” polygons. What’s more is that these can intersect. I could force a restriction that they don’t intersect, but sometimes I dynamically generate polygons in game (for obstacles that come and go, such as doors). It’s easier if I allow for intersection. However, the algorithms discussed above don’t work if the polygons intersect. Luckily, there is an easy-to-use polygon clipping library available.
With Clipper, I can ensure I have a bunch of non-intersecting polygons, from which I can then apply the above algorithms.
Here’s a gif of it in action:
These algorithms generally function on floating point vertices. My game world deals with fairly low resolution integer values, however.
The “Pathfinding on a 2d Polygonal Map” article linked above mentions adding a tolerance to some of the calculations, but this really isn’t sufficient if your values are going to be rounded to integers and fed back into the algorithm.
In addition to paths determined by the method in this article, I also need to support traditional movement – that is, just moving in a particular direction. In this case, instead of finding a path from A to B, I need to ask the question “Am I in a valid area?”. I won’t get into the nitty-gritty details, but often a pathfinding result ends up making an actor pass through pixels that fail the “Am I in a valid area” test. Likewise, sometimes pixels that succeed the “Am I in a valid area” test result in the pathfinding algorithm failing because it can’t find a line-of-sight connection to any of the polygon’s concave vertices. To address these issues, I make the following concessions:
- In the game, I don’t run the “Am I in a valid area?” test if the actor is following a path generated by the pathfinding routines.
- When doing pathfinding, I always allow starting in an invalid area – it will generate a valid path that navigates the actor back into a valid area. This prevents the (terrible) scenario where the player would get stuck out of bounds.
- To accomplish the previous bullet point, I need to start from a point in the polygon that is valid. I perform the “Am I in a valid area?” test with a zero tolerance. If it fails, I find the closest polygon edge, and push the point a tiny amount on the other side of that edge. It will then succeed in finding a line-of-sight connection to a concave vertex (necessary for successful pathfinding).
With proper pathfinding, I can also allow the player to automatically and reliably navigate to various objects in the scene. For instance, if there’s an obvious and specific object on the ground (say, a wrench), I can automatically navigate the player over to the wrench to pick it up if they type “pick up wrench”. This is arguably better than telling the player they aren’t close enough, and require them to manually navigate there and retype their command. I’ll go over this in more detail in a subsequent post.