Game Development Reference
In-Depth Information
}
neighbor.updateF();
10. It might also be that a shorter path has been discovered since
neighbor
was cal-
culated. In this case, the neighbor should be updated again with the
current
node as
parent
. Do that and repeat the previous two steps.
11. If
neighbor
is closed, it shouldn't do anything with it.
12. Once the neighbors have been parsed, the current node should be removed from
openList
.
openList
should then be reordered according to the total cost,
F
,
of the nodes.
13. The looping of
openList
should exit, either when it's empty, or when the
goalNode
has been reached, which is indicated by when it's closed.
14. When the pathfinding is done, the shortest path can be extracted by going through
the parent nodes starting with the
goalNode
, as shown in the following code.
Reversing the resulting list will yield the best path, from
startNode
to
goalNode
. This can be implemented as follows:
private void backtrack() {
List<WaypointNode> path = new
ArrayList<WaypointNode>();
path.add(goalNode);
WaypointNode parent = goalNode;
while (parent != null) {
parent = parent.getParent();
path.add(parent);
}
}