maze_gen.c

Go to the documentation of this file.

/*
    CrossFire, A Multiplayer game for X-windows

    Copyright (C) 2001 Mark Wedel & Crossfire Development Team
    Copyright (C) 1992 Frank Tore Johansen

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 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 GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

    The authors can be reached via e-mail at crossfire-devel@real-time.com
*/

/* 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 <stdlib.h>
#include <stdio.h>
#include <global.h>
#include <maze_gen.h>
#include <time.h>

typedef struct free_walls_struct {
    int *wall_x_list;       
    int *wall_y_list;       
    int wall_free_size;     
} free_walls_struct;

static void fill_maze_full(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *);
static void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *);
static void make_wall_free_list(int xsize, int ysize, free_walls_struct *);
static void pop_wall_point(int *x, int *y, free_walls_struct *);
static int find_free_point(char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize);

char **maze_gen(int xsize, int ysize, int option) {
    int i, j;
    struct free_walls_struct free_walls;

    /* allocate that array, set it up */
    char **maze = (char **)calloc(sizeof(char *), xsize);
    for (i = 0; i < xsize; i++) {
        maze[i] = (char *)calloc(sizeof(char), ysize);
    }

    /* write the outer walls */
    for (i = 0; i < xsize; i++)
        maze[i][0] = maze[i][ysize-1] = '#';
    for (j = 0; j < ysize; j++)
        maze[0][j] = maze[xsize-1][j] = '#';


    /* find how many free wall spots there are */
    free_walls.wall_free_size = 2*(xsize-4)+2*(ysize-4);
    free_walls.wall_x_list = NULL;
    free_walls.wall_y_list = NULL;

    make_wall_free_list(xsize, ysize, &free_walls);

    /* return the empty maze */
    if (free_walls.wall_free_size <= 0)
        return maze;

    /* recursively generate the walls of the maze */
    /* first pop a random starting point */
    while (free_walls.wall_free_size > 0) {
        pop_wall_point(&i, &j, &free_walls);
        if (option)
            fill_maze_full(maze, i, j, xsize, ysize, &free_walls);
        else
            fill_maze_sparse(maze, i, j, xsize, ysize, &free_walls);
    }

    /* clean up our intermediate data structures. */
    free(free_walls.wall_x_list);
    free(free_walls.wall_y_list);

    return maze;
}

static void make_wall_free_list(int xsize, int ysize, free_walls_struct *free_walls) {
    int i, j, count;

    count = 0;  /* entries already placed in the free list */
    /*allocate it*/
    if (free_walls->wall_free_size < 0)
        return;
    free_walls->wall_x_list = (int *)calloc(sizeof(int), free_walls->wall_free_size);
    free_walls->wall_y_list = (int *)calloc(sizeof(int), free_walls->wall_free_size);


    /* top and bottom wall */
    for (i = 2; i < xsize-2; i++) {
        free_walls->wall_x_list[count] = i;
        free_walls->wall_y_list[count] = 0;
        count++;
        free_walls->wall_x_list[count] = i;
        free_walls->wall_y_list[count] = ysize-1;
        count++;
    }

    /* left and right wall */
    for (j = 2; j < ysize-2; j++) {
        free_walls->wall_x_list[count] = 0;
        free_walls->wall_y_list[count] = j;
        count++;
        free_walls->wall_x_list[count] = xsize-1;
        free_walls->wall_y_list[count] = j;
        count++;
    }
}

static void pop_wall_point(int *x, int *y, free_walls_struct *free_walls) {
    int index = RANDOM()%free_walls->wall_free_size;
    *x = free_walls->wall_x_list[index];
    *y = free_walls->wall_y_list[index];
    /* write the last array point here */
    free_walls->wall_x_list[index] = free_walls->wall_x_list[free_walls->wall_free_size-1];
    free_walls->wall_y_list[index] = free_walls->wall_y_list[free_walls->wall_free_size-1];
    free_walls->wall_free_size--;
}

