Еллеров алгоритам генератор лавиринта
Објављено: 16. фебруар 2025. 20:39:12 UTC
Генератор лавиринта који користи Еллер-ов алгоритам за креирање савршеног лавиринта. Овај алгоритам је занимљив јер захтева само чување тренутног реда (не целог лавиринта) у меморији, тако да се може користити за креирање веома, веома великих лавиринта чак и на веома ограниченим системима.Eller's Algorithm Maze Generator
Еллер-ов алгоритам је алгоритам за генерисање лавиринта који ефикасно производи савршене лавиринте (лабиринт без петљи и једну путању између било које две тачке) користећи приступ ред по ред. Он производи лавиринте сличне Крускаловом алгоритму, али то чини тако што генерише само један по један ред, без потребе за чувањем целог лавиринта у меморији. То га чини корисним за генерисање веома великих лавиринта на веома ограниченим системима и за генерисање процедуралног садржаја.
Савршен лавиринт је лавиринт у коме постоји тачно један пут од било које тачке у лавиринту до било које друге тачке. То значи да не можете завршити да се вртите у круг, али ћете често наићи на ћорсокак, приморавајући вас да се окренете и вратите назад.
Мапе лавиринта генерисане овде укључују подразумевану верзију без икаквих почетних и завршних позиција, тако да можете сами да их одлучите: постојаће решење од било које тачке у лавиринту до било које друге тачке. Ако желите инспирацију, можете омогућити предложену почетну и циљну позицију - па чак и видети решење између њих.
О Еллеровом алгоритму
Еллеров алгоритам је представио Давид Еллер.
Алгоритам је познат по свом ефикасном приступу генерисању лавиринта ред по ред, што га чини идеалним за бесконачне лавиринте или лавиринте генерисане у реалном времену. Обично се цитира у литератури о генерисању процедуралног садржаја и генерисању лавиринта, али нисам успео да пронађем примарне изворе који би детаљно описали његову оригиналну публикацију.
Како Еллеров алгоритам функционише за генерисање лавиринта
Еллеров алгоритам обрађује један по ред, одржавајући и модификујући скупове повезаних ћелија. Осигурава повезаност уз избегавање петљи и ефикасно проширује лавиринт надоле.
Теоретски се може користити за генерисање бесконачних лавиринта, међутим како би се осигурало да је генерисани лавиринт заиста решљив, потребно је у неком тренутку прећи на логику "задњег реда" да бисте завршили лавиринт.
Корак 1: Иницијализирајте први ред
- Доделите свакој ћелији у реду јединствени ИД скупа.
Корак 2: Хоризонтално спојите неке суседне ћелије
- Насумично спојите суседне ћелије тако што ћете их поставити на исти ИД скупа. Ово осигурава да постоје хоризонтални пролази.
Корак 3: Направите вертикалне везе до следећег реда
- За сваки скуп који се појави у реду, најмање једна ћелија мора да се повеже надоле (да би се обезбедила повезаност).
- Насумично изаберите једну или више ћелија из сваког скупа да бисте се повезали са следећим редом.
Корак 4: Пређите на следећи ред
- Пренесите вертикалне везе додељивањем истог ИД скупа одговарајућим ћелијама испод.
- Доделите нове ИД-ове скупа свим недодељеним ћелијама.
Корак 5: Поновите кораке 2–4 док се не постигне последњи ред
- Наставите са обрадом ред по ред.
Корак 6: Обрадите последњи ред
- Уверите се да све ћелије у последњем реду припадају истом скупу спајањем свих преосталих засебних скупова.