Klasszikus algoritmusok mazes

- mint a Forbes, csak jobb.

előszó

Írásban cikkek me spodviglo szinte teljes hiánya az anyagok Orosz körülbelül algoritmusok generálására mazes. Ügyéről, az a tény, hogy általában van a témával kapcsolatban, akkor vegye figyelembe a két cikket: egy és kettő. Az érték és a haszon, amelyek közül csak kettő. Az első - a fordítás a formális algoritmus és egy kis magyarázatra. Ami persze jó, de nagyon rosszul, és nem okozott a vágy, hogy vizsgálja meg a téma további.

Adok egy tanácsot - ne nézd meg a kódot, amíg nem írjuk meg a megvalósítás. Kapsz sokkal több örömet és hasznot hibajavítások és hibaelhárítás, mint ha csak lefordítani egyik nyelvről a másikra.

Komolyan. Hallgassa meg a tanácsot. Valószínűleg több időt, de megéri megéri. Én például, a hibák miatt pár tűnt, nagyon vicces generátor „idegen” szövegek, amelyeket fel lehet használni a különböző sci-fi játék, hogy megteremtse a szöveget. Remélem megtanulják a témát maguk és nem siet.

Fogom használni a „offset”, ami arra utal, angol elfogultság. Ie hozzászokik az algoritmus minta minden irányban. Például jobb Shift - labirintusok algoritmus generál hosszú jobb oldali folyosókon.

Színező labirintusok előfordul viszonyítva a távolság a bal szélen a mező sarkában, hogy bizonyos sejtekben. Minél messzebb van a kiinduló helyzetbe - a sötétebb szín.

Tökéletes Maze - egy labirintus, amelyben az egyik cellában van kötve egy másik csak egy. Más szóval, a feszítőfa.

Amikor elkezdtem ásni a labirintus téma, fogalmam sem volt, hogy a végén majd írásban egy cikket, és úgy döntött, a nyelv, amelyen van egy lehetőség, hogy ne túl sok időt töltenek renderelés és az építészet és foglalkozni kizárólag logika. Ennek eredményeként, a C ++ és Lua, esett a választás Lua és Love2D.

Ne aggódj, ha nem ismerik a Lua. ismeri a nyelvet nem fáj, hogy megértsék a végrehajtás, mivel az egyszerűség a szintaxis. Ha legalább egy kicsit tudsz programozni, 80% -a kód nem okoz Önnek problémák megértését. A fennmaradó 20% - a nyelv sajátos, amiről mindig írni az első cikk, ami megmagyarázza a munkájukat.

Az első dolog, amit meg kell mondani:
Lua csak egy adatstruktúra - egy asztal - egy asszociatív tömb, amellyel létrehozzuk a szükséges vázat. Például, osztályok, készletek, hagyományos tömbök, vermek, sorok, és hasonlók. Lásd őket tudjuk sem a kisbetű-gombbal, vagy indexet használ.
Hasonlóképpen, nem korlátozzuk az asztal alatt csak egyféle adatot egy objektumot, és a munka, mint struktúrák C / C ++. Ez a kód teljesen korrekt:

Hozzárendelése nulla eltávolítani a pályáról:

második:
Lua nincs rejtett mechanizmus másolás táblázatokat. Az alábbi kód nem másolja, és hozzon létre egy új objektumot SomeNewArray, csak másolatok utalás a tárgy SomeArray, ezért meg fog változni, ugyanúgy, mint ha át az érték egy nem const referencia vagy pointer C / C ++:

Bináris fa algoritmus

Az első és legegyszerűbb algoritmus, hogy megértsék, hogy én úgy. Ennek lényege az, hogy előkészítsék az utat egy véletlenszerű irányba egyes cella területén: az én végrehajtás vagy felfelé, vagy jobbra (attól függően, hogy a kiválasztott eltolás Ön által). Mi folyamat csak 1 cella időegység, ezért tudunk generálni egy labirintus végtelen méretű, megtartva csak a végeredményt (a labirintus), nem kell tárolni bármilyen mellékhatás információkat.

Egy ilyen módszer generál két mellékhatások:

1. mazes erős átlós elfogultság hiánya holtpontok az ő irányába. Nézd meg a screenshotok a fenti, és látni fogja, hogy az egyes folyosók elkötelezett a jobb felső sarokban a sejt, és ennek eredményeként, egy egyedülálló módon rá, és sehol az úton nincs holtpont:

2. Két üres folyosó két oldalán a labirintusból. Ha az algoritmus „ásni”, amíg a végén a sor / oszlop, akkor nincs más választása, mint folytatni az utat csak egy irányba, ami egy üres „határ”.

By the way, a név nem csak ugyanaz, mint az adatok szerkezetét. Az eredmény az ő munkája - véletlen bináris fa, ahol minden egyes sejt (felső) pontosan egy ösvény felé a gyökér (szülő csomópont), ezért pontosan egy útvonal bármely más sejt. Ennek eredményeként minden cella legfeljebb 3 kapcsolatot a szomszédokkal.

Formai algoritmus (az észak-keleti elmozdulás):

Válasszon egy kezdeti sejt;
Válasszon egy véletlenszerű irányba megnyitva az utat. Ha a szomszédos cellák ezen a területen határán túl a területen, ásni egy cellát az egyetlen lehetséges irány;
Ugrás a következő sejt;
Ismételjük 2-3 addig, amíg az összes sejt feldolgozása megtörtént;

Green - jelenlegi tekinthető cella, piros - első sejtekben, amelyekbe áthelyezi.

