native-m · November 26, 2021 18:19 · Nov 26, 2021
diff --git a/maze.cpp b/maze.cpp
@@ -0,0 +1,243 @@
+#include <iostream>
+#include <stack>
+#include <array>
+#include <algorithm>
+#include <random>
+#include <memory>
+#include <SDL.h>
+
+#undef main
+
+#define WIDTH 10
+#define HEIGHT 10
+
+#define LEFT_WALL (1 << 0)
+#define TOP_WALL (1 << 1)
+#define RIGHT_WALL (1 << 2)
+#define BOTTOM_WALL (1 << 3)
+
+struct Cell
+{
+    int x, y;
+    int wall; // wall bit-field
+    bool visited;
+};
+
+template<int Width, int Height>
+struct Grid
+{
+    Cell* cells = nullptr;
+
+    Grid() :
+        cells(new Cell[Width * Height])
+    {
+        for (int j = 0; j < Height; j++) {
+            for (int i = 0; i < Width; i++) {
+                cells[j * Width + i] = Cell{ i, j, 15, false };
+            }
+        }
+    }
+
+    ~Grid()
+    {
+        delete[] cells;
+    }
+
+    void make_visited(int x, int y)
+    {
+        cells[y * Width + x].visited = true;
+    }
+
+    void remove_wall(int x, int y, int wall)
+    {
+        cells[y * Width + x].wall &= ~wall;
+    }
+
+    int get_cell_count() const
+    {
+        return Width * Height;
+    }
+
+    Cell& get_cell(int x, int y)
+    {
+        return cells[y * Width + x];
+    }
+
+    const Cell& get_cell(int x, int y) const
+    {
+        return cells[y * Width + x];
+    }
+};
+
+struct CellNeighbours
+{
+    Cell neighbours[4]{};
+    int count = 0;
+
+    CellNeighbours()
+    {
+        std::srand(0);
+    }
+
+    void add_neighbour(const Cell& neighbour)
+    {
+        neighbours[count++] = neighbour;
+    }
+
+    int get_count() const
+    {
+        return count;
+    }
+};
+
+template<int Width, int Height>
+void generate_maze(Grid<Width, Height>& grid)
+{
+    std::stack<Cell> s;
+    std::random_device rd;
+    std::mt19937 gen(rd());
+
+    s.push(grid.get_cell(0, 0));
+    grid.make_visited(0, 0);
+
+    while (!s.empty()) {
+        Cell current = s.top();
+        s.pop();
+
+        int left = current.x - 1;
+        int top = current.y - 1;
+        int right = current.x + 1;
+        int bottom = current.y + 1;
+
+        CellNeighbours unvisited_neighbours;
+
+        if (left >= 0 && left < Width) {
+            Cell c = grid.get_cell(left, current.y);
+
+            if (!c.visited) {
+                unvisited_neighbours.add_neighbour(c);
+            }
+        }
+
+        if (top >= 0 && top < Height) {
+            Cell c = grid.get_cell(current.x, top);
+
+            if (!c.visited) {
+                unvisited_neighbours.add_neighbour(c);
+            }
+        }
+
+        if (right >= 0 && right < Width) {
+            Cell c = grid.get_cell(right, current.y);
+
+            if (!c.visited) {
+                unvisited_neighbours.add_neighbour(c);
+            }
+        }
+
+        if (bottom >= 0 && bottom < Height) {
+            Cell c = grid.get_cell(current.x, bottom);
+
+            if (!c.visited) {
+                unvisited_neighbours.add_neighbour(c);
+            }
+        }
+
+        int unvisited_count = unvisited_neighbours.get_count();
+
+        if (unvisited_count > 0) {
+            int idx = gen() % unvisited_count;
+            Cell c = unvisited_neighbours.neighbours[idx];
+
+            s.push(current);
+            s.push(c);
+
+            if (c.x > current.x) {
+                grid.remove_wall(current.x, current.y, RIGHT_WALL);
+                grid.remove_wall(c.x, c.y, LEFT_WALL);
+            }
+            else if (c.x < current.x) {
+                grid.remove_wall(current.x, current.y, LEFT_WALL);
+                grid.remove_wall(c.x, c.y, RIGHT_WALL);
+            }
+
+            if (c.y > current.y) {
+                grid.remove_wall(current.x, current.y, BOTTOM_WALL);
+                grid.remove_wall(c.x, c.y, TOP_WALL);
+            }
+            else if (c.y < current.y) {
+                grid.remove_wall(current.x, current.y, TOP_WALL);
+                grid.remove_wall(c.x, c.y, BOTTOM_WALL);
+            }
+
+            grid.make_visited(c.x, c.y);
+        }
+    }
+}
+
+int main()
+{
+    Grid<40, 40> grid;
+
+    SDL_Init(SDL_INIT_VIDEO);
+
+    SDL_Window* window = SDL_CreateWindow("maze", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, 400, 400, 0);
+    SDL_Renderer* renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_SOFTWARE);
+    SDL_Texture* texture = SDL_CreateTexture(renderer, SDL_PIXELFORMAT_RGBA8888, SDL_TEXTUREACCESS_TARGET, 400, 400);
+    static constexpr int rect_size = 10;
+    static constexpr int thickness = 2;
+
+    generate_maze(grid);
+
+    SDL_SetRenderTarget(renderer, texture);
+    SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255);
+    SDL_RenderClear(renderer);
+    SDL_SetRenderDrawColor(renderer, 255, 255, 255, 255);
+
+    for (int i = 0; i < grid.get_cell_count(); i++) {
+        Cell& c = grid.cells[i];
+
+        if (c.wall & LEFT_WALL) {
+            //SDL_Rect rect{ (c.x * rect_size) - thickness, c.y * rect_size, (c.x * rect_size) + thickness, (c.y + 1) * rect_size };
+            //SDL_RenderFillRect(renderer, &rect);
+            SDL_RenderDrawLine(renderer, c.x * rect_size, c.y * rect_size, c.x * rect_size, (c.y + 1) * rect_size);
+        }
+
+        if (c.wall & TOP_WALL) {
+            //SDL_Rect rect{ c.x * rect_size, (c.y * rect_size) - thickness, (c.x + 1) * rect_size, (c.y * rect_size) + thickness };
+            //SDL_RenderFillRect(renderer, &rect);
+            SDL_RenderDrawLine(renderer, c.x * rect_size, c.y * rect_size, (c.x + 1) * rect_size, c.y * rect_size);
+        }
+
+        if (c.wall & RIGHT_WALL) {
+            //SDL_Rect rect{ ((c.x + 1) * rect_size) - thickness, c.y * rect_size, ((c.x + 1) * rect_size) + thickness, (c.y + 1) * rect_size };
+            //SDL_RenderFillRect(renderer, &rect);
+            SDL_RenderDrawLine(renderer, (c.x + 1) * rect_size, c.y * rect_size, (c.x + 1) * rect_size, (c.y + 1) * rect_size);
+        }
+
+        if (c.wall & BOTTOM_WALL) {
+            //SDL_Rect rect{ c.x * rect_size, ((c.y + 1) * rect_size) - thickness, (c.x + 1) * rect_size, ((c.y + 1) * rect_size) + thickness };
+            //SDL_RenderFillRect(renderer, &rect);
+            SDL_RenderDrawLine(renderer, c.x * rect_size, (c.y + 1) * rect_size, (c.x + 1) * rect_size, (c.y + 1) * rect_size);
+        }
+    }
+
+    SDL_SetRenderTarget(renderer, nullptr);
+    SDL_RenderCopy(renderer, texture, nullptr, nullptr);
+    SDL_RenderPresent(renderer);
+
+    bool running = true;
+    while (running) {
+        SDL_Event event;
+        while (SDL_PollEvent(&event)) {
+            if (event.type == SDL_QUIT) {
+                running = false;
+            }
+        }
+    }
+
+    SDL_DestroyTexture(texture);
+    SDL_DestroyRenderer(renderer);
+    SDL_Quit();
+    return 0;
+}