Modele Comportamentale Utilizabile In Simularea Mediilor Virtuale Deplasare In Labirint Dinamic

Cuprins

1.Introducere

Conform literaturii de specialitate, Realitatea virtuală (VR – Virtual Reality) reprezintă un sistem de calcul, care poate oferi utilizatorului iluzia unei lumi generate pe calculator si a posibilitatii de a calatori fara restrictii în aceasta lume. Conceptul de "realitate virtuala" a fost descris pentru prima data de Jaron Lanier în anii ’80, el punând practic piatra de temelie a acestui domeniu, infiintand compania VPL (Virtual Programming Languages) Research, care a construit cateva dintre primele sisteme VR in acea perioada.

Majoritatea mediilor informatice, care propun spatii de realitate virtuala, reprezinta, in general, experiente vizuale, urmarite pe un monitor sau prin intermediul unor afisaje stereoscopice speciale (tip display), insa unele simulari includ informatii senzoriale aditionale. Adesea, utilizatorii pot interactiona cu mediul virtual prin intermediul dispozitivelor standard de intrare (tastatura, mouse etc.), dar exista si o serie de periferice special create pentru a patrunde si "locui" in lumea virtuala (manusi de date). In consecinta, mediul simulat poate fi asemanator cu lumea reala (simularile pentru pilotare automata sau instruirea in lupta) sau poate fi substantial diferit de realitate (jocurile virtuale).

In prezent, este foarte populara ideea dezvoltarii interfetelor multifunctionale in descrierea interfetelor utilizator si acest lucru apare ca o reactie impotriva conceptului si a interfetei traditionale de realitate virtuala, precum si a problemelor pe care aceasta le ridica. De fapt, ambele tipuri de interfete au scopuri diferite si sunt complementare. Tendinta curenta in domeniul realitatii virtuale este, in general, de a uni cele doua tipuri de interfete amintite si de a crea o colaborare totala si o experienta combinata pentru utilizatori. Prin intermediul interfetelor, conceptele abstracte pot fi prezentate metaforic intr-un mod creativ.

Una din motivatiile pentru utilizarea conditiilor naturaliste este aceea ca rezultatele obtinute au aplicabilitate in lumea reala. Pentru aceasta este necesara examinarea comportamentelor in mediile reale pentru a valida performanta in mediile virtuale. Comportamentul in mediile reale genereaza ipoteze despre controlul motor-visual care poate fi translatat in mediul virtual pentru testare.

Definitii si concepte

Realitatea virtuala este o simulare generata de calculator a unui mediu tridimensional in care utilizatorul este capabil sa vizualizeze si sa manipuleze continutul acestui mediu.

Comportamentul este adesea definit ca fiind calea prin care animalele sau oamenii actioneaza. Este deasemenea raspunsul unui individ, grup sau specii de indivizi catre mediul in care traiesc. Bazandu-se pe aceasta definitie in 1987 Reynolds a introdus termenul si conceptul de animatie comportamentala pentru a descrie automatizarea animatiei de nivel inalt. comportamentul nu ar trebui sa reactioneaze doar la mediu ci ar trebui sa includa fluxul informational care defineste comportamentul entitatiilor vii din mediu cat si a entitatiilor virtuale si foloseste acest flux. Reynolds a studiat in detaliu problema traiectoriilor grupurilor: carduri de pasari , hoarde de animale terestre si bancuri de pesti.

Mediu virtual: reprezentare dimensionala(2D,3D), generata cu calculatorul, a unui mediu, care sugereaza un spatiu real sau imaginar, fara sa urmareasca in mod deosebit fotorealism sau imersiune totala.

Un labirint este :

1. In mod usual o retea confuza si incurcata de cai si pasaje care se interconecteaza intr-o gradina.

2. Un puzzle grafic in care solutia este o cale sau un pasaj neintrerupt printr-un patern complicat format din segmente de linii ce incepe dintr-un punct de start si se continua pana la o iesire.

Punctul de start( intrare , inceputul) : Intrarea este punctul de start al unui labirint, in mod uzual indicat printr-un “S”. Cateva labirinturi au mai multe ouncturi de start desi acest lucru e foarte rar.

Sfarsit( iesire, scopul): Punctul de sfarsit al unui labirint este in mod uzual indicat printr-un “E”. In labirinturile unicursale ( labirinturi cu o singura cale) punctul de iesire se afla de obicei in centru.

Dead end: Este un pasaj ce nu duce nincaieri, si care nu are nici ramificatii nici jonctiuni.

Aleie”oarba” ( cul-de-sac, trap): In mod general, acestea sunt o varietate de pasaje loop-ante sau colectii de pasaje in care odata intrat trebuie iesit prin intoarcerea inapoi pe calea prin care s-a venit.

Jonctiune: Este o arie dint-un labirint unde trei sau mai multe pasaje se intalnesc, fortand pe cel ce rezolva labirintul sa aleaga dintre cel putin doua rute alternative pentru a merge inainte. Jonctiunile bine gandite reusesc sa induca in eroare pe cei ce rezolva labirintul astfel conducandui pe cai incorecte.

Perete exterior( boundary; granita) Este peretele sau bariera ce formeaza cel mai indepartat perimetru al labirintului. Orice altceva inafara peretelui exterior nu face parte din labirint.

Spirala(in labirint) : Este o singura cale care se spiraleaza in ea insasi care duce fie intr-un dead end fie in centrul labirintului

Vortex : Este format din trei sau mai multe pasaje care se spiraleaza una in alta , intr-o jonctiune centrala, unde va trebuie aleasa calea care iese din acest vortex. Vortexurile sunt dezorientante deorece este dificil de prezis in ce directie un pasaj va indica.

Bottleneck: este un pasaj ce leaga o arie a labirintului de alta arie si care trebuie tranversata pentru a rezolva labirintul.

Best solution( shortest path) : Este cea mai scurta ruta prin labirint. Unele labirinturi au mai multe solutii scurte, desi aceste labirinturi sunt foarte rare.

Nota: Proiectul s-a derulat in cadrul si cu sprijinul Laboratorului de CErcetare in domeniul Realitatii Virtuale si Augmentate (CERVA). Pentru detalii vizitati: http://www.univ-ovidius.ro/cerva

2.Starea actuala a domeniului

Maze at St. Louis Botantical Gardens [24]

2.1 Labirint. Generalitati

Labirinturile promoveaza atat gandirea structurata cat si cea creativa si sunt populare si distractive. Ele sunt puzzleluri educationale foarte interesante pentru calatorii si sunt cadouri excelente pentru copii supradotati

Labirintul, termenul provine din grecescul labyrinthos, poate fi definit ca un puzzle tour asezat sub forma unui pasaj arborescent complex unde imlementatorul( cel ce rezolva labirintul) trebuie sa gaseasca o solutie, adica o ruta(pasaj) ce il va scoate din labirint.

Pasajele si peretii unui labirint sunt fixati( predeterminati). Tipurile de labirinturi care isi schimba peretii in timpul jocului, adica in timpul determinarii solutiei fac parte din categoria principala a tour puzzle.

Labirintul apare prima oara in mitologia greaca , unde era o structura elaborata, construita de regele Minos si proiectata de legendarul Dedalus pentru a inchide minotaurul( o creatura mitologica jumatate om, jumatate taur).

Labirinturile au fost construite cu pereti si camere, cu garduri vii, cu gazon sau cu pietre de pavaj de culori si designuri contrastante. Un tip de labirinturi consta intr-un set de camere conectate prin usi (astfel ca un pasaj este doar o alta camera); jucatorii intra intr-o parte si ies prin alta parte sau fie trebuie sa ajunga la un loc specific din labirint. Labirinturile pot fi printate sau desenate pe hartie iar solutia poate fi urmarita cu degetul sau creionul. Exista o varietate de algoritmi de generare a labirinturilor pentru constructia lor atat manuala cat si computerizata. Labirinturile sunt facute mai ales pentru divertismentul celorlalti.

Numeroase labirinturi de diferite tipuri au fost desenate, pictate, publicate in carti si in publicatii periodice , au fost utilizate in publicitate, in software si vandute ca arta. In 1970 a avut loc in publicatii un fenomit numit “maze craze” prin care numeroase carti, si cateva reviste publicau suplimente dedicate exclusiv labirinturilor de o complexitate cababila atat sa provoace adultii cat si copii.

Cateva dintre cele mai bine vandute carti din 1970 si de la inceputul 1980 contineau labirinturile create de Vladimir Koziakin, Rick si Glory Brightfield, Dave Philips, Larry Evans si Greg Bright. Majoritatea lucrariilor lui Koziakin faceau parte din varietatea bidimensionala “traseaza o linie printre peretii labirintului”. Lucrariile lui Brightfield aveau o forma bidimensionala similara dar utiliza o varietate grafic orientata cu tehnici de “ intunecare a cailor”.Chiar daca rutarea era comparabila sau mai simpla decat cea din labirinturile lui Koziakin, labirinturile lui Brightfield nu permite varietatea optiunilor de cai care este discernatata usor la o prima privire asupra labirintului. Lucrarile lui Greg Bright au mers dincolo de formaele standard ce se publicau la acea vreme, astfel el incluzand labirinturile “wave” in care caile pot trece unele peste altele sau pot trece unele sub altele. Lucrariile lui Bright au oferit de asemenea exemple de patterni extremi de complexi de rutare si de iluzii optice pentru cel ce rezolva labirintul. Ceea ce Bright a numit “ centri accesibili mutuali”(The Great Maze Book , 1973) deasemenea numit si labirinturi “braid”, a permis o proliferare a cailor ce “curg” in paterni spirala de la o conexiune centrala si , decat sa se bazeze pe dead enduri pentru a intarzia progresul, mai degraba se bazeaza pe o supraabudenta de optiuni de cai. Deacat sa aiba o singura solutie in labirint, routarea Lui Bright de multe ori ofera multiple rute valide si egale de la punctul de start pana la iesire, fara pierderea complexitatii sau a dificulatii de rezolvare. Cartiile lui Larry Evans erau focalizate pe labirinturile 3D , adesea cu perspective realistice si teme arhitecturale.

Ambii Greg Bright (The Hole Maze Book) si David Philips ( The World’s Most Difficult Maze) au publicat cartii in care laturile paginiilor puteau fi trecute si care gaurile puteau permite cailor sa treaca dintr-o pagina in alta, astfel intensificand capacitatea de routare 3D la ilustatele printate 2D.

O carte recenta scrisa de Galen Wadzinski (The Ultimate Maze Book) ofera reguli formalizate pentru labirinturi inovatoare: labirinturi ce implica cai uni-directionale, simulare de ilustratii 3D, labirnturi “cheie” si “stop la comanda” in care obiectele trebuie sa fie colectate sau vizitate intr-o ordine particulara pentru cresterea dficultatii de routare.

Desi aceste inovatii prezentate de Wadzinski nu sunt in totalitate noi , cartea marcheaza un progres significant in domeniul publicatiilor de labirinturi, oferind o expansiune la clasicile labirinturi si puzzleluri.

2.2 Clasificarea labirinturilor

Labirinturile in general pot fi organizate in sapte clasificari diferite. Acestea sunt: Dimensiune , Hiperdimensiune ,Topologie , Tesselare , Routare, Texturare si Focalizare. Un labirint poate lua un item din fiecare clasa in orice combinatie.

Dimensiune: Clasa dimensiune se refera la cate dimensiuni acopera labirintul in spatiu. Tipurile de dimensiuni sunt:

