Problem mit A*-Algorithmus

[Pfaeff]

Hallo!

Ich versuche momentan den A*-Algorithmus zu implementieren. Meine Nodes sind Punkte im Raum und durch gegenseitige Referenzierung miteinander verbunden:

siehe Link unten

Wenn ich jetzt meinen A* benutze liefert er mir jedesmal ein leeres Array, es sei denn, ich wähle Startknoten=Zielknoten, dann gibt er mit den Start-/Zielknoten zurück.
Als Vorlage habe ich den Wikipedia-Artikel benutzt, ich habe ihn lediglich dahingehend erweitert, dass ich sortiertes Einfügen benutze.
Vielleicht liegt das Problem darin, dass ich die f-Wert zusammen mit den Nodes ablege und dadurch beim Vergleichen Probleme bekomme, da ich den f-Wert eventuell verändere? (€: das sollte in der hochgeladenen Version eigentlich nicht mehr der Fall sein)

Vielen Dank schonmal,

mfg

 

[SlaterB]

was ist Vector2d für eine Klasse?
ein main-Programm mit der Liste der Knoten und Kanten usw wäre auch nützlich,
will doch niemand selber eintippen

 

[hdi]

Also du solltest erstmal die Gleichheit von Nodes definieren, damit du ordentlich drauf arbeiten kannst:

// In Node Klasse:
public boolean equals(Node n){
     return n.position.equals(this.position); 
}

// in Vector2D Klasse:
public boolean equals(Vector2D v){
     return v.x == this.x && v.y == this.y // nur geraten, ich kenne die Klasse ja nicht
}

Und dann:

public void connectWith(Node n) {
        if (!n.equals(this) && !connectedTo(n)) {     // n != this testet auf interne Gleichheit
            nodes.add(n);
            n.nodes.add(this);
        }
    }     

private boolean connectedTo(Node n){
     for(Node cur : nodes){
            if (cur.equals(n)){
                   return true;
            }
     }
     return false;
}

List.remove() benutzt übrigens auch equals().

So, jetzt zu deinem Algo: Weisst du, warum er dir eine leere Liste gibt? Bei sowas ist es immer gut,
ein paar Print-Meldungen einzubauen. Hau mal in jede Zeile, die etwas wichtiges tut, eine sinnvolle Meldung
und lass das Programm dann mal mit nem simplen Beispiel laufen (zB startknoten 1 und zielknoten 2)

PS: Ich hab zwar den a* noch nie implementiert, kann dir aber trotzdem sagen dass du das sicherlich
VIEL zu kompliziert machst. dein Algorithmus ist schlichtweg zu lang ud du benutzt bestimmt unnötig viele
Variablen. Denk nochmal drüber nach, was du brauchst und was nicht.

PPS: Sieh dir mal die Klasse Queue an, für Breiten-/Tiefensuche nimmt man sowas her

 

[Pfaeff]

remove() benutzt automatisch equals? oder nur wenn die Klasse Comparable ist? Gilt das auch für contains() ?

mfg

 

[SlaterB]

contains auch equals, Comparable spielt keine Rolle

 

[Pfaeff]

Ok ich hab mal mein Test-Programm (PolygonTest) hochgeladen (habe den Code leicht verändert). Das beschränkt sich allerdings nicht auf das Pathfinding, interessante Klassen sind Pathfinder, PathList und Node. Die Ausführbare Datei heißt PolygonTest.

Alles noch ziemlich "unschöner" Code, da das auch nur ein Testprogramm ist.

http://[u] Link entfernt[/u]

 

[SlaterB]

also ich schaue mir das nicht alles an,
Einfachheit ist oberstes Gebot bei Testprogrammen, da war dein vorher hier geposteter Code schon besser,
50 Zeilen Node-Klasse, 50 Zeilen Path-Algorithmus und dazu jetzt vielleicht noch 30 Zeilen main-Methode + Vector2d-Klasse

