#include <math.h>
#include <curses.h>
#include <stdlib.h>

#include "obj.h"
#include "vars.h"
#include "dice.h"
#include "pline.h"
#include "vault.h"
#include "areas.h"
#include "digdoors.h"
#include "digshops.h"
#include "digspecial.h"

#include "digdungeon.h"

/*
 * Parameter controlling how wobbly river paths are.
 */
#define RIVER_WOBBLE .1

/*
 * Max sizes for water pool generation.
 */
#define WATER_MAX_W 16
#define WATER_MAX_H 5

/*
 * A location to avoid in ckavoid() and ckavflag().  See their comments
 *  for more.
 */
LOC *avoidloc;

/*
 * Dig a room given as position-and-size.  Caller is responsible for
 *  all checking.
 */
static void digroom(LEVEL *lp, int sx, int sy, int xp, int yp)
{
 int x;
 int y;

 for (x=0;x<sx;x++)
  { for (y=0;y<sy;y++)
     { digcell(lp,xp+x,yp+y);
     }
  }
}

/*
 * Dig the rooms on a level.  Of course, this assumes the level is one
 *  for which digging rooms is a sensible operation - ie, not an
 *  elemental plane, underworld, or hell.
 *
 * There is a chance of getting a slightly bigger room; this chance is
 *  calculated such that the dungeon typically has one or two such
 *  rooms.  Then a number of regular, smaller, rooms are placed.  No
 *  effort is made to avoid overlap.
 */
static void digrooms(LEVEL *lp)
{
 int nrooms;
 int sx;
 int sy;
 int x;
 int y;

 if (onein((2*DUNGEON_LEVELS)/3))
  { sx = roll("3d6");
    sy = roll("2d5");
    x = 1 + rnd(LEV_X-2-sx);
    y = 1 + rnd(LEV_Y-2-sy);
    digroom(lp,sx,sy,x,y);
  }
 for (nrooms=roll("5d3+2");nrooms>0;nrooms--)
  { sx = roll("2d5");
    sy = roll("d4+1");
    x = 1 + rnd(LEV_X-2-sx);
    y = 1 + rnd(LEV_Y-2-sy);
    digroom(lp,sx,sy,x,y);
  }
}

/*
 * This flood-fills a cave region, flagging all cells connected to the
 *  argument location with LF_FLAG.  It's a straightforward recursive
 *  fill.  If this ends up eating up too much stack space, it may need
 *  to be changed to a queue-of-locations flood-fill.  If stairs is
 *  true, fills through stairs as well.
 *
 * The reason we check for CAVE, DOOR and SDOOR here even though this
 *  is used in dungeon digging before doors are created is that it is
 *  _also_ used by wand of digging during play.
 */
void flagregion(LEVEL *lv, int x, int y, int stairs)
{
 LOC *l;
 int bits;
#define U   0x00000001
#define L   0x00000002
#define D   0x00000004
#define R   0x00000008
#define ASC 0x00000010
#define DSC 0x00000020

 l = &lv->cells[x][y];
 if ((l->flags & LF_FLAG) || !((l->type == LOC_CAVE) || (l->type == LOC_DOOR) || (l->type == LOC_SDOOR)))
  { return;
  }
 bits = 0;
 if (x >= 1) bits |= L;
 if (y >= 1) bits |= U;
 if (x < LEV_X-1) bits |= R;
 if (y < LEV_Y-1) bits |= D;
 if (stairs)
  { if (lv->levelno > 1) bits |= ASC;
    if (lv->levelno < DUNGEON_LEVELS) bits |= DSC;
  }
 l->flags |= LF_FLAG;
 lv->nunflagged --;
 if (bits & L)
  { if (bits & U) flagregion(lv,x-1,y-1,stairs);
    flagregion(lv,x-1,y,stairs);
    if (bits & D) flagregion(lv,x-1,y+1,stairs);
  }
 if (bits & R)
  { if (bits & U) flagregion(lv,x+1,y-1,stairs);
    flagregion(lv,x+1,y,stairs);
    if (bits & D) flagregion(lv,x+1,y+1,stairs);
  }
 if (bits & U) flagregion(lv,x,y-1,stairs);
 if (bits & D) flagregion(lv,x,y+1,stairs);
 if ( ((bits & ASC) && (l->cavetype == LOC_STAIRS_U)) ||
      ((bits & DSC) && (l->cavetype == LOC_STAIRS_D)) )
  { flagregion(l->to->on,l->to->x,l->to->y,stairs);
  }
#undef U
#undef L
#undef D
#undef R
#undef ASC
#undef DSC
}

