Algoritam generisanja lavirinta

Ovaj lavirint je generisan modifikovanom verzijom Primovog algoritma.

Algoritmi generisanja lavirinta su automatizovani metodi za kreiranje lavirinta.

Metodi zasnovani na teoriji grafova

Lavirint može biti generisan pomoću ranije određenog rasporeda ćelija (najčešće je to pravougaona mreža, ali su mogući i drugi rasporedi) sa poljima koja predstavljaju zid, a nalaze se između njih. Ovakav, ranije generisan raspored se može smatrati kao povezani graf sa stranicama koje predstavljaju moguća polja za zidove i čvorovima koji predstavljaju ćelije. Ciljem algoritma za generisanje lavirinta se onda može smatrati pravljenje podgrafa u kom je izazov naći put između dva određena čvora.

Ako podgraf nije povezan, onda postoje delovi grafa koji su izgubljeni, jer oni ne spadaju u prostor pretrage. Ako graf sadrži petlje tada može postojati više različitih puteva između izabranih čvorova. Zbog ovoga, generisanju lavirinta se najčešće pristupa generisanjem nasumičnog razapinjućeg stabla. Petlje koje mogu da zbune naivne rešavače lavirinta se mogu dobiti dodavanjem nasumičnih ivica u rezultujući lavirint za vreme izvršavanja.

Pretraga u dubinu

Animacija generisanja lavirinta dimenzije 30 sa 20 korišćenjem pretrage u dubinu.

Ovaj algoritam je slučajna varijanta algoritma pretrage u dubinu. Često implementiran preko steka, ovaj pristup je jedan od najjednostavnijih načina da se lavirint generiše putem računara. Smatrajmo da je prostor za lavirint velika mreža ćelija (kao velika šahovska tabla), gde svaka ćelija startuje sa četiri zida. Počinjući od nasumične ćelije, računar selektuje slučajnu susednu ćeliju koja još nije posećena. Računar uklanja zid između ove dve ćelije i dodaje novu ćeliju na stek (ovo je analogno crtanju linije po podu lavirinta). Računar nastavlja sa ovim procesom, a ćelija koja nema neposećenih suseda se smatra ćorsokakom. Kada se nađe u ćorsokaku, on se vraća po putanji dok ne naiđe na ćeliju koja ima neposećenih suseda, a onda nastavlja genrisanje tako što posećuje tu neposećenu ćeliju. Ovaj proces se ponavlja dok se ne posete sve ćelije, što uzrokuje da računar uradi povratak kroz ceo lavirint do početne ćelije. Ovaj pristup garantuje da je prostor lavirinta u potpunosti posećen.

Kao što je već rečeno, algoritam je veoma jednostavan i ne proizvodi preteške lavirinte. Neka specifična unapređenja algoritma mogu pomoći da se generišu lavirinti koje je teže rešiti.

1. Početi u nekoj ćeliji i nazvati je „izlaz“.
2. Označiti trenutnu ćeliju kao posećenu i uzeti listu njenih suseda. Za svakog suseda, počevši od slučajno izabranog uraditi:
   1. Ako taj sused nije bio posećen, ukloniti zid između te ćelije i tog suseda i ponoviti postupak rekurzivno za susednu ćeliju.

Kao što je ranije navedeno, ovaj algoritam koristi duboku rekurziju koja može prouzrokovati probleme vezane za prekoračenje steka na nekim računarskim arhitekturama. Algoritam se može prepraviti u petlju, čuvanjem povratnih informacija u samom lavirintu. Ovo takođe omogućava brz način da se prikaže rešenje, polazeći od bilo koje tačke povratkom do izlaza.

Lavirinti generisani pretragom u dubinu imaju mali faktor grananja i sadrže mnogo dugačkih putanja, što čini pretragu u dubinu dobrim algoritmom za generisanje lavirinata u video igrama. Slučajnim uklanjanjem određenog broja zidova nakon kreiranja lavirinta metodom pretrage u dubinu može se postići efekat proširenja hodnika lavirinta, što može biti odgovarajući metod ako težina rešavanja lavirinta nije od presudne važnosti. Ovaj metod se takođe koristi u video igrama.

U lavirintima generisanim ovim algoritmom, biće relativno lako naći put do kvadrata koji je probran na početku algoritma, jer većina putanja vodi direktno do njega, ali je zato teško pronaći put nazad.

Rekurzivna analiza naniže

Algoritam pretrage u dubinu je često implementiran korišćenjem analize naniže.

