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!

Character movement

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.

Proper pathfinding

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:

 

Walkable area bounds

Walkable area bounds

 

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:

 

Concave vertex connections

Concave vertex connections

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.

Implementation

My background image editor (and engine) support three types of polygons:

  1. Polygons that dictate where actors can be
  2. 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).
  3. 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:

 

Pathfinding

Pathfinding from one spot to another. The green star is the target, the red stars are the intermediate points.

Robustness

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).

Other notes

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.

 

Getting a branch

Auto-navigating the player somewhere to perform an action.

9 Comments on “2d polygon pathfinding.

  1. This thing isn’t gonna work on an original SCI0 engine at all, isn’t it?

      • Compare and contrast my game, which is like… five kernel calls at most and maybe a color replacement away 🙂

          • Do you have a list for the rest of us to look at?

            In the interest of fair trade, mine’s a single entry with subcommands:
            0 – show a message like you’d get when for example trying to play a missing video file
            1 – invert a range of palette indices
            2 – set title bar colors (near-useless when you have BorderWindows)
            3 – return debug/menu availability
            And DrawPic has a half-functional transition speed parameter now that should be ignored by other terps.

          • Good stuff. I have, roughly:
            – defining color mapping (one color to another) based on tint and hue/sat/lum adjustment
            – setting a color mapping as the current one
            – 3 separate Said extensions that target the three parts of parsing
            – Memory, Sort and AvoidPath kernels, ala SCI1.1
            – 5 kernel calls related to saving/loading games
            – DebugInfo, to get various performance and debug metrics so they can be displayed in game
            – IsKindOf, a faster kernel implementation of the SCI method
            – PostProcess to add post-processing fx (rain particles, screen wobble, etc)
            – Some calls to handle joysticks/controls/keyboard better
            – stuff for autosuggest functionality
            – stuff to take a screenshot for savegames
            – ScriptId that doesn’t crash if the script isn’t available (e.g. non-critical ScriptId)
            – hokey support for reserving a part of the screen for some 3d stuff (unclear if I’ll use this)
            – set menu colors
            – set current reverb (from a fixed set tailored to different environments.. so footsteps will automatically echo if you’re in a cave, for instance).
            – set pic transition time

          • Or perhaps for “teleport to room” functionality that doesn’t crash if I type in a number wrong…

  2. Pingback: Overlapping path finding regions – Cascade Quest blog

Leave a Reply

Your email address will not be published. Required fields are marked *