/*
 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
 * 
 * Copyright (©) 2005,2006,2007,2008,2009 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
 * Copyright (©) Crossfire Development Team (restored, original file without copyright notice)
 * 
 * Deliantra is free software: you can redistribute it and/or modify it under
 * the terms of the Affero GNU General Public License as published by the
 * Free Software Foundation, either version 3 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 Affero GNU General Public License
 * and the GNU General Public License along with this program. If not, see
 * <http://www.gnu.org/licenses/>.
 * 
 * The authors can be reached via e-mail to <support@deliantra.net>
 */

/* peterm@langmuir.eecs.berkeley.edu:  this function generates a random
blocked maze with the property that there is only one path from one spot
to any other, and there is always a path from one spot to any other.

input:  xsize, ysize;
output:  a char** array with # and . for closed and open respectively.

a char value of 0 represents a blank space:  a '#' is
a wall.

*/

/* 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 <vector>

#include <global.h>

#include "random_map.h"
#include "rproto.h"

struct point
{
  short x;
  short y;

  point ()
  {
  }

  point (int x, int y)
  : x(x), y(y)
  {
  }
};

/* global variables that everyone needs:  don't want to pass them in
   as parameters every time. */
static point *seed_list;
static int seed_size;
static int xsize, ysize;
static char **maze;

/*  the free wall points are those outer points which aren't corners or
    near corners, and don't have a maze wall growing out of them already. */
static void
make_wall_free_list ()
{
  // xsize * ysize is plenty too much, but it's temporary
  seed_list = salloc<point> (xsize * ysize);
  seed_size = 0;

  /* top and bottom wall */
  for (int x = 2; x < xsize - 2; x++)
    {
      seed_list [seed_size++] = point (x, 0);
      seed_list [seed_size++] = point (x, ysize - 1);
    }

  /* left and right wall */
  for (int y = 2; y < ysize - 2; y++)
    {
      seed_list [seed_size++] = point (0, y);
      seed_list [seed_size++] = point (xsize - 1, y);
    }
}

/* randomly returns one of the elements from the wall point list */
static point
pop_point ()
{
  int index = rmg_rndm (seed_size);

  point p = seed_list [index];

  /* write the last array point here */
  seed_list [index] = seed_list [--seed_size];

  return p;
}

/* find free point:  randomly look for a square adjacent to this one where
we can place a new block without closing a path.  We may only look
up, down, right, or left. */
static int
find_free_point (point &p, point pc)
{
  /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
  int dirlist[4];
  int count = 0;                /* # elements in dirlist */

  int xc = pc.x;
  int yc = pc.y;

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

      if (cleartest == 0)
        dirlist[count++] = 1;
    }

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

      if (cleartest == 0)
        dirlist[count++] = 2;
    }

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

      if (cleartest == 0)
        dirlist[count++] = 3;
    }

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

      if (cleartest == 0)
        dirlist[count++] = 4;
    }

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

  /* choose a random direction */
  switch (dirlist [rmg_rndm (count)])
    {
      case 1:                  /* up */
        p.x = xc;
        p.y = yc + 1;
        break;

      case 2:                  /* down */
        p.x = xc;
        p.y = yc - 1;
        break;

      case 3:                  /* right */
        p.x = xc + 1;
        p.y = yc;
        break;
        
      case 4:                  /* left */
        p.x = xc - 1;
        p.y = yc;
        break;
    }

  return 1;
}

/* recursive routine which will fill every available space in the maze
        with walls*/
static void
fill_maze_full (point p)
{
  point pc;

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

  /* decide if we're going to pick from the wall_free_list */
  if (rmg_rndm (2) && seed_size)
    fill_maze_full (pop_point ());

  /* change the while to an if for a sparse maze. */
  while (find_free_point (pc, p) != -1)
    fill_maze_full (pc);
}

/* recursive routine which will fill much of the maze, but will leave
        some free spots (possibly large) toward the center.*/
static void
fill_maze_sparse (point p)
{
  point pc;

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

  /* decide if we're going to pick from the wall_free_list */
  if (rmg_rndm (2) && seed_size)
    fill_maze_full (pop_point ());

  /* change the if to a while for a complete maze. */
  if (find_free_point (pc, p) != -1)
    fill_maze_full (pc);
}

/* the outsize interface routine:  accepts sizes, returns a char
** maze.  option is a flag for either a sparse or a full maze. Sparse
mazes have sizable rooms. option = 1, full, 0, sparse.*/
void
maze_gen (Layout maze, int full)
{
  xsize = maze->w;
  ysize = maze->h;
  ::maze = maze;

  maze->clear ();
  maze->border ();

  if (xsize < 4 || ysize < 4)
    return;

  make_wall_free_list ();

  /* recursively generate the walls of the maze */
  /* first pop a random starting point */
  while (seed_size)
    if (full)
      fill_maze_full (pop_point ());
    else
      fill_maze_sparse (pop_point ());

  /* clean up our intermediate data structures. */
  sfree (seed_list, xsize * ysize);
}

#if 0
static struct demo
{
  demo ()
  {
    Layout layout (30, 30);
    rmg_rndm.seed (time (0));

    for(int i=1;i<10;++i)
      {
        maze_gen (layout, 1);
        layout.print ();
      }
    exit (1);
  }
} demo;
#endif