Írjunk programot, amelyik kirajzol egy véletlenszerűen generált, kört nem tartalmazó labirintust karakterekből! A falakat jelezze X karakter, a járatokat meg szóköz. A kimenet nézzen úgy ki, mint oldalt!
XXXXXXXXXXXXXXXXXXX
> X X X X
XXXXX X X XXX X X X
X X X X X X X
X X XXX XXX XXXXX X
X X X X X
X X XXXXX XXX XXX X
X X X X X X
X XXXXX XXX XXX XXX
X X X X X X
X XXXXXXXXXXX X X X
X >
XXXXXXXXXXXXXXXXXXXAz elv
XXXXXXXXXXXXXXXXXXXXXXXXX
X X X
> -- a X e X g --- h X
X X X
X | X | X | XXXXXXX
X X
X b --- d --- f --- i X
X X
X | XXXXXXX | XXXXXXX
X X
X c X k --- j --- l -- >
X X
XXXXXXXXXXXXXXXXXXXXXXXXXNézzük meg először egy kicsit jobban egy labirintus anatómiáját. Az egész labirintus egy kétdimenziós listában tárolható (listák listája); a kétdimenziós pálya ki van töltve X-ekkel, és néhol járat van benne szóközökből. A következő rajz egy kinagyított labirintust mutat, bejárattal és kijárattal.
Látható, hogy a labirintus tartalmaz termeket. Ezeket betűk jelölik. Az egyes termekben járatok lehetnek más termek felé; ha több terem felé indul valahonnan járat, akkor az egy elágazás. Ha elfelejtjük egy időre ezt a 2D ábrázolást, és rajzolunk egy gráfot, amelyen a termek a csúcspontok, az őket összekötő járatok pedig az élek, akkor a következő ábrát kapjuk (a fenti labirintussal teljesen megegyező kialakítással, érdemes összevetni a termek kapcsolatát).
Minden terembe egy járat vezet, és minden teremből indulhatnak ki további járatok, amelyek termekbe vezetnek – amely termekből pedig további labirintusok indulhatnak ki. A szerkezet rekurzív felépítésű, ezért a feladat rekurzívan oldható meg – mondá Niklaus Wirth a híres Algoritmusok + adatstruktúrák = programok című könyvében. A megoldásban a gráf formát viszont nem előnyös használni. A listák listája jobban jön, mert az tárolja az egyes termek szomszédsági viszonyait, koordinátáit is, nem csak az összeköttetéseket.
Az algoritmus
0. XXXXXXX 1. XXXXXXX 2. XXXXXXX 3. XXXXXXX
X X X X XXXXXXX XoXXXXX Xo *XXX
XXXXXXX XXXXXXX X XXXXX X XXXXX
X X X X .XXXXX .XXXXX .XXXXX
XXXXXXX XXXXXXX XXXXXXX XXXXXXXA pályán minden második pozíción (vízszintesen és függőlegesen is) fixen termek vannak, ahonnan járatok indulhatnak tovább (0. rajz). Ezért a pálya méretének, amibe rajzolunk, páratlannak kell lennie mindkét irányban.
Az algoritmus, a fenti rajzokon bemutatva, a következőképpen működik. Induljunk ki egy teljesen kitöltött pályából, és tegyük fel, hogy egy járatot már kivájtunk. A pontot, ahol éppen vagyunk, jelölje a pont (.) karakter (1. rajz). Innen négy irányba mehetünk tovább (fel, le, balra, jobbra). A balra vezető irányt ki kell hagynunk, mert ott már van járat, onnan jöttünk. Ha felfelé indulunk, akkor ki kell vájni a pont feletti helyet, és a kettővel felette lévőt, így kerülünk a karikával jelzett helyre (2. rajz). Az új helyen ugyanaz a feladatunk, mint az előbb: innen is négy irányba mehetünk tovább (persze ebből a lefele irányt nem számítjuk, hiszen ott már járat van). Ha minden lehetséges irányba mentünk, akkor befejeztük a rajzolást – ilyenkor vissza kell ugranunk az előző pontba, és megnézni, hogy onnan tudunk-e még bármerre menni. A rekurzió itt abban segít nekünk, hogy visszamenőlegesen automatikusan meg lehet jegyezni, melyik irányokban jártunk már, és melyik irányok felé kell még járatot vágni (ha lehet).
def labirintus(palya, x, y):
...A labirintusrajzoló függvény paraméterként veszi át, hogy melyik koordinátából indulva kell rajzolnia (x, y). Innen négy irányba mehet tovább; ezen irányok közül véletlenszerűen kell választania, ez adja majd az egész pálya véletlenszerűségét. Ugyanakkor mind a négy irányba el kell indulni, különben kitöltetlen részek maradnak a pályán. Ez úgy oldható meg, hogy egy listába betesszük a négy irányt (fel, le, jobbra, balra) és megkeverjük a listát. Ezzel kialakul egy véletlenszerű sorrend, pl. jobbra, le, fel, balra. Utána ezek szerint kell indulni amerre lehet.
Ha a választott irányba nézve már van egy szóköz, az azt jelenti, hogy ott már van járat. Ez két esetben lehetséges: (1) pont most jöttünk onnan, vagy (2) a kacskaringós labirintus más úton már eljutott oda. Az elsőnél egyértelmű, hogy arrafelé nem kell menni. A második esetben viszont nem is szabad arra menni, mert ha oda járatot vágnánk, akkor kör alakulna ki a labirintusban.
Az algoritmus működését az animáció szemlélteti. A rajzolás a bal felső sarokból indul. Minden helyen, ahol járatot kialakít a program, és rekurzív függvényhívás történik, a videón először egy kék jel lesz csak. Miután a rekurzív függvényhívások mind visszatértek, csak utána cseréli ki ezt a kék jelet a végleges feketére. Így azokat a helyeket, ahol a rajzoló függvény még nem futott le teljesen (ahova még vissza kell térnie, megvizsgálni, hogy esetleg onnan még más irányba is indítható egy út), kékkel lehet látni.
A program
A lenti programban a következő részek vannak. Egy kétdimenziós listát hozunk létre, annak a belsejébe rajzolunk. A lista mindkét irányban páratlan méretű kell legyen (ez látszik a fenti rajzokon is), mert két egységenként van egy pont, ahonnan kanyarodni lehet. Induláskor az egészet fallal töltjük ki és abba vájni a járatokat a labirintus() függvénnyel.
A labirintus() függvény kialakít egy olyan labirintust, amelyik teljesen körbe van zárva fallal. Ezért kell úgy indítani a rajzolást, hogy az (1; 1) koordinátákra hívjuk meg a függvényt – a 0. indexű sorban és oszlopban mindenhol fal lesz. A labirintus rajzolása után trükkösen a main() függvényben a bal felső és a jobb alsó sarokhoz még utólag beírunk egy járatot, hogy úgy nézzen ki, mintha ott lenne a bejárat és a kijárat.
A listát a random modul shuffle függvényével keverjük.
import random
MERETX = 35
MERETY = 15
FAL = '#'
JARAT = ' '
# Kétdimenziós lista az előadásról
def ketdimenzios(szeles, magas, kezdeti=None):
palya = []
for _ in range(magas):
palya.append([kezdeti]*szeles)
return palya
# kirajzolás
def kirajzol(palya):
for y in range(MERETY):
for x in range(MERETX):
print(palya[y][x], end='')
print()
# maga a generáló függvény
def labirintus(palya, x, y):
FEL = 1
BALRA = 2
LE = 3
JOBBRA = 4
# erre a pontra hívtak minket, ide lerakunk egy darabka járatot
palya[y][x] = JARAT
# irányok keverése
iranyok = [FEL, BALRA, LE, JOBBRA]
random.shuffle(iranyok)
# a kevert irányok szerint mindenfelé próbálunk menni, ha lehet.
for irany in iranyok:
if irany == FEL:
if y >= 2 and palya[y - 2][x] != JARAT:
palya[y - 1][x] = JARAT # elindítjuk arrafelé a járatot
labirintus(palya, x, y - 2) # es rekurzíve megyünk tovább
elif irany == BALRA:
if x >= 2 and palya[y][x - 2] != JARAT:
palya[y][x - 1] = JARAT
labirintus(palya, x - 2, y)
elif irany == LE:
if y < MERETY - 2 and palya[y + 2][x] != JARAT:
palya[y + 1][x] = JARAT
labirintus(palya, x, y + 2)
elif irany == JOBBRA:
if x < MERETX - 2 and palya[y][x + 2] != JARAT:
palya[y][x + 1] = JARAT
labirintus(palya, x + 2, y)
def main():
# üres pálya létrehozása
palya = ketdimenzios(MERETX, MERETY, FAL)
# labirintus generálása
labirintus(palya, 1, 1)
# be- és kijárat
palya[1][0] = JARAT
palya[MERETY - 2][MERETX - 1] = JARAT
# és mehet kirajzolásra
kirajzol(palya)
main()Érdekes rokonság figyelhető meg a labirintus rajzoló és az alakzat kifestő algoritmus között. Mindkettőnek az a feladata, hogy a rendelkezésre álló térrészt kitöltse. Ezért mindkét algoritmus mind a négy irányba (fel, le, jobbra, balra) megpróbál menni. A kitöltésnél, mivel a konkrét útvonalnak nincs hatása az eredményre, mindegy, milyen irányba indulunk. A labirintusnál viszont látszik a terület „kifestésének” útvonala is – és mivel a célunk az, hogy össze-vissza haladjunk, az indulás irányát minden lépésben véletlenszerűen választjuk ki. (Érdemes megnézni a labirintusgeneráló program kimenetét akkor, ha kihagyjuk ezt a keverést.) Emiatt egyébként a labirintusgeneráló algoritmus szabálytalan alakú labirintusok létrehozására is alkalmas. Kis módosítás után akár a Batman-jel belsejébe is generálhatnánk egy labirintust vele.
A területet bejáró algoritmus útvonalkeresésre is használható. Ebben az esetben a függvénynek visszatérési értéke is kell legyen: IGAZ, ha abba az irányba indulva megtalálható egy keresett dolog (pl. a kijárat vagy egy elrejtett kincs), HAMIS, ha nem. Ez adja az ötletet ahhoz, hogyan lehet olyan programot írni, amelyik megtalálja a labirintusból kivezető utat.
Lássunk egy igazi iteratív megoldást, mert az előző mintha a rekurzív megoldást utánozná. A következő labirintusrajzoló neve Eller algoritmusa. Az érdekessége, hogy nem mászkál fel-le generálás közben a képen, hanem soronként gyártja le a labirintust; miután egy sort megrajzolt, többé azzal már nem foglalkozik, és így eltárolni se kell. Az általa foglalt memória ezért a labirintus szélességével arányos, és teljesen független a labirintus magasságától!
Az algoritmus működése
A működés lényege a következő. A futáshoz halmazokat kell tárolni: minden terem benne van egy halmazban, mégpedig úgy, hogy ha két tetszőleges terem között valamilyen úton összeköttetés van, akkor a két terem ugyanabban a halmazban kell legyen. Ez az információ segít a generáló algoritmusnak eldönteni, hogy összeköthet-e két egymás melletti termet, mert ha eleve egy halmazban vannak, akkor kör keletkezne. A halmazokat mutatnak egy generálás alatt álló labirintusban a jobb oldali ábra színei.
A kimenet egy sorának létrehozása két lépésből áll:
- Vízszintes összeköttetések létrehozása az egymás melletti termek között véletlenszerűen.
- Függőleges összeköttetések létrehozása az egymás alattiak között, úgyszint véletlenszerűen.
Hogy a labirintusban ne legyen kör, illetve izolált rész (ahova sehogyan sem lehet eljutni), az összeköttetéseknél a következő dolgokra kell figyelni:
- Vízszintes összeköttetéseknél: ha két egymás melletti terem már egy halmazban van, akkor nem szabad összekötni őket, mert különben kör keletkezne. Ha behúzunk egy vízszintes vonalat, akkor viszont az általa összekötött két terem halmazait egyesíteni kell (unió).
- Függőlegeseknél: ha egy cella egyedül van egy halmazban, akkor kötelező bekötni a felette lévőhöz (különben egy izolált pont keletkezne). Ha pedig egy cellát nem kötünk be, akkor az saját, új halmazba kerül.
A legelső és a legutolsó sorra speciális szabályok vonatkoznak. A labirintus generálásának elején minden cella a saját halmazába kerül (minden halmaz egy elemű lesz). Az utolsó sort pedig nem szabad véletlenszerűen létrehoznunk, hanem azokra a helyekre kötelezően kell összeköttetést raknunk, ahol két szomszédos terem külön halmazban van.
A megvalósítás
Észrevehetjük, hogy egy sorban minden terem pontosan egy halmazba tartozik bele. Ha a képzeletbeli halmazainkat megszámozzuk, akkor nincs már más dolgunk, mint hogy minden teremhez azt az egész számot rendelni, amilyen számú halmazba az tartozik. Vagyis semmi másra nem lesz szükségünk, csak egy egész számokat tartalmazó listára!
A halmazok közötti műveletek nagyon egyszerűek maradnak. Ha két szomszédos teremnél kíváncsiak vagyunk rá, hogy egy halmazba tartoznak-e, csak össze kell hasonlítani a hozzájuk rendelt számokat. Amikor két halmazt egyesítünk (uniójukat képezzük), akkor a két halmaz helyett csak egy lesz – vagyis a teendőnk annyi, hogy az utóbbi halmazra hivatkozó egész számokat kicseréljük az előbbire hivatkozó egész számmal. Például ha a 10-es és a 12-es halmazt egyesítjük, akkor az összes 12-est kicseréljük 10-re, és kész. (Ezt a listában mindenhol meg kell tennünk! Lehet, hogy két egymástól távoli terem egy halmazban van.) Amikor pedig új halmazt hozunk létre, hozzárendelünk egy olyan számot, amelyik nem jele egyik addigi halmaznak sem.
Az program forráskódja itt letölthető: eller_print.py. Ezen jobban követhető az algoritmus működése. A program sorról sorra, betűről betűre írja ki a rajz karaktereit, balról jobbra és fentről lefelé. Mindegyik karakterkiírás kommentelve van, hogy hogyan kerül oda.