Page 241 - The Definitive Guide to Building Java Robots

Preston_5564C07.fm Page 222 Monday, September 26, 2005 5:38 AM

222 CHAPTER 7 ■ NAVIGATION

Figure 7-1. A simple graph, a directed graph, and a weighted graph

To illustrate how you can use graphs with navigation, let’s take your commute to the
grocery store. You start at vertex A, and end at vertex B. For fun, let’s add a trip to the gas
station, which will be vertex C, and a trip to the automatic teller machine (ATM) for some cash,
at vertex D. If you add miles or the time it takes to get to and from each of these vertices, the
graph now becomes a weighted graph (as shown in Figure 7-1).
The graph in Figure 7-2 also has other qualities; you cannot get from the ATM or the gas
station to home without going to the grocery. So your robot program only needs to know how
to go from A to B. Then from B it just has to know how to get to C, or D.

Figure 7-2. The trip graph

To represent vertices and edges, I am going to create two classes: one Vertex with a name
field, and an Edge with a name field and two vertices. Later, I will extend these classes so that
the problems of navigation can be broken down into analyzing a path through a graph. See
Examples 7-1 and 7-2.