Game Development Reference
In-Depth Information
of this it should only be used as the heuristic if this is the case. If diagonal move-
ment is allowed, Manhattan distance will often overestimate the actual cost.
Figure 9.5
Manhattan and Euclidean heuristics.
In a 2D grid, the calculation for Manhattan distance is as follows:
h
(
x
) = |
start.x - end.x
| + |
start.y - end.y
|
The second way to calculate a heuristic is
Euclidean distance
. This heuristic is
calculated using the standard distance formula and estimates an “as the crow flies”
route. Unlike Manhattan distance, Euclidean distance can also be employed in
situations where another search space representation, such as path nodes or navig-
ation meshes, is being utilized. In our same 2D grid, Euclidean distance is
Greedy Best-First Algorithm
Once there is a heuristic, a relatively basic pathfinding algorithm can be imple-
mented: the
greedy best-first search
. An algorithm is considered greedy if it does
not do any long-term planning and simply picks what's the best answer “right
now.” At each step of the greedy best-first search, the algorithm looks at all the
adjacent nodes and selects the one with the lowest heuristic.
