Game Development Reference
In-Depth Information
not to the cows. If this particular game were using path nodes, it typically would
need two separate graphs: one for each type of creature. This way, the cows would
stick only to the path nodes they could conceivably use. In contrast, because each
node in a navigation mesh is a convex polygon, it would not take very many cal-
culations to determine whether or not a cow could fit in a certain area. Because of
this, we can have only one navigation mesh and use our calculations to determine
which nodes the cow can visit.
Add in the advantage that a navigation mesh can be entirely auto-generated, and
it's clear why fewer and fewer games today use path nodes. For instance, for many
years the Unreal engine used path nodes for its search space representation. One
suchUnrealenginegamethatusedpathnodeswas
Gears of War
.However,within
the last couple of years the Unreal engine was retrofitted to use navigation meshes
instead. Later games in the
Gears of War
series, such as
Gears of War 3
, used nav-
igation meshes. This shift corresponds to the shift industry-wide toward the nav-
igation mesh solution.
That being said, the representation of the search space does not actually affect
the implementation of the pathfinding algorithm. As long as the search space can
be represented by a graph, pathfinding can be attempted. For the subsequent ex-
amples in this section, we will utilize a grid of squares in the interest of simplicity.
But the pathfinding algorithms will stay the same regardless of whether the rep-
resentation is a grid of squares, path nodes, or a navigation mesh.
Admissible Heuristics
All pathfinding algorithms need a way to mathematically evaluate which node
should be selected next. Most algorithms that might be used in a game utilize a
heuristic
, represented by
h
(
x
). This is the estimated cost from one particular node
to the goal node. Ideally, the heuristic should be as close to the actual cost as pos-
sible. A heuristic is considered
admissible
if the estimate is guaranteed to always
be less than or equal to the actual cost. If a heuristic overestimates the actual cost,
there is decent probability that the pathfinding algorithm will not discover the best
route.
For a grid of squares, there are two different ways to compute the heuristic, as
shown in
Figure 9.5
.
Manhattan distance
is akin to travelling along city blocks in
a sprawling metropolis. A particular building can be “five blocks away,” but that
does not necessarily mean that there is only one route that is five blocks in length.
Manhattan distance assumes that diagonal movement is disallowed, and because
