DFS Un algoritm recursiv, foarte “sinuos”. Rezultatul sau e un labirint extrem de greu de parcurs, cu solutii lungi si intortocheate. Deasemenea, drumuri infundate foarte multe. Metode de functionare este simpla: porneste dintr-un punct si sparge celule nesparte din jur, dupa care se muta in ele si continua pana nu mai are vecini nesparti. Revine apoi la o pozitie anterioara care ii permite spargerea unei noi celule. Algoritmul se opreste in momentul in care nu mai esista nici o celula a carei vecini sa fie izolati.Algoritmul lui Eller Acest algoritm este foarte interesant pentru ca nu numai ca este mai rapid decat toti algoritmii cunoscuti ci este si cel mai eficient din punct de vedere al utilizarii memoriei. Nici macar nu are nevoie ca intregul labirint sa fie incarcat in memorie, ii ajunge o singura linie (rand). Creeaza labirintul rand dupa rand, iar dupa ce a trecut la urmatorul rand, nu se mai uita la cel precedent. Fiecare celula a randurilor este retinuta intr-un set, astfel incat doua celule fac parte din acelasi set doar daca exista un drum intre ele prin partea de labirint generata deja. Avantajul este ca drumul creeat prin labirint nu va contine niciodata bucle sau celule izolate. In aceasta forma este similar oarecum algoritmului lui Kruskall cu deosebirea ca Eller`s rezolva rand dupa rand iar Kruskall revizuieste intregul labirint, tinand ocupata mult mai multa memorie si procesor. Cum creeam un rand? Exista doua metode: Prima, conectarea aleator a doua celule adiacente in acelasi rand prin “spargerea” peretilor dintre doua celule care nu apartin aceluiasi set si refacerea seturilor pe intregul rand in asa fel incat toate celulele de pe acelasi drum sa apartina aceluiasi set. Conectarea verticala se face aleator. La conectarea verticala este absolut necesar sa se conecteze celulele care sunt singure (izolate). Initial, toate celulele fac parte din propriul set, unic, iar apoi se parcurge labirintul linie cu linie si se conecteaza celulele astfel incat fiecare sa faca parte din acelasi set, impiedicandu-se astfel izolarea celulelor. Algoritmul trateaza celulele aleator, astfel generandu-se solutii diferite la fiecare rulare. Algoritmul “Hunt and Kill” Avantajul acestui algoritm este faptul ca nu are nevoie de spatiu suplimentar sau fiind astfel foarte util generarii de labirinturi de dimensiuni foarte mari sau generarii pe sisteme cu cantitate redusa de memorie, el nepunand problema ramanerii fara spatiu de memorie (relativ...). Nu exista o regula fixa de generare asa ca poate fi modificat usor si se pot creea astfel labirinturi de dimensiuni si texturi diferite. Seamna afoarte mult cu o metoda backtracking doar ca in momentul in care ajunge la un impas (in preajma nu mai are nici o celula ne-sparta), nu se opreste ci trece in “hunting-mode”. Va cauta din acel moment o celula izolata, nelegata la labirint si va continua din acel punct pana la un nou impas cand va repeta procedura. Generarea se termina odata ce intregul labirint a fost scanat in “hunting-mode”. Tendinta algoritmului este de a creea labirinturi cu o lungime foarte mare, dar nu la fel de mare ca o procedura clasica back-traking. Pentru a reduce din lungimea drumurilor se poate intra mai des in hunting mode. E foarte lent cand cauta ultimele celule, dar nu e mai rau decat Kruskal.
|