/*
 * Run a `mole' through the dugeon, eating its way around, creating
 *  corridors as it goes.  Various empirical heuristics are applied to
 *  make it tend to link up the level.
 */
static void runmole(void)
{
 int x;
 int y;
 int z;
 LEVEL *lv;
 LOC *lc;
 int dx;
 int dy;
 int happy;

 for (z=0;z<DUNGEON_LEVELS;z++)
  { lv = &levels[z];
    lv->ncorr = 0;
    lv->nstup = 0;
    lv->nunflagged = 0;
    for (x=0;x<LEV_X;x++)
     { LOC *l;
       l = &lv->cells[x][0];
       for (y=0;y<LEV_Y;y++)
	{ l->flags &= ~LF_FLAG;
	  if (l->type == LOC_CAVE)
	   { lv->nunflagged ++;
	   }
	  l ++;
	}
     }
  }
 z = 0;
 lv = &levels[0];
 x = 1 + rnd(LEV_X-2);
 y = 1 + rnd(LEV_Y-2);
 digcell(lv,x,y);
 entrance = &lv->cells[x][y];
 entrance->cavetype = LOC_STAIRS_U;
 entrance->to = 0;
 flagregion(lv,x,y,1);
 lv->nstup = 1;
 switch (rnd(4))
  { case 0:
       dx = 0;
       dy = -1;
       break;
    case 1:
       dx = -1;
       dy = 0;
       break;
    case 2:
       dx = 0;
       dy = 1;
       break;
    case 3:
       dx = 1;
       dy = 0;
       break;
  }
 happy = 0;
 while (1)
  { lc = &lv->cells[x][y];
    if (lc->type != LOC_CAVE)
     { int xx;
       int yy;
       LOC *ll;
       for (xx=1;xx>=-1;xx--)
	{ ll = &lv->cells[x+xx][y+1];
	  for (yy=1;yy>=-1;yy--)
	   { if (ll->type == LOC_CAVE)
	      { happy --;
	      }
	     ll --;
	   }
	}
       digcell(lv,x,y);
       flagregion(lv,x,y,1);
       lv->ncorr ++;
     }
    happy --;
    if ( (x+dx < 1) ||
	 (y+dy < 1) ||
	 (x+dx >= LEV_X-1) ||
	 (y+dy >= LEV_Y-1) ||
	 onein((dx?6:3)+happy) )
     { int tx;
       int ty;
       int bx;
       int by;
       int b;
       if (lv->cells[x][y].cavetype == LOC_JUSTCAVE)
	{ int p;
	  p = (lv->ncorr > 300) ? onein(3) : (rnd(1000) < lv->ncorr);
	  if ((lv->nunflagged < 10) && onein(5))
	   { p = 1;
	   }
	  if (p)
	   { int nz;
	     LOC *l1;
	     LOC *l2;
	     int xx;
	     int yy;
	     if ((z == DUNGEON_LEVELS-1) || ((z > 1) && onein(lv->nstup+2)))
	      { nz = z - 1;
	      }
	     else
	      { nz = z + 1;
	      }
	     if ((z == DUNGEON_LEVELS-1) && !onein(lv->nstup+2))
	      { break;
	      }
	     l1 = &lv->cells[x][y];
	     xx = x + levels[nz].off.x - lv->off.x;
	     yy = y + levels[nz].off.y - lv->off.y;
	     l2 = ((xx >= 1) && (yy >= 1) && (xx < LEV_X-1) && (yy < LEV_Y-1))
		  ? &levels[nz].cells[xx][yy]
		  : 0;
	     if (l2 && ((l2->type != LOC_CAVE) || (l2->cavetype == LOC_JUSTCAVE)))
	      { ((nz>z)?l2->on:lv)->nstup ++;
		l1->cavetype = (nz>z) ? LOC_STAIRS_D : LOC_STAIRS_U;
		l1->to = l2;
		lv = &levels[nz];
		x = xx;
		y = yy;
		digcell(lv,x,y);
		flagregion(lv,x,y,1);
		l2->cavetype = (nz>z) ? LOC_STAIRS_U : LOC_STAIRS_D;
		l2->to = l1;
		z = nz;
		happy = 2;
		continue;
	      }
	   }
	}
       if (lv->nunflagged == 0)
	{ b = rnd(2);
	  happy += 5;
	}
       else
	{ int xdiff;
	  LOC *lc2;
	  b = LEV_X + LEV_Y + 1;
	  for (tx=1;tx<LEV_X-1;tx++)
	   { lc2 = &lv->cells[tx][1];
	     xdiff = (tx > x) ? tx-x : x-tx;
	     for (ty=1;ty<LEV_Y-1;ty++)
	      { if ((lc2->type == LOC_CAVE) && !(lc2->flags & LF_FLAG))
		 { int df;
		   df = xdiff + ((ty > y) ? ty-y : y-ty);
		   if (df < b)
		    { b = df;
		      bx = tx;
		      by = ty;
		    }
		 }
		lc2 ++;
	      }
	   }
	  if (b > LEV_X+LEV_Y)
	   { panic("nunflagged %d on %d but can't find one",
			lv->nunflagged,lv->levelno);
	   }
	  if (((dx*(by-y)) > 0) || ((dy*(bx-x)) < 0))
	   { b = rnd(7) > 4;
	     if (! b)
	      { happy = 2 * ((dx*(by-y)) - (dy*(bx-x)));
	      }
	     else if (happy > 0)
	      { happy = 0;
	      }
	   }
	  else if (((dx*(by-y)) < 0) || ((dy*(bx-x)) > 0))
	   { b = rnd(7) > 1;
	     if (b)
	      { happy = 2 * ((dy*(bx-x)) - (dx*(by-y)));
	      }
	     else if (happy > 0)
	      { happy = 0;
	      }
	   }
	  else
	   { b = rnd(3);
	     if ( (b == 2) && ((dx*(bx-x)) >= 0) && ((dy*(by-y)) >= 0) )
	      { happy = 2 * ((dx*(bx-x)) + (dy*(by-y)));
	      }
	     else if (happy > 0)
	      { happy = 0;
	      }
	   }
	}
       switch (b)
	{ int t;
	  case 0:
	     t = dx;
	     dx = -dy;
	     dy = t;
	     break;
	  case 1:
	     t = -dx;
	     dx = dy;
	     dy = t;
	     break;
	  case 2:
	     break;
	}
       continue;
     }
    x += dx;
    y += dy;
  }
}

