ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/deliantra/server/random_maps/maze_gen.C
(Generate patch)

Comparing deliantra/server/random_maps/maze_gen.C (file contents):
Revision 1.6 by root, Thu Jan 18 19:42:10 2007 UTC vs.
Revision 1.8 by root, Fri Apr 11 21:09:53 2008 UTC

… …
13 13
14/* we need to maintain a list of wall points to generate 14/* we need to maintain a list of wall points to generate
15 reasonable mazes: a straightforward recursive random walk maze 15 reasonable mazes: a straightforward recursive random walk maze
16 generator would generate a map with a trivial circle-the-outer-wall solution */ 16 generator would generate a map with a trivial circle-the-outer-wall solution */
17 17
18#include <stdio.h>
19#include <global.h> 18#include <global.h>
20 19
21/*#include <random_map.h>*/ 20#include "random_map.h"
22#include <maze_gen.h> 21#include "rproto.h"
23#include <time.h>
24
25
26/* this include solely, and only, is needed for the definition of RANDOM */
27
28
29 22
30/* global variables that everyone needs: don't want to pass them in 23/* global variables that everyone needs: don't want to pass them in
31 as parameters every time. */ 24 as parameters every time. */
32int *wall_x_list = 0; 25int *wall_x_list = 0;
33int *wall_y_list = 0; 26int *wall_y_list = 0;
… …
40 33
41/* the outsize interface routine: accepts sizes, returns a char 34/* the outsize interface routine: accepts sizes, returns a char
42** maze. option is a flag for either a sparse or a full maze. Sparse 35** maze. option is a flag for either a sparse or a full maze. Sparse
43mazes have sizable rooms. option = 1, full, 0, sparse.*/ 36mazes have sizable rooms. option = 1, full, 0, sparse.*/
44 37
45char ** 38Maze
46maze_gen (int xsize, int ysize, int option) 39maze_gen (int xsize, int ysize, int option)
47{ 40{
48 int i, j; 41 int i, j;
49 42
50 /* allocate that array, set it up */ 43 Maze maze (xsize, ysize);
51 char **maze = (char **) calloc (sizeof (char *), xsize);
52
53 for (i = 0; i < xsize; i++)
54 {
55 maze[i] = (char *) calloc (sizeof (char), ysize);
56 }
57 44
58 /* write the outer walls */ 45 /* write the outer walls */
59 for (i = 0; i < xsize; i++) 46 for (i = 0; i < xsize; i++) maze[i][0] = maze[i][ysize - 1] = '#';
60 maze[i][0] = maze[i][ysize - 1] = '#'; 47 for (j = 0; j < ysize; j++) maze[0][j] = maze[xsize - 1][j] = '#';
61 for (j = 0; j < ysize; j++)
62 maze[0][j] = maze[xsize - 1][j] = '#';
63
64 48
65 /* find how many free wall spots there are */ 49 /* find how many free wall spots there are */
66 wall_free_size = 2 * (xsize - 4) + 2 * (ysize - 4); 50 wall_free_size = 2 * (xsize - 4) + 2 * (ysize - 4);
67 51
68 make_wall_free_list (xsize, ysize); 52 make_wall_free_list (xsize, ysize);
… …
74 /* recursively generate the walls of the maze */ 58 /* recursively generate the walls of the maze */
75 /* first pop a random starting point */ 59 /* first pop a random starting point */
76 while (wall_free_size > 0) 60 while (wall_free_size > 0)
77 { 61 {
78 pop_wall_point (&i, &j); 62 pop_wall_point (&i, &j);
63
79 if (option) 64 if (option)
80 fill_maze_full (maze, i, j, xsize, ysize); 65 fill_maze_full (maze, i, j, xsize, ysize);
81 else 66 else
82 fill_maze_sparse (maze, i, j, xsize, ysize); 67 fill_maze_sparse (maze, i, j, xsize, ysize);
83 } 68 }
… …
88 free (wall_y_list); 73 free (wall_y_list);
89 74
90 return maze; 75 return maze;
91} 76}
92 77
93
94
95/* the free wall points are those outer points which aren't corners or 78/* the free wall points are those outer points which aren't corners or
96 near corners, and don't have a maze wall growing out of them already. */ 79 near corners, and don't have a maze wall growing out of them already. */
97
98void 80void
99make_wall_free_list (int xsize, int ysize) 81make_wall_free_list (int xsize, int ysize)
100{ 82{
101 int i, j, count; 83 int i, j, count;
102 84
103 count = 0; /* entries already placed in the free list */ 85 count = 0; /* entries already placed in the free list */
104 /*allocate it */ 86 /*allocate it */
105 if (wall_free_size < 0) 87 if (wall_free_size < 0)
106 return; 88 return;
89
107 wall_x_list = (int *) calloc (sizeof (int), wall_free_size); 90 wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
108 wall_y_list = (int *) calloc (sizeof (int), wall_free_size); 91 wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
109
110 92
111 /* top and bottom wall */ 93 /* top and bottom wall */
112 for (i = 2; i < xsize - 2; i++) 94 for (i = 2; i < xsize - 2; i++)
113 { 95 {
114 wall_x_list[count] = i; 96 wall_x_list[count] = i;
… …
129 wall_y_list[count] = j; 111 wall_y_list[count] = j;
130 count++; 112 count++;
131 } 113 }
132} 114}
133 115
134
135
136/* randomly returns one of the elements from the wall point list */ 116/* randomly returns one of the elements from the wall point list */
137
138void 117void
139pop_wall_point (int *x, int *y) 118pop_wall_point (int *x, int *y)
140{ 119{
141 int index = RANDOM () % wall_free_size; 120 int index = rndm (wall_free_size);
142 121
143 *x = wall_x_list[index]; 122 *x = wall_x_list[index];
144 *y = wall_y_list[index]; 123 *y = wall_y_list[index];
145 /* write the last array point here */ 124 /* write the last array point here */
146 wall_x_list[index] = wall_x_list[wall_free_size - 1]; 125 wall_x_list[index] = wall_x_list[wall_free_size - 1];
147 wall_y_list[index] = wall_y_list[wall_free_size - 1]; 126 wall_y_list[index] = wall_y_list[wall_free_size - 1];
148 wall_free_size--; 127 wall_free_size--;
149} 128}
150 129
151
152
153/* find free point: randomly look for a square adjacent to this one where 130/* find free point: randomly look for a square adjacent to this one where
154we can place a new block without closing a path. We may only look 131we can place a new block without closing a path. We may only look
155up, down, right, or left. */ 132up, down, right, or left. */
156
157int 133int
158find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize) 134find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
159{ 135{
160 136
161/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */ 137/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
… …
224 if (count == 0) 200 if (count == 0)
225 return -1; /* failed to find any clear points */ 201 return -1; /* failed to find any clear points */
226 202
227 /* choose a random direction */ 203 /* choose a random direction */
228 if (count > 1) 204 if (count > 1)
229 count = RANDOM () % count; 205 count = rndm (count);
230 else 206 else
231 count = 0; 207 count = 0;
208
232 switch (dirlist[count]) 209 switch (dirlist[count])
233 { 210 {
234 case 1: /* up */ 211 case 1: /* up */
235 { 212 {
236 *y = yc + 1; 213 *y = yc + 1;
… …
254 *x = xc - 1; 231 *x = xc - 1;
255 *y = yc; 232 *y = yc;
256 break; 233 break;
257 } 234 }
258 default: /* ??? */ 235 default: /* ??? */
259 {
260 return -1; 236 return -1;
261 } 237
262 } 238 }
263 return 1; 239 return 1;
264} 240}
265 241
266/* recursive routine which will fill every available space in the maze 242/* recursive routine which will fill every available space in the maze
… …
286 { 262 {
287 fill_maze_full (maze, xc, yc, xsize, ysize); 263 fill_maze_full (maze, xc, yc, xsize, ysize);
288 } 264 }
289} 265}
290 266
291
292/* recursive routine which will fill much of the maze, but will leave 267/* recursive routine which will fill much of the maze, but will leave
293 some free spots (possibly large) toward the center.*/ 268 some free spots (possibly large) toward the center.*/
294
295void 269void
296fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize) 270fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
297{ 271{
298 int xc, yc; 272 int xc, yc;
299 273
… …
307 fill_maze_sparse (maze, xc, yc, xsize, ysize); 281 fill_maze_sparse (maze, xc, yc, xsize, ysize);
308 } 282 }
309 283
310 /* change the if to a while for a complete maze. */ 284 /* change the if to a while for a complete maze. */
311 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1) 285 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
312 {
313 fill_maze_sparse (maze, xc, yc, xsize, ysize); 286 fill_maze_sparse (maze, xc, yc, xsize, ysize);
314 }
315} 287}

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines