O'Reilly logo

Programming Game AI by Example by Mat Buckland

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

}
Bot.MoveTo(NavGraph.GetNodePosition(next.To))
}
You can assume from here onward that any demos using the Raven frame
-
work will use edge paths instead of waypoint paths.
z
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
Dijkstra’s.
Path Smoothing
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
As we have seen, before a path planner can search for a path it must find
the graph nodes closest to the start and destination positions, and these will
not always be the ones that give a natural-looking path. The solution to
both these problems is to post-process paths to “smooth” out the unwanted
kinks. There are a couple of methods for doing this — one rough and one
precise.
Path Smoothing Rough but Quick
A reasonably quick method for smoothing a path works by checking the
“passability” between adjacent edges. If one of the edges is superfluous,
the two edges are replaced with one. See Figure 8.12.
The algorithm proceeds as follows: First, two iterators, E1 and E2, are
positioned at the first and second path edges respectively. Then these steps
are followed:
1. Grab the source position of E1.
2. Grab the destination position of E2.
3. If the agent can move between these two positions unobstructed by
the world geometry, assign the destination of E1 to that of E2 and
remove E2 from the path. Reassign E2 to the new edge following E1.
(Note that this is not a simple line-of-sight test as an entity’s size must
be taken into consideration — it must be able to move between the
two positions without bumping into any walls.)
4. If the agent cannot move unobstructed between the two positions,
assign E2 to E1 and advance E2.
5. Repeat steps until the destination of E2 is equal to the destination of
the path.
354 | Chapter 8
Paths as Nodes or Paths as Edges?
Figure 8.12
Let’s see this algorithm in action and smooth the path shown in Figure
8.13. First, E1 is pointed at the first edge in the path and E2 to the second.
E1istheedgeS-1andE2theedge1-2.Wecanseethat an agent is able
to move unobstructed between E1->Source (S) and E2->Destination (2) so
the position of node index 2 is assigned to E1->Destination, the edge1-2
is removed from the path, and E2 is advanced to point to the edge2-3.
See Figure 8.14. (Notice the edge pointed to by E1 is now linkingS-2.)
Practical Path Planning | 355
Paths as Nodes or Paths as Edges?
Figure 8.13
Figure 8.14
Once again we can see that an agent is able to move unobstructed between
E1->Source (S) and E2->Destination (3), so again the path and iterators are
updated, giving the situation shown in Figure 8.15.
This time, however, the positions E1->Source (S) and E2->Destination (4)
are obstructed. Therefore, E1 and E2 are both advanced one edge. See Fig-
ure 8.16.
Again, the path between nodes 3 and 5 is obstructed so E1 and E2 are
advanced. This time, as the path between 4 and T is passable, the edges are
356 | Chapter 8
Paths as Nodes or Paths as Edges?
Figure 8.15
Figure 8.16

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required