Maze Generation

From RogueBasin
Revision as of 11:59, 10 September 2009 by Deveah (talk | contribs)
Jump to navigation Jump to search

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

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


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.

Now here's the code (written in C):

/*
    Copyright (c) 2009 Vlad Dumitru ("Deveah")

    Permission is hereby granted, free of charge, to any person
    obtaining a copy of this software and associated documentation
    files (the "Software"), to deal in the Software without
    restriction, including without limitation the rights to use,
    copy, modify, merge, publish, distribute, sublicense, and/or sell
    copies of the Software, and to permit persons to whom the
    Software is furnished to do so, subject to the following
    conditions:

    The above copyright notice and this permission notice shall be
    included in all copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
    OTHER DEALINGS IN THE SOFTWARE.

 */
 
// 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.