Java A*-Algorithmus

[RauchenderDachs]

Hi Leute,
ich versuche gerade eine Tower defense Clone zu programmieren. Damit die Creeps den Weg durch die Türme zum Ziel finden würde ich gerne den A*-Algorithmus benutzen. Ich hab mir jetzt ein paar Videos und Seiten dazu durchgelesen und ich glaube ich bin durchgestiegen. Nur an der Implementierung scheiterts gerade. (Code siehe unten)

Problem:
Der Algorithmus schreibt den besten Wegpunkt einfach nicht um.

Meine Vermutung:
Ich denke das Problem entsteht bei der Sortierung der Openlist (Zeile 112). Da ich hier aber kein PRoblem gefunden habe denk ich das , dass Problem in der Schätzung liegen muss hab dort aber auch nichts gefunden.

Ich bitte darum das ihr euch den Code mal anschaut. (Falls ich was vergessen hab kann ich den natürlich nachreichen). Bitte korrigiert meine Quelltext nicht sondern weist mich nur auf den Fehler hin.

Grüße RauchenderDachs

//Schätzung für den A*
    public int doSchaetzung(int x, int y){
        int dx = x - map[zielx][ziely].getX()/10;///10 da ich in Teils rechne
        if (dx < 0) {
            dx = -dx;
        }
    
        int dy = y - map[zielx][ziely].getY()/10;
            if (dy < 0) {
                dy = -dy;
            }
    
        return (int)(Math.sqrt(Math.pow(dx,2)  + Math.pow(dy,2)));
    }
    
 
    public void aStern(){
        //Anfangspunkt zur openlist hinzufügen
        openlist[0] = map[anfangx][anfangy];
        //listcnt damit ich weis wieviele Objekte ich in der Openlist habe
        int listcnt = 1;
        // bester Wegpunkt ist immer der Wegpunkt der an erster Stelle in der openlist ist
        for(int i = 0; i<map.length*map[0].length;i++){
            aktualisiereOpenList(listcnt);
            bestWegpunkt = openlist[0];
            //System.out.println(openlist[0].getX()+" "+openlist[0].getY());
            closedlist[i] = bestWegpunkt;
            if(bestWegpunkt.getStatus() == 2){
                // vom Ziel aus wird zurück gelaufen bis zum Anfang 
                for(int n = 0; n<map.length*map[0].length;n++){
                    if((bestWegpunkt.getX()!=anfangx) && (bestWegpunkt.getY()!=anfangy)){
                        pfad [n] = bestWegpunkt.getVorgaenger();
                        bestWegpunkt = bestWegpunkt.getVorgaenger();
                        System.out.println("1");
                    }
                    else{
                        break;
                    }
                }
                break;
            }
            //Hier finde ich heraus welche Tile nummer der Beste Wegpunkt hat 
            int bestWPx = 0;
            int bestWPy = 0;
            for(int a = 0 ; a<map.length;a++){
                for(int b = 0; b<map[0].length;b++){
                    if((bestWegpunkt.getX() == map[a][b].getX())&&(bestWegpunkt.getY() == map[a][b].getY())){
                        bestWPx = a;
                        bestWPy = b;
                        break;     
                    }
                }
            }
              //System.out.println(bestWPx+" "+ bestWPy);
              
                 //Überprüfung ob Boden oder Tower oder schon in closed oder open list und ggf zur openlist hinzufügen
              if(bestWPx - 1 >= 0){//links
                if((!istteilvonListe(map[bestWPx-1][bestWPy]))){
                    if(map[bestWPx-1][bestWPy].getStatus() == 0){
                        openlist[listcnt] = map[bestWPx-1][bestWPy];
                        //Vorgänger wird gesetzt also von welchem Wegpunkt ich auf den anderen trauf trete
                        openlist[listcnt].setVorgaenger(bestWegpunkt);
                        openlist[listcnt].setSchaetzung(doSchaetzung(bestWPx-1,bestWPy));
                        listcnt++;
                        //System.out.println("1");
                    }
                }
              }
              if(bestWPy + 1 < map[0].length){//unten
                if(!istteilvonListe(map[bestWPx][bestWPy+1])){
                    if(map[bestWPx][bestWPy+1].getStatus() == 0){
                        openlist[listcnt] = map[bestWPx][bestWPy+1];
                        openlist[listcnt].setVorgaenger(bestWegpunkt);
                        openlist[listcnt].setSchaetzung(doSchaetzung(bestWPx,bestWPy+1));
                        System.out.println("2");
                        listcnt++;
                    }
                }
              }
              if(bestWPx + 1 < map.length){//rechts
                if(!istteilvonListe(map[bestWPx+1][bestWPy])){
                    if(map[bestWPx+1][bestWPy].getStatus() == 0){
                        openlist[listcnt] = map[bestWPx+1][bestWPy];
                        openlist[listcnt].setVorgaenger(bestWegpunkt);
                        openlist[listcnt].setSchaetzung(doSchaetzung(bestWPx+1,bestWPy));
                        System.out.println("3");
                        listcnt++;
                    }
                }
              }
              if(bestWPy-1 >= 0){//drüber
                if(!istteilvonListe(map[bestWPx][bestWPy-1])){
                    if(map[bestWPx][bestWPy+1].getStatus() == 0){
                        openlist[listcnt] = map[bestWegpunkt.getX()][bestWPy-1];
                        openlist[listcnt].setVorgaenger(bestWegpunkt);
                        openlist[listcnt].setSchaetzung(doSchaetzung(bestWPx,bestWPy+1));
                        //System.out.println("4");
                        listcnt++;
                    }
                }
              }
              
              System.out.println("x:"+bestWegpunkt.getX()+"    y:"+bestWegpunkt.getY()+"    TileNrx:"+bestWPx+"    TileNry:"+bestWPy);
              System.out.println("Schaetzung:"+openlist[0].getSchaetzung());
              System.out.println("Bubblesort ausgabe"+ " x:"+openlist[0].getX()+ " y:"+openlist[0].getY() + " Gesamtkosten:"+openlist[0].getGesamtkosten() );   
        } 
        if(listcnt >= map.length*map[0].length-1000){
            listcnt = 0;
        }
        
    }
    public void aktualisiereOpenList(int anzahlelemente){
        
        //Einfacher Bubblesort der den günstigen nächsten Knoten ausscuht
        Tile temp;
		for(int i=1; i<anzahlelemente; i++) {
			for(int j=0; j<anzahlelemente-i; j++) {
                            if((openlist[j] != null) && (openlist[j+1] != null)){
				if(openlist[j].getGesamtkosten()> openlist[j+1].getGesamtkosten()) {
					temp=openlist[j];
					openlist[j]=openlist[j+1];
					openlist[j+1]=temp;
				}
                            }
				
			}
		}
     
        
    }

