Алгоритм Еллера — це математичний генератор, що дозволяє створювати лабіринти, у яких між кожними двома точками існує єдиний шлях, тобто лабіринти не містять циклів.
У порівнянні з іншими генераторами, цей алгоритм є одним із найшвидших та потребує незначну кількість пам'яті — пропорційну довжині рядка лабіринту.
Потрібно зберігати в пам'яті лише останній створений рядок — це дозволяє генерувати лабіринти з необмеженою кількістю рядків.
Як відбувається генерація
Алгоритм являє собою цикл додавання нових рядків. Рядок містить одну і ту саму кількість клітинок, яка довільно задається на початку. Клітинки належать до множин, що слугують для контролю можливості проходу між клітинками. На момент генерації поточного рядка клітини однієї множини з'єднані між собою, водночас клітини з різних множин знаходяться в ізольованих між собою частинах лабіринту. У кожної клітинки може бути або не бути права та нижня стінка. Загалом, стінки генеруються випадковим чином, але при дотриманні певних правил, які гарантують відсутність циклів у лабіринті.
Формальний опис алгоритму
- Створити перший рядок. Жодна клітинка не належить жодній множині
- Присвоїти кожній з клітинок, що не мають множини, свою унікальну множину
- Створити праві стінки, рухаючись зліва направо:
- Випадково вирішити, чи додавати стінку:
- Якщо поточна клітинка та клітинка справа належать одній множині, додати стінку (для запобігання зацикленням)
- Якщо вирішено не додавати стінку, об'єднати множини поточної та наступної клітинки
- Випадково вирішити, чи додавати стінку:
- Створити стінки знизу, рухаючись зліва направо:
- Випадково вирішити, чи додавати стінку знизу. При додаванні переконатися, що кожна множина має хоча б одну клітинку без нижньої стінки — це гарантуватиме відсутність ізольованих областей
- Вирішити, чи додавати рядки після поточного
- Якщо вирішено додати рядок, то:
- Вивести поточний рядок
- Видалити всі праві стінки
- Видалити клітинки з нижніми стінками з їх множин
- Видалити всі нижні стінки
- Продовжити з кроку 2
- Якщо вирішено закінчити лабіринт, то:
- Додати нижню стінку до кожної клітинки
- Рухаючись зліва направо:
- Якщо поточна клітинка та клітинка справа належать до різних множин, то:
- Видалити праву стінку
- Об'єднати множини цих клітинок
- Якщо поточна клітинка та клітинка справа належать до різних множин, то:
- Якщо вирішено додати рядок, то:
Приклад генерації
Проілюструємо процес створення лабіринту покроково. Для початку визначимося з довжиною рядка — нехай вона дорівнюватиме 6. (Оскільки лабіринт має бути оточений стінками з усіх боків, перший рядок зробимо з верхніми, останній — з нижніми, усі перші клітинки — з лівими, а останні в кожному рядку — з правими стінками).
1. Створимо перший рядок.
__ ___ __ ___ __ ___ | |
2. Присвоїмо всім клітинкам унікальну множину
__ ___ __ ___ __ ___ | 1 2 3 4 5 6 |
3. Рухаючись зліва направо, випадковим чином вирішимо, чи додавати стінки між клітинками(Оскільки на даному кроці всі клітинки належать до різних множин, наш вибір ніщо не обмежує)
__ ___ __ ___ __ ___ |(1 | 2) 3 4 5 6 | - додаємо праву стінку після першої клітинки __ ___ __ ___ __ ___ | 1 |(2 3) 4 5 6 | - не додаємо стінку після другої __ ___ __ ___ __ ___ | 1 | 2 2 4 5 6 | - об'єднуємо множини, до яких належать 2 та 3 клітинки __ ___ __ ___ __ ___ | 1 | 2 (2 4) 5 6 | __ ___ __ ___ __ ___ | 1 | 2 2 2 5 6 | __ ___ __ ___ __ ___ | 1 | 2 2 (2 | 5) 6 | __ ___ __ ___ __ ___ | 1 | 2 2 2 |(5 | 6)| __ ___ __ ___ __ ___ | 1 | 2 2 2 | 5 | 6 |
4. Додамо нижні стінки
__ ___ __ ___ __ ___ |(1)| 2 2 2 | 5 | 6 | - не додаємо стінку, це - остання клітинка у множині з індексом 1, що не має нижньої стінки. __ ___ __ ___ __ ___ | 1 |_2_ 2 2 | 5 | 6 | __ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 |
5. Вітаю! Ми отримали перший завершений рядок нашого лабіринту. Додамо наступний. Для цього виведемо поточний іще раз:
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 |_2_ 2 _2_| 5 | 6 |
5. 1. 1. Видалимо всі праві стінки
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _2_ 2 _2_ 5 6 |
5. 1. 2. Усі клітинки, що містять нижні стінки, видалимо з їх множин
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _ _ 2 _ _ 5 6 |
5. 1. 3. Видалимо нижні стінки
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 2 5 6 |
Повернемося до пункту 2. Присвоїмо клітинкам, що не належать до множин, унікальні множини
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 3 2 4 5 6 |
3. Створимо праві стінки
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 1 | 2 2 | 5 5 |
4. Створимо нижні стінки
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _1_|_2_ 2 | 5 5 |
5. 1. 1. Продублюємо останній рядок
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _1_|_2_ 2 | 5 5 | | 1 _1_|_2_ 2 | 5 5 |
5. 1. 2. Витремо праві стінки
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _1_|_2_ 2 | 5 5 | | 1 _1_ _2_ 2 5 5 |
5. 1. 3. Видалимо клітинки з нижніми стінками
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _1_|_2_ 2 | 5 5 | | 1 _ _ _ _ 2 5 5 |
5. 1. 4. Видалимо нижні стінки
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _1_|_2_ 2 | 5 5 | | 1 2 5 5 |
Повернемося до пункту 2. Присвоїмо порожні клітинки множинам
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _1_|_2_ 2 | 5 5 | | 1 3 4 2 5 5 |
3. Створимо праві стінки
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _1_|_2_ 2 | 5 5 | | 1 1 | 4 4 5 5 |
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _1_|_2_ 2 | 5 5 | | 1 1 | 4 (4 5) 5 |
Зверніть увагу: ми об'єднуємо множини клітинок, тобто остання клітинка також стане належати до множини 4 після даного кроку.
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _1_|_2_ 2 | 5 5 | | 1 1 | 4 4 4 4 |
Тут обов'язково поставити стінку після 5 клітинки — наступна з тієї самої множини
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _1_|_2_ 2 | 5 5 | | 1 1 | 4 4 (4 | 4)|
4. Додамо нижні стінки
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _1_|_2_ 2 | 5 5 | | 1 _1_| 4 _4_ _4_| 4 |
5. Більше не додаватимемо рядків
5. 2. 1.
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _1_|_2_ 2 | 5 5 | |_1_ _1_|_4_ _4_ _4_|_4_|
5. 2. 2. Праву стінку після 2 клітинки потрібно видалити та об'єднати множини 2 та 3 клітинок(після завершення проходження по рядку усі клітинки мають належати одній множині).
__ ___ __ ___ __ ___ | 1 |_2_ 2 _2_| 5 | 6 | | 1 _1_|_2_ 2 | 5 5 | |_1_ _1_ _1_ _1_ _1_|_1_|
І от, наш лабіринт нарешті завершено. Вхід та вихід можна зробити з будь-якої зовнішньої стінки лабіринту.
__ ___ __ ___ __ ___ |_ _ _ _| | | | _ _|_ _ | | |_ _ _ _ _ _ _ _ _ _|_ _
Приклад згенерованого лабіринту
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |_ _ _ _ | | | | | _| | | | |_ |_ _ | |_ | | | | | |_ |_ _ | | | | | | _ _ |_ | _| | | |_| |_|_ _|_ |_ | _ _ | _ _|_ | | | | | |_| | | |_| | | | | _ _ _| _|_ | | _|_ | _| | _ _ _ _| |_| |_|_ _|_| | |_| | | _| |_ _ |_ | | | | | | |_|_ | _| | | | | |_| | | | | | |_ _| |_|_| | | _ | | |_|_| |_|_ | | | | |_| |_| | | | |_| | | | |_ |_ _ _| | | |_ _|_ _ |_ _ _| |_ |_ | | |_ | |_ _| | | | | | _| | _| | |_|_ _ _| |_|_ | | | | | | |_ _|_| _| |_ _| | |_| | | | |_|_| |_| | | | |_| |_|_ |_ | _|_ | |_ _| | | _| | _ _| | _ _| |_|_ | | | | | |_| | | | | |_ _| | |_|_ | | | |_| _|_| |_|_| | | |_ _| _ _ | | | | |_ | |_| |_| |_ _ | | _ _| | | | | _ _| | _| |_ _|_ _| |_ _ | |_ _| | _ _|_ |_ | |_|_ | |_| _|_|_|_| |_ |_ | | | |_ _| | | | |_ _ | _| |_| _|_ |_ _ _ _| | | _|_| _|_ |_|_ _| | _ _| | _| | _| | _| |_| |_ |_ _ _| _| | _| |_ _ _| _ _| | | | | |_ | | | _ _| | | |_|_ _| _|_ |_ _ _| | | | |_|_| |_ _ | | | |_ _ _ | | | | |_| | | _| | _| | | | | | | |_ | |_ |_ | _ _| | | _| | | _| | | | | | | |_| |_| | | | |_ _| |_| | |_ _ _ _| | | | | _| | _ _| | | |_|_ |_ _| | |_ |_ _ _ _| |_|_| |_ _| | | | |_ _| _| | _|_ | | | | | | | |_ |_ | | | | | _|_ _| | |_ | | _| | |_ | |_| | |_ | | |_|_| | | | |_ _ | | _| _ |_|_| | | | _|_ | |_ _| |_| | | | | | | | | | |_|_|_ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _ _ _|_ _|_ _ _ _ _|_ _|_|_|_ _ _ _
Посилання
http://www.neocomputer.org/projects/eller.html [ 3 жовтня 2013 у Wayback Machine.]
Ця стаття містить текст, що не відповідає . (березень 2017) |
Ця стаття потребує додаткових для поліпшення її . (березень 2017) |
Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm Ellera ce matematichnij generator sho dozvolyaye stvoryuvati labirinti u yakih mizh kozhnimi dvoma tochkami isnuye yedinij shlyah tobto labirinti ne mistyat cikliv U porivnyanni z inshimi generatorami cej algoritm ye odnim iz najshvidshih ta potrebuye neznachnu kilkist pam yati proporcijnu dovzhini ryadka labirintu Potribno zberigati v pam yati lishe ostannij stvorenij ryadok ce dozvolyaye generuvati labirinti z neobmezhenoyu kilkistyu ryadkiv Yak vidbuvayetsya generaciyaAlgoritm yavlyaye soboyu cikl dodavannya novih ryadkiv Ryadok mistit odnu i tu samu kilkist klitinok yaka dovilno zadayetsya na pochatku Klitinki nalezhat do mnozhin sho sluguyut dlya kontrolyu mozhlivosti prohodu mizh klitinkami Na moment generaciyi potochnogo ryadka klitini odniyeyi mnozhini z yednani mizh soboyu vodnochas klitini z riznih mnozhin znahodyatsya v izolovanih mizh soboyu chastinah labirintu U kozhnoyi klitinki mozhe buti abo ne buti prava ta nizhnya stinka Zagalom stinki generuyutsya vipadkovim chinom ale pri dotrimanni pevnih pravil yaki garantuyut vidsutnist cikliv u labirinti Formalnij opis algoritmuStvoriti pershij ryadok Zhodna klitinka ne nalezhit zhodnij mnozhini Prisvoyiti kozhnij z klitinok sho ne mayut mnozhini svoyu unikalnu mnozhinu Stvoriti pravi stinki ruhayuchis zliva napravo Vipadkovo virishiti chi dodavati stinku Yaksho potochna klitinka ta klitinka sprava nalezhat odnij mnozhini dodati stinku dlya zapobigannya zaciklennyam Yaksho virisheno ne dodavati stinku ob yednati mnozhini potochnoyi ta nastupnoyi klitinki Stvoriti stinki znizu ruhayuchis zliva napravo Vipadkovo virishiti chi dodavati stinku znizu Pri dodavanni perekonatisya sho kozhna mnozhina maye hocha b odnu klitinku bez nizhnoyi stinki ce garantuvatime vidsutnist izolovanih oblastej Virishiti chi dodavati ryadki pislya potochnogo Yaksho virisheno dodati ryadok to Vivesti potochnij ryadok Vidaliti vsi pravi stinki Vidaliti klitinki z nizhnimi stinkami z yih mnozhin Vidaliti vsi nizhni stinki Prodovzhiti z kroku 2 Yaksho virisheno zakinchiti labirint to Dodati nizhnyu stinku do kozhnoyi klitinki Ruhayuchis zliva napravo Yaksho potochna klitinka ta klitinka sprava nalezhat do riznih mnozhin to Vidaliti pravu stinku Ob yednati mnozhini cih klitinokPriklad generaciyiProilyustruyemo proces stvorennya labirintu pokrokovo Dlya pochatku viznachimosya z dovzhinoyu ryadka nehaj vona dorivnyuvatime 6 Oskilki labirint maye buti otochenij stinkami z usih bokiv pershij ryadok zrobimo z verhnimi ostannij z nizhnimi usi pershi klitinki z livimi a ostanni v kozhnomu ryadku z pravimi stinkami 1 Stvorimo pershij ryadok 2 Prisvoyimo vsim klitinkam unikalnu mnozhinu 1 2 3 4 5 6 3 Ruhayuchis zliva napravo vipadkovim chinom virishimo chi dodavati stinki mizh klitinkami Oskilki na danomu kroci vsi klitinki nalezhat do riznih mnozhin nash vibir nisho ne obmezhuye 1 2 3 4 5 6 dodayemo pravu stinku pislya pershoyi klitinki 1 2 3 4 5 6 ne dodayemo stinku pislya drugoyi 1 2 2 4 5 6 ob yednuyemo mnozhini do yakih nalezhat 2 ta 3 klitinki 1 2 2 4 5 6 1 2 2 2 5 6 1 2 2 2 5 6 1 2 2 2 5 6 1 2 2 2 5 6 4 Dodamo nizhni stinki 1 2 2 2 5 6 ne dodayemo stinku ce ostannya klitinka u mnozhini z indeksom 1 sho ne maye nizhnoyi stinki 1 2 2 2 5 6 1 2 2 2 5 6 5 Vitayu Mi otrimali pershij zavershenij ryadok nashogo labirintu Dodamo nastupnij Dlya cogo vivedemo potochnij ishe raz 1 2 2 2 5 6 1 2 2 2 5 6 5 1 1 Vidalimo vsi pravi stinki 1 2 2 2 5 6 1 2 2 2 5 6 5 1 2 Usi klitinki sho mistyat nizhni stinki vidalimo z yih mnozhin 1 2 2 2 5 6 1 2 5 6 5 1 3 Vidalimo nizhni stinki 1 2 2 2 5 6 1 2 5 6 Povernemosya do punktu 2 Prisvoyimo klitinkam sho ne nalezhat do mnozhin unikalni mnozhini 1 2 2 2 5 6 1 3 2 4 5 6 3 Stvorimo pravi stinki 1 2 2 2 5 6 1 1 2 2 5 5 4 Stvorimo nizhni stinki 1 2 2 2 5 6 1 1 2 2 5 5 5 1 1 Produblyuyemo ostannij ryadok 1 2 2 2 5 6 1 1 2 2 5 5 1 1 2 2 5 5 5 1 2 Vitremo pravi stinki 1 2 2 2 5 6 1 1 2 2 5 5 1 1 2 2 5 5 5 1 3 Vidalimo klitinki z nizhnimi stinkami 1 2 2 2 5 6 1 1 2 2 5 5 1 2 5 5 5 1 4 Vidalimo nizhni stinki 1 2 2 2 5 6 1 1 2 2 5 5 1 2 5 5 Povernemosya do punktu 2 Prisvoyimo porozhni klitinki mnozhinam 1 2 2 2 5 6 1 1 2 2 5 5 1 3 4 2 5 5 3 Stvorimo pravi stinki 1 2 2 2 5 6 1 1 2 2 5 5 1 1 4 4 5 5 1 2 2 2 5 6 1 1 2 2 5 5 1 1 4 4 5 5 Zvernit uvagu mi ob yednuyemo mnozhini klitinok tobto ostannya klitinka takozh stane nalezhati do mnozhini 4 pislya danogo kroku 1 2 2 2 5 6 1 1 2 2 5 5 1 1 4 4 4 4 Tut obov yazkovo postaviti stinku pislya 5 klitinki nastupna z tiyeyi samoyi mnozhini 1 2 2 2 5 6 1 1 2 2 5 5 1 1 4 4 4 4 4 Dodamo nizhni stinki 1 2 2 2 5 6 1 1 2 2 5 5 1 1 4 4 4 4 5 Bilshe ne dodavatimemo ryadkiv 5 2 1 1 2 2 2 5 6 1 1 2 2 5 5 1 1 4 4 4 4 5 2 2 Pravu stinku pislya 2 klitinki potribno vidaliti ta ob yednati mnozhini 2 ta 3 klitinok pislya zavershennya prohodzhennya po ryadku usi klitinki mayut nalezhati odnij mnozhini 1 2 2 2 5 6 1 1 2 2 5 5 1 1 1 1 1 1 I ot nash labirint nareshti zaversheno Vhid ta vihid mozhna zrobiti z bud yakoyi zovnishnoyi stinki labirintu Priklad zgenerovanogo labirintu Posilannyahttp www neocomputer org projects eller html 3 zhovtnya 2013 u Wayback Machine Cya stattya mistit tekst sho ne vidpovidaye enciklopedichnomu stilyu Bud laska dopomozhit udoskonaliti cyu stattyu pogodivshi stil vikladu zi stilistichnimi pravilami Vikipediyi Mozhlivo storinka obgovorennya mistit zauvazhennya shodo potribnih zmin berezen 2017 Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno berezen 2017 Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi