## c't-Projekte - Mailinglisten

[Voriger (Datum)] [Nächster (Datum)] [Voriger (Thread)] [Nächster (Thread)]
[Nach Datum][Nach Thread]

### [ct-bot] patch Kuerzeste Verbindung

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;
    +	}
    +}
    +

- Antworten:
  - Re: [ct-bot] patch Kuerzeste Verbindung
    - From: Peter König

- Voriger (Datum): [ct-bot] Neue Patches auf der Projektseite, Peter König
- Nächster (Datum): Re: [ct-bot] patch Kuerzeste Verbindung, Peter König
- Voriger (Thread): [ct-bot] Neue Patches auf der Projektseite, Peter König
- Nächster (Thread): Re: [ct-bot] patch Kuerzeste Verbindung, Peter König
- Indizes:
  - Datum
  - Thread