A*-Algorithmus - Probleme mit offener/geschlossener Liste

[_Zoidberg_]

Sers Leute,

ich programmier grad eine Routenplanung. Die sogar funktioniert. :wink: Nur bin ich noch nicht so ganz zufrieden, weil mein Programm beim Berechnen der Route viel zu viele Knoten auf meiner Karte okkupiert.

Ich denk mal, dass ich irgendwo in den Untiefen des Algorithmus einen Fehler gemacht habe, den ich aber trotz längeren Suchens nicht finde.

Wenn ich also z.B. eine Route auf einer leeren (also ohne Hindernisse) Karte zwischen zwei Punkten, die acht Felder voneinander entfernt liegen, berechnen will, hat meine offene Liste 49 Elemente und meine geschlossene 101.

Nachdem mein Programm so verschwenderisch mit dem Speicher umgeht, führt das bei längeren Routen auch schon mal zu einem StackOverflowError, bzw. verlangsamt sich die Berechnung.

Ich bin dabei (größenteils) nach folgendem Tutorial vorgegangen:
http://www.policyalmanac.org/games/aStarTutorial_de.html

Eine implementierte Version (nicht meine) ist hier zu finden:
http://www.arco.in-berlin.de/astern.html

Wenn ich mein Programm und das oben erwähnte vergleiche (also die Punkte vergleichbar setze), sehe ich, das meines viel mehr Punkte zur Berechnung heranzieht, obwohl das Programm (laut Autor) nach demselben Tutorial programmiert wurde.

Mal zum Vergleich:

Auf der Website

In meinem Programm

Was die Farben betrifft:

Bei beiden Versionen: Grün -> Start, Rot -> Ziel
Website - Dunkelgrau -> Route, Hellgrau -> geschlossene Liste
Mein Programm - gelb -> Route, Grau -> geschlossene Liste, türkis -> offene Liste

Damits nicht ganz so unübersichtlich wird, gibts den Code im nächsten Post.

Schon mal im Voraus danke an alle, die mir helfen
MfG
_Zoidberg_

 

[_Zoidberg_]

Die Rechenarbeit wird bei mir in der Klasse Route erledigt, die unter anderem den Ziel- und den Start-Knoten gespeichert hat, außerdem die Karte und andere Variablen.
Der Einfachheit halber kopier ich hier nur mal den Code rein, der den Algorithmus an sich betrifft.

toDo ist die offene Liste, done die geschlossene.
traceBackRoute ermittelt aus der geschlossenen Liste den Pfad vom Start- zum Zielpunkt, was ja funktioniert, deshalb lass ich die Methode hier mal außen vor.

Erst mal die Funktion, die alles in Gang setzt.

private void berechneRoute()
{
	algorithm(0);
		
	int pos = Collections.binarySearch(done, aktuell, new ComparatorWaypoint());
		
	try
	{
		tracebackRoute(done.get(pos));
	}
		
	catch(java.lang.ArrayIndexOutOfBoundsException e)
	{
		System.out.println("Exception in Route.berechneRoute: " + e);
	}
}

Dann die Funktion algorithm().

private boolean algorithm(int durchlauf)
{
// Prüfung auf Erreichung des Zielorts.
	if(checkDone(new Waypoint(ziel, ziel)))
	{
		System.out.println("Ziel erreicht - Wegkosten empirisch: " + aktuell.getWegkostenEmpirisch());
		System.out.println("toDo.size(): " + toDo.size());
		System.out.println("done.size(): " + done.size());
		System.out.println("Durchlauf: " + durchlauf);
	//	toDo.clear();
			
		return true;
	}
		
	if(toDo.isEmpty())
			return false;	
	
	this.checkSurroundingArea(aktuell);
		
	aktuell = getRecommendedPoint();
		
	return(algorithm(durchlauf + 1));
}

checkDone() prüft, ob ein Knoten schon in der geschlossenen Liste vorhanden ist.
Ich füge die Knoten nach ihren x-/y-Koordinaten geordnet ein, daher kann ich dafür eine binarySearch verwenden.

private boolean checkDone(Waypoint w)
{
	try
	{
		int pos = Collections.binarySearch(done, w, new ComparatorWaypoint());
		
		if(pos < 0)
			return false;
		
		else
			return true;
	}
	
	catch(Exception e)
	{
		System.out.println("Exception bei Route.checkDone: " + e);
	}
	
	return false;
}

