Walkable Areas and Path-finding

From Adventure Game Studio | Wiki
Jump to: navigation, search

Introduction

Knowing a few details about the inner workings of AGS's path-finding algorithm can be helpful when designing walkable areas. Some designers have been frustrated by what would seem to be random reasons for a player-character not to be able to navigate to a desired location. For instance, a player-character may be able to successfully navigate a path from one direction and not the other, resulting in the character getting stuck in portions of a room.

The Easiest and Optimal Solution

The easiest way to ensure that you have an optimized walkable area is to make certain that your area fits within the following 3x3 grid. You can expand the grid by pasting together more points at the same aspect ratio.

The engine will direct the player character along the green pixels on this grid

Alternatively, you can create your walkable areas by using a bitmap that is one third of your room size, expanding it using a nearest neighbor filter for import into your game, or you can turn on your painting program’s grid as a guide.

The image below demonstrates the repair of a broken walkable area. The cyan arrow is pointing to the offending area of the mask. A grid in this popular painting program is used to ensure that there is a clear 3x3 path through this narrow bend. The image on the right is slightly zoomed.

Editing a walkable area bitmap using a grid with image editing software.

Here is the repaired mask being successfully navigated by Captain Disaster. The bright green path on the dark green field is a part of the debugging code that was used to investigate the engine's path-finding strategy. The colors are explained later in this document.

The player-character can successfully navigate this repaired walkable area mask.

Using this grid will ensure that your walkable areas are navigable and optimized. However, if the path is laid carefully, even one-pixel paths can be used in AGS. If laid upon the grid, they can even be optimal. Although these paths are not recommend, a careful designer can create such extreme masks by knowing more about the inner workings of the path-finding system.

Engine Path-finding Strategy

When the player asks to walk to a location by clicking on a walkable area, the following steps take place:

  1. The engine calls the underlying Allegro flood-fill function to quickly test for walkability. If the color of the pixel under the player and the desired location are the same, then the area is theoretically reachable, and the engine jumps to step 3.
  2. If the flood-fill check fails, the engine looks for the closest walkable area within a 100x100px square around the desired location on a 3x3 pixel grid. If even this fails, the engine searches the entire screen on a 5x5 grid using the euclidean distance to find the closest walkable area.
  3. Following this “quick” test, Dijkstra's path-finding algorithm is used to find a solution on a 3x3 grid.
  4. If Dijkstra's algorithm fails, the engine reverts to an optimized recursive algorithm that can find a good, but non-optimal, path to the desired location. This search is capable of navigating even a single pixel, but due to the optimizations, it will not always find a solution.

Examples

Given the following mask, the room designer might be frustrated to find that the player cannot always navigate from a starting position in the lower left-hand corner to the desired location in the thin path at the top of the room.

Broken walkable area mask

In the images below, the cyan area is the walkable mask, the green area represents the nodes that were visited by Dijkstra's algorithm, and the orange pixels are those visited by the broken search that is capable of finding a one pixel path. For the sake of simplicity, we will call these searches A and B respectively.

Captain Disaster demonstrating a broken walkable area mask.

On the left, the player tried to move to the upper portion of the walkable area. The player-character informed the player that he is unable to walk to that location. Notice that Search A (the green area) failed due to the bend in the walkable area that did not neatly fit within the 3x3 search grid. The engine reverted to Search B, but due to its optimizations, it cut off the narrow path, and then considered everything above the highest orange pixel to already have been visited. Therefore, no path is found.

On the right, the player-character began on the narrow path at the mouse cursor. The player directed the player-character to walk to the location where he began in the image on the left. This time, the player-character was able to comply. The red line is the path found by Search B. As in the previous example, Search A still failed because the bend in the path from the upper area to the lower areas does not follow the 3x3 grid.

Extreme Examples

Knowing something about the inner workings of the engine will allow the possibility of following extreme paths. Even so, this is not the recommended usage of this engine that is designed primarily for “classic” point-and-click adventure games. Games created with these extreme paths may stress the target machine. Obtaining adequate performance is left to the discretion of the game designer.

In the image below, the designer chose to direct the player along a one-pixel path. Using the 3x3 grid, the designer was able to create a working and optimal path.

An extreme path.

In the next case, depicted below, the designer wanted an irregular one-pixel path to connect two larger areas.

A sub-optimal extreme path.

This worked, but since it relies upon Search B, there may be some cases where it will fail.

Captain Disaster navigating an extreme path.

Conclusion

The safest, most optimal way to design a walkable area is to make certain that the area fits within the 3x3 grid. Large flat areas pose even less problems, because path-finding is only called when the player-character does not have direct line-of-sight to the desired location. Extreme paths are possible, but they ought to be used cautiously with an eye on performance.