/*
 * Link up any leftover pieces, so the dungeon is connected.  Algorithm
 *  is to find an unlinked piece and dig corridors to link it to
 *  something already connected to the entrance, repeat until there is
 *  nothing left disconnected on the level.
 */
static void fixpieces(void)
{
 int x;
 int y;
 int z;
 LEVEL *lv;
 LOC *lc;
 LOC *lastlc;
 int dx;
 int dy;
 int b;

 for (z=0;z<DUNGEON_LEVELS;z++)
  { while <"top"> (1)
     { lv = &levels[z];
       if (lv->nunflagged == 0)
	{ break;
	}
       lc = 0;
       do <"findunflagged">
	{ for (x=0;x<LEV_X;x++)
	   { LOC *l;
	     l = &lv->cells[x][0];
	     for (y=0;y<LEV_Y;y++)
	      { if ((l->type == LOC_CAVE) && !(l->flags & LF_FLAG))
		 { lastlc = l;
		   break <"findunflagged">;
		 }
		l ++;
	      }
	   }
	  panic("level %d: nunflagged %d but can't find one?",
			lv->levelno,lv->nunflagged);
	} while (0);
       while <"newlevel"> (1)
	{ b = LEV_X + LEV_Y + 1;
	  for (x=0;x<LEV_X;x++)
	   { LOC *l;
	     int xdiff;
	     l = &lv->cells[x][0];
	     xdiff = lastlc->x - x;
	     if (xdiff < 0) xdiff = - xdiff;
	     for (y=0;y<LEV_Y;y++)
	      { if ((l->type == LOC_CAVE) && (l->flags & LF_FLAG))
		 { int df;
		   df = xdiff + ((lastlc->y>y) ? lastlc->y-y : y-lastlc->y);
		   if (df < b)
		    { b = df;
		      dx = x - lastlc->x;
		      dy = y - lastlc->y;
		    }
		 }
		l ++;
	      }
	   }
	  x = lastlc->x;
	  y = lastlc->y;
	  while (1)
	   { int k;
	     lastlc = lc;
	     lc = &lv->cells[x][y];
	     if (lc->type != LOC_CAVE)
	      { digcell(lv,x,y);
	      }
	     else if (lc->flags & LF_FLAG)
	      { flagregion(lastlc->on,lastlc->x,lastlc->y,1);
		continue <"top">;
	      }
	     if (onein(40) && (lc->cavetype == LOC_JUSTCAVE))
	      { LEVEL *lv2;
		LOC *lc2;
		int u;
		int xx;
		int yy;
		switch (lv->levelno)
		 { case 1:
		      lv2 = lv->down;
		      break;
		   case DUNGEON_LEVELS:
		      lv2 = lv->up;
		      break;
		   default:
		      lv2 = rnd(2) ? lv->up : lv->down;
		      break;
		 }
		xx = x + lv2->off.x - lv->off.x;
		yy = y + lv2->off.y - lv->off.y;
		lc2 = ((xx >= 1) && (yy >= 1) && (xx < LEV_X-1) && (yy < LEV_Y-1))
		     ? &lv2->cells[xx][yy]
		     : 0;
		if (lc2 && ((lc2->type != LOC_CAVE) || (lc2->cavetype == LOC_JUSTCAVE)))
		 { u = lv2->levelno < lv->levelno;
		   lc->cavetype = u ? LOC_STAIRS_U : LOC_STAIRS_D;
		   lc->to = lc2;
		   lv = lv2;
		   x = xx;
		   y = yy;
		   digcell(lv,x,y);
		   lc2->cavetype = u ? LOC_STAIRS_D : LOC_STAIRS_U;
		   lc2->to = lc;
		   lastlc = lc2;
		   continue <"newlevel">;
		 }
	      }
	     if (onein(2))
	      { k = rnd(5) + ((dx>0)?1:(dx<0)?-1:0) - 2;
		if ((k < 0) && (x > 1))
		 { x --;
		   dx ++;
		 }
		else if ((k > 0) && (x < LEV_X-2))
		 { x ++;
		   dx --;
		 }
	      }
	     else
	      { k = rnd(5) + ((dy>0)?1:(dy<0)?-1:0) - 2;
		if ((k < 0) && (y > 1))
		 { y --;
		   dy ++;
		 }
		else if ((k > 0) && (y < LEV_Y-2))
		 { y ++;
		   dy --;
		 }
	      }
	   }
	  break;
	}
     }
  }
}

