A*-Algorithmus

[stKev]

Hi,

ich habe ein Problem beim A* nach dem der Algo zum Ziel terminiert ist. Ich versuche es erstmal kurz zu halten, da ich denke, dass das Problem von euch Recht einfach zu lösen ist. Falls Mehrbedarf an Information besteht, werde ich die natürlich nachliefern.

Die meisten Knoten befinden sich nun in der closedList. Diese ist ein Set von Knoten. Die Reihenfolge bei der Ausgabe ist sortiert nach ihrer Überprüfung. Ist ein Knoten abschließend geprüft worden, hinsichtlich der Kosten und der "Zeigerrichtung". Jeder Knoten in der Set kennt nach seiner Überprüfung seinen Vorgänger. Ebenso enthält die Set aber auch Knoten die ins "Leere" geführt haben, da ein anderer Weg der zwischenzeitlich gewählt wurde, eine günstigere Alternative anbat.
Er berechnet die Gänge häufig im Wechsel. Je ein Tile. Ja, stimmt sollte ich erwähnen, das Level ist gerastert.

Frisch aus meinem Editor, wobei er bei einem 1500*32 x 1500 * 32 Pixel großem JPanel (ein Grid 32x32) schlappt macht. Aber reicht erstmal.

Zurück zum Thema.

Wie iteriere ich nun mit ein paar schlauen Abfragen über die Set, dass ich am Ende eine ArrayList<Node> habe, die von Start nach Ziel sortiert, mir den Weg wieder gibt den ich suche???:

- Index 0 - x // start - ziel (einmal drüber Männchen läuft )

Ich würde also gerne die nicht relevanten Routen rausfiltern. Wobei es auch schön wäre zu sehen wie er sich den Weg aus dem Labyrinth sucht.

Ich glaube ich komme einfach nicht drauf,es möchte nicht so recht wie ich es will.
Vorallem ich benutzte ja node.getPredecessor(). Nur möchte genau dieser dann ungerne erneut gefragt werden, welcher sein Vorgänger ist. Das klappt nur bedingt.
Jedoch sind alle Pfeile, die die Zeiger auf dem JPanel repräsentieren sollen, richtig ausgerichtet.....???:L

Danke euch. gn8

 

[Marco13]

Viel Text, aber keine Problembeschreibung mit der man was anfangen könnte. Etwas Rubber Ducking könnte hier vermutlich schon helfen.

Aus dem Bauch raus: Wenn der A* fertig ist, enthält jeder Knoten eine Information über den Knoten, von dem aus man in erreicht hat. Da sollte man doch rückwärts langlaufen können?

 

[stKev]

Das habe ich doch geschrieben:

Vorallem ich benutzte ja node.getPredecessor(). Nur möchte genau dieser dann ungerne erneut gefragt werden, welcher sein Vorgänger ist. Das klappt nur bedingt.
Jedoch sind alle Pfeile, die die Zeiger auf dem JPanel repräsentieren sollen, richtig ausgerichtet.....

 

[Illuvatar]

Aber was soll "Das klappt nur bedingt" bedeuten? Da mit getPredecessor durchzugehen scheint mir die richtige Lösung zu sein, und anhand von dem was du geschrieben hast, liefert nicht mal meine Kristallkugel einen Grund, warum das nicht klappen sollte

 

[stKev]

Ja genau das ist die Frage die ich mir stelle. Ich denke nämlich auch, was is daran nun so schwer, den "Pfeilen" auf dem Boden zu folgen. Ich kriegs ja in der visuellen Ansicht auch hin ihnen zu folgen und alle stimmen. Moment ich werde es mal eben nochmal erneut testen, was z.b. "node.getPredecessor().getPredecessor();"

Bin mir über die Ausgabe von gestern Nacht nicht mehr ganz sicher, damit ich weiter arbeiten konnte hatte ich es rückgängig gemacht und erstmal mit dem Feintuning begonnen.

JPanel verschieben etc.

