AStar Heuristik

[23]

Hallo,

ich habe den astar implementiert und habe folgendes Problem:

Path 1 = Ergebnis mit Manhattan Distanz, sieht nicht gut aus... daher nicht brauchbar
Path 2 = Wenn man als Heuristic einfach nur die Differenz zwischen den X Werten zurück gibt (Math.abs(pos1.x - pos2.x))
Path 3 = Das wäre der Wunschpfad... Ist es möglich so einen Pfad mit einer geschickten Heuristik zu erreichen?

Viele Grüße

 

[XHelp]

Und was macht den Wunschpfad zum Wunschpfad?

 

[Logaff]

sry aber darf ich fragen was "AStar" ist?

 

[XHelp]

A*-Algorithmus ? Wikipedia

 

[faetzminator]

@Logaff: A*-Algorithmus ? Wikipedia
@TO: Dieser Pfad wird immer einer von x Möglichkeiten sein. Mach ein Labyrinth oder zumindest Hindernisse rein.

 

[Logaff]

wenn es darum geht nen labyrinth zu lösen evtl mal nach maze-algo suchen

 

[faetzminator]

Öhm Logaff, mit A* löst man genau solche Labyrinthe.
Aber langsam glaub ich, dass der TO was anderes will.

 

[muckelzwerg]

Die Frage von XHelp ist völlig richtig. Welche Bewertungen haben die Pfade denn bekommen? Sind sie gleichgut, oder ist der gefunden Gewinner eben besser?
Das musst Du erstmal klären, weil Du ja prüfen willst, ob die Suche überhaupt funktioniert. Manhattan-Distance sollte doch in dem Fall eigentlich ganz gut gehen, wenn ich das Bild richtig deute.

 

[Logaff]

ah hier is nen schönes applet was es deutlich macht 😛

 

[23]

So mal langsam!

Von einem einfachen rekursiven Maze Algo komme ich schon und der hilft nicht wirklich da er öfter mal seltsame Muster produziert.

Die Nodes sind in einem freien Feld und als Datenstruktur wird wiederum ein 2dim array für den AStar verwendet.

Es gibt keine Gewichtungen zwischen den Knoten d.h. node.g ist immer plus 1. Evtl. wäre hier der Ansatzpunkt.

Es kann Hinternisse geben die dann einfach abgefragt werden und der AStar läuft dann auch schön drumrum...

Ich hätte gerne Path3 weil der schöner aussieht. In diesem Beispiel gab es keine Hinternisse und wie gesagt keine Gewichtungen d.h. der AStar kann sich frei entfalten...

Es kommt nicht auf den kürzesten Weg an sondern einen Weg mit 1-2 knicken...

Wer kurz mal testen möchte kann sich dieses JS (Nicht Java) Framework laden.
Brian Grinstead Blog Archive A* Search Algorithm in JavaScript

 

[Marco13]

Wie wär's mit der Euklidischen Distanz als Abschätzung? :bahnhof:

 

[SlaterB]

wieso ist Path2 mit nur einem Knick nicht schöner als Path3 mit zwei Knicken?
wenn alles schachbrett ohne Hindernisse verläuft, dann ist Path2 schnell gemacht, nach links oder unten und wenn nötig abbiegen,
falls du es irgendwie schöner findest kannst du ja per Zufall noch einen zweiten Knick einbauen?!

Hindernisse sind bestenfalls so wenige, dass die zugehörigen Zeilen und Spalten ignoriert werden und noch genug andere für gerade Wege da sind,
ansonsten geht dein gewünschter Path sowieso nicht

Path1 sieht unlogisch aus, sollte es nicht halbwegs gleichmäßig schräg zum Ziel gehen, wird da Hindernissen ausgewichen?
wäre etwas sinnvoll, die auch mit einzuzeichnen, oder nicht? dann kann man vielleicht verstehen wieso Path2 nicht möglich ist und die Knicks von Path3 vielleicht doch nicht so dumm sondern erforderlich sind

