Navigating Objects - Programming GPS and OpenStreetMap Applications with Java - page 129

9.4.1 Conclusion

The GameMap methods for breadth and for length demonstrate the very ba-
sics of routing and should enable you to use more sophisticated algorithms
to traverse a graph. Most implementations vary single source to single
destination, single source to multiple destinations, and multiple source to
single destination or a bidirectional combination of algorithms to meet
somewhere in the middle. Of course, navigation systems have to add the
real distance (cost) instead of finding a number of edges. (There is infinite
cost for the wrong way of a one-way street, etc.)
The A star algorithm adds the Euclidian distance from origin to desti-
nation to take the deviation into account. The algorithm can be improved
step by step to add pruning to remove branches as early as possible and
identify the better ones by some heuristic information. The routing algo-
rithm can also be supported by the map specification in the form of map
layers or aggregated segments (composite feature). In the end, no routing
algorithm is perfect and each implementation has to be fine-tuned (perfor-
mance vs. quality) and configured by the end user (avoid highways, etc.) In
most systems, the routing algorithm gets a certain slice of the CPU to allow
a maximum amount of time, before providing a route. The user of a navi-
gation system actually \feels" the time from selecting a destination until he
can start driving and the time for re-routing, when leaving the precomputed
route.
All implemented methods start from scratch, while most navigation sys-
tems have a routing thread to make better use of the provided CPU power.
A tree is built from the current origin and every branch is complemented
as far as possible. Every time a move is made the tree's origin is moved up
and alternative moves are dropped. The implementation of an extra search
thread has the advantage that the tree is not lost after a decision which
saves time.
The processing of digital maps opens the world to the real object. Start-
ing out with road maps reduces the globe's surface (500 million km 2 ) by
water (70%) and deserts (30% of land area) to the \car countries." Even
if the real object should not represent a vehicle, the world's road network
can be perceived as the modern map grid. Of course, the real-object ar-
chitecture is fit for a map of airplane trac as well or to process ship data
(search for AIS: Automatic Identification System).

9.5 The Navigator

The Navigator sums up the compilation of navigable maps and uses route
calculation on NavigatedObject s. While the MovingObject s application can