Wollte es vllt so machen das ich nun vom Ziel aus mir den ersten Vörgänger geben lasse ihn in eine ArrayList packe und dann über die ArrayList nach seinem nächsten Nachbarn fragen lasse.

So der Plan. Sobald ich mehr zu der Ausgabe der Vorgänger sagen kann, werde ich sie posten.

:toll:

 

[stKev]

A*-Methode

	private boolean aStar() {
		
		// fügt den Startknoten der Queue hinzu
		openList.add(start);
		
	    // diese Schleife wird durchlaufen bis entweder
	    // - die optimale Lösung gefunden wurde oder
	    // - feststeht, dass keine Lösung existiert
		while (!start.equals(ziel)) {
			
			// setzt current und entfernt das Objekt mit dem geringsten f-Wert von der openList
			Collections.sort(openList);
			this.current = openList.get(0);

			System.out.println("closedList: " + closedList);
			// Knoten mit dem geringsten f Wert aus der Open List entfernen
			openList.remove(0);
			
			// Wurde das Ziel gefunden?
			if (this.current.equals(this.ziel)) {
				System.out.println(path);
				return true;
			}
			
	        // Wenn das Ziel noch nicht gefunden wurde: Nachfolgeknoten
	        // des aktuellen Knotens auf die Open List setzen
			expandNode();
			
			// fügt current der closedList hinzu
			// der aktuelle Knoten ist nun abschließend untersucht
			closedList.add(this.current);
			
			if (openList.isEmpty()) {
				// die Open List ist leer, es existiert kein Pfad
				System.out.println("No Path available.");
				return false;
				
			}
		}
		return false;
	}

A* ruft expandNode auf

	private void expandNode() {
		
		// ermittelt aus den begehbaren Tiles diejenigen, die mit dem derzeit besuchten Tile collidieren.
		// Diese stellen nächstmögliche Schritte dar, die wir ausführen könnten.
		// Sie werden in die Warteschlange eingereiht und warten auf eine Prüfung
		// Die Zeiger werden auf den Vorgänger gerichtet.
		for (int i = 0; i < nodes.length; i++) {
			for (int u = 0; u < nodes[0].length; u++) {
				if (nodes[i][u] != null) {
					if (this.current.getRec().intersects(nodes[i][u].getRec())) {
						// wenn der Nachfolgeknoten bereits auf der Closed List ist - tue nichts
						if (closedList.contains(nodes[i][u])) {
							continue;
						}
						System.out.println("this.current Tile intersected with:");
						System.out.print(nodes[i][u].getRec() + " --/ Index /-- ");
						System.out.println("i [" + i + "] u [" + u + "]\n" + "---------------");
						// g Wert für den neuen Weg berechnen: g Wert des Vorgängers plus
				        // die Kosten der gerade benutzten Kante
						int g = nodes[i][u].computeTempG(current);
						
				        // wenn der Nachfolgeknoten bereits auf der Open List ist,
				        // aber der neue Weg nicht besser ist als der alte - tue nichts
						if (openList.contains(nodes[i][u]) && nodes[i][u].getF() <= g + nodes[i][u].computeH()) {
							continue;
						}
						
						if (!this.current.equals(nodes[i][u])) {
							
							System.out.println("setP");
							nodes[i][u].setPredecessor(current);
							path.add(current.clone());
							nodes[i][u].setG(g);
							nodes[i][u].setF(g +  + nodes[i][u].computeH());
							System.out.println(g);
						}
						
						if (openList.contains(nodes[i][u])) {
							openList.remove(nodes[i][u]);
							
						} else {
							openList.add(nodes[i][u]);
						}
					}
				}	
			}
		}
	}

boolean drawPath bleibt solange false bis aStar true zurück gibt.

	public void displayPath(Graphics2D g2d) {
		g2d.setColor(Color.GRAY);
		for (Node n : path) {
			g2d.fill(n.getRec());
		}
		System.out.println("##########################################################");

                // AB HIER IST BAUSTELLE

		ArrayList<Node> shortestPath = new ArrayList<Node>();
		for (int i = path.size(); i >= 0; i--) {
			System.out.println(i);
			shortestPath.add(path.get(i).getPredecessor());

			
		}
		g2d.setColor(Color.GREEN);
		for (Node n : shortestPath) {
			g2d.fill(n.getRec());
		}
	}