1. Postaviti početnu ćeliju na tekuću i označiti je kao posećenu.
2. Dok postoje neposećene ćelije:
   1. Ako tekuća ćelija ima susede koji nisu posećeni
      1. Odaberi slučajno jednog od neposećenih suseda
      2. Postavi trenutnu ćeliju na vrh steka
      3. Ukloni zid između tekuće i izabrane ćelije
      4. Postaviti odabranu ćeliju na trenutnu ćeliju i označiti je kao posećenu
   2. U suprotnom ako stek nije prazan:
      1. Skini ćeliju sa steka
      2. Postaviti je da bude tekuća ćelija
   3. U suprotnom:
      1. Uzmi slučajnu neposećenu ćeliju, postavi je na tekuću i označi kao posećenu

Slučajni Kruskalov algoritam

Ovaj algoritam je slučajna verzija standardnog Kruskalovog algoritma.

1. Kreiraj listu svih zidova i kreiraj set za svaku ćeliju, gde svaki set sadrži samo po tu jednu ćeliju.
2. Za svaki zid, u nekom slučajnom redosledu:
   1. Ako ćelije podeljene ovim zidom pripadaju različitim setovima:
      1. Ukloniti tekući zid
      2. Spojiti setove prethodno podeljenih ćelija

Postoji nekoliko struktura podataka koje se mogu koristiti da modeluju set ćelija. Efikasna implementacija koja koristi strukturu razdvojenih setova može da izvrši svaku uniju i nađe operaciju nad dva seta u skoro konstantnom vremenu (preciznije, $O(\alpha (V))$ time; $\alpha (x)<5$ za svaku moguću vrednost $x$), pa je vreme izvršavanja ovog algoritma proporcionalno broju zidova koje lavirint može da koristi.

Pitanje je samo da li se lista zidova inicijalno slučajno generiše ili je zid slučajno probran iz liste koja nije slučajno generisana. Bilo koji od ova dva načina je relativno lagan za kodiranje.

Zato što je efekat ovog algoritma da proizvede minimalno razapinjuće stablo iz grafa kom su sve grane iste težine, on teži da proizvede tačne šablone koji su generalno lako rešivi.

Slučajni Primov algoritam

Animacija generisanja lavirinta dimenzije 30 sa 20 korišćenjem Primovog algoritma.

Ovaj algoritam je slučajna verzija Primovog algoritma.

1. Početi sa mrežom popunjenom zidovima.
2. Odabrati ćeliju, obeležiti je kao deo lavirinta. Dodati zidove ćelije u listu zidova.
3. Dok postoje zidovi u listi:
   1. Uzmi slučajan zid iz liste. Ako ćelija na suprotnoj strani nije u lavirintu još uvek:
      1. Napraviti od zida prolaz i obeležiti ćeliju na suprotnoj strani kao deo lavirinta.
      2. Dodaj susedne zidove ćelije u listu zidova.
   2. Ako je ćelija na suprotnoj strani već bila u lavirintu, ukloniti zid iz liste.

Kao u algoritmu pretrage u dubinu, obično će biti relativno lako pronaći put do početne ćelije, ali teško pronaći put bilo gde drugo.

Primetite da jednostavno pokretanje klasičnog Primovog algoritma na graf sa slučajnim vrednostima težina grana proizvodi lavirint stilski identičan onom koji kreira Kruskalov algoritam, zato što su i jedan i drugi algoritam zasnovani na minimalnom razapinjućem stablu. Umesto toga, ovaj algoritam uvodi stilsku varijaciju, jer ivice bliže početnoj tački imaju nižu efektivnu težinu.

Modifikovana verzija

Iako klasični Primov algoritam čuva listu ivica, za generisanje lavirinta možemo umesto toga da održavamo listu susednih ćelija. Ako slučajno izabrana ćelija ima više ivica koje je povezuju sa postojećim lavirintom, treba probrati neku od ovih ivica na slučajan način. Ovakav pristup će da teži da razgrana lavirint malo više nego gornja verzija zasnovana na ivicama.

Metoda rekurzivne podele

Lavirinti mogu biti kreirani i rekurzivnom podelom, algoritmom koji radi na sledeći način: Početi sa prostorom za lavirint bez zidova. Ovo ćemo nazvati dvorana. Podeliti dvoranu slučajno postavljenim zidom (ili više njih) gde svaki zid sadrži slučajno pozicioniran prolaz u sebi. Zatim se rekurzivno ponavlja proces na poddvorane dok sve dvorane ne postanu najmanje moguće. Ovaj metod rezultuje lavirintom sa dugim ravnim zidovima, što olakšava uvid u delove lavirinta koje treba izbegavati.