static int find_free_point(char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize) {
    /* we will randomly pick from this list, 1=up, 2=down, 3=right, 4=left */
    int dirlist[4];
    int count = 0;  /* # elements in dirlist */

    /* look up */
    if (yc < ysize-2 && xc > 2 && xc < xsize-2) {
        int cleartest = (int)maze[xc][yc+1]+(int)maze[xc-1][yc+1]+(int)maze[xc+1][yc+1];

        cleartest += (int)maze[xc][yc+2]+(int)maze[xc-1][yc+2]+(int)maze[xc+1][yc+2];
        if (cleartest == 0) {
            dirlist[count] = 1;
            count++;
        }
    }

    /* look down */
    if (yc > 2 && xc > 2 && xc < xsize-2) {
        int cleartest = (int)maze[xc][yc-1]+(int)maze[xc-1][yc-1]+(int)maze[xc+1][yc-1];

        cleartest += (int)maze[xc][yc-2]+(int)maze[xc-1][yc-2]+(int)maze[xc+1][yc-2];
        if (cleartest == 0) {
            dirlist[count] = 2;
            count++;
        }
    }


    /* look right */
    if (xc < xsize-2 && yc > 2 && yc < ysize-2) {
        int cleartest = (int)maze[xc+1][yc]+(int)maze[xc+1][yc-1]+(int)maze[xc+1][yc+1];

        cleartest += (int)maze[xc+2][yc]+(int)maze[xc+2][yc-1]+(int)maze[xc+2][yc+1];
        if (cleartest == 0) {
            dirlist[count] = 3;
            count++;
        }
    }


    /* look left */
    if (xc > 2 && yc > 2 && yc < ysize-2) {
        int cleartest = (int)maze[xc-1][yc]+(int)maze[xc-1][yc-1]+(int)maze[xc-1][yc+1];

        cleartest += (int)maze[xc-2][yc]+(int)maze[xc-2][yc-1]+(int)maze[xc-2][yc+1];
        if (cleartest == 0) {
            dirlist[count] = 4;
            count++;
        }
    }

    if (count == 0)
        return -1; /* failed to find any clear points */

    /* choose a random direction */
    if (count > 1)
        count = RANDOM()%count;
    else
        count = 0;
    switch (dirlist[count]) {
    case 1: { /* up */
        *y = yc+1;
        *x = xc;
        break;
    };

    case 2: { /* down */
        *y = yc-1;
        *x = xc;
        break;
    };

    case 3: { /* right */
        *y = yc;
        *x = xc+1;
        break;
    }

    case 4: { /* left */
        *x = xc-1;
        *y = yc;
        break;
    }

    default: { /* ??? */
        return -1;
    }
    }
    return 1;
}

static void fill_maze_full(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *free_walls) {
    int xc, yc;

    /* write a wall here */
    maze[x][y] = '#';

    /* decide if we're going to pick from the wall_free_list */
    if (RANDOM()%4 && free_walls->wall_free_size > 0) {
        pop_wall_point(&xc, &yc, free_walls);
        fill_maze_full(maze, xc, yc, xsize, ysize, free_walls);
    }

    /* change the if to a while for a complete maze.  */
    while (find_free_point(maze, &xc, &yc, x, y, xsize, ysize) != -1) {
        fill_maze_full(maze, xc, yc, xsize, ysize, free_walls);
    }
}

static void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *free_walls) {
    int xc, yc;

    /* write a wall here */
    maze[x][y] = '#';

    /* decide if we're going to pick from the wall_free_list */
    if (RANDOM()%4 && free_walls->wall_free_size > 0) {
        pop_wall_point(&xc, &yc, free_walls);
        fill_maze_sparse(maze, xc, yc, xsize, ysize, free_walls);
    }

    /* change the if to a while for a complete maze.  */
    if (find_free_point(maze, &xc, &yc, x, y, xsize, ysize) != -1) {
        fill_maze_sparse(maze, xc, yc, xsize, ysize, free_walls);
    }
}