2D: Majoritatea labirinturilor sunt in aceasta dimensiune, unde este intotdeauna posibil sa afisez planul pe o foaie de hartie(frame, applet) si sa navighezi in el fara sa suprapunem oricare alte pasaje din labirint.

Labirint 2D [27]

3D: Un labirint tridimensional este unul cu nivele multiple, unde( in cel putin cazul orthogonal) pasajele pot “sa mearga” sus sau jos in aditie cu cele 4 puncte cardinale. Un labirint 3D este adesea reprezentat ca un vector de nivele 2D,cu indicatoare “sus” si “jos”.

Labirint 3D [28]

Dimensiune superioara: Este posibil sa avem labirinturi cu 4 sau mai multe dimensiuni. Acestea sunt adesea randate ca labirinturi 3D, cu “portale” speciale pentru a tranversa in a patra dimensiune.

Labirint 4D [15]

Labirint 5D [16]

Weave: Un labirint weave este un labirint 2D(sau mai corect spus un labirint 2.5D) unde pasajele se pot suporice combinatie.

Dimensiune: Clasa dimensiune se refera la cate dimensiuni acopera labirintul in spatiu. Tipurile de dimensiuni sunt:

2D: Majoritatea labirinturilor sunt in aceasta dimensiune, unde este intotdeauna posibil sa afisez planul pe o foaie de hartie(frame, applet) si sa navighezi in el fara sa suprapunem oricare alte pasaje din labirint.

Labirint 2D [27]

3D: Un labirint tridimensional este unul cu nivele multiple, unde( in cel putin cazul orthogonal) pasajele pot “sa mearga” sus sau jos in aditie cu cele 4 puncte cardinale. Un labirint 3D este adesea reprezentat ca un vector de nivele 2D,cu indicatoare “sus” si “jos”.

Labirint 3D [28]

Dimensiune superioara: Este posibil sa avem labirinturi cu 4 sau mai multe dimensiuni. Acestea sunt adesea randate ca labirinturi 3D, cu “portale” speciale pentru a tranversa in a patra dimensiune.

Labirint 4D [15]

Labirint 5D [16]

Weave: Un labirint weave este un labirint 2D(sau mai corect spus un labirint 2.5D) unde pasajele se pot suprapune unele peste altele. In afisare este in general evident care este un drum inchis si care este un pasaj care merge sub un altul.

Labirint weave [14]

Hiperdimensiune: Clasa hiperdimensiune se refera la dimensiunile obiectului pe care il miscam prin labirint,ca opusul dimensiunii mediului labirintului. Tipurile de hiperdimensiune sunt:

Non hiperlabirint: Virtual toate labirinturile, chiar si cele in dimensiuni superioare sau cu reguli speciale, sunt non hiperlabirinturi normale. In ele lucram cu un punct sau un obiect mic pe care il miscam din punct in punct formand o linie ce arata calea parcursa pana la momentul respectiv. Sunt un numar de alegeri usor de retinut la fiecare punct.

Hiperlabirint: Un hiperlabirint este un labirint unde obiectul care returneaza rezolvarea este mai mult decat un punct. Un hiperlabirint standard(sau un hiperlabirint de ordin 1) consta intr-o linie unde pe masura ce obiectul se ramifica si se misca in labirint calea parcursa se trransforma intr-o suprafata.Un hiperlabirint exista doar int-un mediu de dimensiune 3D sau superioara , unde intrarea in hiperlabirint este deasemenea o linie inloc de un punct.

Hiperlabirint [21]

Hipehiperlabirint: Hiperlabirinturile pot fi arbitrar de dimensiuni superioare. Un hipehipelabirint( sau un hiperlabirint de ordin 2) creste din nou dimensiunile obiectului ce returneaza solutia. Aici obiectul ce returneaza solutia este un plan, unde pe masura ce il miscam , claea parcursa se transforma in solid. Un hiperhiperlabirint poate exista intr-o dimensiune 4D sau superioara acesteia.

Topologia: Clasa topologie descrie geometria spatiului in care exista labirintul. Tipuri de topologie:

Normal: Este un labirint reprezant in spatial Euclidian

Planair: Termenul “planair” se refera la orice labirint cu o topologie anormala. Aceasta de obicei inseamna conectarea muchiilor labirintului in forme interesante. De exemplu exista labirinturi pe suprafata unui cub, labirinturi pe suprafata unei fasii Moebius etc.

Labirint planair [20]

Tesselation: Clasa tessellation se refera la geometria celulelor individuale care compune labirintul. Tipuri de tessalation:

Ortogonal: Este o retea rectangulara standard unde celulele au pasaje intersectanduse in unghiuri drepte

Delta: Un labirint Delta este unul compus din triunghiuri angrenate, unde fiecare celula poate avea pana la trei pasaje conectate de ea.

Labirint Delta [10]

Sigma: Un labirint Sigma este un labirint compus din hexagoane angrenate, unde fiecare celula poate avea pana la sase pasaje conectate de ea.

Labirint Sigma [11]

Theta: Theta labirinturile sunt compuse din cercuri concetrice de pasaje, unde inceputul labrintului este in centru si sfarsitul este pe muchia exterioarea(si viceversa).

Labirint Theta [9]

Upsilon: Labinturile Upsilon sunt compuse din octagoane si patrate angrenate, unde fiecare celula poate sa aiba pana la opt sau patru posibile pasaje conectate de ea.

Labirint Upsilon [12]

Zeta: Un labirint Zeta este pe o retea rectangulara, cu exceptia pasajelor diagonale cu un unghi de 45 grade, ce trec printre cellule si care sunt adaugate printre cele verticale si orizontale.

Labirint Zeta [19]

Omega: Termenul “omega” se refera la majoritatea labirintelor cu o consistenta tessellation non ortogonala.

Crack: Un labirint crack este un labirint amorf fara nici o consistenta tessellation , dar mai degraba are pereti sau pasaje la unghiuri random.

Labirint Crack [13]

Fractal: Un labirint fractal este un labirint compus din labirinturi mai mici. O celula fractal labirint este un labirint cu alte labirinturi “decorate” in fiecare celula, unde procesul poate fi repetat de mai mult ori. Un labirint infinit de tip fractal este un fractal adevarat, unde labirintul contine copii ale lui insasi si este intradever un mare labirint infinit.

Labirint Fractal [26]

Routare: Clasa routare este probabil cea mai interesanta clasa cu privinta la generarea labirntului. Se refera la tipurile de pasaje in orice geometrie definite in categoriile de mai sus.

Perfect: Un labirint “perfect” inseamna un labirint fara circuite inchise sau loops si fara arii inaccesibile. Acest tip de labirint mai este numit labirint simplu conectat. Din fiecare punct , exista exact o singura cale catre oricare alt punct. Labirintul are exact o solutie. In termini de informatica un astfel de labirint poate fi descries ca un arbore minimal intins pe un set de celule.

Labirint Perfect [25]

Braid(infasurat): Un labirint “braid” inseamna un labirint fara nici un drum inchis Acest tip de labirint se mai numeste labirint multiplu conectat. Un astfel de labirint foloseste pasajele care care se “incolacesc” de jur imprejur si alearga inapoi unele in celalte si cauzeaza ca obiectul sa se deplaseze in cercuri inloc sa intre in drumuri inchise. Un labirint “braid” bine alcatuit poate fi mult mai greu decat un labirint perfect de acelasi dimensiuni.

Labirint Braid [8]

Unicursal: Un labirint unicursal inseamna un labirint fara junctiuni. Un labirint unicursal are doar un pasaj- sarpe lung care se “incolaceste” pe extindenrea labirintului.. Nu este dificil decat daca accidental obiectul se intoarce inapoi la inceput la jumatatea drumului.

Labirint Unicursal [7]

Braid partial: Un labirint partial braid este doar un labirint mixt ce cuprinde atat loops cat si drumuri inchise.

Texturarea: Clasa texture este subtila si descrie stilul pasajelor in orice routare si in orice geometrie. Cateva exemple de variabile:

Inclinat(bias): Un labirint inclinat este unul cu cai drepte care tind sa mearga intr-o directie mai mult decat in altele. de exemplu, un labirint cu o mere inclinare orinzontala va avea lungi pasaje left-right si doar scurte pasaje up-down care le conecteaza.

Labirint bias [17]

Run: Factorul “run” a unui labirint se refera la cat de mult caile drepte tind sa mearga inainte sa fie fortate sa faca intoarceri. un labirint cu un factor “run” mare va avea pasaje lungi ce vor merge pe un procent destul de mare din suprafata labirintului si va arata exact ca un microcip.

Labirint Run [18]

Elite: Factorul “elitism” a labirintului indica lungimea solutiei cu privinta la dimensiunea labirintului. In general un labirint elitist are solutii scurte si direct pe cand un labirint neelitist are o solutie care merge pe o portiune destul de mare a labirintului. Un labirint elitist bine construit poate fi mai greu decat unul neelitist.

Simetric: Un labirint simetric are pasaje simetrice, de exemplu rotational simetric catre centru, sau reflectat dealungul axei orizontale sau verticale. Un labirint poate fi partial sau total simetric si poate repeat un pattern de un numar oarecare de ori.

River(rau): Caracteristica “river” inseamna ca atunci cand cream un labirint, algoritmul va cauta si va sterge celulele din apropiere(sau pereti) pana la celula curenta create, de exemplu va curge( din termenul “river”) in prtiuni necreate a labirintului ca apa. Un labirint perfect cu mai putin “river” va tinde sa aiba multe drumuri inchise scurte pe cand un labirint cu mai mult “river” va avea mai putine sar mai lungi drumuri inchise

Focus(Focalizare): Clasa focus este obscura, dar arata ca, creearea labirintului poate fi divizata in doua tipuri generale: cei care adauga pereti si cei care taie pasaje. Aceasta e mai mult o diferenta algoritmica atunci cand se genereaza, fata de o diferenta visuala atunci cand se observa, dar este demna de luata in considerare. Acelasi labirint poate fi adesea generat in ambele moduri:

Cei care adauga pereti(wall aders): Algoritmi care se focalizeaza asupra peretilor pornesc cu o arie goala(sau cu granita exterioara) si adauga pereti.

Cei care taie pasaje(passage carvers): Algoritmi care se focalizeaza asupra peretilor pornesc cu un bloc solid si taie pasaje.

Template: Labirinturile pot binenteles sa fie atat wall added cat si passage carved si cativa algoritmi fac asta. Un labirint template se refera la un graphic general care nu este un labirint, care este apoi modificar sa fie un labirint valid in cat mai putini pasi posibili, dar care are inca textura originalului template. Stilurile de labirinturi complicate ca spiralele angrenate sunt mai usor de reprezentat pe un calculator ca un template fata de a incercarea de a creea un labirint valid in timp ce trebuie tinut in stilul ales in acelasi timp.

Altele: Majoritatea tipurilor de labirinturi, incluzand labirnturile cu reguli speciale , pot fi exprimate ca un graf direct,unde vom avea un numar finit de stari un numar finit de alegeri la fiecare stare care este numita echivalenta labirintului . Alte clase si tipuri de labirinturi:

Directie: In acest labirint anumite pasaje pot fi parcurse intr-o singura directie. In termini informatici un astfel de labirint poate fi descries de un graf direct.

Segmentat: In acest labirint are diferite sectii din aria sa care cad in diferite clase.