static void make_water_mask(char (*m)[WATER_MAX_H], int w, int h)
{
 int x;
 int y;
 int i;

 for (y=h-1;y>=0;y--)
  { for (x=w-1;x>=0;x--)
     { m[x][y] = 1;
     }
  }
 for (i=w*h*4;i>0;i--)
  { x = rnd(w);
    y = rnd(h);
    switch (rnd(4))
     { case 0:
	  if ((x >= 1) && m[x-1][y]) continue;
	  break;
       case 1:
	  if ((y >= 1) && m[x][y-1]) continue;
	  break;
       case 2:
	  if ((x < w-1) && m[x+1][y]) continue;
	  break;
       case 3:
	  if ((y < h-1) && m[x][y+1]) continue;
	  break;
     }
    m[x][y] = 0;
  }
}

/*
 * Make water areas (other than water-filled portions of levels).
 *
 * There are two sorts of these: pools and rivers.  Pools occur in
 *  large-enough otherwise-empty spaces; rivers can cross any
 *  otherwise-empty space.  Rivers can overlap ("run through") pools.
 */
static void makewater(void)
{
 int i;
 int x;
 int y;
 int w;
 int h;
 int j;
 int k;
 LEVEL *l;
 LOC *c;
 char mask[WATER_MAX_W][WATER_MAX_H];
 double o_ang;
 double d_ang;
 double rx;
 double ry;

 for <"pools"> (i=100;i>0;i--)
  { l = &levels[rnd(DUNGEON_LEVELS)];
    w = roll("2d6+3");
    h = roll("d4+1");
    if ((w > WATER_MAX_W) || (h > WATER_MAX_H)) abort();
    x = 1 + rnd(LEV_X-2-w);
    y = 1 + rnd(LEV_Y-2-h);
    make_water_mask(&mask[0],w,h);
    for (k=0;k<h;k++)
     { for (j=0;j<w;j++)
	{ if (! mask[j][k]) continue;
	  c = &l->cells[x+j][y+k];
	  if (c->type != LOC_CAVE) continue;
	  if (c->cavetype != LOC_JUSTCAVE) continue <"pools">;
	  if (c->flags & LF_WATERFILL) continue <"pools">;
	}
     }
    for (k=0;k<h;k++)
     { for (j=0;j<w;j++)
	{ if (! mask[j][k]) continue;
	  l->cells[x+j][y+k].flags |= LF_WATER_LOW;
	}
     }
  }
 i = 0;
 for (j=DUNGEON_LEVELS;j>0;j--) i += rnd(3);
 for (;i>0;i--)
  { l = &levels[rnd(DUNGEON_LEVELS)];
    switch (rnd(4))
     { case 0:
	  rx = 0;
	  ry = rnd(LEV_Y);
	  break;
       case 1:
	  rx = LEV_X - 1;
	  ry = rnd(LEV_Y);
	  break;
       case 2:
	  rx = rnd(LEV_X);
	  ry = 0;
	  break;
       case 3:
	  rx = rnd(LEV_X);
	  ry = LEV_Y - 1;
	  break;
     }
    o_ang = atan2(((LEV_Y-1)*.5)-ry,((LEV_X-1)*.5)-rx) + ((frnd() - .5) * M_PI);
    d_ang = o_ang + ((frnd() - .5) * (M_PI * .5));
    while (1)
     { x = floor(rx+.5);
       y = floor(ry+.5);
       if ((x < 0) || (y < 0) || (x >= LEV_X) || (y >= LEV_Y)) break;
       c = &l->cells[x][y];
       if ((c->type == LOC_CAVE) && (c->cavetype == LOC_JUSTCAVE) && !(c->flags & LF_WATERFILL)) c->flags |= LF_WATER_LOW;
       d_ang += (((o_ang - d_ang) / (M_PI * .5)) + (frnd() * 2) - 1) * (M_PI * RIVER_WOBBLE);
       rx += .5 * cos(d_ang);
       ry += .5 * sin(d_ang);
     }
  }
}

