Aceasta este prima din mai multe planificate articole dedicate generarea și rezolvarea labirinturi.
În acest articol, ne vom concentra pe punerea în aplicare a ușor de generație algoritm de „idealul“ al labirintului și aplicarea acestuia la calea de căutare.
Considerăm că un algoritm bazat pe backtracking, permițându-vă să creați labirinturi fără cicluri, cu o singură cale între două puncte. Algoritmul nu este cel mai rapid, destul de lumină asupra resurselor în comparație cu algoritmul Euler sau testul Kruskal, dar foarte ușor de implementat și vă permite să creați labirinturi ramificate cu ramuri mort-end foarte lungi.
Vrei - Eu pun o pisică.
Internetul rusesc este foarte puține informații privind algoritmii de labirinturi generatoare, care a fost motivul pentru a scrie acest articol.
Exemple de cod în limbajul C, precum și codul sursă complet pentru proiect este disponibil pe GitHub sub licența GNU GPLv3.
Link-uri către resurse de limba engleză și proiectul pe care îl va găsi la sfârșitul articolului.
Descrierea algoritmului
Notă: Se presupune că inițial fiecare celulă are pereți pe toate cele patru laturi, care îl separă de celulele vecine.
1. Asigurați-un curent de celule inițiale și marcați-l ca vizitat.
2. Deși există celule nevizitate
1. În cazul în care celula curentă a Nevizitată „vecini“
1. Împingeți celula curentă în stivă
2. Selectați o celulă aleatoare din țările vecine,
3. Scoateți peretele dintre celula curentă și selectată
4. Asigurați celula curentă selectată și marcați-l ca vizitat.
2. În caz contrar, în cazul în care stiva nu este goală
1. Trageți celula din stivă
2. Asigurați-l curent
3. În caz contrar,
1. Selectați o celulă nevizitat aleatoare, face curent și marcați ca vizitat.
Este posibil să fi observat că, atunci când starea 3, labirint gata probabil va avea o zonă izolată.
Această condiție este inclusă în algoritmul în mod excepțional, în practică, în timpul funcționării normale a algoritmului și să corecteze datele sursă, acesta nu este executat.
punerea în aplicare
După cum sa menționat deja mai sus, se presupune că la începutul algoritmului, toate celulele sunt separate pereți.
Ilustrarea algoritmului
0.
1.
2.1.
2.2.
2.1.
2.
codul
Noțiuni de bază la cele mai interesante.
Vom începe să acționeze în ordine și de a genera o primă matrice inițială, care va rula algoritmul.
Pentru comoditate, suntem de acord că toate tipurile de celule sunt specificate în lista.
Acum, că toate pregătirile sunt făcute, puteți începe să genereze.
Structura simplifica în mod semnificativ viața de comunicare între funcții.
Un fragment de cod responsabil pentru generarea:
După cum se poate observa, punerea în aplicare a algoritmului este simplu și abstract al teoriei, cum se spune, „se poate ocupa chiar și un copil.“
Pentru a nu supraîncărca codul de articol de funcții care sunt utilizate în pasajul de mai sus, sub spoiler.
Funcția getNeighbours returnează o matrice de celule vecini nevizitate
Funcția removeWall îndepărtează peretele dintre două celule:
Valoarea calculată mai întâi a diferenței dintre primul și al doilea punctele de coordonate. Evident, valoarea poate fi fie negativ sau pozitiv, sau 0.
Este necesar să se găsească astfel de coordonate pereții xy, atunci când adăugați-le la coordonatele primului punct de coordonatele obținute.
Din moment ce știm că diferența vectorul dintre perete și coordonatele primului punct este fie (| 1 |, 0) sau (0, | 1 |), putem profita de ea.
! Astfel, un aditiv pentru x coordonatele la xdiff = 0 va fi egal xdiff / | xdiff |, când xdiff = 0, la zero. Pentru y respectiv.
Avand aditivi pentru x și y, putem calcula cu ușurință coordonatele peretelui între prima și a doua celule și atribui coordonatele acestora celulei vizitate.
Deci, acum avem un generator de labirint, care poate construi labirinturi, a căror dimensiune este limitată doar de dimensiunea de RAM.
Ca rezultat, putem obține ceva de genul:
Labyrinths. Atenție, traficul!
Generarea de lucru, acum este ușor: afla în acest labirint.
Și încă și mai simplificat, deoarece nu mai avem nevoie pentru a elimina perete.
Pathfinding algoritm backtracking:
1. Asigurați-un curent de celule inițiale și marcați-l ca vizitat.
2. În timp ce nu a aflat
1. În cazul în care celula curentă a Nevizitată „vecini“
1. Împingeți celula curentă în stivă
2. Selectați o celulă aleatoare din țările vecine,
3. Asigurați celula curentă selectată și marcați-l ca vizitat.
2. În caz contrar, în cazul în care stiva nu este goală
1. Trageți celula din stivă
2. Asigurați-l curent
3. În caz contrar, nu există nici o scăpare
Să vedem ce sa întâmplat:
labirint Rezolvat. Trafic!
Roșu marcat cale, albastru - celulele vizitate.
100 x 100
Asta e tot ce ai nevoie pentru o implementare foarte simplă a labirinturi aleatoare.
Pentru cei interesați, codul sursă complet al proiectului de pe GitHub: Maze Generator și Solver (offscreen de redare)
nu OSMesa susținută de unii conducători auto pe bazate pe unix, și pe Windows nu este acceptat deloc. astfel încât persoanele interesate, care nu sunt norocos cu OS / fier, poate sugera să se familiarizeze cu proiectul aferent: Maze Generator și Solver
În ambele modele puse în aplicare aceiași algoritmi, dar primul desen în memorie și ieșiri secvența de imagini PNG-, iar al doilea de pe ecran.
Asamblarea cd construi # 038; # 038;. / configure # 038; # 038; face, dacă inconfortabil, în dosarul src este un fișier QtCreator'a-proiect.