Labrinturi infinite: Este posibil de a crea un labirint infinit lung prin pastrarea unei parti din labirint in memorie la un moment dat si “scrolling” labirintul de la un capat la altul, indepartand randurile anterioare in timp ce cream randuri noi. O cale de generare a acestui labirint este cu o versiune modificata a algoritmului Hunt and Kill.

Labirinturi virtuale fractale: Un labirint virtual este un labirint unde intregul labirint este stocal in memorie. De exemplu stocam doar sectiunea de pasaje de 100×100 sau locatia cea mai apropiata intr-o simulare unde un obiect merge printr-un labirint imens. O extindere a unui labirint fractal poate fi folosit la creeare unui labirint virtual de dimensiune foarte mare, cu milioane si milioane de pasaje. Pentru a ne asigura ca labirintul ramane consistent si niciodata nu se schimba pe masura ce ne deplasam trebuie sa avem o formula pentru determinarea unui numar aleator seed pentru fiecare coordonata la fiecare nivel. Labirunturile fractale virtuale sunt similare cu un set fractal Mandelbrot, unde imaginile in un Mandelbrot exista virtual.

2.3 Algoritmi de creare a labirintului

Lista de algoritmi generali folositi pentru crearea diferitelor tipuri de labirinturi descries mai sus:

Perfect: Creearea unui labirint standard perfect implica deobicei “cresterea(growing)” labirintului in timp ce se asigura ca nu sunt tinute loop-uri si restrictii izolatoare. Incepe cu peretele exterior si adauga un segment al peretelui atingandul aleatoriu. Continua sa adauge aleatoriu pereti labirintului, dar se asigura ca fiecare nou segment atinge la un capat un perete existent si are celalalt capat intr-o portiune necreeata a labirintului. Daca vreodata se adauga un segement de perete unde ambele capete sunt separate de restul labirintului atunci se va creea un un perete detasat cu un loop imprejurul lui si daca vreodata se va adauga un segment de perete in care ambele capete ating labirintului atunci se va creea o arie inaccesibila.

Braid: Pentru a creea un labirint fara drumuri inchise, se adauga in mod aleatoriu segmente prin tot labirintul , dar se va asigura ca fiecare nou segment adaugat nu va cauza creearea unui drum inchis. Pentru aceasta se vor folosi urmatorii 4 pasi:

Incepem cu peretele exterior

Loop prin labirint si se adauga segmentele singure ale peretelui atingand fiecare vertexul peretelui pentru a asigura ca nu exista camere deschise

Loop peste toate segementele posibile intr-o ordine aleatoare, adaugand un perete daca acesta nu cauzeaza un drum inchis

Fie rulam la sfarsit utilitatea isolation remover pentru a face un labirint legal ce are o solutie sau vom aduga in pasul trei conditia ca un perete sa fie adaugat doar daca nu cauzeaza o sectiune izolata.

Unicursal: O cale de a creea un labirint aleatoriu unicursal este de a lua un labirint perfect, de a izola iesirea si astfel avand doar o singura intrare iar apoi adaugand pereti bisectand fiecare pasaj. Aceasta va transforma fiecare drum inchis intr-un pasaj de forma U si axolo ba fi un unicursal pasaj pronind si sfarsind la inceputul original a labirintului. Noul labirint unicursal ba avea de doua ori dimensiunea originalului labirint perfect. Mici trucuri pot fi aplicate pentru a nu avea inceputul si sfarsitul intotdeauna unul langa altul. Atunci cand se creaza labirintul perfect niciodata nu se va adauga segmentele atasate peretilor din dreapta sau din jos astfel labirintul creat va avea o simpla ce urmareste peretele respective.Vom avea intrarea in partea dreapta de sus si dupa ce bisectam pentru a crea ruta unicursala ,se va inlatura peretele din dreapta si cel din jos. Astfle va rezulta uun labirint unicursal care porneste din partea dreapta de sus si se termina in partea stanga de jos.

3D: Labirinturile teri sau de dimensiune superioara pot fi create ca si un labirint standard 2D cu exceptia ca fiecare celulaa poate fi mutata in mod alternativ in sase in loc de patru alte cellule ortogonale. Aceste labirinturi sunt in general pasaje taiate datorira dimensiunei extra.

Weave: Labireinturile weave sunt facute ca pasaje taiate a unu labirint perfect, cu exceptia atunci cand taiem un pasaj nu suntem intotdeauna blocati de un pasaj existent, pe cand avem optiunea de a merge dedesubtului lui si inca sa pastram calitatea “perfecta” a acestuia. Pe un bitmap monocrom , un labirint wave poate fi reprezentat cu patru randuri pe pasaj( doua randuri pe pasaj e sufficient pentru un labirint perfect standard) unde avem un rand pentru insusi pasajul si celelalte trei randuri s ail faca neambiguu cand un pasaj vecin merge sub un alt pasaj inloc sa aiba drumuri inchise langa primul pasaj.

Crack: Labirinturile crack sunt facute la fel ca labirinturile perfecte wall added , cu exceptia ca nu exista cellule tessellation distincte ,altele decat locatiile pixel aleatori. Alegem un pixel care deja este setat ca un perete, alegem aleatoriu o alta locatie si “impuscam” sau incepem sa desenam un perete catre a doua locatie. Va trebui sa ne asiguram ca ne vom opri chiar inainte de a da peste un perete existent astfel incat san u cream izolatii. Daca intr-o perioada de timo in care repetam acest algoritm nu reusim sa adaugam nici un perete significativ atunci ne vom opri.

Omega: Labirinturile in stil omega implica definirea a cateva retele, determinarea modului in care celulele se unesc unele cu altele si modul de de mapare a vertexurilor care inconjoara fiecare celula catre ecran. De exemplu pentru un labirint triangular Delta cu celule triunghiulare angrenate: (1)Exista o retea unde fiecare rand are un numar de celule care creste de doua ori.(2) Fiecare celula este conectata la celulele ei adiacente in randul respective, cu exceptia pasajului al treilea care este conectat cu o celula din randul de joss au de sus, depinde daca este o coloana para sau impara( de exemplu triunghiul are varful in sus sau in jos).(3) Fiecare celula utilizeaza formule matematice pentru un triunghi pentru a determina locul desenarii acestuyia pe ecran. Putem desena toti peretii pe ecran si apoi sa ii taiem pentru a obtine labirintul sau sa mentinem niste vectori modificati in memorie iar apoi sa randam labirintul cand va fi complet generat .

Hiperlabirint: Un hiperlabirint intr-un mediu 3D este asemanator cu opusul unui labirint standard 3D, unde blocurile devin spatii deschise si viceversa. Pe cand un labirint standard 3D consta intr-un arbore de pasaje print-o zona deschisa, un hiperlabirint consta intr-un arbore de bare sau vite printr-o zona deschisa. Pentru a creea un hiperlabirint vom incepe cu un solid in partea de sus si cu fete in partea de jos , apoi vom “creste” cu vite incurcate din aceste fete pentru a umple spatiile dintre ele, pentru a face mai grea trecerea unui segment de linie dintre doua fete. Atata timp cat nici o vita nu conecteaza in acelasi atat cu partea de sus cat si cu partea de jos (atunci se va forma o coloana imposibil de tranversat) si atat timp cat nu exista nici un loop in vitele din sectiunile din partea de sus si cea de jos atunci acestea vor fi legate una de alta intr-un lant imposibil de descurcat, iar hiperlabirintul va fi rezolvabil.

Planar: Labirinturile planare cu o topologie neobisnuita sunt in mod general create ca un vector de una sau mai multe labirinturi mici sau sectiuni de la birint, unde este definit modul in care muchiile se leaga unele de altele. Un labirint ce se afla pe suprafata unui cub este format din sase sectiuni patrate de labirint, unde atunci cand partea de labirint ce este creeata in momentul respectiv intalneste o muchie trece in alta sectiune si in cea mai apropiata muchie din dreapta sa.

Template: Labirinturile bazate pe templaturi sunt create pur si simplu prin alegerea unei imagini template de baza, apoi vom sterge izolariile pentru a ne asigura ca labirintul va avea o solutie, urmata de un loop remover pentru a ne asigura ca labirintul este destul de dur astfel rezultand ca intr-un labirint perfect ce este destul de semanantor cu imaginea initiala de la care am pornind. De exemplu, pentru a creea un labirint format din spirale angrenate vom creea niste spirale aleatorii fara a ne ingrijora daca este un labirint da sau nu apoi vom alica peste el izolatiile si loop-urile.

2.4 Algoritmi de creare a labirintului perfect

Sunt o multime de metode de creare a labirinturilor perfecte, fiecare cu caracteristicile sale. Mai jos voi prezenta o serie de algoritmi care creeaza un labirint perfect fie prin spargerea peretilor sau adaugarea lor:

Backtraking recursiv: Atunci cand spargem peretii, o sa fim cat mai “lacomi” cu putinta , si vom sparge intotdeauna intr-o sectiune “neconstruita daca una este langa celula curenta. De fiecare data cand mutam o celula noua vom pune fosta celula in stiva creata . Daca langa pozitia curenta nu exista celule neconstruite vom scoate o celula din stiva astfel trecand la celula anterioara , respective pozitia anterioara. Labirintul este gata atunci cand in stiva nu mai ramane nici o celula. Acest algoritm da un labirint cu un factor “rau” mare, cu putine dar lungi dead endure si de obicei cu o solutie lunga si intortocheata. Generarea merge repede desi algoritmul lui Prim genereaza putin mai repede decat acest algoritm.

Algoritmul lui Prim: Necesita stocarea proportionala a dimensiunii labirintului. In timpul crearii labirintului, fiecare celula va fi una din cele trei tipuri:

“In”: Celula este o parte din labirint si a fost deja taiata.

“Frontiera”: Celula nu face parte din labirint si inca nu a fost taiata, dar este vecina cu o celula de tip “in”.

“Out” : Celula nu face inca parte din labirint si nici unul dintre vecini ei nu sunt “in”.

Vom alege o celula , o vom face “in “ si vom seta toti vecinii ei sa fie de tip “frontiera”. Apoi vom alege aleatoriu o celula “frontiera” si vom taia in ea din celula vecina care este “in”. Vom schimba celulele “frontiera” in celule “in” si vom updata in celule “frontiera” orice vecini ale lor care sunt “out”.Labirintul este terminat atunci cand numai ramane nici o celula stanga de tip “frontiera” ( ceea ce inseamna ca de asemenea numai sunt celule stanga de tip “out” ,astfel toate sunt de tip “in”). Acest algoritm da un labirint cu un factor “river” foarte mic, cu mule dead enduri scurte iar solutia lui este de obicei destul de directa si daca este implementat cum trebuie acest algoritm ruleaza destul de repede.

Algoritmul lui Kruskal: Acest algortim este destul de interesant deoarece nu “genereaza” labirintul ca un copac ci taie aleatoriu segemente de pasaj in tot labirintul stfel totusi in final rezultand un labirint perfect. Este nevoie de o memorie proportionala cu dimensiunea labirintului impreuna cu abilitatea de a enumera aleatoriu fiecare muchie sau perete dintre celulele labirntului ( care in mod usual inseamna crearea unei liste de muchii si pe care o amestecam in mod aleatoriu). Vom pune un label cu un id unic pe fiecare celula, apoi vom loopa aleatoriu peste toate muchiile labirintului. Pentru fiecare muchie, daca celulele din partea opusa au iduri diferite atunci vom sterge peretele si vom seta toate celeule de pe o parte sa aiba acelasi id cu celulele din partea opusa. Daca celulele de pe orice parte a peretului au acelasi id inseamna ca exista deja o cale intre cele doua celule si vom lasa peretele neatens pentru nu a creea un loop. Acest algoritm da labirinturi cu un factor “river” destul de mic , dar nu atat de mic ca cel dat de algoritmul lui Prim.Implementat bine, acest algoritm ruleaza destul de repede, darn u la fel de repede ca celelalte doua algoritnme de mai sus din cauza listei de muchii si a manangementul setarilor.

