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

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

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

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

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

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

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

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

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

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

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

Дополнително читање

Ако ви се допадна овој пост, можеби ќе ви се допаднат и овие предлози:

• Генератор на лавиринт на алгоритам на Елер
• Лови и убиј генератор на лавиринт
• Крускалов алгоритамски генератор на лавиринт