/*
 * Top-level dungeon-digging routine.  This just initializes the
 *  levels, then calls the various routines (digrooms, runmole, etc) to
 *  dig out the dungeon.
 */
void digdungeon(void)
{
 int l;
 LEVEL *lp;
 static const char *stages[] = { "Rooms",
				 "Corridors",
				 "Connections",
				 "Water",
				 "Special levels",
				 "Shops",
				 "Doors",
				 "Areas",
				 "Vaults",
				 "Done",
				 0 };
 int s;

 for (s=0;stages[s];s++)
  { mvprintw(s,MXO,"%s",stages[s]);
  }
 s = -1;
#define NEXTSTAGE() \
	(s++,standout(),mvprintw(s,MXO,"%s",stages[s]),standend(),refresh())
 for (l=0;l<N_LEVELS;l++)
  { lp = &Levels[l];
    lp->index = l;
    lp->flags = 0;
    lp->visibility = 0;
    lp->shops = 0;
    lp->off.x = 0;
    lp->off.y = 0;
    lp->gate_ib = 0;
    lp->gate_ob = 0;
  }
 for (l=0;l<DUNGEON_LEVELS;l++)
  { char *t;
    lp = &levels[l];
    lp->levelno = l + 1;
    lp->index = l;
    t = malloc(8);
    snprintf(t,8,"%d",lp->levelno);
    lp->shortname = t;
    t = malloc(12);
    snprintf(t,12,"Level %d",lp->levelno);
    lp->longname = t;
    lp->visibility = 7;
  }
 levels[0].up = 0;
 levels[DUNGEON_LEVELS-1].down = 0;
 for (l=1;l<DUNGEON_LEVELS;l++)
  { levels[l-1].down = &levels[l];
    levels[l].up = &levels[l-1];
    if (onein(5))
     { levels[l].off.x = levels[l-1].off.x + rnd(61) - 30;
       levels[l].off.y = levels[l-1].off.y + rnd(17) - 8;
     }
    else
     { levels[l].off.x = levels[l-1].off.x + rnd(13) - 6;
       levels[l].off.y = levels[l-1].off.y + rnd(5) - 2;
     }
  }
 NEXTSTAGE();
 for (l=0;l<DUNGEON_LEVELS;l++)
  { lp = &levels[l];
    clearlevel(lp,LOC_ROCK);
    digrooms(lp);
  }
 NEXTSTAGE();
 runmole();
 NEXTSTAGE();
 fixpieces();
 NEXTSTAGE();
 makewater();
 NEXTSTAGE();
 makespeciallevels();
 NEXTSTAGE();
 makeshops();
 NEXTSTAGE();
 makedoors();
 NEXTSTAGE();
 makeareas();
 NEXTSTAGE();
 makevaults();
 NEXTSTAGE();
}

