Maze Generation

I, personally, like roguelikes that have levels entirely occupied by mazes.

Example

 #####################################################################
 ###############################.#.###################################
 ###############################.#.###################################
 #############################.....###################################
 #############################.#.#####################################
 #########################.#.......###################################
 #########################.#.#.#.#.###################################
 ###################.......#.#.#.#...###...#...#######################
 ###################.#####.#####.#.#.###.###.#########################
 #############.........#...#...#...#...#...#.#######...###############
 #################.###.#.#.#.#.#.#.###.###.#.#########.###############
 #############.....#...#...#...........#.#...###.#.....###############
 ###################.#.#.###.#.###.###.#.###.###.#.###################
 #################...#.#.....#.......#.......#...#.###################
 #################.#.#.#.###.#.#.###.#.#.#.#.#.###.###################
 #################.#.#...#...#.....#...#...........###################
 #################.###.#.###.#.#######.###.###########################
 #################...#...#...#...........#.#.....#####################
 #################.#####.#######.#.#######.#.#########################
 #############.....#...#.#.......#...#.......#.#.#####################
 #############.###.#.###.#.###.#.###.###.#.#.#.#.#####################
 #############.###.....#...........#.#...#.#...#.#####################
 #############.###.#.#.###.#.###.#.###.#.#.#.###.#####################
 #############...#...#.......#...#.....#.........#####################
 #############.###############.#.###########.###.#####################
 ###########.#.........#######.#.#########...#.#.#####################
 ###########.#######.#########.###########.###.#.#####################
 ###########.....###.#.#####...###########.....#...###################
 #############.#.###.#.###############################################
 #############.........###############################################
 #################.###################################################
 #############.....###################################################
 #############.#######################################################
 #############.#######################################################
 #############.#######################################################
 #############.#######################################################
 #############.#######################################################
 #############.#######################################################
 #####################################################################

Description

Here's a simple way to generate mazes:

1. Start from a cell and mark it 'visited'
2. Pick a direction.
3. If the nearest cell in that direction is 'unvisited' or you want to make a loop here, move to it.
4. Mark it 'visited'
5. Move until there is no space left.
6. Pick a random 'visited' cell.
7. Go to step 2 until you're satisfied with the maze.

Code

/* This program is free software. It comes without any warranty, to
 * the extent permitted by applicable law. You can redistribute it
 * and/or modify it under the terms of the Do What The Fuck You Want
 * To Public License, Version 2, as published by Sam Hocevar. See
 * http://sam.zoy.org/wtfpl/COPYING for more details. */ 
 
// NOTE: Since I like the c99 style, I've written this piece of code in it
// so compile with -std=c99!

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// a magic number!
#define magic 666

// the map's width and height
#define max_x 70
#define max_y 40

// distance from a cell to another (in map blocks)
#define cellrad 2

// max map cells
const int maxc_x=max_x/cellrad-1;
const int maxc_y=max_y/cellrad-1;

// the map and cell arrays
int map[max_x][max_y];
int cell[max_x/cellrad-1][max_y/cellrad-1];

// just some counters
int visited_cells=0,total_cells=0;


// this function returns 1 if (x,y) is in the range 2...max_x/y-2, to prevent some nasty bugs
int inrange(int x,int y)
{
    if (x>2 && y>2 && x<max_x-2 && y<max_y-2) return 1; return 0;
}

// this function links two cells together
void clink(int x1,int y1,int x2,int y2){
    int cx=x1,cy=y1;
    while(cx!=x2){
	if(x1>x2){cx--;}else{cx++;}
	if(inrange(cx,cy)==1) map[cx][cy]=0;}
    while(cy!=y2){
	if(y1>y2){cy--;}else{cy++;}
	if(inrange(cx,cy)==1) map[cx][cy]=0;}
}

// this function counts the visited cells and the total cells
void count_cells(void)
{
    visited_cells=0; total_cells=0;
    for(int ix=0;ix<maxc_x;ix++){
	for(int iy=0;iy<maxc_y;iy++){
	    total_cells++;
	    if (cell[ix][iy]==1) visited_cells++;
	}
    }
}

