Crossfire Server, Branch 1.12: /home/leaf/crossfire/server/branches/1.12/random_maps/maze

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 }
/home/leaf/crossfire/server/branches/1.12/random_maps/maze_gen.c
