Рекурзивен Backtracker Лавиринт Генератор

Рекурзивниот алгоритам за повраток е навистина длабинско пребарување за општа намена. Кога се користи за генерирање на лавиринт, тој е малку изменет за да ја избере патеката по случаен избор, додека ако се користи за вистински цели за пребарување, обично се бара секое ниво по линеарен редослед. Има тенденција да произведува лавиринти со долги, кривулести коридори и многу долг, извртувачки раствор.

Совршен лавиринт е лавиринт во кој има точно една патека од која било точка во лавиринтот до која било друга точка. Тоа значи дека не можете да завршите да одите наоколу во кругови, но често ќе наидете на ќорсокак, што ќе ве принуди да се свртите и да се вратите назад.

Мапите на лавиринтот генерирани овде вклучуваат стандардна верзија без никакви позиции за почеток и крај, така што можете сами да ги решите тие: ќе има решение од која било точка во лавиринтот до која било друга точка. Ако сакате инспирација, можете да овозможите предложена почетна и завршна позиција - па дури и да го видите решението помеѓу двете.

Рекурзивниот алгоритам за враќање назад е метод за пребарување на прво длабочина за генерирање совршени лавиринти (лавиринти без јамки и единствена патека помеѓу било кои две точки). Тој е едноставен, ефикасен и создава визуелно привлечни лавиринти со долги, кривулести коридори.

И покрај неговото име, не мора нужно да се имплементира со помош на рекурзија. Често се имплементира во итеративен пристап со користење на редица LIFO (т.е. стек). За многу големи лавиринти, користењето на рекурзија е поверојатно да резултира со прелевање на стек на повици, во зависност од програмскиот јазик и достапната меморија. Редот на LIFO може полесно да се прилагоди за ракување со големи количини на податоци, дури и да ја задржи редот на дискот или во базата на податоци доколку достапната меморија е недоволна.

Како функционира

Алгоритмот работи со користење на пристап за пребарување на длабочина базирана на стек. Еве го прегледот чекор-по-чекор:

1. Изберете почетна ќелија и означете ја како посетена.
2. Додека има непосетени ќелии:
   • Погледнете ги соседните ќелии кои сè уште не се посетени.
   • Ако постои барем еден непосетен сосед:
     • Случајно изберете еден од непосетените соседи.
     • Отстранете го ѕидот помеѓу тековната ќелија и избраниот сосед.
     • Одете до избраниот сосед и означете го како посетен.
     • Турнете ја тековната ќелија на оџакот.
   • Ако не постојат непосетени соседи:
     • Вратете се назад со пукање на последната ќелија од оџакот.
3. Продолжете со овој процес додека магацинот не се испразни.

Интересен факт за овој алгоритам е тоа што работи и како генератор на лавиринт и како решавач на лавиринт. Ако го извршите на веќе генериран лавиринт и само застанете кога ќе ја погодите решената крајна точка, оџакот ќе го содржи решението за лавиринтот.

Јас всушност имам две верзии на овој алгоритам во игра на оваа страница: LIFO заснована на редица за генерирање лавиринти на оваа страница и рекурзија за решавање на лавиринти, исто така лавиринти генерирани од други алгоритми (така се направени мапите со решенијата). Да имаш две различни верзии е само за спорт затоа што јас сум луд на кого му е интересно, или можеше да работи и за двете ;-)