// this is the main maze-generating function
void mkmaze(void)
{
    // some ints for random x, random y and random direction
    int rx=0,ry=0,rd=0;
    // c is used to count tries -- if there are too many tries, the main loop
    // jumps to the end of the function
    int c=0;

    // we fill the map with 'walls'
    for(int ix=0;ix<max_x;ix++){
	for(int iy=0;iy<max_y;iy++){
	    map[ix][iy]=1;
	}
    }
    
    // and the cell array with 'unvisited' cells
    for(int ix=0;ix<maxc_x;ix++){
	for(int iy=0;iy<maxc_y;iy++){
	    cell[ix][iy]=0;
	}
    }
    
    // we choose a random (x,y) pair, but here we use the center of the screen instead
    rx=maxc_x/2;
    ry=maxc_y/2;
    
    // we mark that cell 'visited'
    cell[rx][ry]=1;
    
    // we count the cells
    count_cells();
    
    //and start the main loop!
    while( visited_cells < total_cells ){
    
	// c is increased, and we check whether it is too big
	c++;
	if (c>magic) goto hell;
	
	// we choose a random direction
	rd=rand()%4;
	
	// and then dig!
	if (rd==0){		    // up
	    if (inrange(rx*cellrad,ry*cellrad-1)==1 && (cell[rx][ry-1]==0 || rand()%7==6)){
		clink(rx*cellrad,ry*cellrad,rx*cellrad,(ry-1)*cellrad);
		ry--;
	    }else{
		while(1){
		    rx=rand()%maxc_x;
		    ry=rand()%maxc_y;
		    if (cell[rx][ry]==1) break;
		}
	    }
	}else if (rd==1) {	    //down
	    if (inrange(rx*cellrad,ry*cellrad+1)==1 && (cell[rx][ry+1]==0 || rand()%7==6)){
		clink(rx*cellrad,ry*cellrad,rx*cellrad,(ry+1)*cellrad);
		ry++;
	    }else{
		while(1){
		    rx=rand()%maxc_x;
		    ry=rand()%maxc_y;
		    if (cell[rx][ry]==1) break;
		}
	    }
	}else if (rd==2) {	    //left
	    if (inrange(rx*cellrad-1,ry*cellrad)==1 && (cell[rx-1][ry]==0 || rand()%7==6)){
		clink((rx-1)*cellrad,ry*cellrad,rx*cellrad,ry*cellrad);
		rx--;
	    }else{
		while(1){
		    rx=rand()%maxc_x;
		    ry=rand()%maxc_y;
		    if (cell[rx][ry]==1) break;
		}
	    }
	}else if (rd==3) {	    //right
	    if (inrange(rx*2+1,ry*2)==1 && (cell[rx+1][ry]==0 || rand()%7==6)){
		clink(rx*cellrad,ry*cellrad,(rx+1)*cellrad,ry*cellrad);
		rx++;
	    }else{
		while(1){
		    rx=rand()%maxc_x;
		    ry=rand()%maxc_y;
		    if (cell[rx][ry]==1) break;
		}
	    }
	}
	
	/* NOTE:    the above code checks whether the to-be-dug cell is free.
	 *	    If it isn't, and rand()%7==6, it links it anyway. This is used
	 *	    to give the maze loops, change 7 and 6 as you want to get different
	 *	    results */
	
	// now we mark the reached cell 'visited'
	cell[rx][ry]=1;
	
	// and we put a 'floor' tile on the map, where the maze cell should be
	map[rx*cellrad][ry*cellrad]=0;
	
	// now we count the cells, so we can know how many cells we've visited.
	count_cells();
    }
    
    // hell is a bad place. but we use it to put 'floor' tiles where we have a 'visited' cell
    hell:
    for(int ix=0;ix<maxc_x;ix++){
	for(int iy=0;iy<maxc_y;iy++){
	    if (cell[ix][iy]==1) map[ix*cellrad][iy*cellrad]=0;
	}
    }
}


// now this is a simple function that shows us what we just dug.
// it uses ANSI codes, so it may or may not work on your system
void showmap(void)
{
    printf("\033[2J\033[1;1f");
    for(int iy=0;iy<max_y;iy++){
	for(int ix=0;ix<max_x;ix++){
	    fprintf(stdout, "\033[%i;%if",iy,ix);
	    switch(map[ix][iy]){
		case 1: 
		    printf("#");
		    break;
		case 0:
		    printf(".");
		    break;
		default: 
		    printf("*");
		    break;
	    }
	printf("\n");
	}
    }
    printf("Done.\n");
}

// and now the main function...
int main(void)
{
    // we get a random seed
    srand(time(0));
    
    // we dig the maze
    mkmaze();
    
    // we show the map
    showmap();
    
    // and say 'goodbye'
    return 0;
}

