SDL Maze Generator

maze.cpp

#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;
}