piątek, czerwca 01, 2012

Maszyna stanów kontra labirynt ;-)

OK, wiem że to co tu napiszę nie zawsze działa ;-) [przed chwilą stworzyłem labirynt w którym moja maszyna stanów nie podołała ;-) ale już jest za późna pora by szukać błędu...]

Zobaczyłem dziś na HackerNews linkę do Google Blockly, a tam jeden z przykładów [do napisania ;-)] to rozwiązywanie labiryntu.
Chwilę się tym pobawiłem, ale mi ELSE brakowało w IF, więc sięgnąłem po kawałek papieru (tym razem koperta z banku) i narysowałem sobie maszynę stanów, która jak mi się wydaje powinna rozwiązywać labirynt przez poruszanie się po nim z lewą ręką na ścianie..

Później to zakodowałem w Pythonie i tak wygląda program w działaniu ;-)


Najważniejszy kawałek kodu wygląda tak:

while (startX!=endX) or (startY!=endY):
if state==0:
newDir = turnLeft(dir)
if empty(startX+newDir[0],startY+newDir[1]):
state=1
else:
state=2
continue
if state==1:
dir = turnLeft(dir)
startX+=dir[0]
startY+=dir[1]
state = 0
continue
if state==2:
if empty(startX+dir[0],startY+dir[1]):
state=3
else:
state=4
continue
if state==3:
startX+=dir[0]
startY+=dir[1]
state=0
continue
if state==4:
dir = turnLeft(dir)
state=0
continue

Na wejściu mamy w (startX,startY) pozycję startową, a w (endX,endY) pozycję końcową.
turnLeft() po prostu obraca "wektor" dir w lewo o 90 stopni, a empty() sprawdza czy pole przed nami jest puste, czy nie :-)
state to akutalny stan maszyny, można to zrobić ładniej, ale chciałem by było to widać.

Jak ktoś ciekawy to tutaj pliki do pobrania:
maze.py - program w Pythonie (jeśli chcesz go uruchomić na Linuksie czy innym *niksie to zmień os.system("cls") w os.system("clear"), nie chciało mi się kombinować to użyłem tak ohydnej metody czyszczenia ekranu :-))
maze.txt - labirynt
maze2.txt - labirynt zabójca dla programu ;-) zaczyna się kręcić "jak smród po gaciach" ;-)

I moje 30 minut kodowania (prywatnego) odbębnione :-)


Podobne postybeta
Nigdy nie zapominaj o FSM! ;-)
Z NMEA do KML (chyba najbardziej kryptyczny tytuł postu jak stworzyłem ;-))
Śmierdząca ryba wolności ;-)
Windows mnie jednak nie lubi ;-)
Zdradliwa Java i 8 królowych ;-)