/*
 * Clear out a level to the argument type.  This is usually LOC_ROCK,
 *  but it's LOC_CAVE when creating the elemental planes.
 */
void clearlevel(LEVEL *lp, LOCTYPE t)
{
 int x;
 int y;
 LOC *l;

 for (x=0;x<LEV_X;x++)
  { l = &lp->cells[x][0];
    for (y=0;y<LEV_Y;y++)
     { l->x = x;
       l->y = y;
       l->type = t;
       switch (t)
	{ case LOC_ROCK:
	     break;
	  case LOC_CAVE:
	     l->cavetype = LOC_JUSTCAVE;
	     break;
	  default:
	     abort();
	     break;
	}
       l->flags = 0;
       l->trap = TRAP_KIND_NONE;
       inv_init(&l->objs,IT_LOC,l);
       l->monst = 0;
       l->to = 0;
       l->on = lp;
       l ++;
     }
  }
}

/*
 * Given a rectangle position-and-size, return true iff the whole
 *  rectangle is rock.  This is used for creating things like shops and
 *  vaults that must not overlap with ordinary rooms and corridors.
 */
int solidrock(LEVEL *lp, int sx, int sy, int xp, int yp)
{
 int x;
 int y;
 LOC *l;

 for (x=0;x<sx;x++)
  { for (y=0;y<sy;y++)
     { l = &lp->cells[xp+x][yp+y];
       if (l->type != LOC_ROCK) return(0);
     }
  }
 return(1);
}

/*
 * Dig a single cell.  This also maintains the level's nunflagged value
 *  and handles converting cells adjacent to the newly-dug cell from
 *  rock to wall as appropriate.
 *
 * Attempts to dig border cells do nothing.  (WRAPAROUND levels have no
 *  border cells.)
 */
void digcell_(LEVEL *lp, int x, int y)
{
 LOC *l;
 int i;
 int j;
 int xi;
 int yj;

 if (!(lp->flags & LVF_WRAPAROUND) && ((x < 1) || (y < 1) || (x >= LEV_X-1) || (y >= LEV_Y-1))) return;
 l = &lp->cells[x][y];
 if (l->type == LOC_CAVE) return;
 l->type = LOC_CAVE;
 l->cavetype = LOC_JUSTCAVE;
 l->on->nunflagged ++;
 for (i=1;i>=-1;i--)
  { xi = x + i;
    if (xi < 0) xi += LEV_X; else if (xi >= LEV_X) xi -= LEV_X;
    for (j=1;j>=-1;j--)
     { yj = y + j;
       if (yj < 0) yj += LEV_Y; else if (yj >= LEV_Y) yj -= LEV_Y;
       l = &lp->cells[xi][yj];
       if (l->type == LOC_ROCK)
	{ l->type = LOC_WALL;
	  l->walldoor = LOC_UWALL;
	}
     }
  }
}

