[Rails-commits] 18xx/rails/algorithms RevenueCalculator.java, 1.5, 1.6 RevenueAdapter.java, 1.5, 1.6 NetworkEdge.java, 1.3, 1.4 NetworkVertex.java, 1.6, 1.7

[Stefan F. <ste...@us...>]

Update of /cvsroot/rails/18xx/rails/algorithms
In directory sfp-cvsdas-4.v30.ch3.sourceforge.com:/tmp/cvs-serv8480/rails/algorithms

Modified Files:
	RevenueCalculator.java RevenueAdapter.java NetworkEdge.java 
	NetworkVertex.java 
Log Message:
First implementation to visualize revenue runs on the map

Index: RevenueCalculator.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/RevenueCalculator.java,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** RevenueCalculator.java	19 Apr 2010 19:35:38 -0000	1.5
--- RevenueCalculator.java	20 Apr 2010 19:45:40 -0000	1.6
***************
*** 30,34 ****
      private final int[] trainMaxCities;
      private final int[] trainMaxTowns;
!     private final boolean[] trainTownsCostNothing;
      private final int[] trainMultiplyCities;
      private final int[] trainMultiplyTowns;
--- 30,34 ----
      private final int[] trainMaxCities;
      private final int[] trainMaxTowns;
!     private final boolean[] trainIgnoreTowns;
      private final int[] trainMultiplyCities;
      private final int[] trainMultiplyTowns;
***************
*** 65,68 ****
--- 65,76 ----
      private RevenueAdapter revenueAdapter;
      
+     // termination results
+     private static enum Terminated {
+         WithEvaluation,
+         WithoutEvaluation,
+         NotYet
+         
+     }
+     
      protected static Logger log =
          Logger.getLogger(RevenueCalculator.class.getPackage().getName());
***************
*** 90,94 ****
          trainCities = new int[nbTrains];
          trainTowns = new int[nbTrains];
!         trainTownsCostNothing = new boolean[nbTrains];
          trainMultiplyCities = new int[nbTrains];
          trainMultiplyTowns = new int[nbTrains];
--- 98,102 ----
          trainCities = new int[nbTrains];
          trainTowns = new int[nbTrains];
!         trainIgnoreTowns = new boolean[nbTrains];
          trainMultiplyCities = new int[nbTrains];
          trainMultiplyTowns = new int[nbTrains];
***************
*** 125,132 ****
      }
      
!     void setTrain(int id, int cities, int towns, boolean townsCostNothing, int multiplyCities, int multiplyTowns) {
          trainMaxCities[id] = cities;
          trainMaxTowns[id] = towns;
!         trainTownsCostNothing[id] = townsCostNothing;
          trainMultiplyCities[id] = multiplyCities;
          trainMultiplyTowns[id] = multiplyTowns;
--- 133,140 ----
      }
      