Algoritmul lui Aldous-Broder: Partea interesanta la acest labirint este ca el genereaza toate labirinturile posibile pornind de la o dimensiune data cu o probabilitate egale. De asemenea acest algoritm nu necesita memorie suplimentara sau o stiva. Alegem un punct si il vom muta catre o celula vecina aleatorie. Daca este introdusa o celula netaiata, vom taia in ea pornind de la celula anterioara. Ne vom misca catre celule vecine pana cand toate celulele vor fi taiate. Acest algoritm reda un labirint cu un factor “river” redus, doar putzin mai mare decat cel dat de algoritmul lui Kruskal.( ceea ce inseamna ce pentru o dimensiune data nu sunt mai multe labirinturi cu un factor “river” redus decat cele cu factor “river” mare). Partea proasta la acest algoritm este ca ruleaza foarte greu, deoarece nu face nici o inteligenta “vanatoare” a ultimilor celule, defapt nu avem nici o garantie ca algoritmul se va termina.

Algoritmul lui Wilson: Este o versiune importanta a algoritmului Adous-Broder si genereaza labrinturi exact ca in algoritmul de mai sus, cu exceptia ca acest algoritm ruleaza mai repede. Necesita memorie pana la dimensiunea labirintului. Vom incepe cu facerea unei celule aleatori parte din labirint. Vom continua cu alegerea unei celule aleatori care nu face parte inca din labirint si vom face o parcurgere aleatorie pana cand vom intalni o celula ce face parte din labirint. Odata ce o parte creata din labirint este atinsa vom merge inapoi la celula aleatorie aleasa si vom taia dealungul caii ce a fost parcursa, aditionand acele celule labirintului. Mai speficic , cand reconstruim calea , la fiecare celula taiata dealungul directiei cea mai recenta parcurgere aleatorie are loc atunci cand paraseste acea celula. Aceasta previne adaugarea loop-urilor dealungul cai reonstituite rezultand un singur pasaj lung ce este anexat labirintului.Labirintul este terminat atunci cand toate celulele au fost anexate lui. Acest algoritm are o performanta similara cu algoritmnul lui Aldous-Broder, unde poate dura un timp mai indelungat pentru gasirea celulei initiale de catre prima cale aleatorie, dar cu toate acestea odata ce cateva cai sunt la locul lor, restul labirintului este taiat rapid. In medie acest algoritm ruleaza de cinci ori mai repede ca algoritmul Aldous- Broder.

Algoritmul lui Eller: Acest algoritm este special nu numai din cauza ca este mai rapid decat celelalte ci este de asemenea algoritmul cu memoria cea mai eficienta. Nu necesita ca intregul labirint sa fie stocat in memorie , memoria este proportionala cu dimensiune unui rand. Crearea labirintului se face rand cu rand , unde odata ce un rand a fost generat, algoritmul nu se mai ocupa de el. Fiecare celula dintr-un rand este continuta intr-un grup , unde doua celule sunt in acelasi set daca exista o cale intre ele ( prin partea de labirint create pana la momentul respectiv). Astfel pasajele vor fi taiate in randul current fara crearea izolariilor si a loop-urilor. Acest algoritm este similar cu algoritmul lui Kruskal , completand rand cu rand pe cand algoritmul lui Kruskal zre privire asupra intregului labirint. Crearea unui rand consta in doua parti: Se conecteaza aleatoriu celulele adiacente dintr-un rand , astfel taiem pasajele orizontale , apoi conectam aleatoriu celulele dintre randul current si cel urmator , unde are loc taierea pasajelor verticale. Atunci cand taiem pasajele orizontale nu vom conecta celulele din acelasi grup fiindca altfel se va creea un loop , iar cand taiem pasajele verticale va trebui sa conectam o celula care face parte dintr-un grup cu dimensiunea unu astfel evitand crearea izolarilor. Crearea labirintului incepe cu fiecare celula ce se afla intr-un grup formate numai din ele insasi inainte de a avea loc conetarea lor in primul rand si se termina dupa ce conectam celulele din ultimul rand. O problema a acestui algoritm este aceea ca nu este ehilibrat in privinta tratarii diferitelor muchii a labirintului , unde celulele conectate versus celulele neconectate trebuie sa fie create in proportii juste pentru prevenirea petelor de textura.

Algoritmul “Growing tree” : Est un algoritm general , capabil de crearea labirinturilor de texturi diferite. Necesita o depozitare in memorie pana la dimensiunea labirintului. De fiecare data cand vom taia o celula vom adauga intr-o lista. Vom continua prin alegerea unei celule din lista si taierea intr-o celula vecina ei necreata. Daca nu exista celule necreate vecine celulei curente, o vom sterge din lista. Labirintul este terminat atunci cand lista este goala. Partea cea mai interesanta a acestui algoritm este permiterea alegerii a cator mai multe texturi posibile ce este determinate de modul alegerii celulei din lista. De exemplu, daca vom alege intotdeauna cea mai recenta celula adaugata acest algoritm se transforma in backtracking recursiv. Daca intotdeauna alegem celulele in mod aleatoriu atunci acest algoritm se va comporta similar cu algoritmul lui Prim. Daca vom alege intotdeauna cea mai veche celula adaugata in lista, aceasta va crea labirinturi cu un factor “river” foarte mic, mai mic chiar decat cel dat de algoritmul lui Prim. Daca in mod uzual vom alege celula cea mai recenta , dar ocazional vom alege o celula random , labirintul creat va avea un factor “river” mare dar va avea o slutie scurta si directa. Daca alegem aleatoriu o celula dintre celulele cele mai recente labirintul creat va avea un factor “river” mic cu o solutie lunga.

Algoritmul “hunt and kill”: Acest algoritm nu necesita o depozitare extra in memorie si astfel este potrivit pentru creearea de labirinturi mari sau labirinturi in sisteme limitate, cu memorie putina. Deoarece nu exista reguli care trebuie urmate tot timpul , este deasemenea usor de modificat si de a creea labirinturi de diferite texturi. Se aseamana cel mai mult cu backtrakingul recursiv , cu exceptia ca atunci cand o celula necreata ce este vecina cu celula din pozitia curenta , se intra in modul “hunting” si se scaneaza sistematic labirintul pana cand gasim o celula necreata vecina cu o celula deja taiata si se va incepe din nou taierea la locatia noua gasita. Labirintul se termina cand toate celulele au fost canate odata in modul “hunt”. Acest algoritm tinde sa genereze labirinturi cu un factor “river” mare , dar nu asa de mare ca cel dat de backtrakingul recursiv. Se poate genera labirinturi cu un factor “river” mic daca alegem sa intram in modul “hunt” mai des. Acest algoritm ruleaza mai incet datorita timpului petrecut pentru a “vana” ultimele celule dar nu este mai incet decat algoritmul lui Kruskal.

Algoritm binary tree:Acesta este cel mai simplu si mai rapid algoritm posibil , dar cu toate acestea labirinturile produse de acest labirint au o textura foarte influentabila. Pentru fiecare celula taiem un pasaj care fie conduce sus sau conduce stanga , dar nu in ambele. In versiunea de adaugare de pereti , pentru fiecare vertex vom adauga un segment de perete ce conduce fie spre jos fie spre dreapta, dar niciodata in ambele sensuri. fiecare celula este independenta de celelate si nu trebuie sa ne referim la statutul oricarui alte celule atunci cand o cream. Intr-adevar este un algoritm generator de labirinturi fara necesitatea unei memorii si nu are limita la dimensiunea labirintului pe care il putem crea. Este in mod fundamental un arbore binar , daca consideram ca radacina coltul stanga de sus, de unde labirintul este mult mai usor de navigat de la dreapta jos catre stanga sus. Vom putea intotdeauna sa parcurgem in sus sau la stanga dar niciodata in ambele sensuri , asa ca vom putea intotdeauna parcurge , in mod determinant , in diagonala sus si la stanga fara a atinge nici o bariera. Vom parcurge in jos si la dreapta atunci cand vom intalni alegeri si dead end-uri.

Algoritm sidewinder: Acest algoritm simplu e foarte asemanator cu algoritmul binary tree si e doar putin mai complicat. Acest algoritm genereaza rand cu rand: Pentru fiecare celula aleatoare se decide daca se taie un pasaj ce conduce spre dreapta. Daca pasajul nu este taiat , atunci se considera pasajul orizontal complet, format de celula curenta si oricare alte celule din partea stanga care au taiat pasaje ce conduc catre el. Vom alege in mod aleatoriu una dintre celule de-a lungul acestui pasaj si taiem un pasaj ce conduce in susul lui. Pecand un labirint binary tree intotdeauna merge in sus din cea mai de stanga celula a unui pasaj orizontal, un labirint sidewinder are doar o muchie in partea de sus si un lung pasaj. Ca si un labirint binary tree, un labirint siderwinder poate fi rezolvat in mod determinat fara erori de jos in sus , deoarece, la fiecare rand, va fi intotdeauna un pasaj ce conduce in sus. O solutie a unui labirint sidewinder niciodata nu va vizita un rand de doua ori. Singurul tip de celula care nu poate exista intr-un labirint sidewinder este o celula de tip dead end cu pasajul ce merge in jos , deoarece aceasta va contrazice faptul ca fiecare pasaj merge in sus si conduce inapoi catre inceput. Un labirint sidewinder tinde sa aiba o solutie elitista, unde pasajul drept este foarte direct dar sunt multe pasaje lungi si false ce conduc in jos din partea de sus alaturata lui.

Acest tabel rezuma caracteristicile algoritmilor de creare a labirintul perfect ce au fost prezentati mai sus. Labirintul unicursal ( un labirint unicursal este perfect din punct de vedere tehnic) a fost introdus pentru comparare.

Dead End: Aproximeaza procentul celulelor care sunt dead enduri in labirintul creat de algoritmul respectiv.

Tip: Se refera la modul de construire a labirintului.

Focus: Se refera la modul de implementare a labirintului care poate fi de doua feluri: taiere(spargere) pereti sau adaugare de pereti.

Fara inclinare: Aceasta este daca algoritmul trateaza toate directiile si partile labirintului, unde in urma analizei finale a labirintului nu este dezvaluit nici o inclinare.

Memory Free: Arata daca este necesara existenta unei memorii suplimentare sau a unei stive atunci cand implementam algoritmul.

Timp: Reda o idee cam de cat timp ar fi necesar pentru a creea un labirint folosind algoritmul respectiv.

Solutie: Reda procentul celulelor labirintului prin care solutia trece, pentru un labirint tipic generat de algoritmul respectiv.

2.5 Algoritmi de rezolvare a labirintului

Exista mai multe moduri in care putem rezolva un labirint. In cele ce urmeaza vom prezenta cateva metode de rezolvare reprezentate de algoritmi urmatori:

