maze generator example

#include "surface.h"

#include <cstdlib>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

enum Dir {
    NORTH,
    EAST,
    SOUTH,
    WEST,

    DIR_COUNT
};

struct MazeCell
{
    bool can_join[DIR_COUNT]; // true if the cells can be considered for passage
    bool has_path[DIR_COUNT]; // true if there actually is a path in that dir

    bool visited; // prevents passing through a cell twice during mazegen

    bool special;   // if true, special color will be drawn over cell in output
    RGB special_color;

    MazeCell()
    {
        visited = false;
        special = false;

        for(int i = 0; i < DIR_COUNT; i++)
        {
            can_join[i] = true;  // by default, allow consideration of neighbors
            has_path[i] = false; // but don't actually make any paths
        }
    }
};

struct Point
{
    int x;
    int y;

    Point() : x(0), y(0) {}
    Point(int X, int Y) : x(X), y(Y) {}
};

// gives the opposite direction (e.g. NORTH -> SOUTH)
Dir mirror(int dir)
{
    switch(dir)
    {
        case NORTH:
            return SOUTH;

        case EAST:
            return WEST;

        case SOUTH:
            return NORTH;

        case WEST:
            return EAST;

        default:
            fprintf(stderr, "FATAL: Invalid direction\n");
            exit(1);
    }
}

// Returns the indicated point shifted by one step in the indicated direction
Point point_offset(Point here, int dir)
{
    switch(dir)
    {
        case NORTH:
            return Point(here.x, here.y-1);
        case SOUTH:
            return Point(here.x, here.y+1);
        case EAST:
            return Point(here.x+1, here.y);
        case WEST:
            return Point(here.x-1, here.y);

        default:
            fprintf(stderr, "FATAL: Invalid direction in point_offset\n");
            exit(1);
    }
}

// marks two cells such that a cell at (x,y) and its neighbor in the indicated
// direction both have flags set to indicate that there is a path between them
void break_wall(Surface<MazeCell>& maze, int x, int y, int dir)
{
    if(!maze.bounds_check(x,y))
        return;

    Point here(x, y);
    MazeCell& here_cell = maze.at(x,y);
    here_cell.has_path[dir] = true;

    Point there = point_offset(here, dir);
    int opposite = mirror(dir);

    if(!maze.bounds_check(there.x, there.y))
        return;

    MazeCell& there_cell = maze.at(there.x, there.y);
    there_cell.has_path[opposite] = true;
}

// marks two cells to disconnect them from each other in the graph.
// this will make it so that the maze generator cannot move from one cell
// to its neighbor and vice-versa.
void prevent_path(Surface<MazeCell>& maze, int x, int y, int dir)
{
    if(!maze.bounds_check(x,y))
        return;

    Point here(x, y);
    MazeCell& here_cell = maze.at(x,y);
    here_cell.can_join[dir] = false;
    here_cell.has_path[dir] = false;

    Point there = point_offset(here, dir);
    int opposite = mirror(dir);

    MazeCell& there_cell = maze.at(there.x, there.y);
    there_cell.can_join[opposite] = false;
    there_cell.has_path[opposite] = false;
}

// given a vector of directions, pick one at random
// this is not a very good randomizer, but it was really simple to implement
Dir pick_random(const vector<Dir>& v)
{
    return v[rand() % v.size()];
}

void mazegen(Surface<MazeCell>& maze, Point start)
{
    stack<Point> s;
    s.push(start);

    while(!s.empty())
    {
        Point here = s.top();

        MazeCell& here_cell = maze.at(here.x, here.y);
        here_cell.visited = true; // mark it so we don't pass back through it

        // pick a random neighbor and traverse in that direction
        vector<Dir> neighbors;

        for(int dir = 0; dir < DIR_COUNT; dir++)
        {
            Point there = point_offset(here, dir);

            if(!here_cell.can_join[dir])
                continue;   // user requested we don't travel that way

            if(!maze.bounds_check(there.x, there.y))
                continue;   // neighbor is out of bounds of map

            MazeCell& there_cell = maze.at(there.x, there.y);

            if(there_cell.visited)
                continue;   // we've already made a path through that cell

            neighbors.push_back((Dir)dir);
        }

        // no where to go further on this path; go back and choose another way
        if(neighbors.size() == 0)
        {
            s.pop();
            continue;
        }

        Dir go_dir = pick_random(neighbors);
        break_wall(maze, here.x, here.y, go_dir);
        Point there = point_offset(here, go_dir);

        s.push(there);
    }
}