!     void setTrain(int id, int cities, int towns, boolean ingoreTowns, int multiplyCities, int multiplyTowns) {
          trainMaxCities[id] = cities;
          trainMaxTowns[id] = towns;
!         trainIgnoreTowns[id] = ingoreTowns;
          trainMultiplyCities[id] = multiplyCities;
          trainMultiplyTowns[id] = multiplyTowns;
***************
*** 198,217 ****
  
              // encounterVertex adds value and returns true if value vertex
!             boolean trainTerminated = false; 
!             if (encounterVertex(trainId, vertexId, true)) {
!                 if (useRevenuePrediction && predictRevenues(trainId)) {
                      // cannot beat current best value => leave immediately
                      encounterVertex(trainId, vertexId, false);
                      log.debug("RC: finished startVertex " + vertexId + " for train " +trainId);
                      continue;
-                 } else  {
-                     // check usual train termination
-                     trainTerminated = trainTerminated(trainId);
                  }
              }
              
              // and all edges of it
!             boolean evaluateResult = true;
!             if (!trainTerminated) {
                  for (int j = 0; j < maxNeighbors; j++) {
                      int neighborId = vertexNeighbors[vertexId][j];
--- 206,225 ----
  
              // encounterVertex adds value and returns true if value vertex
!             Terminated trainTerminated = Terminated.NotYet; 
!             boolean valueStation = encounterVertex(trainId, vertexId, true);
!             if (valueStation) {
!                 // check usual train termination
!                 trainTerminated = trainTerminated(trainId);
!                 if (trainTerminated == Terminated.WithoutEvaluation || 
!                         trainTerminated == Terminated.NotYet && useRevenuePrediction && predictRevenues(trainId)) {
                      // cannot beat current best value => leave immediately
                      encounterVertex(trainId, vertexId, false);
                      log.debug("RC: finished startVertex " + vertexId + " for train " +trainId);
                      continue;
                  }
              }
              
              // and all edges of it
!             if (trainTerminated == Terminated.NotYet) {
                  for (int j = 0; j < maxNeighbors; j++) {
                      int neighborId = vertexNeighbors[vertexId][j];
***************
*** 219,223 ****
                      if (neighborId == -1) break; // no more neighbors
                      if (travelEdge(vertexId, neighborId, true)) {
-                         evaluateResult = false;
                          trainStartEdge[trainId] = j; // store edge
                          nextVertex(trainId, neighborId, vertexId);
--- 227,230 ----
***************
*** 227,231 ****
  
              // no more edges to find
!             finalizeVertex(trainId, vertexId, evaluateResult);
              encounterVertex(trainId, vertexId, false);
              log.debug("RC: finished startVertex " + vertexId + " for train " +trainId);
--- 234,238 ----
  
              // no more edges to find
!             finalizeVertex(trainId, vertexId, valueStation);
              encounterVertex(trainId, vertexId, false);
              log.debug("RC: finished startVertex " + vertexId + " for train " +trainId);
***************
*** 270,289 ****
  
          // 1. encounterVertex adds value and returns true if value vertex
!         boolean trainTerminated = false; 
!         if (encounterVertex(trainId, vertexId, true)) {
!             if (useRevenuePrediction && predictRevenues(trainId)) {
                  // cannot beat current best value => leave immediately
                  encounterVertex(trainId, vertexId, false);
                  returnEdge(trainId);
                  return;
-             } else  {
-                 // check usual train termination
-                 trainTerminated = trainTerminated(trainId);
              }
          }
          
          // 2a. visit neighbors, if train has not terminated
!         boolean evaluateResult = true;
!         if (!trainTerminated) {
              for (int j = 0; j < maxNeighbors; j++) {
                  int neighborId = vertexNeighbors[vertexId][j];
--- 277,296 ----
  
          // 1. encounterVertex adds value and returns true if value vertex
!         Terminated trainTerminated = Terminated.NotYet; 
!         boolean valueStation = encounterVertex(trainId, vertexId, true);
!         if (valueStation) {
!             // check usual train termination
!             trainTerminated = trainTerminated(trainId);
!             if (trainTerminated == Terminated.WithoutEvaluation ||
!                     trainTerminated == Terminated.NotYet && useRevenuePrediction && predictRevenues(trainId)) {
                  // cannot beat current best value => leave immediately
                  encounterVertex(trainId, vertexId, false);
                  returnEdge(trainId);
                  return;
              }
          }
          
          // 2a. visit neighbors, if train has not terminated
!         if (trainTerminated == Terminated.NotYet) {
              for (int j = 0; j < maxNeighbors; j++) {
                  int neighborId = vertexNeighbors[vertexId][j];
***************
*** 295,304 ****
                  }
                  if (travelEdge(vertexId, neighborId, edgeGreedy[previousId][vertexId])) {
-                     evaluateResult = false;
                      nextVertex(trainId, neighborId, vertexId);
                  }
              }
              // 2b. restart at startVertex for bottom part
!             if (trainBottomPos[trainId] == 0 && (vertexCity[vertexId] || vertexTown[vertexId])){
                  runBottom(trainId);
              }
--- 302,310 ----
                  }
                  if (travelEdge(vertexId, neighborId, edgeGreedy[previousId][vertexId])) {
                      nextVertex(trainId, neighborId, vertexId);
                  }
              }
              // 2b. restart at startVertex for bottom part
!             if (valueStation && trainBottomPos[trainId] == 0 && (vertexCity[vertexId] || vertexTown[vertexId])){
                  runBottom(trainId);
              }
***************
*** 306,310 ****
          
          // 3. no more edges to visit from here => evaluate or start new train
!         finalizeVertex(trainId, vertexId, evaluateResult);
          
          // 4. then leave that vertex
--- 312,316 ----
          
          // 3. no more edges to visit from here => evaluate or start new train
!         finalizeVertex(trainId, vertexId, valueStation);
          
          // 4. then leave that vertex
***************
*** 326,330 ****
                  trainCurrentValue[trainId] += vertexValue[vertexId] * trainMultiplyCities[trainId];
                  valueVertex = true;
!             } else if (vertexTown[vertexId]) {
                  trainTowns[trainId]++;
                  trainCurrentValue[trainId] += vertexValue[vertexId] * trainMultiplyTowns[trainId];
--- 332,336 ----
                  trainCurrentValue[trainId] += vertexValue[vertexId] * trainMultiplyCities[trainId];
                  valueVertex = true;
!             } else if (vertexTown[vertexId] && !trainIgnoreTowns[trainId]) {
                  trainTowns[trainId]++;
                  trainCurrentValue[trainId] += vertexValue[vertexId] * trainMultiplyTowns[trainId];
***************
*** 338,342 ****
                  trainCurrentValue[trainId] -= vertexValue[vertexId] * trainMultiplyCities[trainId];
                  valueVertex = true;
!             } else if (vertexTown[vertexId]) {
                  trainTowns[trainId]--;
                  trainCurrentValue[trainId] -= vertexValue[vertexId] * trainMultiplyTowns[trainId];
--- 344,348 ----
                  trainCurrentValue[trainId] -= vertexValue[vertexId] * trainMultiplyCities[trainId];
                  valueVertex = true;
!             } else if (vertexTown[vertexId] && !trainIgnoreTowns[trainId] ) {
                  trainTowns[trainId]--;
                  trainCurrentValue[trainId] -= vertexValue[vertexId] * trainMultiplyTowns[trainId];
***************
*** 394,416 ****
      }
      
!     private boolean trainTerminated(int trainId) {
!         boolean terminated;
!         if (trainTownsCostNothing[trainId]) {
!             terminated = trainCities[trainId] == trainMaxCities[trainId];
          } else if (trainTowns[trainId] == 0) {
              // default train
!             terminated = trainCities[trainId] + trainTowns[trainId] == trainMaxCities[trainId];
          } else {
              // plus trains
!             int townDiff = trainMaxTowns[trainId] - trainTowns[trainId];
!             if (townDiff > 0) {
!                 terminated = false;
!             } else if (townDiff == 0) {
!                 terminated = trainCities[trainId] == trainMaxCities[trainId];
!             } else { // negative townDiff, thus too many towns already visited
!                 terminated = trainCities[trainId] == trainMaxCities[trainId] + townDiff;
!             }
          }
!         if (terminated) {
              log.debug ("RC: Train " + trainId + " has terminated: " +
              		"cities = " + trainCities[trainId] + " towns = " + trainTowns[trainId] +
--- 400,422 ----
      }
      
!     private Terminated trainTerminated(int trainId) {
!         Terminated terminated = Terminated.NotYet;
!         if (trainIgnoreTowns[trainId]) {
!             // express trains
!             if (trainCities[trainId] == trainMaxCities[trainId])
!                 terminated = Terminated.WithEvaluation;
          } else if (trainTowns[trainId] == 0) {
              // default train
!             if (trainCities[trainId] + trainTowns[trainId] == trainMaxCities[trainId])
!                 terminated = Terminated.WithEvaluation;
          } else {
              // plus trains
!             if (trainCities[trainId] > trainMaxCities[trainId]){
!                 terminated = Terminated.WithoutEvaluation;
!             } else if (trainCities[trainId] + trainTowns[trainId] == 
!                 trainMaxCities[trainId] + trainMaxTowns[trainId] )
!                 terminated = Terminated.WithEvaluation;
          }
!         if (terminated != Terminated.NotYet) {
              log.debug ("RC: Train " + trainId + " has terminated: " +
              		"cities = " + trainCities[trainId] + " towns = " + trainTowns[trainId] +
***************
*** 474,481 ****
                  trainValue =  maxTrainRevenues[j];
              } else { // the current train
!                 if (trainTownsCostNothing[j]) {
!                     // still TODO
!                     trainValue = 0;
!                 } else if (trainTowns[j] == 0) {
                      // default train
                      trainValue = trainCurrentValue[j] + 
--- 480,484 ----
                  trainValue =  maxTrainRevenues[j];
              } else { // the current train
!                 if (trainMaxTowns[j] == 0) {
                      // default train
                      trainValue = trainCurrentValue[j] + 
***************
*** 524,527 ****
--- 527,531 ----
          buffer.append("trainMaxCities:" + Arrays.toString(trainMaxCities) + "\n"); 
          buffer.append("trainMaxTowns:" + Arrays.toString(trainMaxTowns) + "\n"); 
+         buffer.append("trainIgnoreTowns:" + Arrays.toString(trainIgnoreTowns) + "\n"); 
          buffer.append("maxCityRevenues:" + Arrays.toString(maxCityRevenues) + "\n"); 
          buffer.append("maxTownRevenues:" + Arrays.toString(maxTownRevenues) + "\n"); 

Index: NetworkVertex.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkVertex.java,v
retrieving revision 1.6
retrieving revision 1.7
diff -C2 -d -r1.6 -r1.7
*** NetworkVertex.java	16 Apr 2010 16:38:21 -0000	1.6
--- NetworkVertex.java	20 Apr 2010 19:45:40 -0000	1.7
***************
*** 1,4 ****
--- 1,5 ----
  package rails.algorithms;
  
+ import java.awt.geom.Point2D;
  import java.util.Collection;
  import java.util.Comparator;
***************
*** 14,17 ****
--- 15,20 ----
  import rails.game.Station;
  import rails.game.TokenI;
+ import rails.ui.swing.hexmap.GUIHex;
+ import rails.ui.swing.hexmap.HexMap;
  
  public final class NetworkVertex implements Comparable<NetworkVertex> {
***************
*** 28,31 ****
--- 31,35 ----
      
      private final Station station;
+     private final City city;
      private final int side;
      
***************
*** 51,54 ****
--- 55,59 ----
          if (t.equals(Station.TOWN)){
              this.tokenable = false;
+             this.city = null;
          } else {
              this.tokenable = true;
***************
*** 57,62 ****
--- 62,69 ----
              this.tokenSlots = 0;
              List<City> cities = hex.getCities();
+             City foundCity = null;
              for (City city:cities) {
                  if (station == city.getRelatedStation()) {
+                     foundCity = city;
                      tokens = city.getTokens();
                      this.tokenSlots = city.getSlots();
***************
*** 64,67 ****
--- 71,75 ----
                  }
              }
+             this.city = foundCity;
              this.companiesHaveToken = new HashSet<PublicCompanyI>();
              if (tokens != null) {
***************
*** 80,83 ****
--- 88,92 ----
          this.hex = hex;
          this.station = null;
+         this.city = null;
          this.side = (side % 6);
          
***************
*** 92,95 ****
--- 101,105 ----
          this.hex = null;
          this.station = null;
+         this.city = null;
          this.side = 0;
          
***************
*** 133,136 ****
--- 143,151 ----
      }
      
+     public City getCity() {
+         return city;
+     }
+     
+     
      public int getSide(){
          return side;
***************
*** 256,259 ****
--- 271,288 ----
              v.setPhase(phase);
      }
+ 
+     public static Point2D getVertexPoint2D(HexMap map, NetworkVertex vertex) {
+         GUIHex guiHex = map.getHexByName(vertex.getHex().getName());
+         if (vertex.isCityType()) {
+             return guiHex.getCityPoint2D(vertex.getCity());
+         } else if (vertex.isTownType()) {
+             return guiHex.getCenterPoint2D();
+         } else if (vertex.isSide()) {
+             return guiHex.getSidePoint2D(vertex.getSide());
+         } else {
+             return null;
+         }
+     }
+     
      
  }

Index: RevenueAdapter.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/RevenueAdapter.java,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** RevenueAdapter.java	19 Apr 2010 19:35:38 -0000	1.5
--- RevenueAdapter.java	20 Apr 2010 19:45:40 -0000	1.6
***************
*** 2,5 ****
--- 2,8 ----
  
  import java.awt.EventQueue;
+ import java.awt.Graphics2D;
+ import java.awt.geom.GeneralPath;
+ import java.awt.geom.Point2D;
  import java.util.ArrayList;
  import java.util.Arrays;
***************
*** 20,23 ****
--- 23,27 ----
  import rails.game.TokenI;
  import rails.game.TrainI;
+ import rails.ui.swing.hexmap.HexMap;
  
  
***************
*** 203,207 ****
          String t = trainString.trim();
          
!         int cities = 0; int towns = 0; boolean townsCostNothing = false; int multiplyCities = 1; int multiplyTowns = 1;
          if (t.equals("D")) {
              cities = 99; // diesel
--- 207,211 ----
          String t = trainString.trim();
          
!         int cities = 0; int towns = 0; boolean ignoreTowns = false; int multiplyCities = 1; int multiplyTowns = 1;
          if (t.equals("D")) {
              cities = 99; // diesel
***************
*** 212,221 ****
              // express train
              cities = Integer.parseInt(t.replace("E", ""));
!             townsCostNothing = true;
              multiplyTowns = 0;
          } else if (t.contains("D")) {
              // double (express) train
              cities = Integer.parseInt(t.replace("D", ""));
!             townsCostNothing = true;
              multiplyCities = 2;
              multiplyTowns = 0;
--- 216,225 ----
              // express train
              cities = Integer.parseInt(t.replace("E", ""));
!             ignoreTowns = true;
              multiplyTowns = 0;
          } else if (t.contains("D")) {
              // double (express) train
              cities = Integer.parseInt(t.replace("D", ""));
!             ignoreTowns = true;
              multiplyCities = 2;
              multiplyTowns = 0;
***************
*** 224,228 ****
              cities = Integer.parseInt(t);
          }
!         NetworkTrain networkTrain = new NetworkTrain(cities, towns, townsCostNothing, multiplyCities, multiplyTowns, t); 
          trains.add(networkTrain);
      }
--- 228,232 ----
              cities = Integer.parseInt(t);
          }
!         NetworkTrain networkTrain = new NetworkTrain(cities, towns, ignoreTowns, multiplyCities, multiplyTowns, t); 
          trains.add(networkTrain);
      }
***************
*** 312,315 ****
--- 316,343 ----
      }
      
+     public void drawOptimalRunAsPath(HexMap map) {
+         List<GeneralPath> pathList = new ArrayList<GeneralPath>();
+         Map<NetworkTrain, List<NetworkVertex>> run = getOptimalRun();
+         
+         for (NetworkTrain train:run.keySet()) {
+             GeneralPath path = new GeneralPath();
+             NetworkVertex startVertex = null;
+             for (NetworkVertex vertex:run.get(train)) {
+                 Point2D vertexPoint = NetworkVertex.getVertexPoint2D(map, vertex);
+                 if (startVertex == null) {
+                     startVertex = vertex;
+                     path.moveTo((float)vertexPoint.getX(), (float)vertexPoint.getY());
+                     continue;
+                 } else if (startVertex == vertex) {
+                     path.moveTo((float)vertexPoint.getX(), (float)vertexPoint.getY());
+                     continue;
+                 } 
+                 if (vertexPoint != null)
+                     path.lineTo((float)vertexPoint.getX(), (float)vertexPoint.getY());
+             }
+             pathList.add(path);
+         }
+         map.setTrainPaths(pathList);
+     }
      
      @Override

Index: NetworkEdge.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkEdge.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** NetworkEdge.java	13 Apr 2010 23:21:12 -0000	1.3
--- NetworkEdge.java	20 Apr 2010 19:45:40 -0000	1.4
***************
*** 1,4 ****
--- 1,10 ----
  package rails.algorithms;
  
+ import java.awt.Shape;
+ import java.awt.geom.Line2D;
+ import java.awt.geom.Point2D;
+ 
+ import rails.ui.swing.hexmap.HexMap;
+ 
  public final class NetworkEdge {
      
***************
*** 51,55 ****
        return source + " - >" + target;
      }
!     
      @Override
      // set to "" to faciltate visual graph
--- 57,61 ----
        return source + " - >" + target;
      }
! 
      @Override
      // set to "" to faciltate visual graph
***************
*** 61,63 ****
--- 67,82 ----
      }
      
+     public static Shape getEdgeShape(HexMap map, NetworkEdge edge){
+         Point2D source = NetworkVertex.getVertexPoint2D(map, edge.getSource());
+         Point2D target = NetworkVertex.getVertexPoint2D(map, edge.getTarget());
+         Shape edgeShape;
+         if (source != null && target != null) {
+             edgeShape = new Line2D.Double(source, target);
+         } else {
+             edgeShape = null;
+         }
+         return edgeShape;
+     }
+ 
+     
  }