Log:
27.11 In Zeile 69 und 80 wurde statt <= ein < eingesetzt ; In Zeile 119 wurde statt >= ein > eingesetzt; aktualisiereListe() wurde ein Parameter (listcnt) hinzugefügt.

 

[Magogan]

In Zeile 69 und 80 solltest du das <= durch ein < ersetzen oder einfach das +1 davor weglassen. In Zeile 119 reicht ein >, bei Gleichheit musst du die Elemente ja nicht vertauschen. Warum sortierst du die komplette Openlist, obwohl nur listcnt Elemente drin sind?

 

[RauchenderDachs]

Hab alle Veränderungen oben vorgenommen.
Die Cosole spuckt mir übrigens folgendes aus.
****
2
3
x:0 y:0 TileNrx:0 TileNry:0
Schaetzung:0
Bubblesort ausgabe x:0 y:0 Gesamtkosten:1
2
3
x:0 y:0 TileNrx:0 TileNry:0
Schaetzung:0
Bubblesort ausgabe x:0 y:0 Gesamtkosten:1
2
3
x:0 y:0 TileNrx:0 TileNry:0
Schaetzung:0
Bubblesort ausgabe x:0 y:0 Gesamtkosten:1
****
Ich hoffe auf weitere Lösungsvorschläge

Grüße

 

[RauchenderDachs]

Nach ein paar Stunden im Internet hab ich jetzt eine neuen Lösungsvorschlag versucht zu implementieren. (Code siehe unten)

Hier hab ich jetzt das Problem das ich die Exception StackOverflowError bekomme. Das Problem leigt offenbar in dem Rekursiven aufruf in der Klasse Tile in den Methoden getBisherigekosten() und getGesamtkosten(). Ich hab versucht den vorgaenger zwanghaft zu beginn immer wieder auf Null setzten zu lassen ,sodass die Rekursion eigentlich ein Ende haben müsste.

//In der Klasse Steuerung 
.
.
.
//Im Konstruktor
 //Tile rechts unten ist Ziel
        zielx = map.length-1;
        ziely = map[0].length-1;
        //Tile links oben ist Anfang
        anfangx = 0;
        anfangy = 0;
 //initialisiere die listen
        openList = new LinkedList<Tile>();
        openList.add(0,map[anfangx][anfangy]);
        closedList = new LinkedList<Tile>();