checkSurroundingArea prüft die Knoten in der Umgebung des aktuellen Knotens. Hier nur für einen Knoten in der Umgebung, für die anderen 7, die an den aktuellen Knoten angrenzen, ist die Vorgehensweise genauso.
n.isFree() gibt zurück, ob der Knoten frei ist (also keine Mauer oder sonstiges Hindernis).

try
{
	Node n = karte.getNode(aktuell.getX_coordinate(), aktuell.getY_coordinate()-1);
	
	if(n.isFree())
	{	
		Waypoint nord = new Waypoint(n, aktuell);
		checkStatus(nord);
	}
}
catch(java.lang.IndexOutOfBoundsException e) { System.out.println("Nord draußen."); }

checkStatus überprüft, ob der Knoten dafür geeignet ist, in die Liste aufgenommen zu werden - wenn er noch nicht in der offenen/toDo-Liste ist, dann kommt er dahin. Wenn er schon in der geschlossenen/done-Liste ist, wird gar nichts getan.
Wenn er schon in der offenen/toDo-Liste ist, dann wird überprüft, ob der Pfad vom aktuellen Knoten zu diesem Knoten kürzer ist als der vom Vorgänger zu diesem Knoten (-> createCheckedNewPath; klingt vl. ein bisschen kompliziert, s. unten).

private void checkStatus(Waypoint w)
{
	try
	{
		if(!checkDone(w))
		{
			if(!checkToDo(w))
			{
				int pos = Collections.binarySearch(toDo, w);
				
				if (pos < 0)
				  toDo.add(-pos -1, w);
			}
					
			else
				createCheckedNewPath(w);
		}
	}
	
	catch(java.lang.IndexOutOfBoundsException e) {	System.out.println("Exception in checkEnvironment");	}
}

createCheckedNewPath() überprüft, wie schon gesagt, ob der Pfad vom aktuellen Knoten zu diesem Knoten kürzer ist als der vom Vorgänger des Knotens zu diesem Knoten. Wenn ja, ist der aktuelle Knoten der neue Vorgänger des überprüften Knotens.
Um ehrlich zu sein, weiß ich nicht, wie sich das in der Praxis auswirkt (bzw. bei mir gar nicht, wenn ich die Methode auskommentiere, ändert sich an der Route nichts. Aber vl. hab ich die Methode auch falsch programmiert.), ich hab versucht, die Methode so umzusetzten, wies im Tutorial steht.

private boolean createCheckedNewPath(Waypoint w)
{
        // getWegkostenEmpirisch sind die Wegkosten, die ein Knoten real hat, also wie hoch die Wegkosten bis zu                                          
        // diesem Punkt sind.. Daneben gibt es noch die wegkostenHeuristisch, also die geschätzte Entfernung zum 
        // Zielpunkt.

	int newpath = 0;
	
        // Das if-Konstrukt hier überprüft, ob der Knoten schräg oder "gerade" zum aktuellen Knoten liegt.
        // Dementsprechend gibts einen Wegkosten-Aufschlag von 15 bei schrägen, 10 bei "geraden" Knoten.
	if(aktuell.getX_coordinate() == w.getX_coordinate() + 1 || aktuell.getX_coordinate() == w.getX_coordinate() - 1)
	{
		if(aktuell.getY_coordinate() == w.getY_coordinate() + 1 || aktuell.getY_coordinate() == w.getY_coordinate() - 1)
			newpath = aktuell.getWegkostenEmpirisch() + 15;
			
		else
			newpath = aktuell.getWegkostenEmpirisch() + 10;
	}
		
	else
		newpath = aktuell.getWegkostenEmpirisch() + 10;
		
	if(aktuell.getWegkostenEmpirisch() + newpath < w.getWegkostenEmpirisch())
	{
		int pos = Collections.binarySearch(toDo, w);
		toDo.remove(pos);
		
		w.setAncestor(aktuell);
			
		pos = Collections.binarySearch(toDo, w);
		toDo.add(-pos -1, w);
			
		return true;
	}
		 
	else
		return false;
}

Ich weiß übrigens, dass es viel verlangt ist, dass sich das jemand mal wirklich anschaut. Aber ich bin umso dankbarer.

MfG
_Zoidberg_

 

[Marco13]