Stürzt beim ersten ausführen der Schleife ab.

Exception in thread "AWT-EventQueue-0" java.lang.IndexOutOfBoundsException: Index: 64, Size: 64
at java.util.ArrayList.rangeCheck(Unknown Source)
at java.util.ArrayList.get(Unknown Source)
at lab.PathFinder.displayPath(PathFinder.java:73)
at lab.Lab.paintComponent(Lab.java:95)

Index je variiert je nach Entfernung von Start und Ziel untereinander.

Hoffe mir kann einer Helfen ich krieg keine Ideen, weshalb es nicht klappen möchte.
Da dachte ich doch am Anfang, das wäre zum Schluß am einfachsten.:bahnhof:

Node gibt f-Wert zurück (Bewegungskosten + geschätzte Kosten)

closedList(gelbe Umrandung): [886, 794, 219, 786, 643, 175, 839, 559, 492, 789, 727, 878, 660, 884, 244, 864, 266, 263, 906, 194, 403, 730, 618, 663, 200, 172, 744, 537, 889, 811, 197, 752, 172, 197, 378, 828, 534, 400, 853, 216, 260, 0, 333, 883, 861, 886, 469, 222, 769, 685, 601, 727, 836, 908, 194, 853, 238, 702, 288, 685, 425, 576, 811, 447, 905, 310, 241, 375, 895, 895]


path(graue Felder): [0, 0, 0, 172, 172, 172, 172, 175, 194, 194, 197, 216, 216, 219, 238, 238, 241, 263, 288, 288, 333, 333, 378, 378, 403, 425, 447, 447, 492, 492, 534, 537, 559, 576, 601, 618, 618, 643, 660, 663, 685, 685, 685, 702, 727, 730, 744, 744, 752, 769, 786, 789, 794, 794, 811, 811, 836, 839, 839, 839, 853, 853, 861, 861, 861, 864, 864, 878, 883, 883, 883, 886, 895, 895, 895, 895, 905, 905]

blaue Umrandung = openList

pathList - Minus Programmablauf ohne shortestPath arrayList in displayPath();

 

[Marco13]

