You can assume from here onward that any demos using the Raven frame
work will use edge paths instead of waypoint paths.
TIP Some game worlds include teleporters or “portals” that agents can use to
move magically and instantaneously between locations. If your game makes use
of such devices, you will not be able to use the A* search algorithm to accu
rately plan paths because it’s impossible to accommodate them within the
heuristic. Instead you must utilize an alternative search algorithm such as
Quite often, and especially if a game’s navigation graph is in the shape of a
grid, the paths created by the path planner tend to contain unnecessary
edges, producing kinks like those shown in Figure 8.11. These look unnat-
ural to the human eye — after all, a human wouldn’t zigzag needlessly like
this, so it looks bad when a game agent does it. (Of course this is perfectly
acceptable if you are modeling domestic cats, which appear to have their
own secret agenda when moving from A to B J.)
Using A* and a grid-based navgraph, better-looking paths can be created
using the Manhattan distance heuristic in combination with a function that
penalizes each change in direction. (The Manhattan distance, remember, is
the sum of the number of tiles displaced horizontally and vertically
between the nodes under consideration.) However, the paths produced are
still far from ideal due to the graph’s topology restricting turns to incre
ments of 45 degrees. This method also fails with another common problem.
Practical Path Planning | 353
Paths as Nodes or Paths as Edges?
Figure 8.11. A kinky path