Absender: Michael Prähofer
Datum: Do, 27.07.2006 12:50:56
Hallo, an dem Code kann man sehen, dass ich kein sehr geuebter Java-Programmierer bin. Getestet wurde er mit hunderten von Labyrinthen, und er funktionierte immer einwandfrei. Viele Gruesse, Michael Datum: 27.07.2006 Autor: Michael Praehofer Beschreibung: Im ParcourLoader wird nach dem Laden des xml-files mit Hilfe der parcourMap die kuerzeste Verbindung vom Startpunkt des linken Bots zum Ziel bestimmt und als Polygonzug mit Breite in das Labyrinth eingezeichnet. Damit kann man den Weg den der Bot nimmt mit der Ideallinie (bei Kenntnis des ganzen Labyrinths) vergleichen. gegen Version: Stand im CVS vom 27.07.2006, Wettbewerbsversion Sonstige Voraussetzungen: keine Patchfile: shortestPath.txt Motivation: Mit dem Auge findet man recht schnell einen guenstigen Weg durch das Labyrinth. Zum Benchmarking von Bots ist es jedoch praktisch, wen der Rechner das erledigt. Ziel: Bei der statistischen Auswertung vieler Labyrinthe erleichtert die Kenntnis der kuerzesten Verbindung das Ueberpruefen der Effizienz von Strategien. _____________________________________________________________________ Der WEB.DE SmartSurfer hilft bis zu 70% Ihrer Onlinekosten zu sparen! http://smartsurfer.web.de/?mc=100071&distributionid=000000000071
### Eclipse Workspace Patch 1.0 #P ct-Sim Index: ctSim/model/ParcoursGenerator.java =================================================================== RCS file: /ctbot/ct-Sim/ctSim/model/ParcoursGenerator.java,v retrieving revision 1.3.2.1 diff -u -r1.3.2.1 ParcoursGenerator.java --- ctSim/model/ParcoursGenerator.java 15 Jul 2006 00:00:59 -0000 1.3.2.1 +++ ctSim/model/ParcoursGenerator.java 27 Jul 2006 12:28:11 -0000 @@ -150,6 +150,12 @@ + " <color type=\"specular\">#000000</color>\n" //$NON-NLS-1$ + " <color type=\"emmissive\">#000000</color>\n" //$NON-NLS-1$ + " </appearance>\n" //$NON-NLS-1$ + + " <appearance type=\"p\"><description>Linie</description>\n" //$NON-NLS-1$ + + " <color type=\"ambient\">#ff0000</color>\n" //$NON-NLS-1$ + + " <color type=\"diffuse\">#ff0000</color>\n" //$NON-NLS-1$ + + " <color type=\"specular\">#000000</color>\n" //$NON-NLS-1$ + + " <color type=\"emmissive\">#000000</color>\n" //$NON-NLS-1$ + + " </appearance>\n" //$NON-NLS-1$ + " <appearance type=\"|\"><description>Linie</description>\n" //$NON-NLS-1$ + " <clone>-</clone>\n" + " </appearance>\n" //$NON-NLS-1$ //$NON-NLS-2$ + " <appearance type=\"/\">\n" //$NON-NLS-1$ Index: ctSim/model/ParcoursLoader.java =================================================================== RCS file: /ctbot/ct-Sim/ctSim/model/ParcoursLoader.java,v retrieving revision 1.3.2.1 diff -u -r1.3.2.1 ParcoursLoader.java --- ctSim/model/ParcoursLoader.java 15 Jul 2006 00:00:59 -0000 1.3.2.1 +++ ctSim/model/ParcoursLoader.java 27 Jul 2006 12:28:11 -0000 @@ -24,6 +24,7 @@ import java.io.PrintStream; import java.util.HashMap; import java.util.Iterator; +import java.util.Vector; import javax.media.j3d.Appearance; import javax.media.j3d.BoundingSphere; @@ -38,8 +39,8 @@ import javax.media.j3d.TransformGroup; import javax.vecmath.Color3f; import javax.vecmath.Point3d; +import javax.vecmath.Vector2d; import javax.vecmath.Vector4f; - import org.w3c.dom.Attr; import org.w3c.dom.Document; import org.w3c.dom.NamedNodeMap; @@ -64,7 +65,29 @@ * @author bbe (bbe@xxxxxxxx) */ public class ParcoursLoader { + + /** Wenn true, wird der kuerzeste Weg vom 1. Startpunkt zum Ziel eingezeichnet. + * ACHTUNG: In zweifacher Hinsicht ist der Weg nicht (unbedingt) der schnellste Weg + * fuer den Bot: + * 1. Der Zeitaufwand fuer die Drehung an Knickpunkten ist nicht beruecksichtigt. + * Es koennte also einen etwas schnelleren Weg geben, der mit weniger Drehungen + * auskommt. Der Unterschied sollte allerdings recht klein sein. + * 2. Die Knickpunkte befinden sich von der zugehoerigen Ecke sqrt(2)*botradius auf + * der Diagonalen. Es wird angenommen, dass der Bot sich dort bei fixiertem + * Mittelpunkt in die neue Richtung dreht. Der Drehpunkt ist also der Botmittelpunkt. + * Geringfuegig schneller waere es wenn der Bot das Eck so anfaehrt, dass seine linke + * oder rechte Seite genau das Eck beruehrt, und sich dann auf einem Kreis, dessen + * Mittelpunkt das Eck ist in die neue Richtung dreht. + * + * Das Verhaeltnis von Bot-Radius zum Parcours-Grid ist in der Konstante + * TurningPoint.distFromCorner auf den Wert 0.25 gesetzt, d.h., der Bot schrammt ohne + * Sicherheitsabstand an den Waenden entlang. Erhoeht man ihn leicht, erhaelt man einen + * Sicherheitsabstand zu den Waenden. + */ + public static final boolean showShortestPath=true; + /** Z-Koorndinate der Lampen */ + public static final float LIGHTZ = 0.5f; /** @@ -535,7 +558,52 @@ // Soweit fertig. parse(); // Parcours Zusammenbauen - + + // Den kuerzesten Weg von Startpunkt 1 zum Ziel finden + // und eine Linie zeichnen + + if(ParcoursLoader.showShortestPath){ + // erstellt eine vereinfachte parcour map aus 0 und 1 + int[][] parcoursMapSimple = new int[this.parcours.getDimX()][this.parcours.getDimY()]; + TurningPoint start=null; + TurningPoint finish=null; + for(int i=0;i<parcoursMapSimple[0].length;i++){ + for(int j=0;j<parcoursMapSimple.length;j++){ + int c; + switch(parcoursMap[j][i]){ + case '.':c=0;break; + case ' ':c=0;break; + case '1':start=new TurningPoint(j+0.5,i+0.5);c=0;break; + case '2':c=0;break; + case '0':c=0;break; + case 'Z':if(finish==null)finish=new TurningPoint(j+TurningPoint.distFromCorner,i+1);c=0;break; + case '-':c=0;break; + case '|':c=0;break; + case '/':c=0;break; + case '\\':c=0;break; + case '+':c=0;break; + case '~':c=0;break; + default: c=1;break; + } + parcoursMapSimple[j][i]=c; + //System.out.print(parcoursMapSimple[j][i]); + } + //System.out.println() ; + } + // finde die kuerzeste Verbindung + Vector<TurningPoint> shortestPath= + start.getShortestPathTo(finish, parcoursMapSimple); + if(shortestPath==null || shortestPath.size()<2){ + System.out.println("No way from start to finish point"); + } + else{ + System.out.print("Laenge des Wegs(ohne Drehungen):"); + System.out.println(start.getLengthOfPath(shortestPath)); + for(int i=1;i<shortestPath.size();i++){ + createLine(0,0,shortestPath.get(i-1).returnLineTo(shortestPath.get(i)),getAppearance('p')); + } + } + } } catch (SAXException e) { ErrorHandler.error("Probleme beim Parsen der XML-Datei: "+filename+" : "+e); //$NON-NLS-1$ //$NON-NLS-2$ //e.printStackTrace(); Index: Changelog.txt =================================================================== RCS file: /ctbot/ct-Sim/Changelog.txt,v retrieving revision 1.24.2.4 diff -u -r1.24.2.4 Changelog.txt --- Changelog.txt 24 Jul 2006 10:38:45 -0000 1.24.2.4 +++ Changelog.txt 27 Jul 2006 12:28:11 -0000 @@ -1,5 +1,6 @@ Changelog fuer c't-Sim ====================== +2006-07-24 Michael Praehofer [mpraehofer@xxxxxx]: Klasse TurningPoint hinzugefuegt, mit der im ParcoursLoader der kuerzeste Weg eingezeichnet wird 2006-07-24 Peter Koenig [pek@xxxxxxxx]: Text der GPL eingefuegt Index: ctSim/model/TurningPoint.java =================================================================== RCS file: ctSim/model/TurningPoint.java diff -N ctSim/model/TurningPoint.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ ctSim/model/TurningPoint.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,357 @@ +package ctSim.model; + +import java.util.Vector; + +import javax.vecmath.Vector2d; + +/** + * Diese Klasse beschreibt die Position eines Knicks im Pfad des Roboters, + * wenn er an einem Hindernis abbiegt. + * Ausserdem enthaelt sie Methoden um die Kuerzeste Verbindung + * in einem ungerichteten Graphen zu finden + * @author phophermi (mpraehofer@xxxxxx) + * + */ +public class TurningPoint{ + // Der vertikale bzw. horizontale Abstand den der Mittelpunkt des Bots von + // den Waenden haelt, in grid-Einheiten. 0.25 bedeutet kein Sicherheitsabstand + public static final double distFromCorner=0.25; + + // Eingezeichnete Linienbreite der kuerzesten Verbindung in grid-Einheiten + // (0.5 entspricht bot-Durchmesser) + public static final float lineWidth=0.5f; + + // z-Koordinate der Linie: 0 entspricht Bodenhoehe, dann wird die Linie + // allerdings von Start- und Zielfeld ueberdeckt. + // Nicht getestet wurde ob der bot stolpert, wenn height>0 + public static final float height=0.0f; + + //effektiv unendlich + public static final double infinity=1e30; + Vector2d pos; + TurningPoint(double x,double y){ + pos=new Vector2d(); + pos.x=x; + pos.y=y; + } + /** + * Testet ob this mit p2 in der parcoursMapSimple auf direktem Wege vom Bot + * erreicht werden koennen + * @param p2 + * @param parcoursMapSimple + * @return true wenn direkt erreichbar + */ + boolean isDirectlyConnectedTo(TurningPoint p2,int[][]parcoursMapSimple){ + Vector2d direction=new Vector2d(p2.pos); + direction.sub(this.pos); + double rectL=(this.pos.x<p2.pos.x?this.pos.x:p2.pos.x)-(1.+distFromCorner); + double rectR=(this.pos.x>p2.pos.x?this.pos.x:p2.pos.x)+distFromCorner; + double rectD=(this.pos.y<p2.pos.y?this.pos.y:p2.pos.y)-(1.+distFromCorner); + double rectU=(this.pos.y>p2.pos.y?this.pos.y:p2.pos.y)+distFromCorner; + for(int x=0;x<parcoursMapSimple.length;x++){ + for(int y=0;y<parcoursMapSimple[0].length;y++){ + if(parcoursMapSimple[x][y]==1 && x>rectL && x<rectR && y>rectD && y<rectU){ + Vector2d corner=new Vector2d(x-distFromCorner,y-distFromCorner); + corner.sub(this.pos); + double whichside=direction.x*corner.y-direction.y*corner.x; + corner.set(x+(1.+distFromCorner),y-distFromCorner); + corner.sub(this.pos); + double sameside=direction.x*corner.y-direction.y*corner.x; + if (whichside==0)whichside=sameside; + else if (sameside*whichside<0)return false; + corner.set(x+(1.+distFromCorner),y+(1.+distFromCorner)); + corner.sub(this.pos); + sameside=direction.x*corner.y-direction.y*corner.x; + if (whichside==0)whichside=sameside; + else if (sameside*whichside<0)return false; + corner.set(x-distFromCorner,y+(1.+distFromCorner)); + corner.sub(this.pos); + sameside=direction.x*corner.y-direction.y*corner.x; + if (whichside==0)whichside=sameside; + else if (sameside*whichside<0)return false; + } + } + } + return true; + } + /** + * Euklidischer Abstand von this zu p2 + * @param p2 + * @return Euklidischer Abstand von this zu p2 + */ + double getDistanceTo(TurningPoint p2){ + Vector2d h=new Vector2d(p2.pos); + h.sub(this.pos); + return h.length(); + } + /** + * gibt die Laenge des durch path gegebenen Streckenzugs bezueglich der + * Inzidenz- (und Abstands-)Matrix M zurueck + * @param path + * @param M + * @return laenge von path bezueglich M + */ + double getLengthOfPath(Vector<Integer>path,double[][]M){ + double l=0; + if(path==null)return infinity; + else{ + if(path.size()<2) return 0; + else { + for(int i=1;i<path.size();i++) + l+=M[path.get(i)][path.get(i-1)]; + } + } + return l; + } + /** + * gibt die Laenge des durch path gegebenen Streckenzugs zurueck + * @param path + * @param M + * @return laenge von path bezueglich M + */ + double getLengthOfPath(Vector<TurningPoint>path){ + double l=0; + if(path==null)return infinity; + else{ + if(path.size()<2) return 0; + else { + for(int i=1;i<path.size();i++) + l+=path.get(i-1).getDistanceTo(path.get(i)); + } + } + return l; + } + /** + * die kuerzeste Verbindung von this zu p2 wird rekursiv bestimmt + * @param p2 Zielpunkt + * @param initialPath der bisher untersuchte Weg + * @param upperbound ist der untersuchte Weg laenger wird abgebrochen + * @param parcoursMapSimple Parcours-Array, 0 befahrbar, 1 Hindernis + * + * @return die kuerzeste Verbindung von this zu p2 unter Vermeidung von initialPath + */ + Vector<Integer> getShortestPath( + int s, + int f, + Vector<Integer> initPath, + double cutoff, + double[][]M, + int[][]N){ + if(initPath.contains(s)|| initPath.contains(f)){ + System.out.println("error"); + return null; + } + if(M[s][f]<infinity){ + if(M[s][f]<cutoff) { + Vector<Integer> path=new Vector<Integer>(); + path.add(s);path.add(f); + return path; + } + else return null; + } + else{ + Vector<Integer> minPath=null; + double minDist=cutoff; + Vector<Integer> newInitPath=new Vector<Integer>(initPath); + newInitPath.add(s); + for (int i=0;i<N[s].length;i++){ + if(!initPath.contains(N[s][i]) && M[s][N[s][i]]<cutoff){ + boolean shortcutFlag=false; + for(int j=0;!shortcutFlag && j<N[N[s][i]].length;j++){ + if(initPath.contains(N[N[s][i]][j])){ + shortcutFlag=true; + } + } + if(!shortcutFlag){ + Vector<Integer> helpPath=this.getShortestPath(N[s][i],f,newInitPath,minDist-M[s][N[s][i]],M,N); + double helpDist=getLengthOfPath(helpPath,M)+M[s][N[s][i]]; + if(helpDist<minDist){ + minDist=helpDist; + minPath=helpPath; + } + } + } + } + if(minPath!=null) minPath.insertElementAt(s,0); + return minPath; + } + } + /** + * gibt einen Polygonzug der mit Breite und einer Spitze versehen Linie + * von this zu p2 zurueck, zur Weiterverwendung in createLine() + * @param p2 + * @return {x1,y1,z1,x2,y2,z2,...,x6,y6,z6} + */ + float[] returnLineTo(TurningPoint p2){ + Vector2d offset=new Vector2d(0.5,0.5); + Vector2d length=new Vector2d(p2.pos); + length.sub(this.pos); + Vector2d halfWidth=new Vector2d(-length.y,length.x); + halfWidth.normalize(); + halfWidth.scale(lineWidth/2); + Vector2d corner=new Vector2d(this.pos); + //corner.add(new Vector2d(0.5,0.5)); + corner.sub(halfWidth); + corner.sub(offset); + float[]polygon=new float[18]; + polygon[0]=(float)corner.x; + polygon[1]=(float)corner.y; + polygon[2]=height; + corner.add(length); + polygon[3]=(float)corner.x; + polygon[4]=(float)corner.y; + polygon[5]=height; + corner.add(halfWidth); + corner.add(halfWidth); + polygon[6]=(float)corner.x; + polygon[7]=(float)corner.y; + polygon[8]=height; + corner.sub(length); + polygon[9]=(float)corner.x; + polygon[10]=(float)corner.y; + polygon[11]=height; + corner.sub(halfWidth); + Vector2d head=new Vector2d(length); + head.normalize(); + head.scale(-lineWidth/2); + corner.add(head); + polygon[12]=(float)corner.x; + polygon[13]=(float)corner.y; + polygon[14]=height; + corner.sub(halfWidth); + corner.sub(head); + polygon[15]=(float)corner.x; + polygon[16]=(float)corner.y; + polygon[17]=height; + return polygon; + } + /** + * Findet alle moeglichen Eckpunkte der kuerzesten Verbindung + * @param parcoursMapSimple + * @return eine Liste moeglicher Eckpunkte fuer die kuerzesten Verbindung + */ + Vector<TurningPoint> findTurningPoints(int[][]parcoursMapSimple){ + Vector<TurningPoint> turningPoints = new Vector<TurningPoint>(); +// turningPoints.add(new TurningPoint(start)); +// turningPoints.add(new TurningPoint(finish)); + int count=0; + for(int i=1;i<parcoursMapSimple[0].length;i++){ + for(int j=1;j<parcoursMapSimple.length;j++){ + if(parcoursMapSimple[j-1][i-1]==1 && + parcoursMapSimple[j-1][i]==0 && + parcoursMapSimple[j][i-1]==0 && + parcoursMapSimple[j][i]==0){ + turningPoints.add(new TurningPoint(j+distFromCorner,i+distFromCorner)); + count++; + } + if(parcoursMapSimple[j-1][i-1]==0 && + parcoursMapSimple[j-1][i]==1 && + parcoursMapSimple[j][i-1]==0 && + parcoursMapSimple[j][i]==0){ + turningPoints.add(new TurningPoint(j+distFromCorner,i-distFromCorner)); + count++; + } + if(parcoursMapSimple[j-1][i-1]==0 && + parcoursMapSimple[j-1][i]==0 && + parcoursMapSimple[j][i-1]==1 && + parcoursMapSimple[j][i]==0){ + turningPoints.add(new TurningPoint(j-distFromCorner,i+distFromCorner)); + count++; + } + if(parcoursMapSimple[j-1][i-1]==0 && + parcoursMapSimple[j-1][i]==0 && + parcoursMapSimple[j][i-1]==0 && + parcoursMapSimple[j][i]==1){ + turningPoints.add(new TurningPoint(j-distFromCorner,i-distFromCorner)); + count++; + } + } + } + return turningPoints; + } + /** + * Kreiert die Incidenzmatrix der Punkteliste bezueglich parcoursMapSimple + * @param turningPoints + * @param parcoursMapSimple + * @return double[i][j] ist der Abstand von Punkt i zu j, falls direkt verbunden, + * ansonsten 10e30(unendlich) + */ + double[][] createIncidenceMatrix(Vector<TurningPoint> turningPoints,int[][] parcoursMapSimple){ + int count=turningPoints.size(); + double[][]incidenceMatrix=new double[count][count]; + for(int i=0;i<count-1;i++){ + for(int j=i;j<count;j++){ + if(i==j)incidenceMatrix[i][i]=0; + else { + if(turningPoints.get(i).isDirectlyConnectedTo(turningPoints.get(j), parcoursMapSimple)){ + incidenceMatrix[i][j]=incidenceMatrix[j][i]=turningPoints.get(i).getDistanceTo(turningPoints.get(j)); + //System.out.print("*"); + } + else{ + incidenceMatrix[i][j]=incidenceMatrix[j][i]=infinity; + //System.out.print("0"); + } + } + } + //System.out.println(); + } + return incidenceMatrix; + } + /** + * Gibt eine Liste aller Punkte zusammen mit ihren direkten Nachbarn zurueck + * @param incidenceMatrix + * @return int[i].length ist die Koordinationszahl des i-ten Punktes + */ + int[][] getDirectNeighbors(double[][]incidenceMatrix){ + int count=incidenceMatrix.length; + int[][] neighbors=new int[count][]; + for (int i=0;i<count;i++) { + //System.out.print(turningPoints.get(i).pos);System.out.print(":"); + int coordination=0; + for (int j=0;j<count;j++) { + if(i!=j && incidenceMatrix[i][j]<infinity) coordination++; + } + neighbors[i]=new int[coordination]; + coordination=0; + for (int j=0;j<count;j++) { + if(i!=j && incidenceMatrix[i][j]<infinity) { + neighbors[i][coordination]=j; + coordination++; + //System.out.print(turningPoints.get(j).pos); + } + } + //System.out.println(","); + } + return neighbors; + } + /** + * gibt eine Folge von Punkten zurueck, die unter Beruecksichtigung von + * parcoursMapSimple den kuerzersten Weg von start nach finish beschreiben, + * den der bot durchfahren kann + * @param start + * @param finish + * @param parcoursMapSimple + * @return Eckpunkte der Kuerzesten Verbindung von start zu finish + */ + Vector<TurningPoint> getShortestPathTo(TurningPoint finish, + int[][]parcoursMapSimple){ + Vector<TurningPoint> turningPoints=this.findTurningPoints(parcoursMapSimple); + turningPoints.insertElementAt(finish,0); + turningPoints.insertElementAt(this,0); + // Erstellen der Inzidenzmatrix des ungerichteten Graphen + double[][]incidenceMatrix=this.createIncidenceMatrix(turningPoints, parcoursMapSimple); + // Erstellen der Tabelle der jeweils direkt erreichbaren Nachbarn + int[][] neighbors=this.getDirectNeighbors(incidenceMatrix); + // finde die kuerzeste Verbindung + Vector<Integer> shortestPath= + turningPoints.get(0).getShortestPath(0,1, new Vector<Integer>(), 1e30, incidenceMatrix, neighbors); + Vector<TurningPoint> shortest=new Vector<TurningPoint>(); + if (shortestPath!=null){ + for(int i : shortestPath){ + shortest.add(turningPoints.get(i)); + } + } + return shortest; + } +} +