Класически алгоритми генерират лабиринти

- като Forbes, само по-добре.

предговор

Писане на статии ми spodviglo почти пълната липса на материали в Руската за алгоритмите за генериране на лабиринти. Хабре, от факта, че като цяло има по този въпрос, можем да отбележим две статии: една и две. Стойността и да се възползват от които има само две. Първият - превод на официалната алгоритъм и малко обяснение за това. Което, разбира се, че е добре, но много слабо и не предизвиква желанието да се изследват темата по-нататък.

Аз ще дам един съвет - не се погледнем в кода, докато не напишете своя реализация. Можете да получите много повече удоволствие и да се възползват от корекции на грешки и отстраняване на проблеми, отколкото ако просто превежда от един език на друг.

Сериозно. Вслушайте се в съветите. Вероятно прекарват повече време, но си заслужава да си струва. Аз, например, в резултат на грешки двойка изглеждаше много смешно генератор "чужди" текстове, които могат да бъдат използвани в различни научно-фантастичните игри, за да се създаде текста. Надявам се да научите темата за себе си и не бързайте.

Ще използвам термина "компенсира", което предполага, английски пристрастия. Т.е. пристрастен към модела на алгоритъм в произволна посока. Например, нали смяна - лабиринти алгоритъм генерира дълго десни крила.

Оцветяване лабиринти се случва по отношение на разстоянието от далечния ляв ъгъл на областта към някои клетки. В по-далеч от първоначалната позиция - по-тъмен цвят.

Perfect лабиринт - лабиринт, в която една клетка е свързана с друга само от един. С други думи, една обхващаща дърво.

Когато започнах да се копае в темата на лабиринт, нямах представа, че в края на краищата ще се пише статия, и изберете езика, на който имам възможност да не прекарват твърде много време рендиране и архитектура и да се занимава изключително с логика. В резултат на това между C ++ и Луа, изборът падна върху Луа и Love2D.

Не се притеснявайте, ако не сте запознати с Lua. непознаване на езика, не боли да разберете процеса на изпълнение, поради простотата на синтаксиса. Ако поне малко знаят как да програмирате, 80% от кода няма да ви доведе до проблеми с разбиране. Останалите 20% - езика специфични, за което аз винаги ще напише първата статия, обяснявайки своята работа.

Първото нещо, което трябва да се каже:
Lua има само една структура от данни - таблица - асоциативен масив, с които ние се създаде необходимата структура. Например, класове, комплекти, конвенционални масиви, стекове, опашки и други подобни. Отнесете се към тях можем или чрез използване на малки ключове, или чрез използване на индекси.
По същия начин, ние не ограничаваме таблицата съхранява в само един тип данни в един обект и работи като структури в C / C ++. Този код е абсолютно прав:

Присвояване на нула премахнете полето:

второ:
Lua няма тайна механизъм за копиране таблици. Кодът по-долу няма да копира и да се създаде нов обект SomeNewArray, а само копия препратка към SomeArray на обекта, и затова ще го промени по същия начин, като че ли за да изпратя чрез не-конст справка или показалка в C / C ++:

Binary Tree Алгоритъм

Първият и най-лесният алгоритъм да се разбере, че ще помисли. Нейната същност е да се проправи пътя в произволна посока от всяко поле клетка: в моя изпълнение или нагоре, или надясно (в зависимост от избрания компенсира от вас). Ние обработваме само една клетка за единица време, следователно, ние може да генерира лабиринт от безкраен размер, което запазва само крайния резултат (лабиринта) без да е необходимо да се съхранява всяка страна информация.

Такъв метод за генериране на два странични ефекти:

1. лабиринти имат силен диагонален пристрастия и липса на мъртвите зони в неговата посока. Погледнете скрийншота по-горе и ще видите, че всеки един от коридорите се ангажира с горния десен ъгъл на клетката, както и в резултат на това има уникален начин за него, и никъде по пътя не е задънена улица:

2. Две празен коридор от двете страни на лабиринта. Когато алгоритъмът "копаят" до края на ред / колона, той няма друг избор, освен да продължи пътя само в една посока, което създава празен "граница".

Между другото, името не е просто същата като структурата на данните. В резултат на работата си - случаен двоично дърво, в която всяка от клетките (горе) има точно един път към корена (родител възел), и по тази причина, точно един път за всяка друга клетка. В резултат на това всяка клетка е не повече от 3 връзки със своите съседи.

Официално алгоритъм (за североизточната част на изместване):

Изберете начална клетка;
Изберете произволна посока за да проправят пътя. Ако съседните клетки в тази област от границата на полето, копаят клетка в единствената възможна посока;
Преминаване към следващата клетка;
Повторете 2-3 до тогава, докато всички клетки са обработени;

Green - ток счита клетка, червени - предните клетки, в които се мести.