Feel free to improve it, but please mention what exactly you changed. --Deveah.

Sceptre's Implementation

Really liked the look of the caves generated with this algorithm, but thought I could condense it a bit. Instead of a long series of conditional statements, I generalized the digging process by using a direction lookup Table. Pushed some global variables into macros, changed a few names, mostly trying to help readability. Also should compile on a non-c99 compiler.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAZE_W 60
#define MAZE_H 25

#define CELL_R 2

#define MAGIC 666

#define MAX_C_W (MAZE_W / CELL_R - 1)
#define MAX_C_H (MAZE_H / CELL_R - 1)

// This saves us from making a bunch of similar conditionals
// inside our Maze function.
int dirList[4][2] = { {0, -1}, {1, 0}, {0, 1}, {-1, 0} };

int map[MAZE_W][MAZE_H];
int cell[MAX_C_W][MAX_C_H];

void initGrid(void)
{
    int i, j;
    for (i = 0; i < MAZE_W; i++) {
        for (j = 0; j < MAZE_H; j++){
            map[i][j] = 1;
        }
    }
    // Since we're setting to 0, let's just memset and save ourselves the nested FOR loop.
    memset(cell, 0, sizeof(cell));
}

// Returns 1 if (x, y) wont jump us off map.
int inRange(int x, int y)
{
    if ( x > 2 && y > 2 && x < MAZE_W - 2 && y < MAZE_H - 2)
        return 1;
    return 0;
}

// Links our Cells
void linkCells(int x0, int y0, int x1, int y1)
{
    int cx = x0; int cy = y0;
    while(cx != x1) {
        if (x0 > x1)
            cx--;
        else
            cx++;
        if (inRange(cx, cy) == 1)
            map[cx][cy] = 0;
    }
    while(cy != y1) {
        if (y0 > y1)
            cy--;
        else
            cy++;
        if (inRange(cx, cy) == 1)
            map[cx][cy] = 0;
    }
}

// This function puts Floor Tiles on our map based on our larger 'cells'
void fillCells(void)
{
    int i, j;
    for (i = 0; i < MAX_C_W; i++ ){
        for (j = 0; j < MAX_C_H; j++){
            if (cell[i][j] == 1)
                map[i * CELL_R][j * CELL_R] = 0;
        }
    }
}

void makeMaze(void)
{   
    int rx = 0; int ry = 0;
    int dx; int dy;
    int dir = 0;
    int count = 0;

    int totalCells = MAX_C_W * MAX_C_H;

    initGrid();

    // Replace with desired startX/startY;
    rx = MAX_C_W / 2;
    ry = MAX_C_H / 2;

    cell[rx][ry] = 1;

    int visitedCells = 1; // The Cell we just assigned to 1!

    while( visitedCells < totalCells ) {

        count++;
        if (count < MAGIC){
            fillCells();
        }
        
        // Use Direction Lookup table for more Generic dig function.
        dir = rand()%4; 

        dx = dirList[dir][0];
        dy = dirList[dir][1];

        if(inRange(rx * CELL_R + dx, ry * CELL_R + dy) == 1 && cell[rx + dx][ry + dy] == 0 || rand()%7 == 6){
            linkCells(rx * CELL_R, ry * CELL_R, (rx+dx) * CELL_R, (ry+dy) * CELL_R);
            rx += dx;
            ry += dy;
        } else {
            do {
                rx = rand()% MAX_C_W;
                ry = rand()% MAX_C_H;
            } while ( cell[rx][ry] != 1 );
        }
        
        /* NOTE: Above code checks whether to-be-dug cell is free.
         *        If it isn't, and rand()%7 == 6, it links it anyways.
         *        This is done to create loops and give a more cavelike appearance.
         */
        
        cell[rx][ry] = 1;

        map[rx * CELL_R][ry * CELL_R] = 0;
        
        visitedCells++;
    }
    
    fillCells();
}

void printMaze(void)
{
    int i, j;
    for (j = 0; j < MAZE_H; j++){
        for (i = 0; i < MAZE_W; i++){
            if (map[i][j] == 1)
                printf("#");
            else if (map[i][j] == 0)
                printf(".");
        }
        printf("\n");
    }
    printf("VOILA!");
}

int main(void)
{
    srand(time(0));
    makeMaze();
    printMaze();

    return 0;
}

• Simple maze
• Dynamically Sized Maze