server/random_maps/maze_gen.C

/*
 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
 *
 * Copyright (©) 2017,2018 Marc Alexander Lehmann / the Deliantra team
 * Copyright (©) 2005,2006,2007,2008,2009,2010,2011,2012,2013,2014,2015,2016 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
 * Copyright (©) 1994-2004 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
 * <http://www.gnu.org/licenses/>.
 *
 * The authors can be reached via e-mail to <support@deliantra.net>
 */

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

#include <global.h>

#include <rmg.h>
#include "rproto.h"

/* global variables that everyone needs:  don't want to pass them in
   as parameters every time. */
static fixed_stack<point> seeds;
static int xsize, ysize;
static char **maze;

static void
push (point p)
{
  seeds.push (p);
  maze [p.x][p.y] = '#';
}

/* randomly returns one of the elements from the wall point list */
static point
pop_rand ()
{
  return seeds.remove (rmg_rndm (seeds.size));
}

/*  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
push_walls ()
{
  /* top and bottom wall */
  for (int x = 2; x < xsize - 2; x++)
    {
      push (point (x,         0));
      push (point (x, ysize - 1));
    }

  /* left and right wall */
  for (int y = 2; y < ysize - 2; y++)
    {
      push (point (        0, y));
      push (point (xsize - 1, y));
    }
}

/* 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 (point &p, point pc)
{
  /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
  int dirlist[4];
  int count = 0;                /* # elements in dirlist */

  int xc = pc.x;
  int yc = pc.y;

  /* 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 */
        p.x = xc;
        p.y = yc + 1;
        break;

      case 2:                  /* down */
        p.x = xc;
        p.y = yc - 1;
        break;

      case 3:                  /* right */
        p.x = xc + 1;
        p.y = yc;
        break;
        
      case 4:                  /* left */
        p.x = xc - 1;
        p.y = yc;
        break;
    }

  return 1;
}

/* 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 = 3=full, 2=braided, 1=sparse, 0=rooms.*/
void
maze_gen (layout &maze, int subtype)
{
  xsize = maze.w;
  ysize = maze.h;
  ::maze = maze;

  maze.clear ();
  maze.border ();

  if (xsize < 4 || ysize < 4)
    return;

  seeds.reset (xsize * ysize);

  if (subtype > 0)
    push_walls ();

  if (subtype == 0 || subtype == 2)
    for (int i = (xsize + ysize) / 2; i; --i)
      push (point (rmg_rndm (1, xsize - 2), rmg_rndm (1, ysize - 2)));

  bool full = subtype == 3;

  /* recursively generate the walls of the maze */
  /* first pop a random starting point */
  while (seeds.size)
    {
      point p = pop_rand ();

      for (;;)
        {
          point pc;

          maze [p.x][p.y] = '#';

          if (find_free_point (pc, p) < 0)
            break;

          if (full)
            push (p);

          if (!rmg_rndm (8))
            {
              if (!full)
                push (pc);

              break;
            }

          p = pc;
        }
    }

  seeds.free ();
}