/*
 * Dig a single cell.  This is just like digcell_() except that it
 *  panics if asked to dig border cells.
 */
void digcell(LEVEL *lp, int x, int y)
{
 if (!(lp->flags & LVF_WRAPAROUND) && ((x < 1) || (y < 1) || (x >= LEV_X-1) || (y >= LEV_Y-1)))
  { panic("digging border cell");
  }
 digcell_(lp,x,y);
}

/*
 * Clears out a newly-dug dungeon, preparatory to filling it.
 */
void cleardungeon(void)
{
 int x;
 int y;
 int z;
 LOC *lc;
 LEVEL *lv;

 for (z=0;z<N_LEVELS;z++)
  { lv = &Levels[z];
    lv->ncave = 0;
    lv->nmonst = 0;
    for (x=0;x<LEV_X;x++)
     { lc = &lv->cells[x][0];
       for (y=0;y<LEV_Y;y++)
	{ lc->flags &= LF__PERMANENT;
	  switch (lc->type)
	   { case LOC_WALL:
	     case LOC_SDOOR:
		lc->walldoor = LOC_UWALL;
		break;
	     case LOC_CAVE:
		lv->ncave ++;
		break;
	     default:
		break;
	   }
	  lc ++;
	}
     }
  }
}

/*
 * This is a location test function used when creating objects, to make
 *  sure we create them in reasonable places.  It returns true for any
 *  CAVE/JUSTCAVE cell that is neither SHOP nor VAULT.
 */
int ckroutine(LOC *lc)
{
 if ( (lc->type != LOC_CAVE) ||
      (lc->cavetype != LOC_JUSTCAVE) ||
      (lc->flags & (LF_SHOP|LF_VAULT)) ) return(0);
 return(1);
}

/*
 * This is a location test function used when creating gates on the
 *  elemental planes and, sometimes, objects, to make sure we don't
 *  create the gates too close to one another.  It returns true for any
 *  CAVE/JUSTCAVE cell that is at least 20 away, in the L1 (city-block)
 *  metric, from avoidloc, and is neither SHOP nor VAULT.
 */
int ckavoid(LOC *lc)
{
 int dx;
 int dy;

 if ( (lc->type != LOC_CAVE) ||
      (lc->cavetype != LOC_JUSTCAVE) ||
      (lc->flags & (LF_SHOP|LF_VAULT)) ) return(0);
 dx = lc->x - avoidloc->x;
 if (dx < 0) dx = - dx;
 dy = lc->y - avoidloc->y;
 if (dy < 0) dy = - dy;
 if (dx+dy < 20) return(0);
 return(1);
}

/*
 * This returns a random location satisfying a check function.  It
 *  takes the level the location is to be on and a check function; if
 *  the check function is nil, any location is acceptable.
 */
LOC *randomloc(LEVEL *lv, int (*ckf)(LOC *))
{
 LOC *lc;

 while (1)
  { lc = &lv->cells[rnd(LEV_X)][rnd(LEV_Y)];
    if (!ckf || (*ckf)(lc)) return(lc);
  }
}

/*
 * Do something for all immediate neighbours of a location.
 */
void all_neighbours(LOC *l, void (*fn)(LOC *))
{
 int dx;
 int dy;
 int x;
 int y;

 for (dx=-1;dx<=1;dx++)
  { x = l->x + dx;
    if (l->on->flags & LVF_WRAPAROUND)
     { if (x < 0) x += LEV_X; else if (x >= LEV_X) x -= LEV_X;
     }
    else
     { if ((x < 0) || (x >= LEV_X)) continue;
     }
    for (dy=-1;dy<=1;dy++)
     { y = l->y + dy;
       if (l->on->flags & LVF_WRAPAROUND)
	{ if (y < 0) y += LEV_Y; else if (y >= LEV_Y) y -= LEV_Y;
	}
       else
	{ if ((y < 0) || (y >= LEV_Y)) continue;
	}
       (*fn)(&l->on->cells[x][y]);
     }
  }
}