BitCell

Your IT power source

Skip to content


Generator de labirint (C++)

Această secţiune se ocupă cu programarea, fără a ţine cont de limbaj. Dacă vrei (sau trebuie) să înveți algoritmică, aici este locul potrivit. Descrieri şi idei de algoritmi, algoritmi clasici și întrebări pe baza acestora, toate vor fi postate aici.
Post a reply

Generator de labirint (C++)

Postby smith » 01 Feb 2010, 15:52

Generator de labirint



Am fost forțat rugat de către DarkByte să implementez un algoritm care să genereze un labirint perfect. O regulă de bază ar fi că din orice punct al labirintului poti să vizitezi orice alt punct(vorbim despre puncte care aparțin "drumului" ). Un site unde găsiți mai multe informații despre labirinturi pentru pasionați ar fi acesta.

Ce se întâmplă în spate?



Algoritmul este un DFS ( Deep-First Search ). Metoda mea bordează matricea cu cifra 8 pe margini (funcția build_wall). Apoi se generează un punct cu două coordonate random (funcția rand_start). Acel punct (cell) va fi locul de unde începe algoritmul să genereze labirintul. Coordonatele unui punct sunt reținte într-o structură (coordinate). Punctul cell este adăugat la stivă (trail-pentru a reține drumul parcurs).

Din poziția curentă (cell) algoritmul se uită dacă există vreo celulă ocupabilă din jurul poziției curente (funcția posib_nextcell). Dacă există alege una random dacă aceasta este ocupabilă (funcția get_nextcell) și o adaugă la stivă. Desigur, nu e cea mai eficientă metodă (randomul poate să selecteze o celulă neocupabilă de mai multe ori; se poate rezolva problema asta dar altă dată, poate la o versiune 0.2).

Putem observa ideea de DFS. Se alege o singură celulă-vecină(chiar dacă pot exista mai multe celule-vecine) și se continuă. Algoritmul continuă să selecteze puncte ocupabile și le adaugă la stivă. Dacă ajunge într-o poziție din care nu poate să continue se scoate un element din stivă și se uită dacă poate continua din altă poziție anterioară.
Algoritmul se termină când stiva este goală, deci se revine în poziția de unde am început să generăm algoritmul.

Codul:



Line number On/Off | Expand/Contract | Select all
  1. #include <queue>
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <stack>
  5. #include <cstdlib>
  6. #include <time.h> //optional - depends on operating sistem, i think
  7. #define WALL_VALUE 8
  8. using namespace std;
  9.  
  10. int lab[500][500];   //the matrix :))
  11.  
  12. /*
  13. A structure to represent a point in a matrix
  14. */
  15. struct coordinate
  16. {
  17.     short int x; // the x coordinate
  18.     short int y; // the y coordinate
  19. };
  20.  
  21. /*
  22. A function which returns the south coordinates from a given position
  23. param posit The given position
  24. */
  25. coordinate south(coordinate posit)
  26. {
  27.     coordinate temp;
  28.     temp.x=posit.x-1;  //one line -> down
  29.     temp.y=posit.y;
  30.     return temp;
  31. }
  32.  
  33. /*
  34. A function which returns the north coordinates from a given position
  35. param posit The given position
  36. */
  37. coordinate north(coordinate posit)
  38. {
  39.     coordinate temp;
  40.     temp.x=posit.x+1;  // one line -> up
  41.     temp.y=posit.y;
  42.     return temp;
  43. }
  44.  
  45. /*
  46. A function which returns the east coordinates from a given position
  47. param posit The given position
  48. */
  49. coordinate east(coordinate posit)
  50. {
  51.     coordinate temp;
  52.     temp.x=posit.x;
  53.     temp.y=posit.y+1;  //one collumn ->right
  54.     return temp;
  55. }
  56.  
  57. /*
  58. A function which returns the west coordinates from a given position
  59. param posit The given position
  60. */
  61. coordinate west(coordinate posit)
  62. {
  63.     coordinate temp;
  64.     temp.x=posit.x;
  65.     temp.y=posit.y-1;  //one collumn ->left
  66.     return temp;
  67. }
  68.  
  69. /*
  70. A function which returns true if the cell passed to it is free to be
  71. occupied. The functions looks around the given cell (south,north,
  72. east,west) and sums the values within that surounding cells of the matrix.
  73. The rule is that a free cell can have at most one neighbour.
  74. The "% WALL_VALUE" is there so we can "eliminate" the exterior wall.
  75. See the define (up) and the build_wall function.
  76. param posit The given position
  77. */
  78. bool is_empty(coordinate posit)
  79. {
  80.     if (lab[posit.x][posit.y]==0)
  81.     {
  82.         coordinate sou=south(posit);
  83.         coordinate nor=north(posit);
  84.         coordinate eas= east(posit);
  85.         coordinate wes= west(posit);
  86.  
  87.         int sum=lab[sou.x][sou.y]+
  88.                 lab[nor.x][nor.y]+
  89.                 lab[eas.x][eas.y]+
  90.                 lab[wes.x][wes.y];
  91.  
  92.         return (sum % WALL_VALUE) <= 1 ;
  93.     }
  94.  
  95.     return false;
  96. }
  97.  
  98. /*
  99. A function which returns true if there are free to be occupied
  100. cells around a given point(cell). If at least one of the (south,
  101. north,east,west) cells is free, then the given point(cell) has free
  102. to be occupied cells around it therefore the function returns true.
  103. param posit The given position
  104. */
  105. bool posib_nextcell(coordinate posit)
  106. {
  107.     return (is_empty(south(posit)) ||
  108.             is_empty(north(posit)) ||
  109.             is_empty(east(posit) ) ||
  110.             is_empty(west(posit) ) );
  111. }
  112.  
  113. /*
  114. A function which returns a random coordinate of a free cell
  115. around a given point(cell).
  116. param posit The given position
  117. */
  118. coordinate get_nextcell(coordinate posit)
  119. {
  120.     coordinate aux;
  121.     bool ok = false;
  122.     while ( !ok )
  123.     {
  124.  
  125.     int gen = ( rand() % 4 ) +1;
  126.  
  127.     switch(gen){
  128.         case 1: aux=south(posit); break;
  129.         case 2: aux=north(posit); break;
  130.         case 3: aux=east(posit);  break;
  131.         case 4: aux=west(posit);  break;
  132.         }
  133.     if ( is_empty(aux) ) ok=true;
  134.     }
  135. return aux;
  136. }
  137.  
  138. /*
  139. A function which builds a wall on the exterior lines and columns
  140. of the matrix. The function fills the exterior with the number "8".
  141. param LIN The number of lines that the matrix has
  142. param COL The number of columns that the matrix has
  143. */
  144. void build_wall(int LIN,int COL)
  145. {
  146.     for (int x=0;x<COL;x++) lab[0][x]=lab[LIN-1][x]=8;  //first and last line
  147.     for (int y=0;y<LIN;y++) lab[y][0]=lab[y][COL-1]=8;  //first and last column
  148. }
  149.  
  150. /*
  151. A function which prints the matrix.
  152. param LIN The number of lines that the matrix has
  153. param COL The number of columns that the matrix has
  154. */
  155. void print(int LIN,int COL)
  156. {
  157. for (int y=0;y<LIN;y++)
  158.     {
  159.         for(int x=0;x<COL;x++) cout<<lab[y][x]<<"  ";
  160.         cout<<'\n';
  161.     }
  162. }
  163.  
  164. /*
  165. A function which generates a X and Y coordinate for the starting
  166. point from which the program will generate the labyrinth.
  167. param LIN The number of lines that the matrix has
  168. param COL The number of columns that the matrix has
  169. */
  170. coordinate rand_start(int LIN,int COL)
  171. {
  172.     coordinate aux;
  173.     srand ( time(NULL) );
  174.     aux.x=rand() % LIN; if (aux.x==0) aux.x++;
  175.     aux.y=rand() % COL; if (aux.y==0) aux.y++;
  176.     return aux;
  177. }
  178.  
  179. /*
  180. The main function
  181. */
  182. int main()
  183. {
  184.  
  185. stack <coordinate> trail;   //the stack on which the program will "remember" the road
  186.  
  187. int  LIN=40,COL=40;         //the number of lines and the number of columns
  188.                             //modify this for different labyrinth sizes
  189.  
  190. build_wall(LIN,COL);        //builds the wall
  191.  
  192. coordinate cell = rand_start(LIN,COL);  // generates the first cell coordinates
  193.  
  194. trail.push(cell);           //pushes the coordinates of the cell in the stack
  195.  
  196. lab[cell.x][cell.y]=1;      //marks the cell from the matrix as "visited"
  197.  
  198.                             // LEGEND:
  199.                             // 8 - permanent wall
  200.                             // 0 - wall
  201.                             // 1 - road
  202.  
  203. /*
  204. This part repeats until the stack is empty. The algorith is a
  205. Deep-First Search.  The program looks for the fist occupiable  
  206. point next to a given point. It adds it to the stack and so on.
  207. If it gets to a dead end the program pops some cells from the
  208. stacks. At every point the algorithm looks for new free cells.
  209. The program ends when the stack is empty and the labyrinth is generated.
  210. */
  211.  while(!trail.empty())
  212. {
  213.     cell=trail.top();
  214.     if (posib_nextcell(cell))
  215.     {
  216.         cell=get_nextcell(cell);
  217.  
  218.         trail.push(cell);
  219.  
  220.         lab[cell.x][cell.y]=1;
  221.     }
  222.     else
  223.     {
  224.         trail.pop();
  225.     }
  226. }
  227.  
  228. print(LIN,COL);             //prints the generated labyrinth
  229.  
  230. return 0;
  231. }
  232.  


