Game Development Reference
In-Depth Information
be an obstruction in the way, so the pathfinding algorithm has to assume that any
location that isn't on a node or an edge is invalid.
In practice, this means that when path nodes are employed, there will be either a
lotofunusablespaceintheworldoralotofpathnodes.Thefirstisundesirablebe-
cause it results in less believable and organic behavior from the AI, and the second
is simply inefficient. The more nodes and more edges there are, the longer it will
take for a pathfinding algorithm to arrive at a solution. With path nodes, there is a
very real tradeoff between performance and accuracy.
Analternativesolutionistousea
navigation mesh
.Inthisapproach,asinglenode
in the graph is actually a convex polygon. Adjacent nodes are simply any adjacent
convex polygons. This means that entire regions of a game world can be represen-
ted by a small number of convex polygons, resulting in a small number of nodes
in the graph.
Figure 9.4
compares how one particular room in a game would be
represented by both path nodes and navigation meshes.
Figure 9.4
Two representations of the same room.
With a navigation mesh, any location contained inside one of the convex polygon
nodes can be trusted. This means that the AI has a great deal of space to move
around in, and as a result the pathfinding can return paths that look substantially
more natural.
The navigation mesh has some additional advantages. Suppose there is a game
where both cows and chickens walk around a farm. Given that chickens are much
smaller than cows, there are going to be some areas accessible to the chickens, but
