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

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

#include "digdungeon.h"

/*
 * 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.
 */
static void flagregion(LEVEL *lv, int x, int y)
{
 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))
  { 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 (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);
    flagregion(lv,x-1,y);
    if (bits & D) flagregion(lv,x-1,y+1);
  }
 if (bits & R)
  { if (bits & U) flagregion(lv,x+1,y-1);
    flagregion(lv,x+1,y);
    if (bits & D) flagregion(lv,x+1,y+1);
  }
 if (bits & U) flagregion(lv,x,y-1);
 if (bits & D) flagregion(lv,x,y+1);
 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);
  }
#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);
 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);
       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);
		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 (1)
     {
top:
       lv = &levels[z];
       if (lv->nunflagged == 0)
	{ break;
	}
       lc = 0;
       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;
		goto gotunflag; /* aka break 2 */
	      }
	     l ++;
	   }
	}
       panic("level %d: nunflagged %d but can't find one?",
				lv->levelno,lv->nunflagged);
gotunflag:
newlevel:
       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);
	     goto top;
	   }
	  if (onein(40) && (lc->cavetype == LOC_JUSTCAVE))
	   { LEVEL *lv2;
	     LOC *lc2;
	     int u;
	     int xx;
	     int yy;
	     switch (lv->levelno)
	      { case 1:
		   lv2 = &levels[1];
		   break;
		case DUNGEON_LEVELS:
		   lv2 = &levels[DUNGEON_LEVELS-2];
		   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;
		goto 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 --;
	      }
	   }
	}
     }
  }
}

/*
 * 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",
				 "Special levels",
				 "Doors",
				 "Shops",
				 "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->traps = 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);
    sprintf(t,"%d",lp->levelno);
    lp->shortname = t;
    t = malloc(12);
    sprintf(t,"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();
 makespeciallevels();
 NEXTSTAGE();
 makedoors();
 NEXTSTAGE();
 makeshops();
 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 levels.
 */
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;
       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.  Panics if asked to dig a border 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.
 */
void digcell(LEVEL *lp, int x, int y)
{
 LOC *l;
 int i;
 int j;

 if ((x < 1) || (y < 1) || (x >= LEV_X-1) || (y >= LEV_Y-1))
  { panic("digging border cell");
  }
 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--)
  { for (j=1;j>=-1;j--)
     { l = &lp->cells[x+i][y+j];
       if (l->type == LOC_ROCK)
	{ l->type = LOC_WALL;
	  l->walldoor = LOC_UWALL;
	}
     }
  }
}

/*
 * 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 ++;
	}
     }
  }
}