wenn ich allein die main sehe:
// Polygone
polys[0] = new Polygon();
polys[0].position = new Vector2d(200, 100);
polys[0].addVertex(new Vector2d(50, 25));
polys[0].addVertex(new Vector2d(50, -25));
polys[0].addVertex(new Vector2d(-50, -25));
polys[0].addVertex(new Vector2d(-50, 25));
polys[1] = new Polygon();
polys[1].position = new Vector2d(250, 200);
polys[1].addVertex(new Vector2d(50, 25));
polys[1].addVertex(new Vector2d(60, -25));
polys[1].addVertex(new Vector2d(0, -50));
polys[1].addVertex(new Vector2d(-60, -25));
polys[1].addVertex(new Vector2d(-50, 25));
polys[2] = new Polygon();
polys[2].position = new Vector2d(350, 100);
polys[2].addVertex(new Vector2d(0, 50));
polys[2].addVertex(new Vector2d(25, 43));
polys[2].addVertex(new Vector2d(43, 25));
polys[2].addVertex(new Vector2d(50, 0));
polys[2].addVertex(new Vector2d(43, -25));
polys[2].addVertex(new Vector2d(25, -43));
polys[2].addVertex(new Vector2d(0, -50));
polys[2].addVertex(new Vector2d(-25, -43));
polys[2].addVertex(new Vector2d(-43, -25));
polys[2].addVertex(new Vector2d(-50, 0));
polys[2].addVertex(new Vector2d(-43, 25));
polys[2].addVertex(new Vector2d(-25, 43));
polys[3] = new Polygon();
polys[3].position = new Vector2d(400, 225);
polys[3].addVertex(new Vector2d(-50, 30));
polys[3].addVertex(new Vector2d(50, 25));
polys[3].addVertex(new Vector2d(-10, -40));
polys[4] = new Polygon();
polys[4].position = new Vector2d(175, 300);
polys[4].addVertex(new Vector2d(-60, 20));
polys[4].addVertex(new Vector2d(60, 40));
polys[4].addVertex(new Vector2d(-0, -70));
polys[5] = new Polygon();
polys[5].position = new Vector2d(300, 300);
polys[5].addVertex(new Vector2d(-43, -31));
polys[5].addVertex(new Vector2d(-16, 51));
polys[5].addVertex(new Vector2d(47, 2));
polys[5].addVertex(new Vector2d(24, -62));

damit kann doch niemand was anfangen,
ein einfaches Netz mit wenigen Knoten und wenigen Kanten und einfache Positionen 1, 2, 3, nicht 300 und -43!..

das sollte hier in einen Forum-Beitrag passen, kein JFrame, kein MouseListener und sonstige Unfälle

edit: falls ich den Code wieder löschen soll, sag Bescheid

 

[Pfaeff]

Wenn man das Programm startet kann man die Nodes ja sehen und so überprüfen ob der Algo funktioniert oder nicht. Intern werden ohnehin andere Nodes erzeugt, ich kann ja mal ein einfacheres Testprogramm machen.

Hier ein minimalistischer TestCode

import java.util.*;

public class PathfinderTest {
    public static void main(String[] args) {
        // Pathfinder
        Node nodes[] = new Node[4];
        Pathfinder pf = new Pathfinder();
        ArrayList<Node> path = new ArrayList<Node>();        
        // Pfade erzeugen
        nodes[0] = new Node(new Vector2d(100.0, 100.0));
        nodes[1] = new Node(new Vector2d(200.0, 100.0));
        nodes[2] = new Node(new Vector2d(150.0, 200.0));
        nodes[3] = new Node(new Vector2d(400.0, 200.0));       
        nodes[0].connectWith(nodes[1]);
        nodes[0].connectWith(nodes[3]);        
        nodes[1].connectWith(nodes[2]);
        nodes[2].connectWith(nodes[3]);    
        pf.addNodes(nodes);
        path = pf.findPath(0, 2);     
        for (int i=0; i<path.size(); i++) {
            System.out.println(pf.indexOfNode(path.get(i)));
        }            
    }    
}

mfg

 

[hdi]

Wie willst du eigentlich einen Pfad von int nach int berechnen, wenn du Nodes hast?
Was ist denn findPath(0,2)? Also entweder du gibst einer Node eine ID, oder du arbeitest
direkt auf den Knoten.

Ich hab jetzt mal was gemacht:

public ArrayList<Node> findPath(Node source, Node target){

                List<Node> path = new ArrayList<Node>(); 
		Queue<Node> queue = new LinkedList<Node>(); // Warteschlange
		queue.add(source);
		while (!queue.isEmpty()) {
			expand(queue, path, null, target);
		}
}

rekursive Tiefen-Suche:

/** @ return true wenn die Tiefen-Suche zum Ziel geführt hat, false sonst */
private boolean expand(Queue<Integer> queue, List<Integer> path, Node prev, Node target) {
	
                boolean deadEnd = true; // heisst es gibt keine echten Nachbarn von dem Knoten
		Node v = queue.remove();
                for(Node n : v.getNeighbours()){
                         if( !pathFound && !n.equals(prev)){ // nicht wieder zurückgehen
                              if( n.getID() != target.getID()){
                                   queue.add(n);
                                   deadEnd = expand(queue,path,v);
                              }
                               else{
                                   // Ziel gefunden, den Rest als Leerlauf durchrattern und nur die Queue leeren
                                   path.add(n); 
                                   pathFound = true;
                                   break; 
                               }
                        }
                }
                if(!deadEnd){
                       path.add(v);
                }
                return deadEnd;
}

Das hier erstellt dir eine Liste von Nodes, und zwar von source nach target, in dieser Reihenfolge (in path).
Das ganze bricht ab, sobald der Ziel-Knoten gefunden wurde. (Achtung das ist nicht getestet)

Natürlich ist das nicht der A* Algorithmus, weil du willst ja den BESTEN Pfad haben.
D.h. du musst findPath() immer wieder aufrufen, und zwar solange, bis er den besten Pfad
gefunden hat.
Das wiederum heisst du musst expand() so verändern, dass er nur einen Weg geht, den
er nicht bei einem anderen Aufruf von findPath() schon mal gegangen ist. Dafür brauchst du in
der Methode halt Zugriff auf irgendeine globale Liste von allen möglichen Pfaden, die er schonmal
gegangen ist.

