Hallo,
Ich habe folgendes Problem:
Ich habe ein Programm, dass für einen Roboter selbständig den kürzesten Weg durch ein Labyrinth finden soll. Das Labyrinth ist in Form von 0en und 1en in einen Array gespeichert. Eine 0 stellt einen Weg dar und eine 1 eine Wand. Den kürzesten Weg soll mein Roboter mit einem AStern Algortihmus finden.
So nun zu meinem Problem:
Es werden nicht immer die optimalen Wegen gelaufen. In meinem Beispiel Labyrinth läuft der Roboter im Bereich von der Koordinate (16,11) bis (3,13) im ZickZack und ich habe keine Ahnung warum.
Ich habe mal den Code des Algortihmus angehängt. Wenn jemand Interesse hat kann ich auch das ganze Projekt inklusive Oberfläche schicken.
Schon mal Vielen Dank und ich bin für jeden Tip dankbar!!
Ich habe folgendes Problem:
Ich habe ein Programm, dass für einen Roboter selbständig den kürzesten Weg durch ein Labyrinth finden soll. Das Labyrinth ist in Form von 0en und 1en in einen Array gespeichert. Eine 0 stellt einen Weg dar und eine 1 eine Wand. Den kürzesten Weg soll mein Roboter mit einem AStern Algortihmus finden.
So nun zu meinem Problem:
Es werden nicht immer die optimalen Wegen gelaufen. In meinem Beispiel Labyrinth läuft der Roboter im Bereich von der Koordinate (16,11) bis (3,13) im ZickZack und ich habe keine Ahnung warum.
Ich habe mal den Code des Algortihmus angehängt. Wenn jemand Interesse hat kann ich auch das ganze Projekt inklusive Oberfläche schicken.
Code:
import java.util.*;
/**
*
Title: Kuka für Swt</p>
*
Description: Labyrinth Programm</p>
*
Copyright: Copyright (c) 2005</p>
*/
public class labysolv {
int testelse = 0;
private int[][] walkability ={{0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
// Konstanten
public static int mapWidth = 25; //wirkliche Größe von 1 bis 25
public static int mapHeight = 25;
public static int numberPeople = 500;
public static int onClosedList = 10;
public static int notFinished = 0;
public static int notStarted = 0;
public static int found = 1;
public static int nonexistent = 2;
public static int walkable = 0;
public static int unwalkable = 1;
int test = 4;
// Arrays
Vector liste = new Vector();
Vector liste2 = new Vector();
Vector liste_turn = new Vector();
//int[][] walkability = new int[mapWidth][mapHeight];
int[] openList = new int[mapWidth*mapHeight+2]; // 1 dimensionaler array mit der ID der offenen Knoten
int[][] whichList = new int[mapWidth+1][mapHeight+1]; // 2 dimensionaler array in dem gespeichert wird ob ein Knoten offen oder geschlossen ist
int[] openX = new int[mapWidth*mapHeight+2]; // array um x Koordinaten von Element der offenene Liste zu speichern
int[] openY = new int[mapWidth*mapHeight+2]; // array um y Koordinaten von Element der offenene Liste zu speichern
int[][] parentX = new int[mapWidth+1][mapHeight+1]; // array für x Koordinate des Vaters eines Knoten
int[][] parentY = new int[mapWidth+1][mapHeight+1]; // array für y Koordinate des Vaters eines Knoten
int[] Fcost = new int[mapWidth*mapWidth+2]; // array zum Speichern der F Kosten in der openList
int[][] Gcost = new int[mapWidth+1][mapWidth+1]; // array zum Speichern der G Kosten
int[] Hcost = new int[mapWidth*mapHeight+2]; // array zum Speichern der H Kosten in der openLIst
int pathLength; // speichert die Länge des gefundenen Pfades
int pathLocation; // speichert aktuelle Position entlang des gewählten Pfades
int[] pathBank = new int[numberPeople+1]; // int[]*
// Weg
int[] pathStatus = new int[numberPeople+1];
int xPath;
int yPath;
public labysolv(){
startPathFind(1,0,0,24,24);
}
/*
public Vector start(int[][] walkability)
{
this.walkability = walkability;
// traverse(0, 0); // 0,0 ist der Startpunkt
//a_Stern(grid);
//liste_umd(liste);needed
//printList(liste_turn);
startPathFind(1,0,0,24,24);
return liste_turn;
}
*/
public int FindPath( int startingX, int startingY, int targetX, int targetY) {
// liste_turn.add(new Tupel(0,0));
int onOpenList = 0;
int parentXval = 0;
int parentYval = 0;
int a = 0;
int b = 0;
int m = 0;
int u = 0;
int v = 0;
int temp = 0;
int corner = 0;
int numberOfOpenListItems = 0;
int addedGCost = 0;
int tempGCost = 0;
int path = 0;
int tempX;
int pathX;
int pathY;
int cellPosition;
int newOpenListItemID = 0;
// 1. Die Anfangskoordinaten
int startX = startingX;
int startY = startingY;
targetX = targetX;
targetY = targetY;
// 2. Schnelle Überprüfung des Weges( Mauer, außerhalb des Labyrinths)
// If Startpunkt = Endpunkt
if(startX == targetX && startY == targetY && pathLocation > 0)
return found;
if(startX == targetX && startY == targetY && pathLocation== 0)
return nonexistent;
// If Zielknoten ist nicht begehbar ==> return its a nonexistent path
if (walkability[targetX][targetY] == unwalkable)
//:noPath
{
xPath = startingX;
yPath = startingY;
return nonexistent;
}
//noPath;
// 3. Variablen initialisieren
if (onClosedList > 1000000) //resetwhichList
{
for (int x = 0; x < mapWidth; x++){
for (int y = 0; y < mapHeight; y++){
whichList[x][y] = 0;
}//for
}//for
onClosedList = 10;
}//if
onClosedList = onClosedList + 2;
onOpenList = onClosedList-1;
pathLength = notStarted;
pathLocation= notStarted;
Gcost[startX][startY] = 0; // reset Kosten von Startpunkt auf 0
System.out.println("***3***");
// 4. Füge den Startpunkt zu der offenen Liste hinzu
numberOfOpenListItems = 1;
openList[1] = 1; // als Oberstes im binären heap kennzeichnen
openX[1] = startX;
openY[1] = startY;
//5.mache alles solange bis ein Pfad gefunden ist oder bis alles ohne Ergebnis durchsucht ist
do
{
//6. wenn die offene Liste nicht leer ist, nimm das erste Element der Liste
// dies ist das Element mit den niedrigsten F-Kosten
if(numberOfOpenListItems != 0)
{
//7. pop das erste Element aus der Liste
parentXval = openX[openList[1]];
parentYval = openY[openList[1]]; // speichere die Koordinaten des Elments.
//liste_turn.add(new Tupel(parentXval,parentYval));
//System.out.println("X: " + parentXval + "Y:"+ parentYval);
whichList[parentXval][parentYval] = onClosedList; // füge das Element zur closedList hinzu
//openList ist ein binärer Heap: Lösche dieses Element von der openList
numberOfOpenListItems = numberOfOpenListItems - 1;
// Lösche das oberste Element des heap und ordne ihn neu mit dem kleinstem F-Kosten Element oben
openList[1] = openList[numberOfOpenListItems + 1]; // das letzte Element nach oben
v = 1;
// mache das ganze solange bis das oberste element nach unten sinkt
do
{
u = v;
if (2*u+1 <= numberOfOpenListItems) //es gibt beide Kinder
{
//schau ob F kosten der Eltern größer als die der Kinder sind
// wähle das kleinste won beiden
if (Fcost[openList[u]] >= Fcost[openList[2*u]])
v = 2*u;
if (Fcost[openList[v]] >= Fcost[openList[2*u+1]])
v = 2*u+1;
} //if
else
{
if(2*u <= numberOfOpenListItems) // es gibt nur ein Kind
{
//schau ob die Kosten von Vater größer als Kind
if (Fcost[openList[u]] >= Fcost[openList[2*u]])
v = 2*u;
}// IF
}//else
if ( u!=v) // wenn F von Vater größerals von Kind vertausche
{
temp = openList[u];
openList[u] = openList[v];
openList[v] = temp;
}//if
else
break; //andernfalls beende schleife
}
while (true); //normalerweise mache solange bis du fertig bist also solange true
// 7. prüfe die erwartete Entfernung
for( b = parentYval-1; b <=parentYval + 1; b++){
for ( a = parentXval -1 ; a <=parentXval+1;a++){
//wenn noch nicht außerhalb der Karte(vermeide out of bounds)
if(a != -1 && b != -1 && a != mapWidth && b != mapHeight) {
// if noch nicht auf der closed List
if(whichList[a][b] != onClosedList) {
//if keine wand
if(walkability[a][b] != unwalkable){
//Streife keine Ecken
corner = unwalkable;
if(a== parentXval-1)
{
if(b==parentYval-1)
{
if(walkability[parentXval-1][parentYval] == unwalkable
|| walkability[parentXval][parentYval-1] == unwalkable);// corner = unwalkable; //hier stand mal der Zeilenumbruch mit "\"
} //if
else if(b==parentYval+1)
{
if(walkability[parentXval][parentYval+1] == unwalkable
|| walkability[parentXval-1][parentYval] == unwalkable);//corner = unwalkable;
}//else if
}//if (a== parentXval-1)
else if(a== parentXval+1)
{
if(b==parentYval -1)
{
if(walkability[parentXval][parentYval-1] == unwalkable
|| walkability[parentXval+1][parentYval] == unwalkable);// corner = unwalkable;
} // if
else if(b==parentYval+1)
{
if(walkability[parentXval+1][parentYval]==unwalkable
||walkability[parentXval][parentYval+1]==unwalkable);// corner=unwalkable;
}
}//else if
if (corner == unwalkable) {
// wenn noch nicht auf offen liste add it
if(whichList[a][b] != onOpenList)
{
//ein neues open list opbjekt in binary heap
newOpenListItemID = newOpenListItemID +1; // jedes neue item hat eine id
m= numberOfOpenListItems+1;
openList[m] = newOpenListItemID; // füge das neue Element am boden des baumes ein
openX[newOpenListItemID]=a;
openY[newOpenListItemID]=b; //x,y koordinaten merken
//speichere die G kosten
if(Math.abs(a-parentXval) == 1 && Math.abs(b-parentYval)==1)
addedGCost = 14; //diagonal
else
addedGCost = 10; //non-diagonal
Gcost[a][b] = Gcost[parentXval][parentYval] + addedGCost;
// speichere die H und F Kosten
Hcost[openList[m]] = 10*(Math.abs(a-targetX)+ Math.abs(b-targetY));
Fcost[openList[m]] = Gcost[a][b] + Hcost[openList[m]];
parentX[a][b] = parentXval;
parentY[a][b] = parentYval;
//bewege das neue openlist Element an eine höhere Stelle implements binären heap
//starte am Boden; solange bis richtiger platz gefunden
while(m!=1)
{
//schau ob kosten des kindes f < als F des Vaters. wenn ja tausche
if(Fcost[openList[m]] <= Fcost[openList[m/2]])
{
temp = openList[m/2];
openList[m/2] = openList[m];
openList[m]=temp;
m=m/2;
}//if
else
break;
}
numberOfOpenListItems = numberOfOpenListItems+1; //noch eine zu den elementen implements heap
whichList[a][b]= onOpenList;
}
// 8.************************************************
//*****************************
//Wenn die aktuelle Zelle schon in der offenen Liste schau ob es ein besserer Weg bis hierher vom Startpunkt war
// Wenn ja dann tausche das Elternteil und die G und die F Kosten
else //IF whichLIst(a,b) = onOpenList
{
//Zeige die G Kosten des neuen Pfades
if(Math.abs(a-parentXval)==1 && Math.abs(b-parentYval)==1)
addedGCost=14; //diagonal
else
addedGCost = 10; //nondiagonal
tempGCost =Gcost[parentXval][parentYval]+addedGCost;
}
//wenn der Pfad kürzer ist d.h. die G kosten sind kleiner dann tausche
//die G und F Kosten der aktuellen Zelle
if(tempGCost < Gcost[a][b]) //wenn G Kosten geringer sind
{
parentX[a][b] = parentXval; //tausche die Nachbarn
parentY[a][b] = parentYval;
Gcost[a][b] = tempGCost; //tausche G Kosten
// da das Tauschen der G Kosten auch das Tauschen der F Kosten zu Folge
// hat(wenn das Element in der offenen Liste ist) muss man die gespeicherten
// Kosten und die Position in der open List ändern
for(int x = 1;x <= numberOfOpenListItems; x++) //schau nach dem Element im Heap
{
if(openX[openList[x]]==a &&openY[openList[x]]==b) //element gefunden
{
Fcost[openList[x]]=Gcost[a][b]+Hcost[openList[x]]; // tausche F Kosten
// schau ob das tauschen der Kosten die Position implements Heap verändert
m=x;
while(m!=1) // while das Element nicht oben ist(m=1)
{
//schau ob das Kind < Vater, Wenn ja tausche beide
if(Fcost[openList[m]]<Fcost[openList[m/2]])
{
temp = openList[m/2];
openList[m/2] = openList[m];
openList[m]= temp;
m = m/2;
}
else
break;
}
break; //ende für x = loop
}// if openX(openList(x))=a
}//for x=1 to numberOfOpenLIstItems
}// if tempGCost < GCost(a,b)
}//else if whichList(a,b)
}//If not cutting a corner
}//If not a wall/obstacle
}//if not already on the closedList
}//If not of the map
}//for(a=parenXval-1;a<=parentXval+1);a++)
testelse = testelse + 1;
// System.out.println("ende langes else"+testelse);
}//for(b=parent....
// }
//9. If Open List ist leer das gibt es keinen Pfad
else
{
System.out.println("nonexistent");
path = nonexistent;
break;
}
// If Ziel ist in openList dazugekommen dann gibt es einen Pfad
if(whichList[targetX][targetY]==onOpenList)
{
System.out.println("Path found");
path=found;
break;
}
}
while(true); //solange bis pfad gefunden wurde
//10.Speicher den Pfad wenn es ihn gibt.
if (path == found)
{
//a.Vom Endpunkt zum Startpunkt zurücklaufen und jede Zelle als Vater betrachten
// zeige die Länge des Pfades
pathX = targetX; pathY = targetY;
do
{
//schau nach dem Vater der aktuellen Zelle
tempX = parentX[pathX][pathY];
pathY = parentY[pathX][pathY];
pathX = tempX;
//zeige die Pfadlänge
pathLength = pathLength + 1;
}
while (pathX != startX || pathY != startY);
// kopiere die Pfadinformationen in die databank. Vom Ziel zum Startpunkt in umgekehrter Reihenfolge
pathX = targetX ; pathY = targetY;
cellPosition = pathLength*2;//beginne am Ende
do
{
cellPosition = cellPosition - 2;//immer 2 zurück
pathBank[cellPosition] = pathX;
pathBank[cellPosition+1] = pathY;
System.out.println("******");
System.out.println("PUNKT: X" + pathX +"Y"+ pathY);
// liste_turn.add(new Tupel(pathX,pathY)); //??????????????????
// liste_turn.add(new Tupel(pathX,pathY));
//d.schau nach dem Elternteil der aktuellen Zelle
tempX = parentX[pathX][pathY];
pathY = parentY[pathX][pathY];
pathX = tempX;
//e.Wenn Startpunkt erreicht ==> Ende
}
while (pathX != startX || pathY != startY);
System.out.println("PUNKT: X" + pathX +"Y"+ pathY);
//liste_turn.add(new Tupel(pathX,pathY));//?????????????????????????
//11.lese Startpunkt
// ReadPath(startingX,startingY,1); // hier mal schaun???****************************
}
//System.out.println("Ende");
return path;
} //end pathfinder
public void ReadPath()
{
// wenn es einen Pfad gibt, lies die Daten des Pfades aus der Pfad Bank
pathLocation=1; //Pfad am ersten Schritt
while(pathLocation < pathLength)
{
int a = pathBank[pathLocation*2-2];
int b = pathBank[pathLocation*2-1];
pathLocation=pathLocation+1;
//System.out.println("PUNKT: X" + this.parentX+"Y"+ openY);
System.out.println(""+whichList[a][b]);
whichList[a][b]=3; //zeichne den Pfad
//liste_turn.add(new Tupel (a,b)); //***************hier die Ausgabe an die GUI
}
}
// public void ReadPath(int pathfinderID, int currentX, int currentY,int pixelperframe){};
// public void ReadPathX(int pathfinderID, int pathLocation) {};
// public void ReadPathY(int pathfinderID, int pathLocation) {};
//dies wird einmal meine Hauptfunktion!!!!*******************************
// diese funktion aufrufen um pfad zu berechnen;**************************************************
public void startPathFind(int path, int startX,int startY, int targetX, int targetY) {
if(true)
{
path = FindPath( startX,startY, targetX,targetY);
if(path==found)ReadPath();
}
}
public static void main (String args[]){
new labysolv();
}
}Schon mal Vielen Dank und ich bin für jeden Tip dankbar!!
