Ziel in einem Labyrint finden...
-
Hallo,
ich habe mich kürzlich mal gefragt, wie man einem Computer beibringen könnte, den Zielpunkt in einem Labyrint zu finden.
Ich habe mir daher mal einen kleinen Algo ausgedacht:Er beginnt am Startpunkt, sollte es mehr als eine Richtung geben, in die das Prog gehen kann, setzt es sich einen Wegepunkt und schlägt eine der Wege ein.
So geht es immer weiter, bis es in der Abzweigung nicht mehr weiter geht. Dann springt er zum letztem Wegepunkt zurück und fährt mit den anderen Wegen fort.
Wobei jedes begangene Feld speziell gekennzeichnet wird, sodass man feststellen kann, ob man hier schon war.Was haltet Ihr davon? Ist der Algo kompletter Müll?
Wie könnte man es noch bzw. noch effizienter machen?
Für C-Code wäre ich auch ausgesprochen dankbar!Vielen Dank
mfg grottenolm
-
Das ist ein richtig schöner klassischer Rekursiver Algorithmus dafür. Also durchaus kein Müll.
Was mir spontan einfällt, falls das Labyrinth keine Kreise enthält, kann man immer an der rechten Wand entlanggehen, kommt aber im Endeffekt aufs selbe hinaus wie bei deiner Lösung, sofern man an jeder Abzweigung zuerst rechts, dann mitte und dann links probiert.
-
Danke!
Das beruigt mich ungemein
Aber hat noch jemand ein Codebeispiel parat oder noch eine andere Idee, wie man das lösen könnte?
mfg grottenolm
-
Schau dich im INet mal nach A* um oder anderen Pathfinding Algos.
Dein Algo funktioniert so auch. Wenn du das Buch Gameprogramming Gems I hast ( sehr zu empfehlen ) dann hast du dort über 10 Algorithmen für dieses Problem drin. Deiner ist auch dabei.
Du könntest aber auch nach Richtung eine Priorität setzen. Das heißt du weißt ja wo das Ziel ist. Nimm dir den Vector dieser Richtung, und setzte diesen mit höherer Priorität. So könntest du schneller ans ziel kommen.
Man könnte auch mit einer Elipsenpriorität arbeiten. Das heißt um deine Position verschiebt sich eine Elipse in richtung Ziel. Und wenn du an einer Kreuzung bist, sucht er automatisch als erstes in diese Richtung.
-
sehr zu empfehln: http://www-cs-students.stanford.edu/~amitp/gameprog.html#Paths
-
Ok, danke. Klasse Tipps
Wen es Interessiert hier noch ein kleines recht gutes Tutorial, auf das ich gestoßen bin: http://www.policyalmanac.org/games/aStarTutorial.htm
mfg grottenolm