Goal-Based Vector Field Pathfinding

Understanding Goal-Based Vector Field Pathfinding https://gamedevelopment.tutsplus.com/tutorials/understanding-goal-based-vector-field-pathfinding--gamedev-9007

This article covers vector field pathfinding and its advantages over traditional pathfinding algorithms such as Dijkstra’s algorithm. A basic understanding of Dijkstra’s algorithm and potential fields will make this article easier to follow.

Introduction

There are many solutions to pathfinding, each with its own trade-offs. Many pathfinding algorithms compute a path to the destination for each individual seeker, which means the more seekers there are, the more duplicated computation you get. That’s acceptable in many cases, but when you have thousands of seekers, you need a more efficient approach.

Vector field pathfinding computes a path from the goal to every node in the graph. To reinforce the explanation, I’ll use a purpose-built example from my own implementation to explain the algorithm.

Note: vector field pathfinding can generally be abstracted to nodes and graphs; even though I use a grid here, that doesn’t mean the algorithm is limited to grid-based worlds.

Video Overview

Vector field pathfinding has three steps:

• Create a heatmap describing the path distance from every node on the map to the goal
• Create a vector field indicating the direction toward the goal.
• All particles seeking that common goal use this vector field to navigate to the goal.

The video shows the final result and gives you a comprehensive overview of the concept before the full tutorial below.

Generating the Heatmap

The heatmap stores the path distance from every point on the map to the goal point. Path distance differs from Euclidean distance in that it is the distance between two points traveling only over traversable terrain. GPS, for example, always computes path distance; to it, roads are the only traversable terrain.

Below, you can see the difference between path distance and straight-line distance. Red is the goal point, pink is a randomly picked starting point. The tiles rendered in green are impassable. As you can see, the path distance (yellow) is 9, while the white straight-line distance (light blue) is roughly 4.12.

The number in the top-left corner of each tile shows the path distance to the goal, computed by the heatmap generation algorithm. Note that there may be more than one path distance between two points; in this article we’re only interested in the shortest one.

The heatmap generation algorithm is a wavefront algorithm. It starts at the goal with a value of 0 and then flows outward to fill all traversable areas. There are two steps:

• Starting at the goal tile, mark its path distance as 0.
• Then, for each marked tile, find the unmarked neighboring tiles and mark them as previous tile's path distance + 1
• Repeat until all reachable tiles are marked.

Note: the wavefront algorithm is a breadth-first search over a grid that records how many steps it took to reach each tile along the way. It’s sometimes also called the brushfire algorithm.

Generating the Vector Field

Now that we have the path distance from each tile to the goal, we can easily determine the path to the goal. Computing it per seeker, per frame, at runtime is possible, but it’s usually better to compute the vector field once and then have all seekers reference it.

The vector field stores a vector in each tile pointing in the direction of the goal. Here’s a visualization of the vector field, with vectors pointing from the center of each tile all the way along the shortest path toward the goal (red).

The vector field is generated one tile at a time by examining the heatmap. x and y are computed separately:

Vector.x = left_tile.distance - right_tile.distance Vector.y = up_tile.distance - down_tile.distance

Note: each tile’s distance variable holds the path distance computed earlier by the wavefront algorithm.

If a referenced tile (up, down, left, or right) is unreachable and therefore has no distance data available, just use the current tile’s distance value instead. Once the path vector has been roughly computed, normalize it to avoid skewed data later on.

Seeker Movement

Now that the vector field has been computed, a seeker can easily compute its movement. Let vector_field(x,y) return the computed vector at tile (x,y), and let desired_velocity be a scalar. Here’s how to compute the velocity of a particle at tile (x,y):

velocity_vector = vector_field(x, y) * desired_velocity

The particle just needs to start moving in the direction the vector indicates. That’s the simplest approach, and a flow field can be used to implement more complex movement systems.

For example, the techniques described in Understanding Steering Behaviors can be used for seeker movement. In that case, the velocity_vector we computed above is used as the desired_velocity, and the steering behavior takes care of computing the actual movement each time step.

Local Optima

When computing movement, a problem sometimes crops up known as a local optimum. It occurs when a tile has two optimal (shortest) paths to the goal at the same time.

You can see the problem in the image below. The pink tile has a path vector whose x and y components are both 0.

Local optima cause seekers to get stuck, because they’re referencing a vector field that can’t point them in a useful direction. When this happens, the seeker stays frozen on that tile until it’s fixed.

I found that the most straightforward way to solve this problem is to subdivide the heatmap and vector field once. Each tile of the heatmap and vector field is split into 4 smaller tiles. On the subdivided grid, the problem still exists — it’s just slightly reduced.

What actually works is using the 4 subdivided sub-tiles as goal tiles instead of just 1 goal tile. To do that, we have to modify the heatmap generation algorithm from the first step. Previously we placed a single goal tile with a starting path distance of 0; now we place 4 adjacent tiles as the goal.

There are many ways to pick these 4 tiles, but which ones you choose is basically irrelevant — as long as the four tiles are adjacent and traversable, the technique works.

Here’s the modified procedure for heatmap generation:

• Start with the 4 goal tiles, marking all 4 with a path distance of 0
• Then, for each marked tile, find the unmarked neighboring tiles and mark them as previous tile's path distance + 1
• Repeat until all reachable tiles are marked.

And here’s the final result, where you can clearly see that the local optimum problem is gone.

Although this solution is very simple, it’s far from ideal. Using it means heatmap and vector field computation takes 4 times as long, because the grid is 4 times larger.

Other solutions require doing some kind of check on top of this problem to figure out which direction to go, and that check would significantly slow down particle movement computation. As for my approach, subdividing the map is probably the best option.

Summary

I hope this tutorial has taught you how to implement goal-based vector field pathfinding in a grid world. Remember, the core of this type of pathfinding is that particles move along the gradient of the tile distance function (toward the goal).

The implementation is a bit more involved, but it breaks down into three manageable steps:

• Heatmap generation
• Vector field generation
• Particle movement