Dead end filler: Este un algoritm simplu de rezolvare a unui labirint. Este focalizat pe labirint, este intotdeauna rapid si nu foloseste memorie extra. Se scaneaza labirintul, se umple fiecare dead end si umplem pasajul pana cand ajungem la o jonctiune. La sfarsit doar solutia va ramane , sau solutiile daca sunt mai mult de una. Acest algoritm va gasi o unica solutie pentru labirinturile perfecte dar nu va face nimic util pentru labirinturile care nu au dead enduri.

Wall follower: Acest algoritm este inca un alt simplu algoritm de rezolvare a labirinturilor. Se focalizeaza pe obicectul (persoana) ce parcurge labirintul , este intotdeauna foarte rapid si nu foloseste memorie extra. Incepe cu urmarirea pasajelor si de fiecare data cand ajungem la o junctiune intotdeauna facem dreapta( sau stanga). aceasta metoda nu va da in mod necesar cea mai scurta solutie si nu merge atunci cand iesirea(scopul) este plasat in mijlocul labirintului. Acest algoritm poate fi facut intr-un mod determinist intr-un labirint 3D prin proiectarea pasajelor 3D in planul 2D.

Cul-de-sac filler: Aceasta metoda gaseste si umple in cul-de-sacs sau laturi, adica construieste intr-un labirint constand intr-o alee “oarba” trunchi care are un singur loop la capat. Ca si algoritmul dead end filler se focalizeaza pe labirint, este intotdeauna rapid si nu utilizeaza memorie extra. Se scaneaza labirintul, si pentru fiecare jonctiune lat ( o jonctiune lat fiind una unde doua dintre pasajele conduse din el se conecteaza unul cu altul fara alte jonctiuni dealungul lor) se adauga un perete pentru a converti un intreg lat intr-un lung dead end. Dupa aceea se ruleaza algoritmul dead end filler.

Blind alley filler: Aceasta metoda gaseste toate solutiile posibile , indiferent de lungimea lor. Face acest lucru prin umplerea aleielor “oarbe” , unde o aleie “oarba” este un pasaj in care daca mergi in josul lui intr-o singura directie, va trebuia sa mergi backtrack prin pasajul respectiv in directia cealalta pentru a atinge scopul. toate dead endurile sunt alei “oarbe” si toate laturile descrise in cul-de-sac filler sunt deasemenea , impreuna cu orice sectiune de pasaje dimensionata si conectata de restul labirintului printr-un singur trunchi. Acest algoritm se focalizeaza pe labirint, nu foloseste memorie extra dar din nefericire este foarte lent. Pentru fiecare jonctiune, trimite un perete urmarind un robot in jos pe fiecare pasaj de la el si vede daca robotul trimis in josul unei cai vine inapoi pe aceasi cale. Daca se intoarce atunci pasajul si tot ce este in josul lui nu poate fi pe nici o cale care este solutie asa ca va sigila acel pasaj si il va umple totul din spatiul sigilat.

Blind alley sealer: Este asemanator cu algoritmul blind alley filler, astfel ca si acest algoritm gaseste toate solutiile posibile prin inlaturarea aleielor “oarbe” din labirint. Oricum acest algoritm umple pasajul trunchi a fiecarei aleie “oarbe” si nu atinge nici o colectie de pasaje la capatul lui. Astfel se va crea sectiuni de pasaje inacesibile pentru cul-de-sacs sau orice alta aleie “oarba” mai complicata decat un dead end. Acest algoritm este focalizat pe labirint , ruleaza mult mai rapid decat algoritmul blind alley filler desi are nevoie de memorie extra. Se va asigna fiecare sectiune de pereti conectata unui grup unic. Pentru a realiza acest lucru vom face pasii urmatori: pentru fiecare sectiune de pereti ce nu se afla deja intr-un grup vom “inunda” dealungul partii de sus a peretiilor in punctul respectiv, si vom asigna toti peretii accesibili unui grup nou. Dupa ce toti peretii se afla in grupuri, pentru fiecare sectiune de pasaj vom verifica daca peretii de pe fiecare parte a lui se afla in acelasi grup si apoi vom sigila pasajul respectiv.

Algoritmul Pledge: Acest algoritm este o versiune modificata a algoritmului wall follower care poate sa sara intre insule, sa rezolve labirinturile pe care algoritmul wall follower nu poate sa le rezolve. E o modalitate garantata de a ajunge la o iesire pe muchia exterioara a oricarui labirint 2D din orice punct din mjloc (de retinut ca reciproc nu e valabil). Vom incepe prin alegerea unei directii si intotdeauna ne vom misca in acea directie cand este posibil. Cand un perete este atins vom incepe sa urmarim peretii pana cand va fi disponibila directia aleasa.

Algoritm lant(chain): Algoritmul lant rezolva labirinturile prin tratarea lui efectiva ca un numar de labirinturi mici legate intre ele ca intr-un lant si rezolvandu-le in secvente. Va trebui sa specificam punctul de start si iesirea dorita si algoritmul va gasi intotdeauna o cale catre punctul de start si iesire(daca exista una) unde solutia tinde sa fie una din cele mai scurte solutii ale labirintului daca nu este chiar cea mai scurta solutie a lui. De aici rezulta ca acest algoritm nu poate rezolva labirinturi a carui iesire nu se cunoaste. algoritmul este asemanator cu algoritmul Pledge deoarece in esenta este un urmaritor de pereti cu un mijloc de sarire intre insule. Vom incepe prin desenarea unei lini drepte (sau cel putin a unei linii care nu se repliaza asupra sa) de la punctul de start pana la iesire, lasand sa tranverseze peretii daca este nevoie, iar apoi doar urmarim linia trasata. Daca lovim un perete, va trebui sa il ocolim astfel ca vom trimite doi “roboti” ce vor urmari peretele in ambele directii dealungul lui. Daca roboti se lovesc din nou de linia indrumatoare si aceasta se afla intr-un punct care este aproape de iesire ne vom opri si vom urmari peretele respectiv pana cand vom ajunge acolo. Vom repeta procedeul pana cand vom ajunge la iesire. Daca ambii roboti se intorc la locatia lor originala atunci rezulta ca labirintul nu are solutie.

Backtraking recursiv: Acest algoritm va gasi o solutie, dar aceasta solutie nu va fi in mod necesar cea mai scurta solutie. Este focalizat pe implementator, este rapid pentru orice tip de labirint si foloseste stive ce pot avea dimensiunea mai mica sau egala cu cea a labirintului. Acest algoritm este destul de simplu: Daca suntem cumva la un perete( sau la o arie care deja a fost schitata) vom intoarce insucces, altfel daca ne vom afla la sfarsit vom intoarce succes, altfel vom incerca in mod recursiv sa ne miscam in cele patru directii. Vom schita o linie atunci cand incercam o noua directie si vom sterge una atunci cand se va intoarce un insucces si o singura solutie va fi marcata atunci cand se obtine succes. Atunci cand facem backtrecking este bine sa marcam spatiul vizitat cu o valoare speciala astfel incat sa nu vizitam din nou acelasi spatiu atunci cand venim dintr-o alta directie. Acest algoritm este denumit in termeni informatici ca DFS( deep first search). Aceasta metoda va gasi intotdeauna o solutie daca aceasta exista dar nu va fi in mod necesar cea mai scurta solutie.

Algoritmul lui Tremaux: Acest algoritm de rezolvare a labirinturilor este conceput pentru a putea fi utilizat de o fiinta umana ce se afla intr-un labirint( putem implementa obiecte cu inteligenta artificiala). Este asemanator cu algoritmul backtracking recursiv si va gasi o solutie pentru toate labirinturile. Pe masura ce inaintam intr-un pasaj, vom desena o linie ce va marca drumul parcurs. Cand vom intalni un dead end ne vom intoarce inapoi pe calea pe care am venit. Cand vom intalni o jonctiune pe care nu am vizitat-o inainte o vom trata ca pe un dead end si ne vom intoarce inapoi pe drumul pe care am venit.( acest pas este cheia ce ne previne sa mergem in cercuri sau sa pierdem pasaje in labirinturi braid). Daca inaintam intr-un pasaj pe care l-am vizitat inainte si intalnim o joctiune vom lua orice nou pasaj disponibil( daca acesta exista) a;tfel vom lua un pasaj vechi( adica unul pe care l-am marcat deja). Cand vom atinge in final iesirea , calea marcata exact odata va indica solutia. Daca labirintul nu are soluite ne vom afla la punctul de start unde toate pasajele vor fi marcate de doua ori.

Algoritmul collison solver: Mai este si numit algoritmul “amiba” solver , aceasta metoda gaseste toate solutiile scurte. Este focalizat pe implementator, este rapid pentru toate tipurile de labirinturi si necesita cel putin o copie a labirintului in memorie in aditia memoriei utilizate ce poate ajunge pana la dimensiunea labirintului. In mod fundamental inunda labirintul cu “apa” astfel ca toate distantele de la punctul de start sunt umplute in acelasi timp(este un breadth first search in termeni informartici ) si defiecare data cand doua “coloane de apa” abordeaza un pasaj din ambele capete( indica un loop) se va adauga un perete la labirintul original acolo unde se vor ciocni. Odata ce toate partile labirintului au fost “inundate” se va umple toate noile dead enduri csre nu pot fi pe cea mai scurta cale si se repeta procesul pana cand nu vor mai avea loc coliziuni.

Algoritmul “shortest path finder” : Asa cum numele indica, acest algoritm gaseste calea cea mai scurta, alegand una dintre ele daca exista mai multe solutii scurte. este focalizat pe implementator de multiple ori , este rapid pentru toate tipurile de labirinturi si necesita putina memorie extra proportionala cu dimensiunea labirintului. Ca si algoritmul collision solver , acesta inunda in mod fundamental labirintul cu “apa” astfel incat toate distantele de la punctul de start sa fie umplute in acelasi timp, dar fiecare “picatura” sau pixel tine minte care pixel a fost umplut de el. Odata ce solutia este atinsa de o “picatura” vom urmari inapoi drumul parcurs de la el pana la punctul de start si aceasta va fi calea cea mai scurta. Acest algoritm functioneaza bine indiferent de datele de intrare.

Algoritmul “shortest paths finder”: Este foarte similar cu algoritmul “shortest path finder” de mai sus cu exceptia ca acest algoritm gaseste toate solutiile scurte ale labirntului. Este focalizat pe implementator de multiple ori, este rapid pentru toate tipurile de labirint, necesita memorie extra proportionala cu dimensiunea labirintului si functioneaza bine pentru orice date de intrare dearece nu necesita ca labirintul sa aiba un pasaje largi de un pixel pe care trebuie sa le urmarim. Ca si algoritmul “shortest path finder” face a breadth first search, inundand labirintul cu “apa” astfel incat toate distantele de la punctul de start sunt umplute in acelasi timp cu exceptia ca fiecare pixel isi aminteste cat de departe se afla de punctul de start. Odata ce iesirea este atinsa , vom face o alta breadth first search pornind de la iesire, deasemenea doar pemitand sa fie inclusi acelor pixeli care se alfla la o distanta de o unitate fata de pixelul curent. Pixeli inclusi vor marca precis toate solutiile scurte.

Algoritmul “random mouse”: Pentru contrast vom prezenta o metosa ineficienta de rezolvare a labirintului care se bazeaza pe miscarea aleatorie, adica ne miscam intr-o directie si vom urmari acel pasaj prin orice intoarcere pana cand vom atinge jonctiunea urmatoare. Nu vom face intoarceri de 180 de grade decat daca este necesar. Acest algoritm simuleaza miscarea aleatorie a unui obiect fara nici o memorie despre locurile strabatute in labirint. Este incet si nu garanteaza terminarea lui sau rezolvarea labirintului si odata ce iesirea este atinsa va fi foarte greu de reurmarit pasi parcursi dar este simplu si nu necesita nici o memorie extra pentru implementare.