Hab's jetzt nicht komplett nachvollzogen, aber ... dein Bild sieht aus, als würdest du eine "Breitensuche" machen (also praktisch den Dijkstra). Das Tutorial ist ziemlich ... umfangreich (manchmal kann man Sache auch totlabern :roll: ) .. und die Zusammenfassung ist IMHO alles andere als Übersichtlich. Deine Aussage zur ominösen "createCheckedNewPath"-Methode klingt ein bißchen wie "ich schreib' einfach mal runter, egal was" (also, offenbar weißt du ja nicht, was du da geschrieben hast). Wenn es dir darum geht (aber auch wenn nicht) könntest du dich bei der Implementierung lieber an "übersichtlicheren" Pseudocodes orientieren, wie etwa dem auf http://de.wikipedia.org/wiki/A*-Algorithmus

 

[_Zoidberg_]

Meinst du meine Zusammenfassung oder die im Tutorial?

Ansonsten geb ich dir Recht, diesen einen Teil hab ich nicht wirklich nachvollziehen können. Hab mir aber mehr oder weniger gedacht, dass das eh wurscht is. :wink: Werd ich mir nochmal anschauen.

Was den Dijkstra angeht...ich hab das so verstanden, dass der Dijkstra keine Koordinaten, sondern nur Entfernungen von einem Knoten zum anderen verwendet (oder lieg ich da falsch?).
Insofern ist mir nicht ganz klar, was du meinst. Aber wenn du mirs erklärst, könnte mir das sehr weiterhelfen.

 

[Der Müde Joe]

Was den Dijkstra angeht...ich hab das so verstanden, dass der Dijkstra keine Koordinaten, sondern nur Entfernungen von einem Knoten zum anderen verwendet (oder lieg ich da falsch?).

A* ist eigentlich ein Dijkstra Single Shortest Path Algorithmus. Zusätzlich wird jedoch noch eine
Heuristik benutzt, sprich die Entfernung zum Ziel geschätzt. Dies macht dem Algo recht
zielstrebig.

Eine gute Seite die ich dir empfehlen kann
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html#S2

 

[_Zoidberg_]

Sehr interessante Seite, thx für den Link. Werd ich mir mal anschauen.

 

[Marco13]

Ja, das Bild bei "Dijkstra" sieht deinem ja schon verdammt ähnlich :wink:

Ich meinte übrigens die "Zusammenfassung der A*-Methode" auf der Seite. Das, was da steht, ist eigentlich "Pseudocode", aber sowas wie Punkt 2c) zu lesen und nachzuvollziehen :autsch: äh ja - den ganzen Atrikel mal zu lsen, um den Kontext zu verstehen ist vielleicht OK, aber diese Zusammenfassung als Richtlinie für eine Implementierung zu verwenden könnte ungünstig sein...

 

[_Zoidberg_]

Tjo, wie man sieht, isses ungünstig, zumindest für mich.

Mir drängt sich aber die Frage auf, wo jetzt genau der implementierungstechnische Unterschied zwischen Dijkstra und A* liegt. Ich hab mir auch den Wiki-Artikel durchgelesen, mir ist aber kein Unterschied zu meiner Implementierung aufgefallen.

Ich weiß zwar, dass da einer sein muss (und ich nur zu blöd bin, ihn zu finden :? ), aber es kommt mir komisch vor, dass ich einen A*-Algorithmus programmieren will und plötzlich kommt ein Dijkstra raus, weil ich irgendwo was vergessen/zuviel gemacht/falsch gemacht hab. Da kann der Unterschied, die Implementierung betreffend, doch nicht so groß sein.
Fragt sich nur, wo der genau liegt.


[Edit] Okay, Schande über mich. Mittlerweile funktionierts, der Fehler war selten dämlich.

Wen's interessiert: Der Unterschied zwischen Dijkstra und A* liegt, wenn ich das richtig verstanden hab, darin, dass der Dijkstra nur die bisherigen Wegkosten berücksichtigt, A* auch die geschätzten bis zum Ziel.

Ich hab in meinem Programm aber die bisherigen Wegkosten mit 10 bzw. 15 pro Feld angesetzt - die heuristischen, also die geschätzen bis zum Ziel, wurden aber in Math.abs(Koordinate - Koordinate) ausgerechnet. Damit waren die geschätzten Kosten zehn- bis fünfzehnmal weniger "wert" als die bisherigen und sind deshalb nicht ins Gewicht gefallen.
Deshalb lief das Programm zwar theoretisch als A*, praktisch aber als Dijkstra.

Auf jeden Fall noch mal danke für alle Antworten.

MfG
Zoidberg