From cae4043e82e330f6b440cac5a14c8b389ad0386a Mon Sep 17 00:00:00 2001
From: Victor Zamanian <victor.zamanian@gmail.com>
Date: Sat, 8 Nov 2008 01:26:11 +0100
Subject: [PATCH] Added dynamic road top speed; removed "Path to goal" from
 return string; fixed A* fastest(?).

---
 src/MySearcher.java | 57 +++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 40 insertions(+), 17 deletions(-)

diff --git a/src/MySearcher.java b/src/MySearcher.java
index ea4fa5c..18d71c8 100644
--- a/src/MySearcher.java
+++ b/src/MySearcher.java
@@ -16,12 +16,14 @@ import org.jdom.*;
  */
 public class MySearcher extends MapSearcher {
    private Graph map;
+   private int topSpeed;
 
    /**
     * Skapar en ny MySearcher-instans.
     */
    public MySearcher () {
       super ();
+      topSpeed = 1;
    }
 
    /**
@@ -69,6 +71,9 @@ public class MySearcher extends MapSearcher {
                Road road =
                   new Road(Integer.parseInt(roadElement.getAttributeValue("speed")),
                            distance);
+               if (road.getSpeed() > topSpeed) {
+                   topSpeed = road.getSpeed();
+               }
                map.insertEdge(cityNode.getName(),
                               nodeAtEndOfRoad.getName(),
                               road);
@@ -124,7 +129,7 @@ public class MySearcher extends MapSearcher {
             }
             pathToGoal = n.getName() + ", " + pathToGoal; // Beginning
             System.out.println("\nAll expanded nodes:\n" + expandedNodes + "\n\n");
-            return "Path to goal:\n" + pathToGoal + "\n";
+            return pathToGoal;
          }
          // 5. Otherwise add the children of n to N,
          GraphNode neighbour;
@@ -157,12 +162,14 @@ public class MySearcher extends MapSearcher {
    public String aStar (String from, String to, boolean fastest) {
       String pathToGoal = "",
          expandedNodes = "";
+
       // 1. Set N to be a sorted list of initial nodes;
       PriorityQueue<GraphNode> queue =
          new PriorityQueue<GraphNode>(this.map.size());
       // Set fromNodes distance to 0.0
       map.getNode(from).setDistanceTraveled(0.0);
       queue.add(map.getNode(from));
+
       GraphNode n;
       while (!queue.isEmpty()) { // 2. If N is empty,
          // 3. set n to be the first node in N, and remove n from N;
@@ -181,36 +188,52 @@ public class MySearcher extends MapSearcher {
             }
             pathToGoal = n.getName() + ", " + pathToGoal; // Beginning
             System.out.println("\nAll expanded nodes:\n" + expandedNodes + "\n\n");
-            return "Path to goal:\n" + pathToGoal + "\n";
+            return pathToGoal;
          }
+
          // 5. Otherwise add the children of n to N,
          GraphNode neighbour;
          for (Enumeration<GraphNode> e = n.getNeighbours();
               e.hasMoreElements();) {
             neighbour = e.nextElement();
+
             if (fastest) {
+                Double neighbourEval = n.getDistanceTraveled()
+                   + ((Road) n.getEdge(neighbour)).getTravelTime()
+                   + neighbour.getDistanceToGoal() / (topSpeed / 3.6);
+
+               if (neighbourEval < neighbour.getEvalFuncVal()) {
+                   neighbour.setDistanceTraveled(n.getDistanceTraveled()
+                           + ((Road) n.getEdge(neighbour)).getTravelTime());
+                   neighbour.setDistanceToGoal(map.getNode(to));
+                   neighbour.setEvalFuncVal(neighbour.getDistanceTraveled()
+                           + neighbour.getDistanceToGoal() / (topSpeed / 3.6));
+
+                   if (queue.contains(neighbour)) {
+                       queue.remove(neighbour);
+                       queue.add(neighbour);
+                   } else if (!neighbour.isVisited()) {
+                       queue.add(neighbour);
+                   }
+                   neighbour.setParent(n);
+               }
+
+            } else {
                neighbour.setDistanceTraveled(n.getDistanceTraveled()
-                                             + ((Road) n.getEdge(neighbour)).getTravelTime());
-               neighbour.setDistanceToGoal(map.getNode(to));
-               neighbour.setEvalFuncVal(neighbour.getDistanceTraveled()
-                                        + neighbour.getDistanceToGoal() / (110 / 3.6));
-            }
-            else {
-               neighbour.setDistanceTraveled(n.getDistanceTraveled()
-                                             + ((Road) n.getEdge(neighbour)).getDistance());
+                    + ((Road) n.getEdge(neighbour)).getDistance());
                neighbour.setDistanceToGoal(map.getNode(to));
                neighbour.setEvalFuncVal(neighbour.getDistanceTraveled() +
                                         neighbour.getDistanceToGoal());
-            }
-
-            // sort the nodes in N according to the value on their
-            // evaluation function
-            //else if (!queue.contains(neighbour)) {//&& !neighbour.isVisited()) {
             if (!neighbour.isVisited()) {
                neighbour.setParent(n);
                queue.add(neighbour);
                // and return to step 2. (end of loop)
             }
+            }
+
+            // sort the nodes in N according to the value on their
+            // evaluation function
+            //else if (!queue.contains(neighbour)) {//&& !neighbour.isVisited()) {
          }
       }
       System.out.println();
@@ -255,7 +278,7 @@ public class MySearcher extends MapSearcher {
             }
             pathToGoal = n.getName() + ", " + pathToGoal; // Beginning
             System.out.println("\nAll expanded nodes:\n" + expandedNodes + "\n\n");
-            return "Path to goal:\n" + pathToGoal + "\n";
+            return pathToGoal;
          }
          //   * Otherwise push all the (so-far-unexamined) successors
          //   * (the direct child nodes) of this node into the end of
@@ -305,7 +328,7 @@ public class MySearcher extends MapSearcher {
             }
             pathToGoal = n.getName() + ", " + pathToGoal; // Beginning
             System.out.println("\nAll expanded nodes:\n" + expandedNodes + "\n\n");
-            return "Path to goal:\n" + pathToGoal + "\n";
+            return pathToGoal;
          }
          //   * Otherwise push all the unvisited connecting nodes of n
          else {
-- 
2.11.4.GIT