Beim Überfliegen
for (int i = path.size(); i >= 0; i--) {
ändern in
for (int i = path.size()-1; i >= 0; i--) {

Ansonsten... ist das vermutlich nicht besonders effizient, aber... da müßte man genauer schauen...

 

[stKev]

shortestPath - Minus

so sieht aus mit:

	public void displayPath(Graphics2D g2d) {
		g2d.setColor(Color.GRAY);
		for (Node n : path) {
			g2d.fill(n.getRec());
		}
		System.out.println("##########################################################");
		ArrayList<Node> shortestPath = new ArrayList<Node>(path.size());
		for (int i = path.size()-1; i >= 0; i--) {
			System.out.println(i);
			shortestPath.add(path.get(i).getPredecessor());

			
		}
		g2d.setColor(Color.CYAN);
		for (Node n : shortestPath) {
			if (n != null) {
				g2d.fill(n.getRec());
			}
			
		}
	}

Es sind also noch weitere Zweige da, die es zu eliminieren gilt, bevor der shortestPath for mir liegt.
Nun ist meine Frage: Was frage ich nun bevor ich path.get(i).getPredecessor(); aufrufe und diesen Knoten zum shortestpath hinzufüge?

 

[Marco13]

Wegen des Ungleichgewichts zwischen (unübersichtlichem) Code und ... schwer verständlichen Fragen, ein bißchen Pseudocode, vielleicht meinst du das:

List<Node> shortestPath = new ArrayList<Node>();
Node current = lastNode;
while (current != null)
{
    shortestPath.add(0, current);
    current = current.getPredecessor();
}

Wenn nicht.... muss man wohl doch mehr Zeit investieren...

 

[stKev]

Wegen des Ungleichgewichts zwischen (unübersichtlichem) Code und ... schwer verständlichen Fragen, ein bißchen Pseudocode, vielleicht meinst du das:

unübersichtlichem Code? Da stehen ein paar sysout drin mit den ich mich vorgearbeitet habe beim implementieren und genug Kommentare um die Schritt nachvollziehen zu können. Deine Kritikpunkte seh ich leider nicht. Aber darfst mich gerne Aufklären, bin da aufgeschlossen.

Habe ein Link hinzugefügt, sodass du die Möglichkeit hast, die visuelle Ausgabe zu betrachen. 0 0 0 ist Start x x 0 (untere Zahl 0) ist Ziel. Die Zeiger sind wohl anscheinend richtig gesetzt. Keine Idee wie ich die Sackgassen ausfilter?
Deine Methode habe ich ein wenig anders implementiert. Glaube aber auch deine würde die Sackgassen nicht ausfiltern,
sondern selbiges wie die meine tun.

-> shortestPath - Minus (neue Version Farben angepasst)

Magenta = path enthält alle während des Prozesses beschrittenen Tile
(diese müssen nicht alle auf der kürzesten Route liegen - Sackgassen entstehen sobald ein Gang bessere Bewegungskosten aufweist)

Der Algo springt meist zwischen den verschiedenen Gängen hin und her, wobei es aber auch Phasen gibt, in denen er sicht schnell in eine Richtung entwickelt.

aus der ArrayList möchte ich die Sackgassen rausfiltern und wäre fertig.
Ich kriege es aber nicht hin zu implementieren. Leider!!

 

[stKev]

List<Node> shortestPath = new ArrayList<Node>();
Node current = lastNode;
while (current != null)
{
shortestPath.add(0, current);
current = current.getPredecessor();
}

War die Lösung für mein Problem. Habe es später gegen mein Versuch getauscht, um es zu testen und es stellte sich raus, klappt. Hm, dachte meins macht das selbe woran es bei mir nun gehappert hat habe ich bis dato noch nicht ermitteln können.

Ich danke dir. :toll:

 

[Marco13]

Naja, "unübersichtlich" ... Das mit dem Grid sieht irgendwie seltsam aus. Sollte man nicht von jedem Knoten aus direkt die Nachbarn expanden können? So, mit dem Grid, dem Collections.sort und vielen, vielen (O(n)) contains-Aufrufen ist das sicher alles andere als effizient...

 

[stKev]

Ok bei der Lauzeitbetrachtung muss ich dir natürlich Recht geben. Da gibt es sicherlich noch einiges dran zu verfeinern. Dafür war es nun aber auch erstmal ein Testprogramm um sich mit dem A* auseinanderzusetzen. Dafür terminiert er aber relativ schnell auf das Ziel zu und das Lab ist nicht grade klein.

Wobei sich dann natürlich am Ende immer die Frage stellt, wie sieht es aus, wenn es da nicht nur um eine Berechnung für einen kürzesten Weg. Sondern wenn für viele Objekte die eine Bewegungsanfrage haben dieser benötigt wird.
Da könnte es vllt dann zu Problemen führen in der Performance. Aber soweit bin ich dann wohl noch nicht fortgeschritten. Ich progge aber auch einfach gerne drauf los und habe nur eine grobe Idee im Kopf. Bin dann am Ende selber überrascht, wenn es wieder einmal funktioniert.
Aber für Freizeitprogrammierung um die Sprache zu lernen und mal zu sehen was ist möglich. Finde ist das eine gute Herrangehensweise die auch Spaß bereitet. Die Effizienz denke ich, stellt sich dann mit der Zeit von selbst ein, sobald man anfängt aus seinen Fehler zu lernen. Dann beim nächsten Projekt versucht man es noch ein wenig besser zu implementieren.

contains = O(n) linear ist ja noch zu verkraft. Zumal die openList wird ja immer schön geleert (sauber gehalten).