Еллеров алгоритам генератор лавиринта

Елеров алгоритам је алгоритам за генерисање лавиринта који ефикасно производи савршене лавиринте (лавиринте без петљи и са једном путањом између било које две тачке) користећи приступ ред по ред. Производи лавиринте слично Крускаловом алгоритму, али то ради генерисањем само једног реда у исто време, без потребе за чувањем целог лавиринта у меморији. То га чини корисним за генерисање веома великих лавиринта на веома ограниченим системима и за генерисање процедуралног садржаја.

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

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

О Елеровом алгоритму

Елеров алгоритам је представио Дејвид Елер.

Алгоритам је познат по свом ефикасном приступу генерисању лавиринта ред по ред, што га чини идеалним за бесконачне лавиринте или лавиринте генерисане у реалном времену. Често се цитира у литератури о генерисању процедуралног садржаја и генерисању лавиринта, али нисам успео да пронађем примарне изворе који детаљно описују његову оригиналну публикацију.

Како Елеров алгоритам функционише за генерисање лавиринта

Елеров алгоритам обрађује један ред истовремено, одржавајући и мењајући скупове повезаних ћелија. Обезбеђује повезаност избегавајући петље и ефикасно проширује лавиринт надоле.

Теоретски се може користити за генерисање бесконачних лавиринта, међутим, да би се осигурало да је генерисани лавиринт заиста решив, потребно је у неком тренутку прећи на логику „последњег реда“ да би се лавиринт завршио.

Корак 1: Иницијализујте први ред

• Доделите свакој ћелији у реду јединствени ИД скупа.

Корак 2: Спојите неке суседне ћелије хоризонтално

• Насумично спојите суседне ћелије тако што ћете их поставити на исти ИД скупа. Ово осигурава да постоје хоризонтални пролази.

Корак 3: Креирајте вертикалне везе са следећим редом

• За сваки скуп који се појављује у реду, барем једна ћелија мора бити повезана надоле (да би се осигурала повезаност).
• Насумично изаберите једну или више ћелија из сваког скупа да бисте их повезали са следећим редом.

Корак 4: Пређите на следећи ред

• Пренесите вертикалне везе тако што ћете доделити исти ИД скупа одговарајућим ћелијама испод.
• Доделите нове ИД-ове скупова свим недодељеним ћелијама.

Корак 5: Понављајте кораке 2–4 док се не дође до последњег реда

• Наставите са обрадом ред по ред.

Корак 6: Обрада последњег реда

• Уверите се да све ћелије у последњем реду припадају истом скупу спајањем свих преосталих одвојених скупова.

Даље читање

Ако сте уживали у овом посту, можда ће вам се свидети и ови предлози:

• Алгоритам растућег дрвета Мазе Генератор
• Рекурзивни Бацктрацкер Мазе Генератор
• Крускалов алгоритам Мазе Генератор