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

For example, the Manhattan distance between the nodes v and w in Figure
5.39 is 10 (6 + 4).
The Manhattan distance gives a speed increase over the Euclidean heuristic
because no square root is required for the calculation.
Summing Up
You should now have a decent understanding of graphs and of the algo-
rithms you can use to search them. As with most AI techniques, your
understanding will grow enormously through practical experience, so I
urge you to attempt at least some of the following problems.
Practice Makes Perfect
1. Using a pencil and paper, trace out the DFS, BFS, and Dijkstra’s algo
-
rithm for the following graph. Use a different start and finish node for
each search. Extra points will be awarded for use of style and color.
The Secret Life of Graphs | 247
Summing Up
Figure 5.39. Calculating the Manhattan distance between two nodes
2. Create a Manhattan distance heuristic policy class to estimate the dis-
tance between a node and the target in a navigation graph. Try the
heuristic out with different graphs. Is it better or worse than the
Euclidean heuristic for grid-based graphs?
3. The Euclidean heuristic calculates the straight-line distance between
nodes. This calculation requires the use of a square root. Create a heu-
ristic that works in distance-squared space and note the shape of the
paths it creates.
4. Create a program to find the best solution to the n-disk Towers of
Hanoi puzzle where n can be any positive integer. To do this you must
rewrite the BFS algorithm so that nodes and edges are added to the
state graph as the search proceeds. This is an excellent way to test
your understanding of the material presented in this chapter.
5. Now modify the algorithm you created in 4 to search for the best solu
-
tion using iterative deepening DFS. How does it compare?
6. Use the A* algorithm to solve a shuffled Rubik’s Cube. Give much
consideration to the design of the heuristic function. This is a difficult
problem, searching a potentially enormous search space, so first try
your algorithm on a cube that is only one rotation away from a solu
-
tion, then two, and so on. (Tip: If you are having difficulty designing a
heuristic, do a search on the Internet… there are several interesting
papers and articles on the subject.)
248 | Chapter 5
Summing Up
Figure 5.40

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