A Pathfinding Optimization Using Flood Fill

Pathfinding in games usually boils down to answering the question: "What is the shortest route from point A to point B?" In most games, however, this simple question is complicated by the addition of other constraints, such as the need to avoid moving objects or maintain formation. In this post, I describe a technique used to tackle the most basic question: "Does any path exist from point A to point B?"

An Example

Let's consider the case of a two-dimensional real-time strategy game (RTS). Starcraft is an example of one such game. In a 2D RTS, the map is generally subdivided into square cells. These cells (also called tiles) are assigned different textures, so they look like grass, trees, sand, mountains, water, etc. For basic pathfinding, however, the only important cell property is whether it is walkable or non-walkable. Below is a simple map in which the white cells are walkable and the black cells are non-walkable. Consider the black cells to be walls. Let's also assume that a character on the map can only move in four directions: up, down, left, and right.

One way to determine if it's possible to move from one cell to another is to assign each connected region a unique color before the game begins. Then, the only necessary step is to compare the colors of A and B. If the colors match, a path exists. Otherwise, no path exists.

The Steps
To color the initial map, we perform a raster scan. In the example below, we start at the top left cell and move across the row. At the end of the row, we continue to the leftmost cell of the row below it. Whenever an uncolored, walkable cell is reached, we perform the flood fill operation using a unique color.

In most games, walls can either be built or destroyed. When a wall is built, a connected region may be split into two or more regions. In order to recolor the map it is necessary to examine each of the four neighbors and flood fill them with a new, unique color. When a wall is destroyed, it is possible that two or more distinct regions become connected. In this case, we use a single color to flood fill the previously distinct regions.

It is important to note that common pathfinding algorithms such as A* approach their worst case run time when a path does not exist. Using this technique will prevent the worst case scenario, at the cost of using additional memory. The technique can also be used to implement features such as: highlighting the region that a selected unit is in or changing the mouse cursor to an X when it is over a cell the selected unit cannot find a path to.

The same methods can be used on any type of graph, not just a grid based one. If you are using walk meshes or waypoints, the same techniques can still be applied.