Given a system of nodes linked together, you want to find the shortest path from node a to node b. Since there are many paths and you search through them recursively this immediately seems like the traveling salesman problem, but it''s not. The traveling salesman problem doesn''t have a destination node, and that''s why it''s unbound.
The best way to even walk the path would be to have a "least distance to destination" measurement in each node, so you can easily select the next node in the path, as in:
class Node extends Vector {
Point position; // x,y,z of this node
double leastDistanceToDestination; // least distance to destination
Node nextNode() {
Enumeration e = elements(); // get list of links
Node nextNode = e.nextElement(); // init next node to first link
while (e.hasMoreElements()) { // for each link from this node
Node n = e.nextElement();
// set next node to n if n''s least distance is lesser
if (n.leastDistanceToDestination < nextNode.leastDistanceToDestination)
nextNode = n;
}
return nextNode;
}
}
To walk the path, the controlling program just repeatedly calls: currentNode = currentNode.nextNode();
Which automaticly selects the shortest path. Of course we still don''t know what these "least distances" are.
The algorithm to compute the least distance measurements:
The algorithm starts by setting all the leastDistanceToDestination to finite Infinity (maximum double floating point value). You can do this simply by
void resetDistances() {
if (leastDistanceToDestination < Double.MAX_VALUE) {
leastDistanceToDestination = Double.MAX_VALUE;
// recursively call all the links
for (Enumeration e = elements(); e.hasMoreElements(); ) {
Node n = e.nextElement();
n.resetDistances();
}
}
}
Then, appropriately, the destination node''s leastDistanceToDestination value is set to 0. The algorithm then recursively examines the nodes linked to the current node, starting with the destination node. If the current node''s least destination distance plus the absolute distance to the linked node is less than what''s in the linked node''s leastDistanceToDestination variable, then the algorithm updates that node''s least distance value to the newly computed value, and only then makes the recursive call on that node.
It''s easy to see that initially, since all the nodes are set to finite infinity, and the destination node''s leastDistanceToDestination is 0, each node linked to the destination will be "updated", because 0 + "real distance to linked node" < finite infinity. The program would then update these nodes'' values to whatever the 0 + "real distance to linked node" and recursively call those nodes to update the distances. This is just like resetting the distances, except you do some additional calculating.
void measureDistances() {
for (Enumeration e = elements(); e.hasMoreElements(); ) {
Node n = e.nextElement();
double computedDistance = this.leastDistanceToDestination +
(Math.sqrt((this.position - n.position)^2));
if (computedDistance < n.leastDistanceToDestination) {
n.leastDistanceToDestination = computedDistance;
n.measureDistances();
}
}
}
So, finally, the controlling program would have to do several steps to find the shortest path between two nodes.. First call "resetDistances" then "measureDistances", and finally walk the path using "nextNode" method. I hope this works for your game, I have found it pretty useful. One final note is that the algorithm is not thread safe, unless the nodes are cloned.
