Game Development Reference
In-Depth Information
Although this may seem like a reasonable solution, the best-first algorithm can of-
ten result in sub-optimal paths. Take a look at the path presented in
Figure 9.6
.
The green square is the starting node, the red square is the ending node, and grey
squares are impassable. The arrows show the greedy best-first path.
Figure 9.6
Greedy best-first path.
This path unnecessarily has the character travel to the right because, at the time,
those were the best nodes to visit. An ideal route would have been to simply go
straight down from the starting node, but this requires a level of planning the
greedy-best first algorithm does not exhibit. Most games need better pathfinding
than greedy best-first can provide, and because of this it does not see much use
in actual games. However, the subsequent pathfinding algorithms covered in this
chapter build on greedy best-first, so it is important you first understand how this
algorithm is implemented before moving on.
First, let's look at the data we need to store for each node. This data will be in
addition to any adjacency data needed in order to construct the graph. For this al-
gorithm, we just need a couple more pieces of data:
struct
Node
Node
parent
