Maze Generation
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):
/*
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
Version 2, December 2004
Copyright (C) 2004 Sam Hocevar <sam@hocevar.net>
Everyone is permitted to copy and distribute verbatim or modified
copies of this license document, and changing it is allowed as long
as the name is changed.
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
0. You just DO WHAT THE FUCK YOU WANT TO.
*/
// 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.