Acest tabel rezuma cateva caracteristici ale algoritmilor de rezolvare a labirintului de mai sus.

Solutie: Descrie numarul de solutii pe care algoritmul le gaseste

Garantat?: Arata daca algoritmul garanteaza sa gaseasca cel putin o solutie in labirint.

Focus: In mod general exista doua tipuri de rezolvare a algoritmilor: focalizati pe implementator sau pe labirint. intr-o focalizare implementator avem fie un singur punct(obiect, persoana etc) sau un set de puncte( grup de obiecte, grup de persoane etc) pe care le incercam sa le miscam prin labirint de la punctul de start pana la iesire. In focalizarea labirint privim labirintul ca pe un intreg si invalidam pasaje inutile.

Fara pasaj?: Spune daca un algoritm poate fi facut oriunde, cateva algoritme necesita ca labirintul sa aiba pasaje evidente sau muchii distincte intre noduri distincte( in termeni de grafuri) sau un pasaj larg de un pixel cand este implementat intr-un calculator.

Fara memorie?: Arata daca algoritmul are nevoie de memorie suplimentara sau de stiva atunci cand trebuie sa fie implementat.

Rapid?: Arata daca porcesul de rezolvare dat de algoritm este considerat rapid.

2.6 Aplicatii generatoare de labirinturi

1.Daedalus

Este o aplicatie windows, programata in C++, ce permite crearea, rezolvarea, analizarea, parcurgerea labirinturilor.

[22]

2.Maze Maker

Este un applet Java ce creaza labirinturi aleatori si permite utilizatorului sa rezolve el insusi; nu genereaza solutia.Permite vizualizarea labirintului in 3D si parcurgerea lui de la tastatura.

[23]

3.Custom Maze Generator

Genereaza labirinturi custom, in functie de dimensiune si dificultate. Nu prezinta solutia labirintului.

3.Prezentarea solutiei propuse

3.1 Prezentare generala

Pentru acest proiect am ales ca mediu de simulare Visual Studio 2005 si ca limbaj de programare C#.

Solutia este reprezentata de un labirint 2D , perfect , non hiperdeimensional, ortogonal in care simulam deplasarea unei entitati( bila, soricel).

Labirintul este generat aleatoriu, utilizatorul poate stabili dimensiuniile labirintului si a celulei, solutia este gasita prin algoritmul backtracking recursiv (DFS).

Inafara de generare si rezolvare a labirintului am implementat si deplasare in labirint exemplificat prin parcurgerea solutiei gasite si printr-un joculet in care utilizatorul va trebui sa conduca soricelul prin labirint astfel incat el sa manace toata branza in timpul impus.

Deplasarea in labirint este fie automata ( implementarea comportamentului prin animatie in frame) fie se va face cu ajutorul tastaturii,in cazul deplasarii joricelului in labirint, prin apasarea tastelor sageti.

3.2 Prezentarea Labirintului

3.2.1 Prezentarea algoritmului de generare

Pentru ca labirintul nostru este renctangular vom avea nevoie de o retea de felul urmator:

[2]

Fiecare dreptunghi din retea reprezinta o celula , iar liniile orinzontale si verticale reprezinta peretii labirintului. Vom presupune ca, la inceput, toti peretii vor fi “sus”. Apoi vom sparge pereti in mod selectiv pana cand vom obtine labirintul nostru perfect.

Pasii algoritmului de generare:

Alegem orice celula aleatoare din reteaua construita( in cazul aplicatiei noastre in coltul dreapta sus)

Gasim o celula vecina aleatoare care nu a fost vizitata inca.

Daca gasim o celula de acest tip, vom demonta peretele dintre celula curenta si celula vecina

Daca nu gasim nici o celula de acest tip ne intoarcem la celula precedenta

Repetam pasii 2 si 3( sau 2 si 4) pentru fiecare celula din retea.

Scrierea algoritmului in pseudocod:

Atunci cand loop-ul while se termina algoritmul este complet. Fiecare celula a fost vizitata si astfel nici o celula nu este inacesibila. De asemenea , fiindca am testat fiecare posibila miscare pentru a vedea daca am vizitat deja celula, acest algoritm previne crearea de arii deschise sau loop-uri.

3.2.2 Determinarea Solutiei

Algoritmul de determinare a solutiei functioneaza prin repetarea unui loop prin labirint, blocand toate dead endurile intalnite.

Fiecare iteratie a loop-ului ne aduce aproape de terminarea parcurgerii labirintului pana cand in final nu mai gasim dead enduri si va ramane doar solutia labirintului.

Determinarea acestei solutii este ca si cum am ansambla un puzzle jigsaw.

3.2.3 Deplasarea in labirint

Simularea acestui model comportamental este realizata cu ajutorul claselor specifice animatiei in frame a limbajului C# si cu ajutorul butoanelor sageti de la tastatura

4.Prezentarea aplicatiei

4.1 Implementarea aplicatiei

Aplicatia este implementata in limbajul C# si ruleaza in mediul dat de Visual Studio 2005 si contine 10 clase, dintre care trei sunt ferestre.

Voi imparti aplicatia in trei sectiuni : Generare labirint , Determinarea solutiei si Deplasare in labirint.

4.1.1 Generare labirint

Generarea labirintului se face prin implementarea algoritmului prezentat mai sus.

Clasele folosite pentru generarea labirintului sunt :Cell.cs;Maze.cs, DimensionDialog.cs si frmMaze.cs, care este fereastra pricipala; interfata care interactioneaza cu utilizatorul.

Labirintul este format din celule; o celula este implementata in clasa Cell.cs iar definiresi construirea labirintului are loc in clasa Maze.cs.

Initial labirintul este o retea de celule dispuse in mod rectangula ;reteaua de celule este reprezentata prin definirea unei matrici de nxn de celule in clasa Maze.cs.

Dupa cum putem observa din desenul UML, clasa Maze genereaza labiritnul si contine o colectie de celulle din Cells pentru ca lagoritmul sa poata rula. fiecare celula contine un vector de patru pereti care pot fi “sparti” prin setarea a unui element din vector cu 0. Codul de implementare a DFS( deep first search) este prezentat mai jos. Incrementeaza numarul total al celulelor vizitate intr-un ciclu while si se termina atunci cand celulele vizitate (VisitedCells) este egal cu numarul nxn al celulelor dispuse in retea( cu dimensiunea matrici construite de celule). Asa cum este specificat in algoritm , prima data se va lua o lista cu celulele vecine care au cei patru pereti intacti si alegem aleatoriu una dintre ele ( daca exista celule vecine cu aceste proprietati). Celula curenta este adaugata in stiva si celula alesa in mod aleatoriu devine noua celula curenta. Daca nu exista nici o celula adiacenta vecina cu cei patru pereti intacti, celula precedenta este scoasa din stiva si facuta noua celua curenta.

Codul implemetat prin care realizeaza generarea :

public void Generate()

{

while (VisitedCells < TotalCells)

{

// ia o lista de celule vecine cu peretii intacti

ArrayList AdjacentCells = GetNeighborsWithWalls(CurrentCell);

// testeaza dc o celula de genul asta exista

if (AdjacentCells.Count > 0)

{

// da,alege una,sterge peretele dintre ea si cea curenta

int randomCell = Cell.TheRandom.Next(0, AdjacentCells.Count);

Cell theCell = ((Cell)AdjacentCells[randomCell]);

CurrentCell.KnockDownWall(theCell);

CellStack.Push(CurrentCell); // punem celula curenta in stiva

CurrentCell = theCell; //facem celula vecina pe cea curenta

VisitedCells++;

}

else

{

CurrentCell = (Cell)CellStack.Pop();

}

}

// arata iesirea si iese

Cells[0][0].Walls[0] = 0;

Cells[kDimension-1][kDimension-1].Walls[3] = 0;

}

4.1.2 Determinarea Solutiei

Clasele care participa la determinarea solutiei sunt acelasi ca si cele de la Generarea Labirintului cu exceptia clasei DimensionDialog, care seteaza dimesiuniile celulei si nr de celule atunci cand generam labirintul.

Pentru rapiditatea algoritmului de gasire a solutiei vom folosi mai multe threaduri care lucreaza in paralel.Putem folosi cate threaduri dorim.

In aplicatie folosim doua threaduri pentru determinarea solutiei.

Clasa ce creeaza threaduri si le controleaza in C# este clasa System.Threading.Thread . Clasa Thread are o varietate de metode dintre care cateva mai interesante:

Start(): porneste executia unui thread

Suspend(): suspenda threadul, iar daca threadul este deja suspendat , nimic nu se va intampla

Resume(): rezuma un thread care a fost supendat

Interrupt(): intrerupe un thread care este in modeul de asteptare, in modul sleep sau modul join

Join(): blocheaza un thread ce este chemat pana cand threadul curent este terminat de executat

Sleep( int x): suspenda threadul pentru o perioada determinata de timp (in milisecunde)

Abort(): Termina threadul chiar daca este in proces de executie. Odata ce threadul este terminat prin aceasta procedura el numai oate fi restartat prin reapelarea functiei Start().

Executia threadului incepe odata ce utilizatorul acceseaza din meniul File, submeniul Rezolva:

Thread aThread = new Thread(new ThreadStart(TheMaze.SolveA));

aThread.Start();

In obiectul labirint avem doua metode diferite de rezolvare a labirintului : SolveA si SolveB ,astfel incat sa putem asigna cele 16 culori diferite celor doua threaduri folosite.

Prima metoda este SolveA.aceasta metoda apleleaza metoda SolveIt care loopeaza in mod repetat in labirint, blocand dead endurile cu WALLA( care este definita printr-o culoare albastra). Atunci cand parcurgerea este completa se va lansa evenimentul MazeSolutionComplete.

public void SolveA()

{

SolveIt( Cell.CellState.WALLA );

MazeSolutionComplete( this, EventArgs.Empty );

}

Metoda SolveB este similara, numai ca al doilea thread incepe din partea de jos al labirintului (de la iesire) catre partea de sus( punctul de start).Metoda ce implementeaza parcurgerea inversa a labirintului este SolveItBackward.

public void SolveB()

{

SolveItBackward( Cell.CellState.WALLB );

MazeSolutionComplete( this, EventArgs.Empty );

}

4.1.3 Deplasare in labirint

Deplasarea in labirint este reprezitanta prin animatie in frame , obiectul se deplaseaza dealungul solutiei gasite( implementarea se face in frmMaze.cs) sau prin tastele sageti de tastatura , utilizatorul deplaseaza obiectul in labirint cu ajutorul tastaturii( implementarea se face in Form1.cs si Soricel.cs) .

Clasele ce participa la deplasarea in labirint sunt : Cell.cs , Maze.cs, Form1.cs ,TimerDisplay.cs ,Cheese.cs, Soricel.cs , Scor.cs si binenteles frmMaze.cs.

Interfata grafica reprezentata de Form1 are o relatie de agrerare 1 la 1 cu celelalte clase , dupa cum se poate observa in diagrama umele de mai sus.

Diagrama Uml realizata cu SmartDraw2007

Diagrama de secventa

Diagrama de secventa realizata cu WithClass2000 UML Tool

