Algorithm Maze Generator Eller

Reiknirit Ellers er völundarhús kynslóð reiknirit sem framleiðir á skilvirkan hátt fullkomin völundarhús (völundarhús án lykkja og einni leið á milli hvaða tveggja punkta sem er) með því að nota röð fyrir röð nálgun. Það framleiðir völundarhús svipað reiknirit Kruskal, en það gerir það með því að búa til aðeins eina röð í einu, án þess að þurfa að geyma allt völundarhúsið í minni. Það gerir það gagnlegt til að búa til mjög stór völundarhús á mjög takmörkuðum kerfum og til að búa til málsmeðferðarefni.

Fullkomið völundarhús er völundarhús þar sem það er nákvæmlega ein leið frá hvaða stað sem er í völundarhúsinu til annars staðar. Það þýðir að þú getur ekki endað á því að fara í hringi, en þú munt oft lenda í blindgötum, sem neyðir þig til að snúa við og fara til baka.

Völundarkortin sem mynduð eru hér innihalda sjálfgefna útgáfu án upphafs- og lokastaða, svo þú getur ákveðið þær sjálfur: það verður lausn frá hvaða stað sem er í völundarhúsinu til hvers annars. Ef þú vilt innblástur geturðu virkjað tillögu um upphafs- og lokastöðu - og jafnvel séð lausnina á milli þeirra tveggja.

Um reiknirit Ellers

Reiknirit Ellers var kynnt af David Eller.

Reiknirit þetta er þekkt fyrir skilvirka röð-eftir-röð aðferð við völundarhúsagerð, sem gerir það hugbúnaðarlega hentugt fyrir óendanleg völundarhús eða völundarhús sem eru búnu til í rauntíma. Það er oft nefnt í fræðiritum um ferla í innihaldsgenerun og völundarhúsagerð, en ég hef ekki náð að finna frumheimildir sem útskýra upprunalega útgáfu þess.

Hvernig reiknirit Ellers virkar fyrir völundarhúsagerð

Reiknirit Ellers fer í gegnum eina röð í einu, viðheldur og breytir settum tengdra frumna. Það tryggir tengingu meðan það forðast lykkjur og lengir völundarhúsið á skilvirkan hátt niður á við.

Það er í raun hægt að nota það til að búa til óendanleg völundarhús, en til að tryggja að búið völundarhús sé raunverulega leysanlegt, er nauðsynlegt að skipta yfir í "lokaröð" rökréttina á einhverjum tímapunkti til að ljúka völundarhúsinu.

Skref 1: Fyrsta röðin upphafin

• Úthluta hverri frumu í röðinni einstökum sett-ID.

Skref 2: Sameina einhverjar aðliggjandi frumur lárétt

• Sameina aðliggjandi frumur með því að stilla þær á sama sett-ID. Þetta tryggir að það séu láréttar göng.

Skref 3: Búa til lóðrétta tengingu við næstu röð

• Fyrir hvert sett sem kemur fyrir í röðinni, verður að minnsta kosti ein fruma að tengjast niður á við (til að tryggja tengingu).
• Veldu slembið eina eða fleiri frumur úr hverju setti til að tengjast næstu röð.

Skref 4: Fara í næstu röð

• Flytja lóðréttu tengingarnar áfram með því að úthluta sama sett-ID á samsvarandi frumur fyrir neðan.
• Úthluta nýjum sett-ID á allar óúthlutaðar frumur.

Skref 5: Endurtaka skref 2–4 þar til síðasta röðin er náð

• Halda áfram að vinna röð eftir röð.

Skref 6: Vinna með lokaröðina

• Tryggja að allar frumur í lokaröðinni tilheyri sama settinu með því að sameina allar eftirliggjandi aðskildar settir.