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