Und ganz am Ende packst du dir die Liste aller gespeicherten Pfade und zählst von jedem die Kosten
über alle Knoten zusammen. So kriegste dann den besten.

 

[Pfaeff]

Danke schonmal. Die Übergabe-Parameter sind die Indizes der Nodes im Array der Pathfinder-Klasse. Ich könnte auch direkt die Nodes übergeben, nur war das so einfacher zu testen.

Wenn das auf Wikipedia erläuterte Prinzip funktioniert, so müsste es auch so gehen wie ich es gemacht habe. Die Tiefensuche zu verwenden und so erweitern, wäre mein Ansatz, falls ich das hier nicht zum Laufen bekomme. Wichtig ist mir, dass es schnell läuft und ich auf jedenfall den kürzesten Weg erhalte.

mfg

 

[hdi]

Ich würde an deiner Stelle von deinem spezifischen Programm etwas weggehen,
und es nur mal ganz abstrakt und leicht programmieren, damit du nur den Algorithmus hinbekommst
und ihn gut verstehst.

Einfach ein 2d-int-Array als Adjazenz-Matrix. So nennt man eine quadratische Matrix deren Zeilen und Spalten
für die ID's von Knoten stehen und die Einträge für die Gewichtung der Kanten zwischen ihnen.

zB

0 5 2
0 0 3
0 0 0

wäre dann:

Knoten 1 -> Knoten 2 = 5 Kosten
Knoten 1 -> Knoten 3 = 2 Kosten
Knoten 2 -> Knoten 3 = 3 Kosten

Dann kannst du ganz simpel nur mit int-werten rechnen und hast nicht irgendwelche echten Objekte mit
tausend Methoden usw. Du musst nur beachten dass ja der erste Eintrag in einem Array immer Index 0 hat.

 

[Pfaeff]

So spezifisch ist mein Problem eigentlich nicht Ich finde das Problem mit Klassen und Methoden eigentlich auch anschaulicher, trotzdem habe ich jetzt mal eine Tiefensuche gemacht (nicht so leicht, durch die Rekursion irgendwie den Pfad mitzugeben, ich habe jetzt einfach einen String genommen):

public class TestPathfinding {
    public static void main(String[] args) {
        int numNodes = 5;
        int[][] matrix = new int[numNodes][numNodes];
        matrix[0][1] = 3;
        matrix[0][2] = 7;        
        matrix[1][2] = 5;
        matrix[2][3] = 8;
        matrix[2][4] = 5;
        findPath(matrix, 0, 3, new String());
    }
    public static int findPath(int[][] matrix, int from, int to, String path) {
        if (from == to) {
            System.out.println("found: " + from + " path: " + path);
            return from;
        }
        for (int i=0; i<matrix[from].length; i++) 
            if (matrix[from][i] != 0) {
                findPath(matrix, i, to, new String(path + i));
        }
        return -1;
    }
}

Nur bin ich mir nicht sicher, ob ich darauf aufbauen kann. Der A* unterscheidet sich ja doch schon in einigen Punkten von der Tiefensuche. Angefangen damit, dass er nicht rekursiv modelliert ist. Außerdem brauche ich noch eine Näherungsfunktion, das war leichter als ich noch Vektoren hatte ich kann zwar jetzt alle gefundenen Wege durchsuchen und schauen, welcher der kürzeste ist, allerdings gibt es Probleme, wenn ich ungerichtete Graphen benutze, bzw wenn ich jetzt sowas hinzufüge: matrix[4][2] = 1; bekomme ich zirkuläre Referenzen und laufe Gefahr, dass wenn ich einfach abbreche, den Optimalen Weg übersehe, also muss ich eine maximale Rekursionstiefe festlegen. Ich glaube das wird fummelig

€: Ich habe den A* jetzt zum Laufen bekommen, es waren ein paar kleine Programmierfehlerchen dafür verantwortlich. Die Index-Abfrage beim Remove in meiner Pathlist Klasse war schlichtweg falsch und beim Hinzufügen eines neuen Nodes, wurden nur dann Nodes hinzugefügt, wenn schon welche drin waren. (So wurde also nie ein Node hinzugefügt). Bei der Ausgabe des Pfades verschwand dann auch plötzlich die Zeile tmp = tmp.predecessor und als die wieder drin war lief es einwandfrei

mfg

 

[Marco13]

...es nur mal ganz abstrakt und leicht programmieren, ...

Einfach ein 2d-int-Array als Adjazenz-Matrix.

Das klingt IMHO widersprüchlich: Eine Adjazenzmatrix ist EINE Möglichkeit, einen gewichteten Graphen zu repräsentieren. Im Idealfall ist der Algorithmus aber unabhängig davon, wie die Daten intern repäsentiert werden. Also, es kann nicht schaden statt sowas wie
float weight = matrix[j];
sowas zu schreiben wie
float weight = getWeightOfEdge(getNode(i), getNode(j));
oder so...