edit:
mit muckelzwerg's Posting kommt mir eine Idee:
A-Stern oder irgendeine sonstige rekursive Suche verwenden und bei jedem Knick die Kosten des Weges deutlich erhöhen
-> das sollte Wege mit weniger Knicks letztlich bevorzugen, wobei das ohne Entfernungsheuristik evtl. nicht so viel besser als Bruteforce aller möglichen Weg-Kombinationen ist..

 

[muckelzwerg]

Langsam, Du willst den "schönsten" Weg und nicht den Kürzesten? Dann ist A* nicht unbedingt geeignet.
Path1 passt ja sauber zur Aufgabe, die A* löst. Vielleicht kannst Du was tricksen, indem Du die Suche fortsetzt, solange der Zielpfad noch zu viel "Knicke" hat. Allerdings wirds dann mit der Laufzeit unter Umständen nicht mehr schön.
Ansonsten gibt es in der Graphentheorie Verfahren mit denen man solche Optimierungen machen kann. Soweit ich weiß gibt es z.B. für VTK verschiedene Plugins, die Kantenüberschneidungen minimieren. (kann man bei UML Linienchaos gut gebrauchen ^^)
Konkret kann ich Dir da leider kein Verfahren nennen. Vielleicht recherchierst Du mal in diese Richtung.

 

[Gast2]

A* passt auch ... einfach statt Distanz die Anzahl der Knicke nehmen ... dann würde zwar Path2 rauskommen ... aber Ziel sind ja 1-2 Knicke 🙂

 

[23]

@SlaterB da sind keine Hinternisse... ein Hinternis wäre eine weitere Node also eine Zelle in dem 2dim array...

Hm hab grad einige weitere Tests durchgeführt und die Performance ist ganz schön schlecht bei großen Graphen. Man muss dazu sagen ich implementiere das ganze in JavaScript... AStar scheint wohl auch nicht zu klappen da es einfach ewiger dauert und ewig bedeutet Minuten...

Ich hab das Thema schonmal in einem andern Thread geschildert jedoch konnte keiner richtig verstehn was das Problem ist.

Ihr habt einfach eine Fläche und legt zufällig Nodes drauf. Jede Node hat Kinder. Dann klickt man eine Node an und es sollen einfach alle Kinder also alle Abhängigkeiten eingezeichnet werden.

=> Ergeben sich viele Möglichkeiten und Probleme aber was mich interessiert ist nur der Weg von Node A nach Node B => Dies lässt sich einfach mit einem 2dim Array abbilden...

In diesem Thread ist weiter unten ein Code für einen Backtracker also ein Algo der gut in einem Maze funktioniert... in einem freien Feld mit evtl. 1-2 Hinternissen entstehen seltsame Muster...
Code für den Maze-Solver:
http://www.java-forum.org/spiele-mu...53-zufallsweg-bzw-weg-2dim-matrix-finden.html

Ich bin langsam am Ende mit meinem Wissen 🙁

Hat jemand eine einfache Idee von A nach B zu kommen?

Der Backtracker läßt sich auch optimieren:

		if(nextRow == targetRow) {
			
			moveOn = (nextColumn > targetColumn) ? backtrackerOpt(nextRow, nextColumn-1, stack) : backtrackerOpt(nextRow, nextColumn+1, stack);
			
		} else if(nextColumn == targetColumn)  {
			
			moveOn = (nextRow > targetRow) ? backtrackerOpt(nextRow-1, nextColumn, stack) : backtrackerOpt(nextRow+1, nextColumn, stack);
			
		}

=> wenn er auf "gleiche Höhe" ist versucht er diese Richtung zu laufen.

 

[fallencake]

Hi
Was unterscheided denn Path3 von Path2? Mit ist schöner kann der Computer nichts anfangen (und wir auch nicht🙂.
Wenn du also definieren kannst was Path3 von path2 unterscheided dann kannste das auch irgendwie umsetzen.

Und zum Zufallsweg: Da gibts fast unendlich viele Möglichkeiten wie du zu einem mal mehr mal weniger zufälligen Weg kommst. Bau doch einfach mal eine Zufallszahl als Wegkosten zwischen den Notes ein 🙂 - Dann wirst du erstmal wirr herumlaufen bevor du dann irgendwann zum Ziel kommst.