🚀 go-pugleaf

On 6 Jan 1998 12:02:10 GMT, in pl.comp.lang.c Piotr Auksztulewicz
<piotras@zeus.polsl.gliwice.pl> wrote:

>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.
Nie musi, niezbyt oszczędny pamięciowo i czasowo algorytm rozwiązywania
labiryntu, określany mianem "wypalania stepu" polega na stworzeniu tablicy
opisującej labirynt, i przejrzeniu jej "n" razy, a przy każdym przejściu
jeżeli wartość w komórce jest "x" to sprawdzamy sąsiadujące komórki i jeśli
sa puste to wpisujemy do nich wartość "x+1" jeżeli jesteśmy w sąsiedztwie
wyjścia to już koniec (chyba ze szukamy wszystkich dróg a nie najkrótszej).
Teraz można wrócic po "sladach" czyli malejące liczby doprowadzą nas od
wyjscia do wejscia. Warunek stopu to oczywiście brak wartości której
szukamy, wtedy nie ma przejscia.
Mozna to oczywiście jeszcze optymalizować (np dodajac dwie listy punktow w
labiryncie), ale powyższe jest najprostszą wersja.
Oczywiście tablice-labirynt trzeba odpowiednio spreparowac czyli ustalić
niezbedna ilość bajtów do reprezentacji, wartosci zastrzezone na
wejscie,wyjscie(a) i sciany.
Np.: dla labiryntu ekranowego(80x25), wystarczą 2bajty na komórkę i np
0xFFFD na wejscie, 0xFFFE na wyjscie oraz 0xFFFF na ścianę.

Poza tym ten algorytm ma tą zaletę że się ładnie wizualizuje :-).

Hobbit
PS. Nie do końca jestem pewien czy kolejne przejścia określic mianem powrotu
czy iteracji, ale poza tym jest OK :-).

--
-------------------------------------|
Krzysztof Swiatkowski - Lodz, Poland | replying cut bezspam from my address
e-Mail:  hobbit@dom.vr.pl.bezspam    | odpowiadajac usun bezspam z adresu

"Kto sie pozno polozy, wczesnie z lozka wyskoczy
ten od tego glupieje i nie widzi na oczy"
>Gra Endera< O.S.Card