EaterCell reprezinta celula in care se afla eaterul, adica soricelul in cazul aplicatiei noastre iat TheEater reprezintaobiectul soricel ce este implementat in clasa Soricel.cs.

In diagrama de mai sus arata ca dupa ce este apasata tasta sageata stanga( left arrow key) , programul ia celula in care soricelul este localizat in labirint. Apoi il utilizeaza in intersectia a peretelui stang a celulei dreptunghiulare si a marginii soricelului( care reprezinta un obiect bitmap asezat intr-un dreptunghi) pentru a determina daca soricelul poate sa se miste catre perete. Daca soricelul nu intersecteaza peretele atunci el poate contiunua miscarea sa catre stanga.

Codul implementat in vederea daca un eather ( soricel) se poate misca in celula se afla in clasa Form1.cs si este:

private bool CanSoricelMove(Side aSide)

{

int theSide = (int)aSide;

Cell SoricelCell = TheMaze1.GetCellFromPoint(Soricel.Position.X + 10, Soricel.Position.Y + 10);

if (SoricelCell.Walls[theSide] == 1)

{

if (SoricelCell.GetWallRect((int)aSide).IntersectsWith(Soricel.GetFrame()))

{

return false; // blocat

}

}

return true; // nu e blocat

}

string LatestKey = "none";

4.2 Explicarea codului implementat

Dupa cum am specificat mai sus aplicatia are 10 clase , dintre care trei frame-uri implementate in limbajul C# in mediul Visual Studio 2005.

Clasele se afla intr-un proiect C# numit MazeSolution.

4.2.1 Clasa frmMaze

Clasa frmMaze implementeaza fereastra principala, aici gasinduse metoda main. frmMaze implementeaza toate legaturile cu celelate clase si ferestre pentru a prezenta solutia generala a proiectului.

Variabile:

grafice: components de tip IContainer ; button1 de tip Button ; mainMenu1 de tip MainMenu ; menuItem1 , PreviewMenu , DimensionsMenu , ResetMenu , Solve ,SolveSingleThread ,mnuExit de tip MenuItem ; statusBar de tip StatusBar

nongrafice: TheMaze de tip Maze , o matrice de celule labirint ; variabile integer i , j , x , y , threads , threadCount ; variabile Thread t , athread , bthread , cthread.

Constructorul:

public frmMaze()

{

//

//Windows Form Designer support

//

InitializeComponent();

SetStyle(ControlStyles.AllPaintingInWmPaint, true);

SetStyle(ControlStyles.UserPaint, true);

SetStyle(ControlStyles.DoubleBuffer, true);

this.Cursor = Cursors.WaitCursor;

TheMaze = new Maze();

TheMaze.addObserver(this);

TheMaze.Generate();

TheMaze.MazeSolutionComplete += new Maze.MazeEventHandler(MazeComplete);

this.Cursor = Cursors.Default;

SetBounds(this.Left, this.Top, (Maze.kDimension + 8) * Cell.kCellSize + Cell.PADDING, (Maze.kDimension + 12) * Cell.kCellSize + Cell.PADDING + statusBar.Height);

System.Console.WriteLine();

}

Metode:

protected override void Dispose(bool disposing): sterge orice resursa a fost utilizata

private void InitializeComponent():crearea ferestrei si integrarea elementelor grafice in fereastra

static void Main(): metoda principala in care specificam rularea ferestrei

private void frmMaze_Paint(object sender, System.Windows.Forms.PaintEventArgs e): metoda grafica ce deseneaza labirintul

private void button1_onclick(object sender, EventArgs e): metoda ce implementeaza un eveniment click; atunci cand apasam button1 se va afisa fereastra Form1

private void mnuExit_Click(object sender, System.EventArgs e): metoda ce implementeaza un eveniment click si care inchide fereastra principala odata cu selectarea submeniul Iesire din fereastra

private void DimensionsMenu_Click(object sender, System.EventArgs e): metoda ce implementeaza un eveniment click si care genreaza un labirint cu parametri introdusi de utilizator in fereastra afisata odata cu selectarea submeniului Generare Labirint din fereastra principala

private void ResetMenu_Click(object sender, System.EventArgs e): metoda ce implementeaza un eveniment click si reseteaza labirintul odata cu selectarea submeniului Reseteaza Labirint din fereastra principala

private void SolveSingleThread1_Click(object sender, System.EventArgs e): metoda ce implementeaza un eveniment click si rezolva labirintul cu un singur thread

private void Solve_Click(object sender, System.EventArgs e): metoda ce implementeaza un eveniment click si afiseaza solutia labirintului odata cu accesarea submeniului Rezolva din fereastra principala. Mai intai vom initializa variabilele necesare apoi vom rula codul pentru un sigur thread si dupa accea vom adauga inca un thread.

private void SolveSingleThread_Click(object sender, System.EventArgs e): rezolva labirintul cu un singur thread si porneste un thread ce simuleaza deplasarea in labirint pe solutia gasita a unui obiect

private void MazeComplete(object sender, EventArgs e):recheama threadurile si afiseaza rezultatele obtinute

protected override void OnClosed(EventArgs e):inchide threadurile athred si t

public void Run(): metoda ce realizeaza animatia in fereastra principala folsind un thread

private Cell getNextCell(int iCurent, int jCurent):metoda ce determina celula urmatoare in perspectiva deplasarii in labirint si a realizarii animatiei in fereastra

4.2.2 Clasa Cell

Clasa Cell.cs implementeaza o celula si comportamentul ei in labirint.

Variabilele: Pentru desenarea celulei si pentru determinarea solutie definim enumerarea cellState ; dimensiunea celulei este data de variabila kCellSize ; definim un vector Walls ce reprezinta peretii unei celule (N,S,E,V) si iau valoarea 1; o valoare aleatorie TheRandom folosita la alegerea unei celule aleatorii; doua vaolri intregi row si collumn folosite ca atribute a unei celule; o variabila long Seed=DateTime.Now.Ticks care este folosita la crearea unei celule ; o variabila boolean vizitat care determina daca o celula este sau nu vizitata.

Metode:

public bool HasAllWalls():determina daca o celula are peretii intacti si intoarce true daca celula are toti pereti intacti si false daca celula are unul sau mai multi pereti “sparti”

public void KnockDownWall(int theWall): sparge peretele unei celule prin atribuirea valorii 0 elementului vectorului Walls corespunzator peretelui

public void KnockDownWall(Cell theCell): sparge peretii unei celule;gaseste peretele adiacent si il sparge ca apoi sa il sparga si pe opusul lui

public int FindAdjacentWall(Cell theCell): gaseste peretele adiacent a unei celule prin parcuregerea celulei pe rand sau pe coloana; returneaza o valoare intreaga

public int GetRandomWall():intoarce valoarea unui perete aleatoriu din labirint

public Point CellCenter():intoarce centrul unei celule

public Rectangle CellBounds(): determina granitile unei celule; intoarce un dreptunghi

public Rectangle GetWallRect(int side):intoarce peretele dreptunghiului determinat de granitiile unei celule ,in functie de partea in care se afla el

public void Draw(Graphics g): deseneaza celulele , umplecelulele care nu sunt libere in functie de tipul de perete(WallA, WallB etc)

4.2.3 Clasa Maze

Variabile: Definim o matrice de celule Cells; definim o stiva ce stocheaza celulele parcurse CellStack ; definim o celula curenta CurrentCell care va fi de tip Cell ; definim dimensiunea labirintului kDimension ; definim o variabila int VisitedCells pe care o intializam cu 1; numarul celulelor din labirint este dat de variabila TotalCells ; definim un obiect observer de tip frmMaze si un eveniment de tip MazeEventHandler MazeSolutioncomplete.

Constructorul:

public Maze()

{

// Windows Form Designer support

Initialize();

}

Metode:

public Point GetCellCenter(int cellNumberX, int cellNumberY):returneaza centrul celulelor din labirint

public Cell GetCellFromPoint(int x, int y): intoarce o celula dintr-un punct dat

public void addObserver(frmMaze obs): adauga un obiect de tip frmMaze

public Cell[][] getLabirint(): intoarce labirintul

private ArrayList GetNeighborsWithWalls(Cell aCell): intoarce o lista cu vecinii unei celule, care au peretii intacti.

public void Initialize(): creaza un labirint initial in care nici o celula nu este vizitata iar stiva va fi nula

public void Generate(): genereaza un labirint. Atata timp cat numarul celulelor viztate sunt mai mici decat numarul total de ceule din labirint vom lua o lista cu celulele vecine care au peretii intacti; vom verifica daca exista o celula de acest gen; daca exista vom sterge peretele dintre ea si celula curenta; o vom adauga in stiva si facem celula vecina sa fie celula curenta; daca nu exista nici o celula de acest gen vom scoate din stiva celula precedenta.

public void SolveIt( Cell.CellState cellState ): implementeaza algoritmul de determinare a solutiei; face loop in labirint blocand la fiecare pas dead endurile pana cand valoarea booleana declarata in metoda steadyState va avea faloarea true.

public void SolveItBackward(Cell.CellState cellState): asemanatoare cu metoda SoveIt numai ca loop-eaza inapoi in labirint blocand dead endurile.

public void SolveA(): rezolva labirintul si lanseaza un evenimentul MazeSolutioncomplete

public void SolveB(): rezolva labirintul “inapoi” si declanseaza evenimentul MazeSolutionComplete

private bool IsFree( int x, int y ):determina daca o celula este libera sau nu ;stabilim daca celula este libera examinand starea peretiilor ei si starea celulelor vecine; daca o celula nu este libera o blocam.

public void Reset(): reseteaza labirintul la setarile intiale

public Cell getNextCell(Cell celula): intoarce celula urmatoare din lista vecinilor cu pereti intacti

public void Draw(Graphics g): deseneaza labirintul

4.2.4 Clasa DimensionDialog

Clasa DimensionDialog implementeaza o fereastra prin care utilizatorul poate seta dimensiuniile labirintului si a celulei atunci cand este generat.

Variabile: Definim doua variabile de tip Button CnclButton si OKButton pentru crearea butoanelor Cancel si OK; variabilele label1 si label2 de tip Label; si variabele numericUpDown1 si numericUpDown2 de tip NumericUpDown ce definesc valorile dimensiuni labirintului cat si a celulei pe care utilizatorul le introduce ; definim si o componenta de tip Container pentru a realiza fereastra.

Constructorul:

public DimensionsDialog()

{

// Windows Form Designer support

InitializeComponent();

}

Metode:

private void InitializeComponent():creaza fereastra , toate elementele grafice sunt initializate in aceasta metoda

protected override void Dispose( bool disposing ): sterge toate resursele utilizate

4.2.5 Clasa Form1

Variabile:

public static extern long PlaySound(String lpszName, long hModule, long dwFlags);

private ArrayList Cheeses = new ArrayList(30);

private Soricel Soricel = new Soricel(100, 100);

private Random RandomGen = new Random();

private const int NumberOfCheeses = 25;

private Scor Scor = new Scor(400, 290);

private int TheSeconds = 150;

private TimerDisplay TheTime = new TimerDisplay(20, 290);

private System.Windows.Forms.Timer timer1;

private System.ComponentModel.IContainer components;

private Thread oThread = null;

private Maze TheMaze1 = new Maze();

private bool m_bGameDone = false;

private GameMessage TheStatusMessage = new GameMessage(10, 10);

private GameMessage TheCheeseMessage = new GameMessage(460, 10);

public enum Side {top = 0, left = 1, bottom = 2, right = 3};

