🚀 go-pugleaf

Michał Suski <suseu@polbox.com> wrote:
: moze sie i da, ale to bedzie syzyfowa praca w przypadku przeszukiwania
: labiryntów dla znalezienia drogi z początku na koniec. ale i tak dzięki

Nieprawda! Algorytm nierekurencyjny jest bardzo prosty! Oczywiście
musi być to algorytm z powrotami, ale nie mysi być rekurencyjny.

Tworzysz sobie programowo (na stercie) strukturę typu stos, w której
przechowujesz ścieżkę, którą idziesz. Tworzysz pętlę while z warunkiem wyjścia
takim, że kończy się ona, gdy jesteś w punkcie wyjścia z labiryntu.
W każdym obiegu pętli robisz jeden krok "do przodu" (na przyległe pole,
na którym jeszcze nie byłeś i na które da się przejść) lub "do tyłu" (gdy
nie istnieje takie pole o jakim mowa w poprzednim nawiasie - wszedłeś
w ślepy zaułek - i musisz się wycofać po własnych śladach). Przy poruszaniu
się "do przodu" odkładasz aktualne współrzędne na stos i robisz krok, czyli
zmieniasz aktualne współrzędne zgodnie z kierunkiem ruchu. Przy "cofaniu się"
po prostu zdejmujesz ze stosu współrzędne pola, w którym byłeś poprzednio.
Gdy pętla skończy się, na stosie masz szukaną ścieżkę.

W ten sposób nie używasz stosu procesora, który rzeczywiście może się
przepełnić przy dużych labiryntach. Programowo możesz sobie zrobić taki stos
na ile masz pamięci w kompie.

-- 
Piotr Auksztulewicz                 piotras@zeus.polsl.gliwice.pl
Centrum Komputerowe Politechniki Śląskiej, Gliwice, Akademicka 16