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):
/*
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;
}