Global Positioning System Reference
In-Depth Information
proprietary implementation and best-kept secret of each system is the black
box for the cost calculation. A full-fledged navigation system can combine
computations about time and distance, consider time of day, day of week,
speed limit, restrictions, and real-time trac information (TMC, trac
message channel, etc.).
9.4
Exploring the Graph with a
GameMap
For a basic understanding of (or as a starting point for) routing algorithms,
the next practical steps will be implemented in a
GameMap
. The idea is to
use the
NavigableMap
to set up the graph and then use the
GameMap
to tra-
verse the graph without considering heuristic costs. On a game board, each
edge can be related to one move, regardless of its distance. Mathematical
formulas are avoided in favor of discrete node IDs without location informa-
tion. The cost, considering vehicle type, dynamic barriers, time and speed
dependency, preprocessed hints, etc.
could be added later by consulting
the
NavigableMap
.
Again, we suggest that you run the main method of
roaf.book.navigation.GameMap
hard-coded to
../resources/gps/GER
/germany.net.osm
for a preview.
Class Design
The
GameMapextendsNavigableMap
and overrides the constructor, which
creates a graph from an OSM file (i.e.,
germany.net.osm
) as described in
Section 8.4.2. Since the creation of the graph is private to the
NavigableMap
,
the reader can focus on its
protected
and
public
members and methods.
getNodeMap()
. First, the main method retrieves the node map via
navMap
.getNodeMap()
(see page 115), which supplies all addressable origin and
destination nodes of the network. In order to find the way from node O
to node D, two search strategies can be used: search by depth or search
by breadth. Most navigation systems implement shortest path algorithms
by searching many destinations from the origin and vice versa. The search
results are combined in a distance matrix for all vertices (nodes) of the
graph. Shortest times can be derived by dividing the lengths of links by
speed (map feature).
All links have indexes of the network and their names and number can
be retrieved via the string array
linkFeatures
.
Search WWH ::
Custom Search