PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : JAVA - Hamster


M@tes
2005-09-02, 18:39:26
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
2005-09-02, 18:52:45
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
2005-09-02, 19:07:31
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
2005-09-03, 00:35:22
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
2005-09-03, 18:39:42
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
2005-09-03, 19:00:31
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
2005-09-04, 04:02:23
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
2005-09-04, 15:09:20
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
2005-09-04, 23:25:40
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
2005-09-05, 01:44:25
Das funktioniert für jedes Labyrinth, das keine Zyklen hat.
Stimmt, das ist die genauste und kürzeste Formulierung.

Coda
2005-09-05, 02:42:38
Uhm A* anyone?

Trap
2005-09-05, 13:25:43
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
2005-09-05, 15:06:01
Gut, ich kannte die genaue Aufgabenstellung ja nicht.