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.7 by root, Sat Jan 27 02:19:37 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 22
25/* 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
26 as parameters every time. */ 24 as parameters every time. */
27int *wall_x_list = 0; 25int *wall_x_list = 0;
28int *wall_y_list = 0; 26int *wall_y_list = 0;
… …
35 33
36/* the outsize interface routine: accepts sizes, returns a char 34/* the outsize interface routine: accepts sizes, returns a char
37** 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
38mazes have sizable rooms. option = 1, full, 0, sparse.*/ 36mazes have sizable rooms. option = 1, full, 0, sparse.*/
39 37
40char ** 38Maze
41maze_gen (int xsize, int ysize, int option) 39maze_gen (int xsize, int ysize, int option)
42{ 40{
43 int i, j; 41 int i, j;
44 42
45 /* allocate that array, set it up */ 43 Maze maze (xsize, ysize);
46 char **maze = (char **) calloc (sizeof (char *), xsize);
47
48 for (i = 0; i < xsize; i++)
49 {
50 maze[i] = (char *) calloc (sizeof (char), ysize);
51 }
52 44
53 /* write the outer walls */ 45 /* write the outer walls */
54 for (i = 0; i < xsize; i++) 46 for (i = 0; i < xsize; i++) maze[i][0] = maze[i][ysize - 1] = '#';
55 maze[i][0] = maze[i][ysize - 1] = '#'; 47 for (j = 0; j < ysize; j++) maze[0][j] = maze[xsize - 1][j] = '#';
56 for (j = 0; j < ysize; j++)
57 maze[0][j] = maze[xsize - 1][j] = '#';
58
59 48
60 /* find how many free wall spots there are */ 49 /* find how many free wall spots there are */
61 wall_free_size = 2 * (xsize - 4) + 2 * (ysize - 4); 50 wall_free_size = 2 * (xsize - 4) + 2 * (ysize - 4);
62 51
63 make_wall_free_list (xsize, ysize); 52 make_wall_free_list (xsize, ysize);
… …
69 /* recursively generate the walls of the maze */ 58 /* recursively generate the walls of the maze */
70 /* first pop a random starting point */ 59 /* first pop a random starting point */
71 while (wall_free_size > 0) 60 while (wall_free_size > 0)
72 { 61 {
73 pop_wall_point (&i, &j); 62 pop_wall_point (&i, &j);
63
74 if (option) 64 if (option)
75 fill_maze_full (maze, i, j, xsize, ysize); 65 fill_maze_full (maze, i, j, xsize, ysize);
76 else 66 else
77 fill_maze_sparse (maze, i, j, xsize, ysize); 67 fill_maze_sparse (maze, i, j, xsize, ysize);
78 } 68 }
… …
83 free (wall_y_list); 73 free (wall_y_list);
84 74
85 return maze; 75 return maze;
86} 76}
87 77
88
89
90/* 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
91 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. */
92
93void 80void
94make_wall_free_list (int xsize, int ysize) 81make_wall_free_list (int xsize, int ysize)
95{ 82{
96 int i, j, count; 83 int i, j, count;
97 84
98 count = 0; /* entries already placed in the free list */ 85 count = 0; /* entries already placed in the free list */
99 /*allocate it */ 86 /*allocate it */
100 if (wall_free_size < 0) 87 if (wall_free_size < 0)
101 return; 88 return;
89
102 wall_x_list = (int *) calloc (sizeof (int), wall_free_size); 90 wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
103 wall_y_list = (int *) calloc (sizeof (int), wall_free_size); 91 wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
104
105 92
106 /* top and bottom wall */ 93 /* top and bottom wall */
107 for (i = 2; i < xsize - 2; i++) 94 for (i = 2; i < xsize - 2; i++)
108 { 95 {
109 wall_x_list[count] = i; 96 wall_x_list[count] = i;
… …
124 wall_y_list[count] = j; 111 wall_y_list[count] = j;
125 count++; 112 count++;
126 } 113 }
127} 114}
128 115
129
130
131/* randomly returns one of the elements from the wall point list */ 116/* randomly returns one of the elements from the wall point list */
132
133void 117void
134pop_wall_point (int *x, int *y) 118pop_wall_point (int *x, int *y)
135{ 119{
136 int index = rndm (wall_free_size); 120 int index = rndm (wall_free_size);
137 121
… …
141 wall_x_list[index] = wall_x_list[wall_free_size - 1]; 125 wall_x_list[index] = wall_x_list[wall_free_size - 1];
142 wall_y_list[index] = wall_y_list[wall_free_size - 1]; 126 wall_y_list[index] = wall_y_list[wall_free_size - 1];
143 wall_free_size--; 127 wall_free_size--;
144} 128}
145 129
146
147
148/* 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
149we 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
150up, down, right, or left. */ 132up, down, right, or left. */
151
152int 133int
153find_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)
154{ 135{
155 136
156/* 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 */
… …
250 *x = xc - 1; 231 *x = xc - 1;
251 *y = yc; 232 *y = yc;
252 break; 233 break;
253 } 234 }
254 default: /* ??? */ 235 default: /* ??? */
255 {
256 return -1; 236 return -1;
257 } 237
258 } 238 }
259 return 1; 239 return 1;
260} 240}
261 241
262/* recursive routine which will fill every available space in the maze 242/* recursive routine which will fill every available space in the maze
… …
282 { 262 {
283 fill_maze_full (maze, xc, yc, xsize, ysize); 263 fill_maze_full (maze, xc, yc, xsize, ysize);
284 } 264 }
285} 265}
286 266
287
288/* 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
289 some free spots (possibly large) toward the center.*/ 268 some free spots (possibly large) toward the center.*/
290
291void 269void
292fill_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)
293{ 271{
294 int xc, yc; 272 int xc, yc;
295 273
… …
303 fill_maze_sparse (maze, xc, yc, xsize, ysize); 281 fill_maze_sparse (maze, xc, yc, xsize, ysize);
304 } 282 }
305 283
306 /* change the if to a while for a complete maze. */ 284 /* change the if to a while for a complete maze. */
307 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)
308 {
309 fill_maze_sparse (maze, xc, yc, xsize, ysize); 286 fill_maze_sparse (maze, xc, yc, xsize, ysize);
310 }
311} 287}

Diff Legend

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