JAVA - Hamster

[M@tes]

Während die anderen in meiner Klasse noch beim rechtUm(); sind, hab ich es schon geschafft, den Hamster autonom durch das Labyrinth zu jagen.
Hab zwar in JAVA genauso wenig ahnung wie die anderen, aber konnte paar Sachen aus meinen Perlkenntnissen übernehmen :biggrin:
Hab das Script gerad nich da, aber es läuft folgendermassen:
Hats nen Korn?
Ist vorne frei?
JA: Er läuft gerade aus.
NEIN: Er dreht einmal nach links.
Ist vorne frei?
JA: Er läuft gerade aus.
NEIN: Er dreht einmal nach links. // Achtung, er könnte im Kreis laufen! Drum gehts so weiter:
Geht er wieder zurück?
JA: Er dreht sich nochmal nach links. // Somit geht er nach rechts
Ist vorne frei?
JA: Er läuft gerade aus.
NEIN: Er dreht sich 3mal nach links. // Somit geht er wieder zurück
Ist vorne frei?
JA: Er läuft gerade aus.
...

Er läuft also immer im Kreis. Immer nach links.
Es hat aber einen Haken!
Einige Positionen erreicht man nur, wenn der Hamster rechts geht.
Woher weiss der Hamster nun aber, das er diesmal nach rechts gehen soll und nicht nach links?
Hatte dafür 3 Ideen, die aber meinen Wissensstand um längen übersteigen:
1. Nach 50 Endlosschleifen geht er irgendwann immer nur rechts. Billig, aber janu^^
2. 2Dimensionales Array, wo halt gespeichert wird, wo was ist und er erkennt, wo er noch hin muss.
3. Etwas ähnlich, nur halt als eine Binärzahl. Jedes Kästchen bekommt dann eine Zahl ( 1,2,4,8,16,32,... ). So kann man schnell ausrechnen, welche Kästchen noch nicht besucht wurden.

Ist das überhaupt noch im Hamster möglich?
Bin ich auf dem richtigen Weg?
Wie habt ihr das damals gemacht?

[Trap]

Es kommt darauf an wie das Labyrinth aufgebaut ist. Im allgemeinsten Fall musst du eine Tiefensuche machen. Wenn das Labyrinth Ein- und Ausgänge an einer Außenwand hat und ich glaub noch ein paar mehr Bedingungen erfüllt sind reicht immer linksrum oder immer rechtsrum an der Wand entlang laufen.

Tiefensuche sollte als Suchwort für Google reichen.

[M@tes]

Hmm, kenn das in Verbindung mit dem n-Tupel Modell.
Es tönt plausibel, wüsste jetzt aber nicht, wie ich das umsetzen kann.
Werds mir mal durch den Kopf gehen lassen.
Thanks

[ethrandil]

rekursiv gehts auch, und er ist am Ende sogar da wo er angefangen hat *g*. Such dann unter Backtracing...

Leider ist das mit dem Array problematisch, da der Hamster seine Position und die größe des Labyrints nicht kennt!

Ich habe aber meinen Java-Hamster damals so gehackt, dass ich auf diese Daten zugreifen konnte *g*. Außerdem hab ich eine Erweiterung namens "Doppelhamster" geschrieben, mit der ich zwei Hamster laden / ablaufen lassen konnte. gleichzeitig... hach ja. das waren Zeiten =)

- Eth

[M@tes]

Hehe, ein Informatiker aus der Klasse hat auch mal eben die rechtsUm Funktion so hinzugefügt. Also nicht 3mal links, sondern gleich rechts.
Mit dem Array gehts schon. Man kann den ja nachträglich erweitern lassen. Ihn quasi selbst erkennen lassen, wie gross das Labyrinth ist.

[Abnaxos]

Ist vorne frei?
JA: Er läuft gerade aus.
NEIN: Er dreht einmal nach links.

Umgekehrt:

Ist links frei?
JA: Nach links.
NEIN: Um 90° nach rechts drehen und nochmal links versuchen (also gleichbedeutend mit: "In dem Fall geraudeaus, dann rechts und schlussendlich zurück versuchen").

IIRC klappt das in 100% der Fälle, ohne auch nur einen einzigen Spezialfall einbauen zu müssen. Ich bin mir jedoch auch nicht mehr ganz sicher, ist doch schon ein paar Jährchen her ... :biggrin:

[Gast]

das problem beim speichern der "gelaufenen" positionen im array ist, dass du dir wege verbauen kannst, das kann fast immer klappen, aber halt nicht immer. die saubere lösung wäre per rekursion ( oder habe ich das falsch verstanden, wie du das im array speichern willst?)

[Trap]

Umgekehrt:

Ist links frei?
JA: Nach links.
NEIN: Um 90° nach rechts drehen und nochmal links versuchen (also gleichbedeutend mit: "In dem Fall geraudeaus, dann rechts und schlussendlich zurück versuchen").

IIRC klappt das in 100% der Fälle, ohne auch nur einen einzigen Spezialfall einbauen zu müssen. Ich bin mir jedoch auch nicht mehr ganz sicher, ist doch schon ein paar Jährchen her ... :biggrin:
Das ist "an der Wand entlanglaufen". Funktioniert nicht in allen Labyrinthen, wenn der Eingang oder der Ausgang nicht an einer Außenwand sind muss es nicht funktionieren.

[ethrandil]

Das funktioniert für jedes Labyrinth, das keine Zyklen hat und nur Wege, die nur einen Schritt breit sind!

Ideal um im Labyrinth ein Ziel zu finden wäre eine Tiefensuche mit einem Array, das verhindert, dass der Hamster Stellen doppelt absucht.

- Eth

[Trap]

Das funktioniert für jedes Labyrinth, das keine Zyklen hat.
Stimmt, das ist die genauste und kürzeste Formulierung.

[Coda]

Uhm A* anyone?

[Trap]

Uhm A* anyone?
A* passt auf die Aufgabenstellung nicht. Dazu fehlen die Koordinatenangaben.

A* ohne Metrik ist Tiefensuche und das hab ich schon vorgeschlagen.

[Coda]

Gut, ich kannte die genaue Aufgabenstellung ja nicht.