.
.
.
//Ende Konstruktor
 private void aStern() {
        
    //Tile bestWegpunkt;
    
      //untersuche die vier nachbarn wenn möglich
      //also nicht wenn dort ein stein liegt
      //und nicht wenn der punkt bereits in der closed list ist
      bestWegpunkt = openList.get(this.getFirstBestListEntry(openList));
      closedList.add(openList.remove(this.getFirstBestListEntry(openList)));
      //System.out.println("untersuche: x:" + bestWegpunkt.getX() + " y:" + bestWegpunkt.getY() + " DeltaZiel: " + this.heuristik(bestWegpunkt.getX()/10, bestWegpunkt.getY()/10));
      try {
    Thread.sleep(100);                 //1000 milliseconds is one second.
} catch(InterruptedException ex) {
    Thread.currentThread().interrupt();
}
      //wenn der beste punkt das ziel ist, ist der beste weg gefunden
      if (bestWegpunkt.getX()/10 == this.zielx && bestWegpunkt.getY()/10 == this.ziely) {
        for(int i = 0; i<map[0].length*map.length;i++){
            pfad[i] = bestWegpunkt.getVorgaenger(); 
            System.out.println(1);
            if(bestWegpunkt.getVorgaenger().getX() == anfangx && bestWegpunkt.getVorgaenger().getY() == anfangy){
                break;
            }
        }
      }
      System.out.println("untersuche: x:" + bestWegpunkt.getX() + " y:" + bestWegpunkt.getY() + " DeltaZiel: " + bestWegpunkt.getSchaetzung());
     
      //oberhalb
      this.openListAddHelper(bestWegpunkt.getX()/10, bestWegpunkt.getY()/10 - 1, openList, closedList, bestWegpunkt);
      //rechts
      this.openListAddHelper(bestWegpunkt.getX()/10 + 1, bestWegpunkt.getY()/10, openList, closedList, bestWegpunkt);
      
      //unterhalb
      this.openListAddHelper(bestWegpunkt.getX()/10, bestWegpunkt.getY()/10 + 1, openList, closedList, bestWegpunkt);
      
      //links
      this.openListAddHelper(bestWegpunkt.getX()/10 - 1, bestWegpunkt.getY()/10, openList, closedList, bestWegpunkt);
  }
  
  
  /**
   * checkt ob die angewählte zelle schon total untersucht ist
   * (befindet sich dann in closedList)
   * prüft ob das feld überhauptbegehbar ist und ob es noch nicht
   * in der openList ist.
   * an der stelle kann man auch den sachverhalt implementieren
   * ob es einen besseren pfad zu einem bereits in der openList
   * exitierenden zelle gibt. ist aber bei solch einem pathfinding 
   * nicht nötig. wäre aber nötig wenn es zum beispiel
   * sümpfe geben wurde die den spieler langsamer machen
   * @param x
   * @param y
   * @param openList
   * @param closedList
   * @param vorher 
   */
  private void openListAddHelper(int x, int y, LinkedList<Tile> openList, LinkedList<Tile> closedList, Tile vorher){
    if (x < 0 || y < 0 || x >= map.length|| y >= map[0].length) {
    } else {
      //if(x!=anfangx && y!=anfangy) {
        if (this.isPointInList(x, y, closedList) == false 
            && this.map[x][y].getStatus() == 0
            && this.isPointInList(x, y, openList) == false) {
          openList.add(map[x][y]);
          map[anfangx][anfangy].removevorgaenger();
          map[x][y].setSchaetzung(heuristik(x,y));
          map[x][y].setVorgaenger(vorher);
        }
      //}
    }
  }
  
  
  /**
   * die abschätzung wie weit es noch bi szum ziel ist, wenn von
   * diesem punkt aus gar keine hindernisse im weg wären.
   * @param x
   * @param y
   * @return 
   */
  private int heuristik(int x, int y) {
    int dx = x - this.zielx;
    if (dx < 0) {
      dx = -dx;
    }
    
    int dy = y - this.ziely;
    if (dy < 0) {
      dy = -dy;
    }
    
    return dx + dy;
  }
  
  /**
   * sucht das element aus der liste welches
   * am vielversprechendsten ist.
   * @param list
   * @return 
   */
  private int getFirstBestListEntry(LinkedList<Tile> list) {
    int best = list.get(0).getGesamtkosten();
    
    for (int i = 1; i < list.size(); i++) {
      if (list.get(i).getGesamtkosten() < best) {
        best = list.get(i).getGesamtkosten();
        return i;
      }
    }
    //get first element with best costs
    for (int i = 0; i < list.size(); i++) {
      if (list.get(i).getGesamtkosten() == best) {
        return i;
      }
    }
    System.out.println("da ist etwas schiefgelaufen in 'getFirstBestListEntry'");
    return 0;
  }
  
  private boolean isPointInList(int x, int y, LinkedList<Tile> list) {
    for (int i = 0; i < list.size(); i++) {
      if (list.get(i).getX() == x && list.get(i).getY() == y) {
        return true;
      }
    }
    
    return false;
  }