void draw_maze(RGBSurface& output, const Surface<MazeCell>& input)
{
    RGB bgcolor(0,0,0x7F);

    RGBSurface space;   // image to draw an open space
    RGBSurface wall;    // image to draw a wall
    RGBSurface special; // image to highlight an area for special emphasis


    if(!load_image(wall, "wall.png"))
    {
        fprintf(stderr, "Failed to load wall.png\n");
        wall.resize(32, 32);
        wall.fill(RGB(0,0,0));
    }

    space.resize(wall.width(), wall.height());
    space.fill(bgcolor);

    special.resize(wall.width(), wall.height());

    output.resize(
        2*wall.width()*input.width() + wall.width(),
        2*wall.height()*input.height() + wall.height()
    );

    // convenience macro to calculate pixel positions relative to a maze cell
    // and the local wall-scale offset.
    // e.g. X(0,0) corresponds to the first * in the diagram below,
    //      X(0,1) corresponds to the first N in the diagram below,
    //      X(1,0) corresponds to the 2nd * in the diagram below, etc.
    #define X(xx, off) (wall.width() * (2*xx + off))
    #define Y(yy, off) (wall.height() * (2*yy + off))

    // fill walls in 2x2 block pattern:
    //
    //    * N  * N  * N
    //    W _  W _  W _  ...
    //
    //    * N  * N  * N
    //    W _  W _  W _
    //
    //    ...
    //

    for(int iy = 0; iy < input.height(); iy++)
    for(int ix = 0; ix < input.width(); ix++)
    {
        blit(output, wall, X(ix, 0), Y(iy, 0));
        blit(output, wall, X(ix, 1), Y(iy, 0));
        blit(output, wall, X(ix, 0), Y(iy, 1));
        blit(output, wall, X(ix, 1), Y(iy, 1));
    }

    // draw EAST/SOUTH extreme border walls as a special case step
    for(int y = 0; y < input.height(); y++)
    {
        blit(output, wall, X(input.width(), 0), Y(y, 0));
        blit(output, wall, X(input.width(), 0), Y(y, 1));
    }

    for(int x = 0; x < input.width(); x++)
    {
        blit(output, wall, X(x, 0), Y(input.height(), 0));
        blit(output, wall, X(x, 1), Y(input.height(), 0));
    }

    // draw final corner on SE edge
    blit(output, wall, X(input.width(), 0), Y(input.height(), 0));


    // traverse the grid knocking down walls where open paths should be
    for(int iy = 0; iy < input.height(); iy++)
    for(int ix = 0; ix < input.width(); ix++)
    {
        // draw open space for cell
        blit(output, space, X(ix,1), Y(iy, 1));

        // draw N/E/S/W paths
        // yes, this does more work that strictly necessary...
        const MazeCell& input_here = input.at(ix, iy);

        if(input_here.has_path[NORTH])
            blit(output, space, X(ix,1), Y(iy,0));

        if(input_here.has_path[EAST])
            blit(output, space, X(ix,2), Y(iy,1));

        if(input_here.has_path[SOUTH])
            blit(output, space, X(ix,1), Y(iy,2));

        if(input_here.has_path[WEST])
            blit(output, space, X(ix,0), Y(iy,1));

        // allow special coloring to override regular behavior
        // bit of an ugly hack to allow adding emphasis
        if(input_here.special)
        {
            special.fill(input_here.special_color);
            blit(output, special, X(ix, 1), Y(iy, 1));
        }
    }
}

int main()
{
    //srand(12345);
    srand(554433);

    Surface<MazeCell> maze(15,15);
    RGBSurface output_image;

    // build a square in the middle
    for(int y = 5; y < 10; y++)
    {
        prevent_path(maze, 5, y, EAST);
        prevent_path(maze, 10, y, WEST);
    }

    for(int x = 5; x < 10; x++)
    {
        prevent_path(maze, x, 5, SOUTH);
        prevent_path(maze, x, 10, NORTH);
    }

    // emphasize the block in the middle by coloring it red
    for(int y = 6; y < 10; y++)
    for(int x = 6; x < 10; x++)
    {
        maze.at(x,y).special = true;
        maze.at(x,y).special_color = RGB(0xFF,0,0);
    }

    // generate a maze starting from the top-left corner
    mazegen(maze, Point(0,0));

    draw_maze(output_image, maze);
    save_png(output_image, "output.png");
}