Algorithmus gesucht

[chmee]

aStar A* ist der wohl passende Algorithmus.

http://de.wikipedia.org/wiki/A*-Algorithmus

mfg chmee

 

[Shakie]

Ich kannte A* zwar nicht, aber Wiki sagt:

Der A*-Algorithmus findet allgemein einen optimalen Pfad zwischen zwei Knoten in einem Graphen.

Ich verstehe nicht wie A* für die Schatzsuche behilflich sein sollte. Schließlich ist der Zielknoten nicht bekannt!?

 

[kle-ben]

aStar A* ist der wohl passende Algorithmus.

Tiefen- und Breitensuche funktioniert hier nicht da die Karte unbekannt ist.
Der A* Algorithmus funktioniert leider erst recht nicht da das Ziel unbekannt ist.
Es gibt also keine Heuristik mit der man einen optimalen weg bestimmen kann.

Es bleibt dir also nichts anderes übrig als die gesammte Karte abzulaufen.
Da du jedoch über den Rand laufen kannst ist das jedoch relativ einfach.

- Laufe solange nach Links bis du wieder zu deiner Ausgangspositon gelangst.
- Gehe zwei Felder nach unten und definiere die aktuelle Position als Ausgangspunkt.
- Beginne wieder von vorne.

Kommt während dieses Ablaufs das Item in deinen Sichtbereich musst du
natürlich unterbrechen und darauf zulaufen. Merke dir bei dem Vorgang alle
Felder. Bist du bei deiner Suche nach dem Item auf das Zielfeld gestoßen zu
dem du das Item später bringen musst, dann kannst du anschließend den
A* Algorithmus anwenden um den kürzesten weg zu finden.

 

[chmee]

Sorry, ich hab dann zu schnell überfolgen und nicht gelesen, dass Punkt B nicht bekannt ist, sondern erst gesucht werden muß. Folgend: Wenn Du auf der Karte losgehst, erscheinen also mehr Felder als nur das betretene..

Die eben genannte Idee scheitert an Löchern zwischen zwei Hindernissen. Und man sieht an einer Zeichnung, dass es in der Vertikalen auch mehr Schritte sein dürfen..

Letztlich muß ein Alg.s gefunden werden, der die Welt vollständig absucht - da würd ich erstmal definieren, dass es freie und unfreie Felder gibt. Unter den unfreien Feldern gibt es welche, die nicht passierbar sind und jene, die etwas bringen (sprich: Schatz). Da sollte sich etwas in der Robotik finden (zB Bug-Alogrithmus?).

Auch wenn folgende Links nicht immer direkt mit diesem Problem zu tun haben,
pack ich sie mal hier rein:
http://www.phpgangsta.de/algorithmus-wettbewerb-shortest-path
http://www.o-bizz.de/qbtuts/ai-tuts/pathfind/pdf/pathfinding.pdf

Diese beiden PDFs klingen vielversprechend:
http://www.brichzin.de/seminarfach/SA07_Pfadsuche.pdf
http://page.mi.fu-berlin.de/alt/vorlesungen/sem0809/Folien-hempel.pdf

mfg chmee

 

[gufi]

Hei

danke für euere Antworten. Ich werd die Woche den Algo. mal einbaun und am 25.1. weis ich dann wies ausgegangen is! Geb euch natürlich bescheid

Sollte noch wer andere Vorschläge haben, werd ich auch diese gerne ausprobieren.

lg