Constructorul:

public Form1()

{

InitializeComponent();

Maze.kDimension = 20;

Cell.kCellSize = 30;

TheMaze1.Initialize();

TheMaze1.Generate();

InitializeCheeses();

InitializeSoricel();

InitializeMessage();

InitializeTimer();

InitializeScor();

SetBounds(10, 10, (Maze.kDimension + 1) * Cell.kCellSize + Cell.PADDING, (Maze.kDimension + 3) * Cell.kCellSize + Cell.PADDING);

SetStyle(ControlStyles.UserPaint, true);

SetStyle(ControlStyles.AllPaintingInWmPaint, true);

SetStyle(ControlStyles.DoubleBuffer, true);

}

Metode:

public void PlayASound():defineste rularea unui sunet wave

public void PlaySoundInThread(string wavefile): ruleaza un sunet wave cu ajutorul unui thread

public void InitializeTimer(): initializeaza timpul in care soricelul trebuie sa colecteze toata branza

public void InitializeMessage():afiseaza in partea stanga a ferestrei mesajul “Cheese"

public void InitializeScor(): reseteaza si initializeaza scorul

public void InitializeCheeses(): fixeaza “branza” in celula ; adjusteaza imaginea bitmap la dimensiuniile celulei astfel incat sa se integreze in labirint

public Point GetRandomCellPosition(): returneaza centrul uneoi celule aleatorii

public void InitializeSoricel(): ajusteaza soricelul la dimensiuniile labirintului si il plaseaza in centrul celulei

protected override void Dispose( bool disposing ): sterge toate resursele folosite

private void InitializeComponent(): metoda ce construieste fereastra si integreaza elementele grafice in ea

private void Form1_Paint(object sender, System.Windows.Forms.PaintEventArgs e):metoda grafica in care se deseneaza scorul , timpul , un mesaj ce indica statusul jocului, deseneaza branza, deseneaza un mesaj ce indica cate bucati de branza “ a mancat” soricelul , deseneaza si soricelul

private int CheckIntersection(): daca soricelul si branza se intersecteaza atunci aceasta metoda returneaza un integer

private bool CanSoricelMove(Side aSide):defineste deplasarea in labirint a soricelului prin verificarea intersectiei dintre soricel si peretii labirintului

private void HandleLatestKey():defineste deplasarea in labirint a soricelului de catre utilizator cu ajutorul tastaturii

private void Form1_KeyDown(object sender, System.Windows.Forms.KeyEventArgs e): implementeaza un eveniment KeyDown

private void timer1_Tick(object sender, System.EventArgs e):trateaza “scurgerea” timpului alocat soricelului sa se deplaseze in labirint si sa manance branza

4.2.6 Clasa Cheese

Clasa Cheese implementeaza un obiect Bitmap in labirint.

Variabile: Definim un obiect Bitmap CheeseImage care va avea valoarea nula si definim o variabila de tip Point Position.

Constructor: Avem doi constructori:

public Cheese()

{

Position.X = 0;

Position.Y = 0;

if (CheeseImage == null)

{

CheeseImage = new Bitmap("e22.gif");

}

}

public Cheese(int x, int y)

{

Position.X = x;

Position.Y = y;

if (CheeseImage == null)

{

CheeseImage = new Bitmap("e22.gif");

}

}

Metode:

public Rectangle GetFrame():intoarce un dreptughi de dimensiunile imagini

public void Draw(Graphics g): deseneaza imaginea in labirint

4.2.7 Clasa GameMessage

Aceasta clasa defineste mesajele jocului implementat. Este o clasa cu un scop pur si simplu grafic.

Variabile:

public Point Position = new Point(0,0);

public Font MyFont = new Font("Compact", 20.0f, GraphicsUnit.Pixel );

public string Message = "";

Constructor:

public GameMessage(int x, int y)

{

//

// TODO: Add constructor logic here

//

Position.X = x;

Position.Y = y;

}

Metode:

public void Draw(Graphics g):deseneaza mesajul pentru a putea fi integrat si vizualizat in fereastra jocului

public Rectangle GetFrame():returneaza un dreptunghi in care se va afla mesajul

4.2.8 Clasa Scor

Aceasta clasa implementeaza scorul ( numarul de branza mancata de soricel).

Variabile:

int Count = 0;

public Point Position = new Point(0,0);

public Font MyFont = new Font("Compact", 20.0f, GraphicsUnit.Pixel );

Constructor:

public Scor(int x, int y)

{

Position.X = x;

Position.Y = y;

}

Metode:

public void Draw(Graphics g): deseneaza scorul pentru a fi integrat in fereastra principala

public Rectangle GetFrame():intoarce un dreptunghi in care se va afla scorul in fereastra principala

public void Reset(): reseteaza scorul la valoarea 0

public void Increment(): incrementeaza scorul cu o unitate

4.2.9 Clasa Soricel

Aceasta clasa implementeaza un obiect Bitmap in labirint si defineste deplasarea lui in acel labirint.

Variabile:

public Point Position;

static Bitmap SoricelImage = null;

static Bitmap SoricelImage2 = null;

int inc = 3;

int LastPositionX = 0;

int LastPositionY = 0;

Constructor:

public Soricel()

{

Position.X = 30;

Position.Y = 35;

if (SoricelImage == null)

{

SoricelImage = new Bitmap("mouse.gif");

}

if (SoricelImage2 == null)

{

SoricelImage2 = new Bitmap("mouse.gif");

}

}

public Soricel(int x, int y)

{

//

// TODO: Add constructor logic here

//

Position.X = x;

Position.Y = y;

if (SoricelImage == null)

{

SoricelImage = new Bitmap("mouse.gif");

}

if (SoricelImage2 == null)

{

SoricelImage2 = new Bitmap("mouse.gif");

}

}

Metode:

public Rectangle GetFrame(): returneaza un dreptunghi in care este amplasat obiectul Bitmap

public void Draw(Graphics g): deseneaza obiectul Bitmap (soricelul) in labirint

public void MoveLeft(Rectangle r):deplasam dreptunghiul la stanga

public void MoveRight(Rectangle r): deplasam dreptunghiul la dreapta

public void MoveUp(Rectangle r): deplasam dreptunghiul in sus

public void MoveDown(Rectangle r): deplasam dreptunghiul in jos

4.2.10 Clasa TimerDisplay

Variabile:

public enum TimeDirection {Up, Down};

public Point Position = new Point(0,0);

public Font MyFont = new Font("Compact", 20.0f, GraphicsUnit.Pixel );

public string TheString;

private TimeDirection m_Direction = TimeDirection.Up;

Constructor:

public TimerDisplay(int x, int y)

{

Position.X = x;

Position.Y = y;

}

Metode:

public void Draw(Graphics g, int secs): deseneaza timpul in secunde pe directiile stabilite in constructor

public string FormatTime(int secs): stabileste formatul in care va fi afisat timpul

public Rectangle GetFrame(): intoarce un dreptunghi in care va fi plasat timpul desenat

5.Concluzii

Dupa cum se poate observa in capitolele de mai sus labirinturile au reprezentat intotdeauna o fascinatie pentru oameni , rezolvarea lor a devenit o procovare. Odata cu aparitia limbajelor de programare s-a incercat generarea mai rapida a acestui puzzle. S-au dezvoltat tot felul de algoritmi, atat de generare cat si de determinare a solutiei. Pe masura ce industria IT a evoluat, labirinturile au inceput sa fie folosite in jocuri astfel ca necesitatea unor algoritmi mai performati a crescut.

Aplicatia implementata de mine are ca scop simularea deplasarii in labirint a obiectelor impreuna cu studierea labirintului si determinarea solutiei lui.

Aplicatia suporta generarea de labirinturi pana la dimensiuni destul de mari, rezolvarea si deplasarea in labirint se desfasoara fara nici o problema singura inconvenienta fiind nesincronizarea threadului in cazul rezolva si dupa aceea reseteaza.

Aplicatia este implementata in C# , un limbaj ce deriva din C++ si care simplifica mult scrierea de programe pentru sistemul de operare Windows.

Aceasta aplicatie poate fi transpusa intr-un mediu 3D cu ajutorul Truevision3D , care este un motor 3D ce este conceput pentru a da acces la toate resusele avansate folosite pentru vizualizarea jocurilor si aplicatiilor 3D. are suport pentru limbajele urmatoare : Visual Basic 6, Visual Basic.Net, C# , delphi si C++.

Screenshot-uri din aplicatii facute cu Truevision3D [29]

Se poate implenta in aceasta aplicatie si logica fuzzy in care obiectul ce strabate labirintul sa aiba implentat un comportament inteligent si sa fie capabil sa ia decizi singur. Astfel se poate simula nu numai deplasarea in labirint ci si coliziunea cxu alte obiecte din labirint panica in cazul in care ramane blocat in labirint sau frica in caz cand intalneste un pradator in labirint.

Aplicatia se poate extinde pentru a studia un model comportamental de grup in acest labirint in care fiecare individ avand un comportament diferit fata de ceilalti indivizi.

O mare gama de domenii pot folosi labirintul, atat ca si concept cat ca si aplicatie.

Referinte Biblografice

http://www.astrolog.org/labyrnth/algrithm.htm

http://www.mazeworks.com/mazegen/mazetut/

http://www.codeproject.com/csharp/

http://en.wikipedia.org/wiki/Maze

http://en.wikipedia.org/wiki/DFS_algorithm

http://www.red3d.com/cwr/boids/

http://www.astrolog.org/labyrnth/maze/unicursl.gif

http://www.astrolog.org/labyrnth/maze/braid.gif

http://www.astrolog.org/labyrnth/maze/theta.gif

http://www.astrolog.org/labyrnth/maze/delta.gif

http://www.astrolog.org/labyrnth/maze/sigma.gif

http://www.astrolog.org/labyrnth/maze/upsilon.gif

http://www.astrolog.org/labyrnth/maze/crack.gif

http://www.astrolog.org/labyrnth/maze/weave.gif

http://www.astrolog.org/labyrnth/maze/4d.gif

http://www.astrolog.org/labyrnth/maze/5d.gif

http://www.astrolog.org/labyrnth/maze/bias.gif

http://www.astrolog.org/labyrnth/maze/run.gif

http://www.astrolog.org/labyrnth/maze/zeta.gif

http://www.astrolog.org/labyrnth/maze/planair.gif

http://www.astrolog.org/labyrnth/maze/hyper.gif

http://www.astrolog.org/labyrnth/maze/word2.gif

http://www.astrolog.org/labyrnth/java.htm

http://upload.wikimedia.org/wikipedia/commons/7/75/Maze.JPG

http://upload.wikimedia.org/wikipedia/commons/3/34/Maze01-01.png

http://www.clickmazes.com/dragon/FractalMaze.jpg

http://news.thomasnet.com/IMT/archives/maze.jpg

http://www.wingimp.org/tutorial/3d_maze/3dmaze.jpg

http://www.truevision3d.com/gallery.php?sid=d2865513f12085443e01705980b0e623

http://msdn2.microsoft.com/en-us/vcsharp/aa336803.aspx

Professional C# – Simon Robinson,Christian Nagel,Karli Watson,Jay Glynn,Morgan Skinner, Bill Evjen

Limbajul C# pentru incepatori Volumul V – Clase – L.Negrescu

The Art of the Maze – Adrian Fisher & Georg Gerster, Weidenfeld & Nicolson (1990)

User Interfaces in C#: Windows Forms and Custom Controls – Matthew MacDonald