Performanță și un exemplu:



Nu prea putem să vorbim despre performanță până când nu voi rezolva problema acelui random. Complexitatea algoritmului DFS este de O ( V + M ) , unde V reprezintă numărul de varfuri și M numărul de muchii. Totuși programul rulează ireproșabil sub o secundă pentru matrici de 500x500.

Exemplul următor este un labirint de 40x40. Am înlocuit 1 cu X ca să se vedea mai bine care e drum și care nu.
  • 8 -zid permanent (exterior)
  • X -drum
  • 0 -zid
Line number On/Off | Expand/Contract | Select all
  1. 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
  2. 8 X X X X X 0 X X X X X 0 X X X X 0 X X X 0 X X X X X X X 0 0 X X X X X X X X 8
  3. 8 X 0 0 X 0 0 X 0 X 0 0 X X 0 0 X X X 0 X 0 X 0 0 0 0 X 0 X X X 0 0 0 0 0 X 0 8
  4. 8 X X 0 X X X X 0 X 0 0 X 0 X X X 0 X 0 X 0 0 X X X 0 X X X 0 X 0 X X X X X X 8
  5. 8 0 X X 0 0 0 X 0 X X X X 0 X 0 0 0 X 0 X X 0 X 0 X X 0 X 0 X X 0 X 0 X 0 X 0 8
  6. 8 X 0 X 0 X X 0 X 0 0 0 0 X 0 X X X X 0 0 X 0 X X 0 X X 0 X X 0 X X 0 X 0 X X 8
  7. 8 X 0 X X 0 X X X X X X 0 X 0 X 0 0 0 X 0 X X 0 X X 0 X 0 0 0 X X 0 X 0 X X 0 8
  8. 8 X 0 X 0 X X 0 0 X 0 X X X 0 X 0 X X X 0 0 X 0 0 X 0 X X X X X 0 X X X X 0 X 8
  9. 8 X 0 X X 0 X X X 0 X X 0 0 X X 0 0 0 X X 0 X X X X X 0 0 0 0 0 X 0 X 0 0 X X 8
  10. 8 X 0 0 X X 0 0 X X 0 X 0 X X 0 X X X 0 X X X 0 0 0 0 X X X X 0 X X X X 0 0 X 8
  11. 8 X X 0 0 X X X 0 0 0 X 0 X 0 X X 0 X 0 0 X 0 X X X X X 0 0 X X 0 0 0 X X X X 8
  12. 8 0 X X X X 0 X X X X X 0 X 0 0 X 0 X X X 0 X X 0 X 0 0 X X X 0 X X X 0 0 X 0 8
  13. 8 X 0 0 0 0 X 0 X 0 0 X 0 X X X X X 0 0 X 0 X 0 0 0 X X X 0 0 X X 0 X X 0 X X 8
  14. 8 X X X X X X X 0 X X X 0 0 0 0 0 X X 0 X X X X 0 X X 0 0 X 0 X 0 X 0 X 0 0 0 8
  15. 8 0 X 0 0 0 0 X 0 X 0 0 X X X X X 0 0 X 0 0 X 0 0 X 0 X X X 0 X 0 X 0 X X X X 8
  16. 8 X X X X X 0 X X 0 0 X X 0 0 0 X 0 X X X X 0 X X X 0 X 0 X X X 0 X 0 X 0 0 X 8
  17. 8 X 0 0 0 X X 0 X X X X 0 X X X X 0 X 0 0 X X X 0 0 0 X X 0 0 0 X X X 0 0 0 X 8
  18. 8 X 0 X X 0 X X 0 0 0 0 X X 0 X 0 X X X 0 0 X 0 X X X 0 X 0 X X 0 0 X X 0 X X 8
  19. 8 X 0 X 0 X 0 X X X X 0 0 X X 0 X X 0 X X X 0 X X 0 X X X 0 0 X X X 0 X 0 X 0 8
  20. 8 X 0 X X X 0 0 0 0 X X X 0 X X X 0 X X 0 X 0 X 0 X 0 0 0 X X X 0 X 0 X 0 X X 8
  21. 8 X 0 0 X 0 X X X 0 X 0 X 0 0 0 0 0 0 0 X 0 0 X 0 X X X 0 X 0 X 0 X X X 0 X 0 8
  22. 8 X X 0 X X X 0 X X 0 X X X X X X 0 X X X X X X 0 X 0 X X X X 0 X 0 0 X 0 X 0 8
  23. 8 0 X X 0 X 0 X 0 X X 0 0 0 0 0 X 0 X 0 0 0 X 0 0 X X 0 0 0 X 0 X X X X 0 X X 8
  24. 8 X 0 X 0 X X X X 0 X X X X X 0 X X X 0 X X 0 X X X 0 0 X X X 0 X 0 X 0 X 0 X 8
  25. 8 X 0 X X 0 X 0 X X 0 0 0 0 X X 0 0 0 X 0 X X X 0 0 X X X 0 0 X X 0 0 X X X X 8
  26. 8 X X 0 X X 0 X X 0 X X X X 0 X X X X X X 0 X 0 0 X X 0 0 X X X 0 X 0 X 0 0 X 8
  27. 8 X 0 X 0 X X 0 0 X X 0 0 X 0 0 X 0 X 0 X X 0 X X X 0 X 0 X 0 X X X 0 X X X 0 8
  28. 8 X 0 X X 0 X X X X 0 X 0 X X X 0 0 X X 0 X X X 0 0 X X 0 X 0 X 0 0 X 0 0 X 0 8
  29. 8 X X X 0 X 0 0 0 0 X X X 0 0 X X X 0 X X 0 X 0 X X 0 X 0 X X 0 X X X X 0 X X 8
  30. 8 0 X 0 X X X X X X 0 0 X X X 0 0 X X 0 X 0 0 X 0 X X X X 0 X 0 X 0 0 X 0 0 X 8
  31. 8 X X X X 0 X 0 0 X X X 0 X 0 X X 0 X 0 X X X X 0 X 0 0 X 0 X 0 X 0 X X X 0 X 8
  32. 8 X 0 X 0 0 X X 0 0 0 X X X 0 X 0 X X 0 X 0 0 X 0 X 0 X X 0 X 0 X X 0 0 X X X 8
  33. 8 X 0 0 X X X 0 X X X 0 X 0 X X X 0 X 0 0 0 X X 0 X X 0 X X X X 0 X 0 X X 0 X 8
  34. 8 X X X 0 X 0 X X 0 X 0 X 0 X 0 X X X X X X X 0 X 0 X X 0 X 0 X 0 X 0 0 X X 0 8
  35. 8 X 0 X 0 X 0 X 0 0 X X 0 X X X 0 0 0 0 X 0 X X X X 0 X 0 0 X 0 0 X X X 0 X X 8
  36. 8 X 0 X 0 0 0 X X X 0 X X X 0 X 0 X X 0 0 0 X 0 0 X X 0 X X X X X 0 0 X X 0 X 8
  37. 8 X 0 X X X X 0 X 0 X 0 0 X 0 X X X 0 X X X 0 X X X 0 X X 0 X 0 X X X 0 X X 0 8
  38. 8 X 0 0 0 0 X X X X X 0 X 0 X 0 0 0 X X 0 X X 0 0 0 X X 0 X 0 X 0 0 X 0 0 X X 8
  39. 8 X X X X X 0 X 0 0 X X X 0 X X X X X 0 0 0 X X X X X 0 X X X X X X X X X X 0 8
  40. 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8

Thanks for reading! :D

P.S.: Nu promit, dar probabil că în viitor va exista altă versiune, poate și cu gui.
6p / 1 votes
Ilea Cristian
User avatar
smith
Enum
 
Joined: 29 Dec 2009
Location: Cluj-Napoca
Status: 82

Re: Generator de labirint (C++)

Postby DarkByte » 14 Feb 2010, 18:46

Good job :)

In curand o sa postez si eu varianta mea (nu e doar generator).

Keep up :)
0,0p / 0 votes


Last bumped by smith on 14 Feb 2010, 18:46.
User avatar
DarkByte
11011011
 
Joined: 29 Dec 2009
Status: 136
Post a reply

Return to Algoritmică

Who is online

Users browsing this forum: No registered users and 0 guests


Powered by phpBB © phpBB Group
cron