Като се започне с координати (0, 0). Най-високо в тази серия не мога да отида, защото в противен случай да излезе от лабиринта на границата. Отиди надясно до упор, по пътя надолу, като всички стени.

Всички безизходица. Къде да отидат. Движим се към следващия ред и да видим, че сега е възможно да се качим горе и в дясно.

Ние хвърлят монета и да изберете ... Най-високо. Премахване на стената и да преминете към следващата клетка.

Отличен. Дело ни казва да отиде в дясно. Премахване на стената и да се премести към следващата клетка.

Нямаме друг избор, от ляво не може да отиде, а след това ние премахваме стената в горната част и да преминете към следващия ред.

Coin ни убеждава в дясно. Е, да слушате. Премахване на стената и да преминете към sleuduyuschey клетка.

Ride м, нашето жалко парче метал пада и казва, че е време да се кача горе. Разрушаването на стената, стъпката на следващата клетка, и както е изключителна в този ред, отстраняване на горната част на стената. Maze завършена.

плюсове:

А просто изпълнение;
Висока скорост;
Способността да се изгради един безкраен лабиринт;

минуси:

Ниска сложност модел;
Силна смяна диагонално;
Липсата на мъртвите зони за преместване;
Монотонността генерирани лабиринти;

«Sidewinder» Алгоритъм

Алгоритъм непреводима име Sidewinder за работата му е много подобен на алгоритъма на двоично дърво, за разлика, че той не разполага с характеристиката компенсира по диагонал, един празните коридори и клетки, ние не се разглежда отделно и комплекти. Лабиринти получени с предимно вертикално или хоризонтално отместване (в зависимост от изпълнението), с липсата на мъртвите зони в тяхната посока. В сравнение с по-примитивен човек, отместването не е толкова забележим и по-скоро като "спирала", която постепенно замества вертикални и хоризонтални коридорите.

Що се отнася до странични ефекти, в Сайдуиндър създава само един празен коридор от една страна вместо два. От създаването на наборите от първия ред на областта, ние нямаме възможност да копаят пътя към върха, тъй като ние сме в най-краен вертикално положение и се опитват да отида по-горе води до изхода на границите. Но, ако се организира комплекти без да излизате от вертикалата, ние ще създадем няколко изолирани зони една от друга.

За пример 9 на първия ред на клетки могат да бъдат разделени в три групи, които са разположени между стените. Всяка група от втория ред ще копае пътя към една от трите "блокове" по-горе. Третият ред ще проправи пътя на "елементи" на втория. И така нататък до края на полето. В резултат на това ние ще се превърне 3 разклонена изолирани един от друг вертикално зрително поле, което не е подходящо за перфектен лабиринт, в който всяка от точките на областта има точно един път за всеки друг.

Официално алгоритъм (за стандартен офсет):

Изберете начален номер;
Избор на клетъчната линия и да я направи ток;
Инициализиране на празен набор;
Добави текущата клетка в комплекта;
Решете дали да проправи пътя на дясно;
Ако постлан, а след това се премести в нова клетка и да я направи ток. Повторете стъпки 3-6;
Ако не постлан, ние подбираме случаен набор от клетки и да проправят пътя към върха от там. Ходим на следващия ред и повторете 2-7;
Продължете, докато всеки ред ще се обработват;

Червени клетки - множество елементи.
Започваме от първия ред и да видим, че над нас - извън границите. Разрушаването на стените и отиде директно на втория ред, създава празен сет.

Така че, и тук-интересно. Нека добавим към набора от първите две серии от клетки.

Изберете една от тези клетки и премахване на свързаното с тях горна стена на първия ред.

Null комплект, добавете към него следващата клетка ред.

Този път с никой да се съчетаят, просто да проправят пътя към горния десен ъгъл на тази единствена клетка.

Повтаряме нашите действия. Null комплект, преминаване към следващата клетка, добавете го ... И тъй като тя е последната от поредицата, след това просто да се премахне горната част на стената и да преминете към номера по-долу.

Сега просто се комбинират първите три клетки в един комплект.

Произволно изберете клетка, в този случай, втората стена и премахване на върха на предишния ред.

Е, тук отново имаме друг избор, премахване на върха на стената и да преминете към номера по-долу.

По това време, най-клетъчна Pervan ние ще направим само един. Премахване на стената, за да предишния ред, и преминете към следващата клетка.

Да предположим, че искаме да се съчетаят трите в крайните клетки.

Отново привлича средно множество клетка, от която стената и премахване върха. Всички наши лабиринт е готова.

Способността да се изгради един безкраен лабиринт;
Само един празен коридор;
Една по-сложна картина, за разлика от двоичен алгоритъм на дърво;

минуси:

А по-сложно изпълнение;
Липсата на мъртвите зони за преместване;
Силна вертикално изместване;