Na primer, u pravougaonom lavirintu, napravi na slučajnim tačkama dva zida koji su normalni jedan na drugi. Ova dva zida dele veliku dvoranu u četiri manje, odvojene sa četiri zida. Odaberi tri od ova četiri zida na slučajan način i otvori rupu veličine jedne ćelije na slučajnoj poziciji u svakom od ta tri zida. Nastaviti na isti način rekurzivno, dok svaka dvorana ima veličinu jedne ćelije u bilo kom smeru.

Jednostavni algoritmi

3D verzija Primovog algoritma. Vertikalni nivoi su označeni od 1 do 4 od dna prema vrhu. Stepenice na gore su označene sa "/", stepenice nadole sa "\", a stepenice koje idu u oba smera sa "x". Izvorni kod je uključen u opis slike.

Postoje i drugačiji algoritmi koji zahtevaju samo onoliko memorije koliko je potrebno za čuvanje jedne linije 2D lavirinta ili jedne ravni 3D lavirinta. Oni sprečavaju petlje tako što pamte koje ćelije u trenutnoj liniji su povezane sa ćelijama u prethodnim linijama, i nikada ne uklanjaju zidove između bilo koje dve ćelije koje su već povezane.

Većina algoritama za generisanje lavirinata zahteva održavanje veza između ćelija, da bi se osiguralo da će krajnji rezultat biti rešiv. Validni jednostavno rešivi lavirinti mogu ipak biti generisani fokusiranjem na svaku ćeliju nezavisno. Lavirint binarnog stabla je standardni ortogonalni lavirint gde svaka ćelija uvek ima prolaz koji vodi levo ili gore, ali nikada oboje. Da bi se kreirao lavirint binarnog stabla, za svaku ćeliju bacimo novčić i odredimio da li će ta ćelija imati prolaz koji vodi levo ili gore. Uvek se uzima isti pravac za ćelije na granicama, i krajnji rezultat će biti validni jednostavno rešivi lavirint koji izgleda kao binarno stablo, kod kog je gornji levi ćošak njegov koren.

Primer koda za generisanje lavirinta napisan u programskom jeziku Python

import numpy
from numpy.random import random_integers as rand
import matplotlib.pyplot as pyplot

def maze(width=81, height=51, complexity=.75, density=.75):
    # Only odd shapes
    shape = ((height // 2) * 2 + 1, (width // 2) * 2 + 1)
    # Adjust complexity and density relative to maze size
    complexity = int(complexity * (5 * (shape[0] + shape[1])))
    density    = int(density * (shape[0] // 2 * shape[1] // 2))
    # Build actual maze
    Z = numpy.zeros(shape, dtype=bool)
    # Fill borders
    Z[0, :] = Z[-1, :] = 1
    Z[:, 0] = Z[:, -1] = 1
    # Make isles
    for i in range(density):
        x, y = rand(0, shape[1] // 2) * 2, rand(0, shape[0] // 2) * 2
        Z[y, x] = 1
        for j in range(complexity):
            neighbours = []
            if x > 1:             neighbours.append((y, x - 2))
            if x < shape[1] - 2:  neighbours.append((y, x + 2))
            if y > 1:             neighbours.append((y - 2, x))
            if y < shape[0] - 2:  neighbours.append((y + 2, x))
            if len(neighbours):
                y_,x_ = neighbours[rand(0, len(neighbours) - 1)]
                if Z[y_, x_] == 0:
                    Z[y_, x_] = 1
                    Z[y_ + (y - y_) // 2, x_ + (x - x_) // 2] = 1
                    x, y = x_, y_
    return Z

pyplot.figure(figsize=(10, 5))
pyplot.imshow(maze(80, 40), cmap=pyplot.cm.binary, interpolation='nearest')
pyplot.xticks([]), pyplot.yticks([])
pyplot.show()

Vidi još

• Algoritam za rešavanje lavirinta

Spoljašnje veze

• HTML 5 prezentacija sa demonstracijama algoritama za generisanje lavirinta
• Think Labyrinth: Maze algorithms (Detalji u vezi sa opisanim i nekim drugim algoritmima)
• Maze Generation Arhivirano na sajtu Wayback Machine (28. februar 2014) - Master's Thesis (Java aplet koji omogućava korisnicima da kreiraju lavirint korišćenjem različitih algoritama)
• Kolekcija kodova za generisanje lavirinata u različitim programskim jezicima
• Generisanje i kretanje kroz 3D lavirint