Crossfire Server, Branch 1.12
R12190
|
00001 /* 00002 CrossFire, A Multiplayer game for X-windows 00003 00004 Copyright (C) 2001 Mark Wedel & Crossfire Development Team 00005 Copyright (C) 1992 Frank Tore Johansen 00006 00007 This program is free software; you can redistribute it and/or modify 00008 it under the terms of the GNU General Public License as published by 00009 the Free Software Foundation; either version 2 of the License, or 00010 (at your option) any later version. 00011 00012 This program is distributed in the hope that it will be useful, 00013 but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 GNU General Public License for more details. 00016 00017 You should have received a copy of the GNU General Public License 00018 along with this program; if not, write to the Free Software 00019 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00020 00021 The authors can be reached via e-mail at crossfire-devel@real-time.com 00022 */ 00023 00031 /* we need to maintain a list of wall points to generate 00032 * reasonable mazes: a straightforward recursive random walk maze 00033 * generator would generate a map with a trivial circle-the-outer-wall solution 00034 */ 00035 00036 #include <stdlib.h> 00037 #include <stdio.h> 00038 #include <global.h> 00039 #include <maze_gen.h> 00040 #include <time.h> 00041 00043 typedef struct free_walls_struct { 00044 int *wall_x_list; 00045 int *wall_y_list; 00046 int wall_free_size; 00047 } free_walls_struct; 00048 00049 static void fill_maze_full(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *); 00050 static void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *); 00051 static void make_wall_free_list(int xsize, int ysize, free_walls_struct *); 00052 static void pop_wall_point(int *x, int *y, free_walls_struct *); 00053 static int find_free_point(char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize); 00054 00068 char **maze_gen(int xsize, int ysize, int option) { 00069 int i, j; 00070 struct free_walls_struct free_walls; 00071 00072 /* allocate that array, set it up */ 00073 char **maze = (char **)calloc(sizeof(char *), xsize); 00074 for (i = 0; i < xsize; i++) { 00075 maze[i] = (char *)calloc(sizeof(char), ysize); 00076 } 00077 00078 /* write the outer walls */ 00079 for (i = 0; i < xsize; i++) 00080 maze[i][0] = maze[i][ysize-1] = '#'; 00081 for (j = 0; j < ysize; j++) 00082 maze[0][j] = maze[xsize-1][j] = '#'; 00083 00084 00085 /* find how many free wall spots there are */ 00086 free_walls.wall_free_size = 2*(xsize-4)+2*(ysize-4); 00087 free_walls.wall_x_list = NULL; 00088 free_walls.wall_y_list = NULL; 00089 00090 make_wall_free_list(xsize, ysize, &free_walls); 00091 00092 /* return the empty maze */ 00093 if (free_walls.wall_free_size <= 0) 00094 return maze; 00095 00096 /* recursively generate the walls of the maze */ 00097 /* first pop a random starting point */ 00098 while (free_walls.wall_free_size > 0) { 00099 pop_wall_point(&i, &j, &free_walls); 00100 if (option) 00101 fill_maze_full(maze, i, j, xsize, ysize, &free_walls); 00102 else 00103 fill_maze_sparse(maze, i, j, xsize, ysize, &free_walls); 00104 } 00105 00106 /* clean up our intermediate data structures. */ 00107 free(free_walls.wall_x_list); 00108 free(free_walls.wall_y_list); 00109 00110 return maze; 00111 } 00112 00123 static void make_wall_free_list(int xsize, int ysize, free_walls_struct *free_walls) { 00124 int i, j, count; 00125 00126 count = 0; /* entries already placed in the free list */ 00127 /*allocate it*/ 00128 if (free_walls->wall_free_size < 0) 00129 return; 00130 free_walls->wall_x_list = (int *)calloc(sizeof(int), free_walls->wall_free_size); 00131 free_walls->wall_y_list = (int *)calloc(sizeof(int), free_walls->wall_free_size); 00132 00133 00134 /* top and bottom wall */ 00135 for (i = 2; i < xsize-2; i++) { 00136 free_walls->wall_x_list[count] = i; 00137 free_walls->wall_y_list[count] = 0; 00138 count++; 00139 free_walls->wall_x_list[count] = i; 00140 free_walls->wall_y_list[count] = ysize-1; 00141 count++; 00142 } 00143 00144 /* left and right wall */ 00145 for (j = 2; j < ysize-2; j++) { 00146 free_walls->wall_x_list[count] = 0; 00147 free_walls->wall_y_list[count] = j; 00148 count++; 00149 free_walls->wall_x_list[count] = xsize-1; 00150 free_walls->wall_y_list[count] = j; 00151 count++; 00152 } 00153 } 00154 00163 static void pop_wall_point(int *x, int *y, free_walls_struct *free_walls) { 00164 int index = RANDOM()%free_walls->wall_free_size; 00165 *x = free_walls->wall_x_list[index]; 00166 *y = free_walls->wall_y_list[index]; 00167 /* write the last array point here */ 00168 free_walls->wall_x_list[index] = free_walls->wall_x_list[free_walls->wall_free_size-1]; 00169 free_walls->wall_y_list[index] = free_walls->wall_y_list[free_walls->wall_free_size-1]; 00170 free_walls->wall_free_size--; 00171 } 00172 00191 static int find_free_point(char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize) { 00192 /* we will randomly pick from this list, 1=up, 2=down, 3=right, 4=left */ 00193 int dirlist[4]; 00194 int count = 0; /* # elements in dirlist */ 00195 00196 /* look up */ 00197 if (yc < ysize-2 && xc > 2 && xc < xsize-2) { 00198 int cleartest = (int)maze[xc][yc+1]+(int)maze[xc-1][yc+1]+(int)maze[xc+1][yc+1]; 00199 00200 cleartest += (int)maze[xc][yc+2]+(int)maze[xc-1][yc+2]+(int)maze[xc+1][yc+2]; 00201 if (cleartest == 0) { 00202 dirlist[count] = 1; 00203 count++; 00204 } 00205 } 00206 00207 /* look down */ 00208 if (yc > 2 && xc > 2 && xc < xsize-2) { 00209 int cleartest = (int)maze[xc][yc-1]+(int)maze[xc-1][yc-1]+(int)maze[xc+1][yc-1]; 00210 00211 cleartest += (int)maze[xc][yc-2]+(int)maze[xc-1][yc-2]+(int)maze[xc+1][yc-2]; 00212 if (cleartest == 0) { 00213 dirlist[count] = 2; 00214 count++; 00215 } 00216 } 00217 00218 00219 /* look right */ 00220 if (xc < xsize-2 && yc > 2 && yc < ysize-2) { 00221 int cleartest = (int)maze[xc+1][yc]+(int)maze[xc+1][yc-1]+(int)maze[xc+1][yc+1]; 00222 00223 cleartest += (int)maze[xc+2][yc]+(int)maze[xc+2][yc-1]+(int)maze[xc+2][yc+1]; 00224 if (cleartest == 0) { 00225 dirlist[count] = 3; 00226 count++; 00227 } 00228 } 00229 00230 00231 /* look left */ 00232 if (xc > 2 && yc > 2 && yc < ysize-2) { 00233 int cleartest = (int)maze[xc-1][yc]+(int)maze[xc-1][yc-1]+(int)maze[xc-1][yc+1]; 00234 00235 cleartest += (int)maze[xc-2][yc]+(int)maze[xc-2][yc-1]+(int)maze[xc-2][yc+1]; 00236 if (cleartest == 0) { 00237 dirlist[count] = 4; 00238 count++; 00239 } 00240 } 00241 00242 if (count == 0) 00243 return -1; /* failed to find any clear points */ 00244 00245 /* choose a random direction */ 00246 if (count > 1) 00247 count = RANDOM()%count; 00248 else 00249 count = 0; 00250 switch (dirlist[count]) { 00251 case 1: { /* up */ 00252 *y = yc+1; 00253 *x = xc; 00254 break; 00255 }; 00256 00257 case 2: { /* down */ 00258 *y = yc-1; 00259 *x = xc; 00260 break; 00261 }; 00262 00263 case 3: { /* right */ 00264 *y = yc; 00265 *x = xc+1; 00266 break; 00267 } 00268 00269 case 4: { /* left */ 00270 *x = xc-1; 00271 *y = yc; 00272 break; 00273 } 00274 00275 default: { /* ??? */ 00276 return -1; 00277 } 00278 } 00279 return 1; 00280 } 00281 00297 static void fill_maze_full(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *free_walls) { 00298 int xc, yc; 00299 00300 /* write a wall here */ 00301 maze[x][y] = '#'; 00302 00303 /* decide if we're going to pick from the wall_free_list */ 00304 if (RANDOM()%4 && free_walls->wall_free_size > 0) { 00305 pop_wall_point(&xc, &yc, free_walls); 00306 fill_maze_full(maze, xc, yc, xsize, ysize, free_walls); 00307 } 00308 00309 /* change the if to a while for a complete maze. */ 00310 while (find_free_point(maze, &xc, &yc, x, y, xsize, ysize) != -1) { 00311 fill_maze_full(maze, xc, yc, xsize, ysize, free_walls); 00312 } 00313 } 00314 00329 static void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *free_walls) { 00330 int xc, yc; 00331 00332 /* write a wall here */ 00333 maze[x][y] = '#'; 00334 00335 /* decide if we're going to pick from the wall_free_list */ 00336 if (RANDOM()%4 && free_walls->wall_free_size > 0) { 00337 pop_wall_point(&xc, &yc, free_walls); 00338 fill_maze_sparse(maze, xc, yc, xsize, ysize, free_walls); 00339 } 00340 00341 /* change the if to a while for a complete maze. */ 00342 if (find_free_point(maze, &xc, &yc, x, y, xsize, ysize) != -1) { 00343 fill_maze_sparse(maze, xc, yc, xsize, ysize, free_walls); 00344 } 00345 }