Kezdve koordinátái (0, 0). Top ebben a sorozatban nem megy, mert különben jön ki a labirintusból a határ. Menj jobbra ütközésig, az úton vesz le a falakat.

Minden holtpont. Hová menni. Célunk, hogy a következő sort, és látni, hogy most lehet menni az emeletre, és a jobb oldalon.

Mi dobjon egy pénzérmét, és válassza ... Top. Távolítsuk el a fal, és menj a következő cellába.

Kitűnő. Esetben azt mondja, hogy menj jobbra. Távolítsuk el a fal, és mozgassa a következő cellába.

Nincs más választásunk, a bal nem megy, akkor távolítsa el a fal tetején, és menj a következő sorba.

Coin meggyőz bennünket, hogy a jobb oldalon. Nos, figyelj. Távolítsuk el a fal, és menj sleuduyuschey sejt.

Ride mérő, szerencsétlen fémdarabot esik, és azt mondja, hogy itt az ideje, hogy menjen fel az emeletre. A bontási a fal, a lépés, hogy a következő cella, és, mivel ez extrém ebben a sorban, távolítsa el a felső fal. Maze kész.

Előnyök:

Egy egyszerű végrehajtását;
Nagy sebességű;
Az a képesség, hogy létrehoz egy végtelen labirintus;

hátránya:

Olcsó komplexitás minta;
Erős műszak átlósan;
A hiányzó holtpontjainak elmozdulás;
Monotónia generált mazes;

«Sidewinder» algoritmus

Algoritmus lefordíthatatlan neve Sidewinder munkája nagyon hasonlít az algoritmus egy bináris fa, ezzel szemben, hogy nem az a jellemzőjük, offset átlósan, az egyik üres folyosókon és sejtek, nem tartjuk külön-külön, készletek. Labyrinths kapott főleg függőleges vagy vízszintes eltolás (attól függően, hogy a végrehajtás), a hiánya holtpontok az irányba. Összehasonlítva a primitív ember, az offset nem annyira észrevehető, és több, mint egy „spirál”, amely fokozatosan váltja fel a függőleges és vízszintes folyosók.

Ami a mellékhatásokat, a Sidewinder létre egyetlen üres folyosó egyik oldalán kettő helyett. Létrehozása óta a készlet az első sorban a területen, akkor nem kell a lehetőséget, hogy ásni az utat a csúcsra, mint mi a legszélsőségesebb függőleges helyzetbe, és megpróbálja fölé menni vezet a kijárat a határokat. De ha szervezünk készletek elhagyása nélkül a függőleges, akkor hozzon létre néhány elszigetelt területek egymástól.

A 9. példa esetében az első sorban a sejtek osztható három, melyek között található a falak. Mindegyik készlet a második sor fog ásni egy utat, hogy az egyik a három „blokk” a fenti. A harmadik sor megnyitná az utat a „blokk” a második. És így tovább, amíg a végén a területen. Ennek eredményeként, mi pedig 3 ágú egymástól elszigetelve függőleges területen, amely nem alkalmas a tökéletes labirintus, amelyben az egyes pontok a mezőnek pontosan egy út a többi.

Formai algoritmus (szabványos offset):

Válasszon ki egy kiindulási számot,
Válassza ki a kiindulási sejtek, és ez a jelenlegi;
Inicializáljon egy üres halmaz;
Add az aktuális cella a készlet;
Döntse el, hogy előkészítsék az utat a jobb oldalon;
Ha betonozott, majd helyezze egy új sejt, és ez a jelenlegi. Ismételje meg a 3-6 lépéseket;
Ha nem aszfaltozott, akkor válasszon egy véletlenszerű halmaza sejt és megnyitva az utat a csúcsra onnan. Mi megy a következő sort és ismételje 2-7;
Folytassa, amíg minden sorban kerülnek feldolgozásra;

Red sejtek - tagok sokasága.
Kezdjük az első sorban, és látja, hogy a fejünk felett - a határokat. A bontás és a falak közvetlenül a második sorban, hozzon létre egy üres halmaz.

Tehát, itt érdekes. Nézzük hozzá a sor az első két sorozat sejteket.

Válasszon egy ilyen sejtek, és távolítsa el az ezekhez kapcsolódó felső fal az első sorban.

Null set, add hozzá a következő cellába sor.

Ezúttal senki nem kombinálni, csak megnyitva az utat a jobb felső sarokban ez az egyetlen sejt.

Megismételjük tetteinkért. Null set, mozog a következő cellába, add meg ... És ő volt az utolsó a sorozatban, akkor csak vegye ki a fal tetején, és menj az alábbi telefonszámot.

Most csak kombinálni az első három sejtek egy készletben.

Véletlenszerűen kiválasztunk egy sejt, ebben az esetben, a második fal és távolítsa el a felső az előző sor.

Nos, újra itt nincs más választásunk, távolítsa el a fal tetejére, és menj az alábbi telefonszámot.

Ebben az időben, a legtöbb sejt Pervan teszünk egyetlen. Távolítsuk el a fal az előző sor, és lépni a következő cellába.

Tegyük fel akarta egyesíteni a három a végén sejtekben.

Ismét vonzott átlagosan több sejt, amelyből a falon, és távolítsa el a felső. Minden labirintus kész.

Az a képesség, hogy létrehoz egy végtelen labirintus;
Csak egy üres folyosón;
Egy sokkal összetettebb képet, szemben a bináris fa algoritmus;

hátránya:

A bonyolultabb végrehajtását;
A hiányzó holtpontjainak elmozdulás;
Erős függőleges elmozdulás;