/*
* This file is part of Deliantra, the Roguelike Realtime MMORPG.
*
* Copyright (©) 2005,2006,2007,2008,2009 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
* Copyright (©) Crossfire Development Team (restored, original file without copyright notice)
*
* Deliantra is free software: you can redistribute it and/or modify it under
* the terms of the Affero GNU General Public License as published by the
* Free Software Foundation, either version 3 of the License, or (at your
* option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the Affero GNU General Public License
* and the GNU General Public License along with this program. If not, see
* .
*
* The authors can be reached via e-mail to
*/
/* peterm@langmuir.eecs.berkeley.edu: this function generates a random
blocked maze with the property that there is only one path from one spot
to any other, and there is always a path from one spot to any other.
input: xsize, ysize;
output: a char** array with # and . for closed and open respectively.
a char value of 0 represents a blank space: a '#' is
a wall.
*/
/* we need to maintain a list of wall points to generate
reasonable mazes: a straightforward recursive random walk maze
generator would generate a map with a trivial circle-the-outer-wall solution */
#include
#include "random_map.h"
#include "rproto.h"
/* global variables that everyone needs: don't want to pass them in
as parameters every time. */
static int *wall_x_list = 0;
static int *wall_y_list = 0;
static int wall_free_size = 0;
/* the free wall points are those outer points which aren't corners or
near corners, and don't have a maze wall growing out of them already. */
static void
make_wall_free_list (int xsize, int ysize)
{
int i, j, count;
count = 0; /* entries already placed in the free list */
/*allocate it */
if (wall_free_size < 0)
return;
wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
/* top and bottom wall */
for (i = 2; i < xsize - 2; i++)
{
wall_x_list[count] = i;
wall_y_list[count] = 0;
count++;
wall_x_list[count] = i;
wall_y_list[count] = ysize - 1;
count++;
}
/* left and right wall */
for (j = 2; j < ysize - 2; j++)
{
wall_x_list[count] = 0;
wall_y_list[count] = j;
count++;
wall_x_list[count] = xsize - 1;
wall_y_list[count] = j;
count++;
}
}
/* randomly returns one of the elements from the wall point list */
static void
pop_wall_point (int *x, int *y)
{
int index = rmg_rndm (wall_free_size);
*x = wall_x_list[index];
*y = wall_y_list[index];
/* write the last array point here */
wall_x_list[index] = wall_x_list[wall_free_size - 1];
wall_y_list[index] = wall_y_list[wall_free_size - 1];
wall_free_size--;
}
/* find free point: randomly look for a square adjacent to this one where
we can place a new block without closing a path. We may only look
up, down, right, or left. */
static int
find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
{
/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
int dirlist[4];
int count = 0; /* # elements in dirlist */
/* look up */
if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
{
int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + maze[xc + 1][yc + 1]
+ maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2];
if (cleartest == 0)
dirlist[count++] = 1;
}
/* look down */
if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
{
int cleartest = maze[xc][yc - 1] + maze[xc - 1][yc - 1] + maze[xc + 1][yc - 1]
+ maze[xc][yc - 2] + maze[xc - 1][yc - 2] + maze[xc + 1][yc - 2];
if (cleartest == 0)
dirlist[count++] = 2;
}
/* look right */
if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
{
int cleartest = maze[xc + 1][yc] + maze[xc + 1][yc - 1] + maze[xc + 1][yc + 1]
+ maze[xc + 2][yc] + maze[xc + 2][yc - 1] + maze[xc + 2][yc + 1];
if (cleartest == 0)
dirlist[count++] = 3;
}
/* look left */
if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
{
int cleartest = maze[xc - 1][yc] + maze[xc - 1][yc - 1] + maze[xc - 1][yc + 1]
+ maze[xc - 2][yc] + maze[xc - 2][yc - 1] + maze[xc - 2][yc + 1];
if (cleartest == 0)
dirlist[count++] = 4;
}
if (count == 0)
return -1; /* failed to find any clear points */
/* choose a random direction */
switch (dirlist [rmg_rndm (count)])
{
case 1: /* up */
*y = yc + 1;
*x = xc;
break;
case 2: /* down */
*y = yc - 1;
*x = xc;
break;
case 3: /* right */
*y = yc;
*x = xc + 1;
break;
case 4: /* left */
*x = xc - 1;
*y = yc;
break;
}
return 1;
}
/* recursive routine which will fill every available space in the maze
with walls*/
static void
fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
{
int xc, yc;
/* write a wall here */
maze[x][y] = '#';
/* decide if we're going to pick from the wall_free_list */
if (rmg_rndm (2) && wall_free_size > 0)
{
pop_wall_point (&xc, &yc);
fill_maze_full (maze, xc, yc, xsize, ysize);
}
/* change the while to an if for a sparse maze. */
while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
fill_maze_full (maze, xc, yc, xsize, ysize);
}
/* recursive routine which will fill much of the maze, but will leave
some free spots (possibly large) toward the center.*/
static void
fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
{
int xc, yc;
/* write a wall here */
maze[x][y] = '#';
/* decide if we're going to pick from the wall_free_list */
if (rmg_rndm (2) && wall_free_size > 0)
{
pop_wall_point (&xc, &yc);
fill_maze_sparse (maze, xc, yc, xsize, ysize);
}
/* change the if to a while for a complete maze. */
if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
fill_maze_sparse (maze, xc, yc, xsize, ysize);
}
/* the outsize interface routine: accepts sizes, returns a char
** maze. option is a flag for either a sparse or a full maze. Sparse
mazes have sizable rooms. option = 1, full, 0, sparse.*/
void
maze_gen (Layout maze, int full)
{
maze->clear ();
maze->border ();
/* find how many free wall spots there are */
wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
make_wall_free_list (maze->w, maze->h);
/* return the empty maze */
if (wall_free_size <= 0)
return;
/* recursively generate the walls of the maze */
/* first pop a random starting point */
while (wall_free_size > 0)
{
int i, j;
pop_wall_point (&i, &j);
if (full)
fill_maze_full (maze, i, j, maze->w, maze->h);
else
fill_maze_sparse (maze, i, j, maze->w, maze->h);
}
/* clean up our intermediate data structures. */
free (wall_x_list);
free (wall_y_list);
}
#if 0
static struct demo
{
demo ()
{
Layout layout (30, 30);
rmg_rndm.seed (time (0));
for(int i=1;i<10;++i)
{
maze_gen (layout, 1);
layout.print ();
}
exit (1);
}
} demo;
#endif