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

from the origin over all moves and retrieve one node for every move. As
soon as a queue is empty, the next one is filled until they are all used up.
Sometimes a look at the data (structures) is more helpful than the pseu-
docode. The graph is transformed into a tree view from the origin's per-
spective:

graph -> tree view -> collection view -> move loop
currPath[] queues[]
origin: 1 move#: 1 2 3 [0] = origin
move# / | \ : 1 2 5 11 [1] = [0]
1 2 3 4 currPath 1 2 6 X :
/| / \ |\ : 1 3 7 12 [2] = [1]
2 5 6 7 8 9 10 : : : : : :
| / \ | | \ : 1 4 10 16 [moves] =
3 11 12 13 14 15 16 path [0][1][2][3] [moves-1]

The GameMap implementation traverses all paths. For an effective navigation
system, this search should be optimized (by removing visited nodes, etc.),
since even the germany.net.osm map has more than two million paths for
only nine moves.
Depending on the application, an additional feature filter could be added
for each method:

getDestinations( origin, nrMoves, feature )
getMinimumMoves( origin, destination, feature )
getPaths( origin, destination, feature )

Finally, after the node IDs are determined, the actual route can be retrieved
from the map links provided by the NavigableMap .

validateMap() . This method is private and can be used to handle quality
control for a digital map. Nevertheless, this method is a very optimistic
brute-force method traversing all connections of the graph. Note that the
GameMap.main method includes a validation of the entire network and takes
about three minutes. Of course this line can be commented out. As the
map gets larger, the validation time approaches infinity. In order to validate
only one entire city, large machines, search strategies, and network layers
come into play.

findNodeID(Positionpos) . This method is basically for use with a
visual map. Since it is practically impossible to click on the precise lat
and lon values of a node, there has to be a mechanism to find the closest
node to a given point. Usually this requires yet another collection of all
the nodes, where each node can be looked up with a spatial index. For the
time being (and for a small number of nodes), the method implements a
simple, although slow, loop over all nodes. 1

1 Check out the java spatial index, jsi, at sourceforge.net/projects/jsi .