// In der Klasse Tile 
public class Tile extends Item{
    private Tile vorgaenger;
    private int schaetzung;
    private int kosten = 1;
    private int status;//0 = boden,1 = wand/tower, 2 =  Ziel
    
    public Tile(int x,int y,int status){
        super(x,y);
        this.status = status;
        this.vorgaenger = null;
    }
    Tile getVorgaenger(){
        return vorgaenger;
    }    
    void setVorgaenger(Tile v){
        vorgaenger = v;
    }
    int getGesamtkosten(){
        if(vorgaenger == null){
            //System.out.println(1);
            return kosten+schaetzung;
        }
        return getBisherigekosten() + this.kosten + this.schaetzung;
    }
    int getBisherigekosten(){
        if (this.vorgaenger == null) {
            System.out.println("2");
            return 0;
        }
        return vorgaenger.getBisherigekosten() + this.kosten;
    }

 

[Magogan]

Wahrscheinlich läuft der irgendwie im Kreis, so schnell sollte kein Stack Overflow auftreten. Auch nicht bei 500x500 Feldern. Aber debugge das doch mal selbst, das Forum ist nicht dafür da, dass wir dir die ganze Arbeit abnehmen. Zumindest hab ich nicht die Zeit, um den Fehler zu suchen. Eclipse sollte alle nötigen Funktionen haben (Haltepunkte etc.).

 

[Henni]

Ein paar Dinge die mir nur auf die schnelle auffallen:

• Nimm für closedList lieber ein Set (welche Variante auch immer) und implementiere equals und hashCode für Tile - dann kannst du dir die isPointInList Methode sparen (java.util.Set hat eine contains Methode).
• Deine heuristik ist meiner Meinung nach falsch - die alte Variante (Vector Längenberechnung) ohne / 10 (und ohne die beiden IFs) ist für deinen Zweck vermutlich richtiger. Btw. anstatt des IFs hättest du auch Math.abs verwenden können.
• getFirstBestListEntry Methode geht davon aus dass sich eine maximale Änderung von einem Element ergeben hat (soweit ich das interpretiere). Sobald mehr als ein Element hinzugekommen ist kann es sein dass dir die Methode das falsche Element zurückgibt. Entweder du stellst sicher dass du wirklich das beste bekommst (indem du immer alle Elemente durchgehst und das beste heraussuchst) oder du verwendest eine andere Datenstruktur (z.B. SortedSet mit Comparator).
• Mir scheint sowieso das der Code wie du ihn da reinkopiert hast nicht funktionieren kann. (Es fehlt z.B. die 'unendliche' Schleife für A*, aber auch manche Methoden scheinen zu fehlen.

Woher hast du eigentlich her wie der Algorithmus funktioniert bzw. implementiert gehört? Ich habe mir die Variante der deutschen Wikipedia angesehen und nachimplmentiert und (auf den ersten Blick) sieht diese anders aus als das was du versuchst zu implementieren?

 

[BxB]

1. Der BESTE weg ist manchmal ziemlich teuer, meist sogar zu teuer. oft reicht ein akzeptabel guter approximierter Weg, der enorm viel schneller sein kann.
2. Meine Empfehlung ist auf jeden Fall diese Suche zu speichern und erst neu zu berechnen, wenn ein Gebäude sich verändert hat [zerstört/gebaut/entfernt], denn solange sollte diese Berechnung gültig sein. Pufferung für das Prinzip "die beste berechnung, ist die nicht berechnete" ^^
3. A* hat immer noch den Nachteil, dass es exponentiell zur Länge der Lösung wachsen kann und im Worst Case O(b^M) möglich ist. Als möglicher limitierender Faktor kann sein, dass alle Knoten mit Durchgängen) im Speicher gehalten werden müssen, es gibt aber modifizierte Varianten, die auf die Speicherbeschränkung zielen.
Ich habe u.a. A* testweise auf das TSP angewendet und es war grausam langsam. Am besten hat mein fix gebauter eigener "Nearest-neighbour + Post Korrekturen" funktioniert. Meist war es dann so ca rum: 100 Städte in 2.5-5sek, 150 Städte in 9-27.
Wenn mal bissl Zeit ist, will ich ne Adjazenzmatrix bauen und damit paar Algorithmen durchjagen ... mal gucken, wie der wird.
4.
A* gilt zwar als Algorithmus, der die wenigsten Knoten expandiert bei der entsprechenden Heuristik, aber ich persönlich würde einfach mal als alternativen Ansatz darüber nachdenken das Brett als einen Graphen zu betrachten.Graphsuchen sind relativ schnell und einfach. Du musst den ja nicht machen, aber man sollte immer mehrere Möglichkeiten abwegen oder austesten. Mit Graphen kannst du auch checken, ob du 2 Teilgraphen hast, also der Weg versperrt ist.

So spontan hab ich mir eine Idee überlegt, die du dir mal durch den Kopf gehen lassen solltest.

1. Graph aus dem Brett bauen.
- Knoten sehen wie folgt aus: boolean visited; List<Nodes> bestPath; bestPathLen;
- 2 Listen: Unvisited, Visited
- Gehe alle Felder durch, erstelle bei jedem Feld einen Knoten, falls dieser nicht belegt ist. Füge ihn der Liste unvisited zu.
- gehe in der zweiten Iteration alle Felder durch und verknüpfte die Nachbarn (add if not belegt).
- wähle startNode und zielNode aus. startNode als PathAdden mit Wert 0. Entferne aus Unvisited.
2. Durchlauf:
- Du bist bei einem Knoten. Du gehst jede Kombination durch, wohin du springen kannst und berechnest die bisherige Entfernung + den Weg zu den jeweiligen Knoten (hier wohl 1 für + ... bzw anders wenn schräg auch geht).
- Wenn der Knoten in Unvisited ist, verschiebst du ihn mit dem Entfernungsweg in die visited und "weiterVerbessernListe".
- Wenn der knoten in Visited drin ist, vergleichst du den Weg und schaust, ob dieser einen niedrigeren Wert hat => wenn ja, setzt du den neuen bestPathLen und den aktuellen weg als neuen.
- die verbesserten Visited ersetzt man auch in die Liste "weiterVerbessernListe". diese liste beinhaltet alle noch zu kontrollierenden Knoten, die weiter verfolgt werden - sie wird anfangs voller, kann maximal alle knoten beinhalten und wird später schnell leerer.
- wenn ziel gefunden wurde, setze BestFoundPath. Sobald dieser Wert überschritten wird, verfolge hier nicht weiter
3. Abbruch-Kriterien.
- Das kann z.b. sein, wenn der erste Weg gefunden wird. Schnelle Approximations-Lösung, aber nicht optimal.
- Wenn vom startpunkt ausgehend alle Knoten in visited sind, aber noch keine lösung gefunden (foundTargetNode) wurde => 2 abgetrente und damit Weg blockiert
- wenn man am ziel ist, geht er keinen weg weiter, überprüfe andere Knoten.
- wenn weiterVerbessernListe leer, dann ...[bei keinem Ziel gefunden: keine Lösung], bei ziel gefunden: [target sollte ne gute lösung haben]

Man muss das auch nicht als Graph machen, man kann das auch mit ner ArrayMatrix von Nodes machen (dafür mit vielen IFnotBelegt aber). Ich denke nur im Graph lässt sich das einfacher vorstellen.

=> meine Gedanken dazu:
(1) A* ist gut, wenn der Weg sehr geringfügig blockiert ist und der Weg nahe der Manhattan-Distanz geht. Kleine Umwege kann er schnell umgehen. Bei komplexen Labyrinthen mit vielen Abzweigungen und langen Mauern wird er hier viel zu viele Kombinationen erstellen, die zuviel für den Speicher sind!
(2) Graph: ist ganz gut, wenn es z.B. viele breite Hindernisse gibt, die sehr viele Umwege erstellen, z.B. wie häufig in TD das prinzip die gegner die reihen dauernd hin und her zu laufen. Hier punkten der Graphenansatz sehr, er füllt sehr fix die Punkte auf läuft die Wege nur bei besseren Möglichkeiten nochmal durch. Dazu ist die einzige Problematik die vielen Nodes im Graphen im Speicher halten zu können mit dem bisher genommenen Weg!

Als Abwandlung kannst du auch dauernd die zuVerbessernListe mit einer Heuristik bewerten (Manhatten) und danach sortieren, welcher Node als nächstes genommen wird. Das würde eine potentiell schnelle Annäherung wie A* bedeuten, jedoch gefolgt von einem Postprocessing, falls noch Potential da ist.

Vllt liegt es auch an der nicht geschlafenen Nacht, dass ich Bullshit erzähle, oder viele Details noch fehlen, aber insgesamt denke ich, dass man den Ansatz ausprobieren könnte ^^