Revision:	1.31
Committed:	Sat Nov 17 23:40:02 2018 UTC (5 years, 7 months ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.30:	+1 -0 lines
Log Message:	copyright update 2018
#	User	Rev	Content
1	root	1.16	/*
2			* This file is part of Deliantra, the Roguelike Realtime MMORPG.
3	root	1.29	*
4	root	1.31	* Copyright (©) 2017,2018 Marc Alexander Lehmann / the Deliantra team
5	root	1.30	* Copyright (©) 2005,2006,2007,2008,2009,2010,2011,2012,2013,2014,2015,2016 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
6	root	1.27	* Copyright (©) 1994-2004 Crossfire Development Team (restored, original file without copyright notice)
7	root	1.29	*
8	root	1.16	* Deliantra is free software: you can redistribute it and/or modify it under
9			* the terms of the Affero GNU General Public License as published by the
10			* Free Software Foundation, either version 3 of the License, or (at your
11			* option) any later version.
12	root	1.29	*
13	root	1.16	* This program is distributed in the hope that it will be useful,
14			* but WITHOUT ANY WARRANTY; without even the implied warranty of
15			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16			* GNU General Public License for more details.
17	root	1.29	*
18	root	1.16	* You should have received a copy of the Affero GNU General Public License
19			* and the GNU General Public License along with this program. If not, see
20			* <http://www.gnu.org/licenses/>.
21	root	1.29	*
22	root	1.16	* The authors can be reached via e-mail to <support@deliantra.net>
23			*/
24	root	1.5
25	elmex	1.1	/* peterm@langmuir.eecs.berkeley.edu: this function generates a random
26			blocked maze with the property that there is only one path from one spot
27			to any other, and there is always a path from one spot to any other.
28
29			input: xsize, ysize;
30			output: a char** array with # and . for closed and open respectively.
31
32			a char value of 0 represents a blank space: a '#' is
33			a wall.
34
35			*/
36
37			/* we need to maintain a list of wall points to generate
38			reasonable mazes: a straightforward recursive random walk maze
39			generator would generate a map with a trivial circle-the-outer-wall solution */
40
41	root	1.20	#include <vector>
42
43	elmex	1.1	#include <global.h>
44	root	1.3
45	root	1.26	#include <rmg.h>
46	root	1.8	#include "rproto.h"
47	elmex	1.1
48			/* global variables that everyone needs: don't want to pass them in
49			as parameters every time. */
50	root	1.23	static fixed_stack<point> seeds;
51	root	1.19	static int xsize, ysize;
52	root	1.20	static char **maze;
53	elmex	1.1
54	root	1.21	static void
55			push (point p)
56			{
57	root	1.23	seeds.push (p);
58			maze [p.x][p.y] = '#';
59			}
60	root	1.21
61	root	1.23	/* randomly returns one of the elements from the wall point list */
62			static point
63			pop_rand ()
64			{
65			return seeds.remove (rmg_rndm (seeds.size));
66	root	1.21	}
67
68	elmex	1.1	/* the free wall points are those outer points which aren't corners or
69			near corners, and don't have a maze wall growing out of them already. */
70	root	1.14	static void
71	root	1.21	push_walls ()
72	root	1.3	{
73	elmex	1.1	/* top and bottom wall */
74	root	1.20	for (int x = 2; x < xsize - 2; x++)
75	root	1.3	{
76	root	1.21	push (point (x, 0));
77			push (point (x, ysize - 1));
78	root	1.3	}
79	elmex	1.1
80			/* left and right wall */
81	root	1.20	for (int y = 2; y < ysize - 2; y++)
82	root	1.3	{
83	root	1.21	push (point ( 0, y));
84			push (point (xsize - 1, y));
85	root	1.3	}
86	elmex	1.1	}
87
88			/* find free point: randomly look for a square adjacent to this one where
89			we can place a new block without closing a path. We may only look
90			up, down, right, or left. */
91	root	1.14	static int
92	root	1.20	find_free_point (point &p, point pc)
93	root	1.3	{
94	root	1.12	/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
95	root	1.3	int dirlist[4];
96			int count = 0; /* # elements in dirlist */
97	elmex	1.1
98	root	1.20	int xc = pc.x;
99			int yc = pc.y;
100
101	elmex	1.1	/* look up */
102	root	1.3	if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
103	elmex	1.1	{
104	root	1.17	int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + maze[xc + 1][yc + 1]
105			+ maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2];
106	root	1.3
107			if (cleartest == 0)
108	root	1.12	dirlist[count++] = 1;
109	elmex	1.1	}
110
111			/* look down */
112	root	1.3	if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
113	elmex	1.1	{
114	root	1.17	int cleartest = maze[xc][yc - 1] + maze[xc - 1][yc - 1] + maze[xc + 1][yc - 1]
115			+ maze[xc][yc - 2] + maze[xc - 1][yc - 2] + maze[xc + 1][yc - 2];
116	root	1.3
117			if (cleartest == 0)
118	root	1.12	dirlist[count++] = 2;
119	elmex	1.1	}
120
121			/* look right */
122	root	1.3	if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
123	elmex	1.1	{
124	root	1.17	int cleartest = maze[xc + 1][yc] + maze[xc + 1][yc - 1] + maze[xc + 1][yc + 1]
125			+ maze[xc + 2][yc] + maze[xc + 2][yc - 1] + maze[xc + 2][yc + 1];
126	root	1.3
127			if (cleartest == 0)
128	root	1.12	dirlist[count++] = 3;
129	elmex	1.1	}
130
131			/* look left */
132	root	1.3	if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
133	elmex	1.1	{
134	root	1.17	int cleartest = maze[xc - 1][yc] + maze[xc - 1][yc - 1] + maze[xc - 1][yc + 1]
135			+ maze[xc - 2][yc] + maze[xc - 2][yc - 1] + maze[xc - 2][yc + 1];
136	root	1.2
137	root	1.3	if (cleartest == 0)
138	root	1.12	dirlist[count++] = 4;
139	elmex	1.1	}
140
141	root	1.3	if (count == 0)
142			return -1; /* failed to find any clear points */
143	elmex	1.1
144			/* choose a random direction */
145	root	1.12	switch (dirlist [rmg_rndm (count)])
146	elmex	1.1	{
147	root	1.5	case 1: /* up */
148	root	1.20	p.x = xc;
149			p.y = yc + 1;
150	root	1.12	break;
151
152	root	1.5	case 2: /* down */
153	root	1.20	p.x = xc;
154			p.y = yc - 1;
155	root	1.12	break;
156
157	root	1.5	case 3: /* right */
158	root	1.20	p.x = xc + 1;
159			p.y = yc;
160	root	1.12	break;
161
162	root	1.5	case 4: /* left */
163	root	1.20	p.x = xc - 1;
164			p.y = yc;
165	root	1.12	break;
166	elmex	1.1	}
167	root	1.12
168	elmex	1.1	return 1;
169			}
170
171	root	1.13	/* the outsize interface routine: accepts sizes, returns a char
172			** maze. option is a flag for either a sparse or a full maze. Sparse
173	root	1.21	mazes have sizable rooms. option = 3=full, 2=braided, 1=sparse, 0=rooms.*/
174	root	1.13	void
175	root	1.25	maze_gen (layout &maze, int subtype)
176	root	1.13	{
177	root	1.24	xsize = maze.w;
178			ysize = maze.h;
179	root	1.20	::maze = maze;
180	root	1.19
181	root	1.24	maze.clear ();
182			maze.border ();
183	root	1.13
184	root	1.20	if (xsize < 4 \|\| ysize < 4)
185			return;
186	root	1.13
187	root	1.23	seeds.reset (xsize * ysize);
188	root	1.21
189			if (subtype > 0)
190			push_walls ();
191
192			if (subtype == 0 \|\| subtype == 2)
193			for (int i = (xsize + ysize) / 2; i; --i)
194			push (point (rmg_rndm (1, xsize - 2), rmg_rndm (1, ysize - 2)));
195
196			bool full = subtype == 3;
197	root	1.13
198			/* recursively generate the walls of the maze */
199			/* first pop a random starting point */
200	root	1.23	while (seeds.size)
201	root	1.21	{
202			point p = pop_rand ();
203
204			for (;;)
205			{
206			point pc;
207
208			maze [p.x][p.y] = '#';
209
210			if (find_free_point (pc, p) < 0)
211			break;
212
213			if (full)
214			push (p);
215
216			if (!rmg_rndm (8))
217			{
218			if (!full)
219			push (pc);
220
221			break;
222			}
223
224			p = pc;
225			}
226			}
227	root	1.13
228	root	1.23	seeds.free ();
229	root	1.13	}
230