DIMENSI0N

DIMENSION_Maze_solver

Dec 25th, 2019
392
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.44 KB | None
  1. #include <windows.h>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <vector>
  5. #include <ctime>
  6. #include <iomanip>
  7.  
  8.  
  9.  
  10. // ---------- Affichage ----------
  11.  
  12.  
  13.  
  14. HWND myconsole = GetConsoleWindow();
  15. HDC mydc = GetDC(myconsole);
  16.  
  17. std::vector<std::vector<int>> maze; // Structure définissant le labyrinthe
  18.  
  19. int size = 101; // Taille du labyrinthe
  20.  
  21. int zoom = 7; // Taille des cases en pixel
  22.  
  23. int ScreenX = size * zoom;
  24. int ScreenY = size * zoom;
  25.  
  26. int GapX = 200; // Décalage en X
  27. int GapY = 100; // Décalage en Y
  28.  
  29.  
  30.  
  31. // Affiche une case du labyrinthe
  32.  
  33. void set_point(int y, int x, COLORREF color)
  34. {
  35.     if (x >= 0 and x <= ScreenX and y >= 0 and y <= ScreenY)
  36.     {
  37.         x = GapX + zoom * x;
  38.         y = GapY + zoom * y;
  39.  
  40.         for (int i = 0; i < zoom; i++)
  41.         {
  42.             for (int j = 0; j < zoom; j++)
  43.                 SetPixel(mydc, x + i, y + j, color);
  44.         }
  45.     }
  46. }
  47.  
  48.  
  49.  
  50. // Affiche tout le labyrinthe
  51.  
  52. void show()
  53. {
  54.     for (int i = 0; i < size; i++)
  55.     {
  56.         for (int j = 0; j < size; j ++)
  57.         {
  58.             if (maze.at(i).at(j) == -1)
  59.                 set_point(i, j, RGB(255, 255, 255));
  60.         }
  61.     }
  62. }
  63.  
  64.  
  65.  
  66. // Fonction permettant de choisir la taille du labyrinthe dans le main
  67.  
  68. void set_size(int s)
  69. {
  70.     if (s < 6)
  71.         s = 6;
  72.  
  73.     if (s % 2 == 0)
  74.         s += 1;
  75.  
  76.     size = s;
  77.  
  78.     zoom = 700 / size;
  79.  
  80.     if (zoom == 0)
  81.         zoom = 1;
  82. }
  83.  
  84.  
  85.  
  86. // ---------- Génération du labyrinthe ----------
  87.  
  88.  
  89.  
  90. // Vérifie si le labyrinthe est terminé
  91.  
  92. bool is_finished()
  93. {
  94.     for (int i = 1; i < size - 1; i += 2)
  95.     {
  96.         for (int j = 1; j < size - 1; j += 2)
  97.         {
  98.             if (maze.at(i).at(j) != maze.at(1).at(1))
  99.                 return 0;
  100.         }
  101.     }
  102.  
  103.     return 1;
  104. }
  105.  
  106.  
  107.  
  108. // Remplie le labyrinthe de telle sorte à ce que chaque case soit entourée par des murs
  109.  
  110. void create_grid()
  111. {
  112.     int nb = 0;
  113.     std::vector<int> wall;
  114.     std::vector<int> line;
  115.  
  116.     for (int i = 0; i < size; i++)
  117.     {
  118.         wall.push_back(-1);
  119.  
  120.         if (i % 2 == 1)
  121.             line.push_back(0);
  122.  
  123.         else
  124.             line.push_back(-1);
  125.     }
  126.  
  127.     for (int i = 0; i < size; i++)
  128.     {
  129.         if (i % 2 == 0)
  130.             maze.push_back(wall);
  131.  
  132.         else
  133.             maze.push_back(line);
  134.     }
  135.  
  136.     for (int i = 0; i < size; i++)
  137.     {
  138.         for (int j = 0; j < size; j++)
  139.         {
  140.             if (maze.at(i).at(j) == 0)
  141.             {
  142.                 nb++;
  143.                 maze.at(i).at(j) = nb;
  144.             }
  145.         }
  146.     }
  147.  
  148.     maze.at(1).at(0) = 1;
  149.     maze.at(size - 2).at(size - 1) = nb;
  150. }
  151.  
  152.  
  153.  
  154. // Casse les murs jusqu'à ce que toutes les cases soient accessibles
  155. // (Si "is_hard" = 1, alors le labyrinthe sera complexe, sinon il sera simple)
  156.  
  157. void maze_generator(bool is_hard)
  158. {
  159.     while (is_finished() == 0)
  160.     {
  161.         int i = rand() % (size - 2) + 1;
  162.         int j;
  163.  
  164.         if (i % 2 == 0)
  165.             j = ((rand() % ((size - 1) / 2))) * 2 + 1;
  166.  
  167.         else
  168.             j = ((rand() % ((size - 2) / 2))) * 2 + 2;
  169.  
  170.         int cell_1;
  171.         int cell_2;
  172.  
  173.         if (maze.at(i - 1).at(j) == -1)
  174.         {
  175.             cell_1 = maze.at(i).at(j - 1);
  176.             cell_2 = maze.at(i).at(j + 1);
  177.         }
  178.  
  179.         else
  180.         {
  181.             cell_1 = maze.at(i - 1).at(j);
  182.             cell_2 = maze.at(i + 1).at(j);
  183.         }
  184.  
  185.         if (cell_1 != cell_2)
  186.         {
  187.             maze.at(i).at(j) = 0;
  188.             set_point(i, j, RGB(0, 0, 0));
  189.  
  190.             for (int k = 1; k < size - 1; k += 2)
  191.             {
  192.                 for (int l = 1; l < size - 1; l += 2)
  193.                 {
  194.                     if (maze.at(k).at(l) == cell_2)
  195.                         maze.at(k).at(l) = cell_1;
  196.                 }
  197.             }
  198.         }
  199.     }
  200.  
  201.     if (is_hard) // rend le labyrinthe complexe
  202.     {
  203.         for (int k = 0; k < size; k++)
  204.         {
  205.             int i = rand() % (size - 2) + 1;
  206.             int j;
  207.  
  208.             if (i % 2 == 0)
  209.                 j = ((rand() % ((size - 1) / 2))) * 2 + 1;
  210.  
  211.             else
  212.                 j = ((rand() % ((size - 2) / 2))) * 2 + 2;
  213.  
  214.             maze.at(i).at(j) = 0;
  215.             set_point(i, j, RGB(0, 0, 0));
  216.         }
  217.     }
  218. }
  219.  
  220.  
  221.  
  222. // ---------- Résolution du labyrinthe ----------
  223.  
  224.  
  225.  
  226. // Donne une couleur à partir de la distance entre une case et la sortie
  227.  
  228. COLORREF color(int d, int max)
  229. {
  230.     d = int(double((double(d) / double(max)) * double(255)));
  231.  
  232.     if (d <= 255)
  233.         return RGB(255, 255 - d, 0);
  234.  
  235.     if (d > 255 and d <= 255 * 2)
  236.         return RGB(2 * 255 - d, 0, d - 255);
  237.  
  238.     if (d > 255 * 2 and d <= 255 * 3)
  239.         return RGB(0, 0, (255 * 3 - d));
  240.  
  241.     return RGB(0, 0, 0);
  242. }
  243.  
  244.  
  245.  
  246. // Résout le labyrinthe
  247.  
  248. void maze_solver()
  249. {
  250.     maze.at(1).at(0) = 0;
  251.  
  252.     for (int i = 1; i < size - 1; i++)
  253.     {
  254.         for (int j = 1; j < size - 1; j++)
  255.         {
  256.             if (maze.at(i).at(j) >= 0)
  257.                 maze.at(i).at(j) = 0;
  258.         }
  259.     }
  260.  
  261.     int d = 1;
  262.     std::vector<std::vector<int>> temp;
  263.  
  264.     maze.at(size - 2).at(size - 1) = 1;
  265.     set_point(size - 2, size - 1, RGB(255, 255, 0));
  266.  
  267.     while (maze.at(1).at(1) == 0) // Donne à chaque case la distance entre sa position et la sortie (ainsi qu'une couleur correspondante)
  268.     {
  269.         temp = maze;
  270.         d++;
  271.  
  272.         for (int i = size - 2; i > 0; i--)
  273.         {
  274.             for (int j = size - 2; j > 0; j--)
  275.             {
  276.                 if (maze.at(i).at(j) == 0)
  277.                 {
  278.                     if (maze.at(i - 1).at(j) > 0 or maze.at(i + 1).at(j) > 0 or maze.at(i).at(j - 1) > 0 or maze.at(i).at(j + 1) > 0)
  279.                     {
  280.                         temp.at(i).at(j) = d;
  281.                         set_point(i, j, color(d, size * 1.5));
  282.                     }
  283.                 }
  284.             }
  285.         }
  286.  
  287.         maze = temp;
  288.     }
  289.  
  290.     maze.at(1).at(0) = d + 20;
  291.  
  292.     for (int i = 0; i < size; i++)
  293.     {
  294.         for (int j = 0; j < size; j++)
  295.         {
  296.             if (maze.at(i).at(j) == 0)
  297.                 maze.at(i).at(j) = d + 1;
  298.  
  299.             if (maze.at(i).at(j) == -1)
  300.                 maze.at(i).at(j) = d + 10;
  301.         }
  302.     }
  303.  
  304.     set_point(1, 0, RGB(0, 255, 0));
  305.     set_point(1, 1, RGB(0, 255, 0));
  306.  
  307.     int x = 1;
  308.     int y = 1;
  309.  
  310.     while (x != size - 2 or y != size - 2) // Trace le chemin vert (le chemin le plus court entre l'entrée et la sortie)
  311.     {
  312.         if (maze.at(x).at(y - 1) <= maze.at(x).at(y + 1) and maze.at(x).at(y - 1) <= maze.at(x - 1).at(y) and maze.at(x).at(y - 1) <= maze.at(x + 1).at(y))
  313.             y = y - 1;
  314.  
  315.         else if (maze.at(x).at(y + 1) <= maze.at(x).at(y - 1) and maze.at(x).at(y + 1) <= maze.at(x - 1).at(y) and maze.at(x).at(y + 1) <= maze.at(x + 1).at(y))
  316.             y = y + 1;
  317.  
  318.         else if (maze.at(x - 1).at(y) <= maze.at(x).at(y - 1) and maze.at(x - 1).at(y) <= maze.at(x).at(y + 1) and maze.at(x - 1).at(y) <= maze.at(x + 1).at(y))
  319.             x = x - 1;
  320.  
  321.         else if (maze.at(x + 1).at(y) <= maze.at(x).at(y - 1) and maze.at(x + 1).at(y) <= maze.at(x).at(y + 1) and maze.at(x + 1).at(y) <= maze.at(x - 1).at(y))
  322.             x = x + 1;
  323.  
  324.         set_point(x, y, RGB(0, 255, 0));
  325.     }
  326.  
  327.     set_point(size - 2, size - 1, RGB(0, 255, 0));
  328. }
  329.  
  330.  
  331.  
  332. // ---------- Le main ----------
  333.  
  334.  
  335.  
  336. int main()
  337. {
  338.     int nb_simulation = 100; // Choisir le nombre de simulations
  339.     set_size(100); // Choisir la taille du labyrinthe
  340.  
  341.     for (int s = 0; s < nb_simulation; s++)
  342.     {
  343.         create_grid();
  344.         show();
  345.         maze_generator(1);
  346.  
  347.         maze_solver();
  348.  
  349.         Sleep(1000);
  350.  
  351.         maze.clear();
  352.         system("cls");
  353.     }
  354.  
  355.     return 0;
  356. }
RAW Paste Data Copied