build.cpp

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to POWDER
 * Development, and is not to be reproduced, transmitted, or disclosed
 * in any way without written permission.
 *
 * Produced by:	Jeff Lait
 *
 *      	POWDER Development
 *
 * NAME:        build.cpp ( POWDER Library, C++ )
 *
 * COMMENTS:
 *	build.cpp contains all the routines used to build dungeon levels.
 *	These are as many and varied as are the types of levels that can
 *	be built.
 *
 *	The major hook is MAP::build, which is where the level layout
 *	is determined and used for determining which generator should
 *	be applied.
 */

#include <stdio.h>
#include <math.h>
#include "mygba.h"
#include "map.h"
#include "msg.h"
#include "rand.h"
#include "assert.h"
#include "creature.h"
#include "item.h"
#include "victory.h"

#include "rooms/allrooms.h"

void
MAP::clear()
{
    memset(mySquares, 0, MAP_WIDTH * MAP_HEIGHT);
    memset(myFlags, 0, MAP_WIDTH * MAP_HEIGHT);
    //memset(myFlags, SQUAREFLAG_LIT, MAP_WIDTH * MAP_HEIGHT);
    //memset(myFlags, SQUAREFLAG_MAPPED, MAP_WIDTH * MAP_HEIGHT);

    MOB		*mob, *mnext;
    ITEM	*item, *inext;

    for (mob = myMobHead; mob; mob = mnext)
    {
	mnext = mob->getNext();
	mob->setNext(0);
	delete mob;
    }
    myMobHead = 0;
    myMobCount = 0;

    for (item = myItemHead; item; item = inext)
    {
	inext = item->getNext();
	item->setNext(0);
	delete item;
    }
    myItemHead = 0;
    myItemCount = 0;
}

void
MAP::build(bool alreadysavedseed)
{
    // Save our random seed used...
    if (!alreadysavedseed)
	mySeed = rand_getseed();
    
    // Empty the map...
    clear();

    // Clear out our wall map.
    memset(ourWallMap, 0, MAP_WIDTH * MAP_HEIGHT);
    
    // Decide what sort of map to build.  If the current level is 10
    // we do the big room.
    // Rough map:
    // 0: Surface World.
    // 1-5: Roguelikes.
    // 6-7: Lit QIX.
    // 8-9: Unlit QIX.
    // 10: Big Room
    // 11-14: Mazes
    // 15: Cretan Minotaur
    // 16-17: Lit cavern
    // 18: Dark cavern
    // 19-20: Dark water cavern
    // 21: Dark cavern, Belweir
    // 22: Quizar
    // 23: Hruth
    // 24: Klaskov
    // 25: Circles of Hell.
    if (0)
    {
	// Stress test all room generators.
	static int ct = 0;
	ct++;
	switch (ct % 9)
	{
	    case 0:
		buildRoguelike();
		break;
	    case 1:
		buildDrunkenCavern(true, false, true, true);
		break;
	    case 2:
	    {
		static int	ct2 = 0;

		ct2++;
		switch (ct2 % 5)
		{
		    case 0:
			// We really don't want a crash here!
			buildSurfaceWorld();
			break;
		    case 1:
			buildQuest(GOD_ROGUE);
			break;
		    case 2:
			buildQuest(GOD_BARB);
			break;
		    case 3:
			buildQuest(GOD_FIGHTER);
			break;
		    case 4:
			buildTutorial();
			break;
		}
		break;
	    }
	    case 3:
		buildQix(true);
		break;
	    case 4:
		// This breaks, I eat my shoe.
		buildBigRoom();
		break;
	    case 5:
		buildMaze(rand_choice(4)+1);
		break;
	    case 6:
		buildRiverRoom();
		break;
	    case 7:
		buildHello();
		break;
	    case 8:
		buildSpaceShip();
		break;
	}

	if (!(ct & 127))
	    printf("Current room count %d\n", ct);
    }
    else if (glbStressTest && !glbMapStats)
    {
	// Pick a random depth.
	myDepth = rand_range(0, 25);
	// Pick a random branch... Currently only tridude supported.
	if (!rand_choice(15))
	    myBranch = BRANCH_TRIDUDE;
	else
	    myBranch = BRANCH_MAIN;
    }

    if (glbTutorial)
    {
	buildTutorial();
	return;
    }

    if (branchName() == BRANCH_TRIDUDE)
    {
	// Simple enough.
	buildSpaceShip();
	return;
    }

    if (myDepth == 0)
    {
	buildSurfaceWorld();
    }
    else if (myDepth <= 5)
    {
	//buildQix(true);
	//buildQuest(GOD_ROGUE);
	buildRoguelike();
    }
    else if (myDepth >= 6 && myDepth <= 7)
    {
	buildQix(true);
    }
    else if (myDepth >= 8 && myDepth <= 9)
    {
	buildQix(false);
    }
    else if (myDepth == 10)
    {
	buildBigRoom();
    }
    else if (myDepth >= 11 && myDepth <= 15)
    {
	buildMaze(rand_choice(4)+1);
    }
    else if (myDepth >= 16 && myDepth <= 17)
    {
	buildDrunkenCavern(true, false, true, true);
    }
    else if (myDepth >= 18 && myDepth <= 18)
    {
	buildDrunkenCavern(false, false, true, true);
    }
    else if (myDepth >= 19 && myDepth <= 20)
    {
	buildDrunkenCavern(false, true, true, true);
	// If depth is 20, we want hard floors to prevent cheating!
	myGlobalFlags &= ~MAPFLAG_DIG;
    }
    else if (myDepth == 21)
    {
	// Belweir's library is here!
	buildDrunkenCavern(false, false, true, true);
    }
    else if (myDepth == 22)
    {
	buildQuest(GOD_ROGUE);
    }
    else if (myDepth == 23)
    {
	buildQuest(GOD_BARB);
    }
    else if (myDepth == 24)
    {
	buildQuest(GOD_FIGHTER);
    }
    else if (myDepth == 25)
    {
	buildHello();
    }
    else
    {
	// This should not happen.
	buildRoguelike();
    }
    
    // Build some random traps.
    int 	numtraps, i;

    numtraps = rand_choice(myDepth);
    for (i = 0; i < numtraps; i++)
    {
	int		tries = 10;
	int		x, y;

	while (tries--)
	{
	    if (!findRandomLoc(x, y, MOVE_WALK,
			    true, false, false, false, false, false))
	    {
		tries = 0;
		break;
	    }

	    if (createTrap(x, y, 0))
		break;
	}
	// Failed to find after 10 tries? Give up on all traps!
	if (!tries)
	    break;
    }

    // Verify we have appropriate up and down stairs
#ifdef USEASSERT
    if (myDepth)
    {
	int x, y;
	UT_ASSERT(findTile(SQUARE_LADDERUP, x, y));
    }
    if (myDepth < 25)
    {
	int x, y;
	UT_ASSERT(findTile(SQUARE_LADDERDOWN, x, y));
    }
#endif
}

void
MAP::roomToMapCoords(int &x, int &y, const ROOM &room, int rx, int ry)
{
    int		tmp;

    if (room.rotation & ROOM_FLIP_X)
	x = room.definition->size.x - rx - 1;
    else
	x = rx;
    if (room.rotation & ROOM_FLIP_Y)
	y = room.definition->size.y - ry - 1;
    else
	y = ry;
    if (room.rotation & ROOM_FLOP)
    {
	tmp = x;
	x = y;
	y = tmp;
    }
    x += room.l.x;
    y += room.l.y;
}

void
MAP::mapToRoomCoords(int &rx, int &ry, const ROOM &room, int x, int y)
{
    int		tmp;
    
    x -= room.l.x;
    y -= room.l.y;
    if (room.rotation & ROOM_FLOP)
    {
	tmp = x;
	x = y;
	y = tmp;
    }
    if (room.rotation & ROOM_FLIP_Y)
	ry = room.definition->size.y - y - 1;
    else
	ry = y;
    if (room.rotation & ROOM_FLIP_X)
	rx = room.definition->size.x - x - 1;
    else
	rx = x;
}

// Draws a walled room using the inclusive rectangle specified.
void
MAP::drawRoom(const ROOM &room, bool lit, bool mazetype, bool caverntype)
{
    int		x, y;

    if (room.definition)
    {
	int		squarenum;
	int		rx, ry, i;

	squarenum = 0;
	for (ry = 0; ry < room.definition->size.y; ry++)
	{
	    for (rx = 0; rx < room.definition->size.x; rx++)
	    {
		roomToMapCoords(x, y, room, rx, ry);
		ourWallMap[y * MAP_WIDTH + x] = 1;
		SQUARE_NAMES		square;

		square = room.definition->squarelist[squarenum];
		if (caverntype && square == SQUARE_WALL)
		    square = SQUARE_EMPTY;
		if (caverntype && square == SQUARE_FLOOR)
		    square = SQUARE_CORRIDOR;
		if (mazetype && square == SQUARE_CORRIDOR)
		    square = SQUARE_FLOOR;
		if (mazetype && square == SQUARE_EMPTY)
		    square = SQUARE_WALL;
		setTile(x, y, square);

		squarenum++;
	    }
	}

	for (i = 0; room.definition->squareflaglist[i].data != SQUAREFLAG_NONE;
		i++)
	{
	    rx = room.definition->squareflaglist[i].x;
	    ry = room.definition->squareflaglist[i].y;
	    roomToMapCoords(x, y, room, rx, ry);
	    setFlag(x, y, room.definition->squareflaglist[i].data);
	}
	
	return;
    }

    for (y = room.l.y; y <= room.h.y; y++)
    {
        for (x = room.l.x; x <= room.h.x; x++)
	{
	    // Mark the entire room in the wall map.
	    ourWallMap[y * MAP_WIDTH + x] = 1;

	    if (x == room.l.x || x == room.h.x ||
		y == room.l.y || y == room.h.y)
	    {
		// Draw a wall.
		setTile(x, y, caverntype ? SQUARE_EMPTY : SQUARE_WALL);
		setFlag(x, y, SQUAREFLAG_LIT, lit);
	    }
	    else
	    {
		// Draw the floor.
		setTile(x, y, caverntype ? SQUARE_CORRIDOR : SQUARE_FLOOR);
		setFlag(x, y, SQUAREFLAG_LIT, lit);
	    }
	}
    }
}

bool
MAP::isMapExit(int x, int y) const
{
    UT_ASSERT(x >= 0 && x <= MAP_WIDTH);
    UT_ASSERT(y >= 0 && y <= MAP_HEIGHT);
    switch (getTile(x, y))
    {
	case SQUARE_DOOR:
	case SQUARE_BLOCKEDDOOR:
	case SQUARE_SECRETDOOR:
	case SQUARE_CORRIDOR:
	case SQUARE_FLOOR:
	case SQUARE_OPENDOOR:
	    return true;
	default:
	    break;
    }
    return false;
}

bool
MAP::isRoomExit(const ROOM &room, int x, int y) const
{
    UT_ASSERT(x >= 0 && x < room.definition->size.x);
    UT_ASSERT(y >= 0 && y < room.definition->size.y);

    UT_ASSERT(room.definition != 0);

    switch (room.definition->squarelist[x + y * room.definition->size.x])
    {
	case SQUARE_DOOR:
	case SQUARE_BLOCKEDDOOR:
	case SQUARE_SECRETDOOR:
	case SQUARE_CORRIDOR:
	case SQUARE_FLOOR:
	case SQUARE_OPENDOOR:
	    return true;

	case SQUARE_WATER:
	case SQUARE_LAVA:
	case SQUARE_ACID:
	default:
	    return false;
    }
}

bool
MAP::isMapPathway(int x, int y) const
{
    if (x < 0 || x >= MAP_WIDTH)
	return false;
    if (y < 0 || y >= MAP_HEIGHT)
	return false;

    switch (getTile(x, y))
    {
	case SQUARE_CORRIDOR:
	case SQUARE_FLOOR:
	case SQUARE_WATER:
	case SQUARE_LAVA:
	case SQUARE_ACID:
	    return true;
	default:
	    break;
    }
    return false;
}

bool
MAP::isTileWall(int tile) const
{
    switch (tile)
    {
	case SQUARE_WALL:
	case SQUARE_DOOR:
	case SQUARE_BLOCKEDDOOR:
	case SQUARE_SECRETDOOR:
	case SQUARE_OPENDOOR:
	    return true;
	default:
	    break;
    }
    return false;
}

bool
MAP::isMapWall(int x, int y) const
{
    // The -1 for width & hieght here is to intentionally leave a 1 space
    // border on the edges so we can scroll past the edges.
    if (x < 0 || x >= MAP_WIDTH-1)
	return true;
    if (y < 0 || y >= MAP_HEIGHT-1)
	return true;

    if (ourWallMap[y * MAP_WIDTH + x])
	return true;

    return false;
}

//
// Logic for setting a tile on a path...
//
void
MAP::setPathTile(int x, int y, bool lit, bool usefloor)
{
    SQUARE_NAMES	oldtile, newtile;

    oldtile = getTile(x, y);
    newtile = oldtile;		// Do nothing by default.
    switch (oldtile)
    {
	case SQUARE_EMPTY:
	    if (usefloor)
		newtile = SQUARE_FLOOR;
	    else
		newtile = SQUARE_CORRIDOR;
	    break;
	case SQUARE_FLOOR:
	    newtile = SQUARE_FLOOR;
	    break;
	case SQUARE_CORRIDOR:
	    if (usefloor)
		newtile = SQUARE_FLOOR;
	    else
		newtile = SQUARE_CORRIDOR;
	    break;
	case SQUARE_BLOCKEDDOOR:    
	    // We only have two choices here.  We don't want to
	    // turn into a corridor or normal door or we allow creatures
	    // to escape.  Secret door is acceptable as creatures don't
	    // yet search by default
	    switch (rand_choice(6))
	    {
		case 0:
		case 1:
		case 2:
		case 3:
		case 4:
		    newtile = SQUARE_BLOCKEDDOOR;
		    lit = true;
		    break;
		case 5:
		    newtile = SQUARE_SECRETDOOR;
		    // Inherit existing lit flag.
		    lit = getFlag(x, y, SQUAREFLAG_LIT);
		    break;
	    }
	    
	    break;
	case SQUARE_DOOR:    
	case SQUARE_WALL:
	case SQUARE_SECRETDOOR:
	case SQUARE_OPENDOOR:
	    // We have several choices:
	    // 1) Secret door
	    // 2) Door
	    // 3) No door.
	    switch (rand_choice(6))
	    {
		case 0:
		case 1:
		case 2:
		    newtile = SQUARE_DOOR;
		    lit = true;
		    break;
		case 3:
		    newtile = SQUARE_OPENDOOR;
		    lit = true;
		    break;
		case 4:
		    if (usefloor)
			newtile = SQUARE_FLOOR;
		    else
			newtile = SQUARE_CORRIDOR;
		    break;
		case 5:
		    newtile = SQUARE_SECRETDOOR;
		    // Inherit existing lit flag.
		    lit = getFlag(x, y, SQUAREFLAG_LIT);
		    break;
	    }
	    break;
	// Error checking:    
	default:
	    newtile = SQUARE_WATER;
	    lit = true;
	    break;
    }

    // Set the tile.
    setTile(x, y, newtile);
    setFlag(x, y, SQUAREFLAG_LIT, lit);
}

//
// This initializes ourDistanceMap with the distance to go, including
// tunnelling as allowed.  Thus, if isMapWall, we can't go through it.
// If we must tunnel, distance is 2.
// We return false if there is no path (should not happen!)
//
#define STACK_SIZE 2048

bool
MAP::buildMoveDistance(int px, int py, MOVE_NAMES move)
{
    s8		stackx[STACK_SIZE], stacky[STACK_SIZE];
    int		stackdepth = 0, stackbot = 0, stacktop = 0;
    int		dist, nextdist;
    int		dx, dy, x, y;
    
    // Initialize to infinity.
    memset(ourDistanceMap, 0xff, MAP_WIDTH * MAP_HEIGHT * sizeof(u16));

    // Zero distance to self.
    ourDistanceMap[py * MAP_WIDTH + px] = 0;
    
    // Add to our distance stack...
    stackx[stacktop] = px;
    stacky[stacktop] = py;
    stacktop++;
    stackdepth++;
    stacktop &= STACK_SIZE-1;
    
    // And recurse...
    while (stackdepth)
    {
	// Pull top guy off the stack...
	stackdepth--;
	px = stackx[stackbot];
	py = stacky[stackbot];
	stackbot++;

	// Now, see if anyone will have a shorter distance if they came
	// from here...
	dist = ourDistanceMap[py * MAP_WIDTH + px];

	FORALL_4DIR(dx, dy)
	{
	    y = py + dy;
	    if (y < 0)
		continue;
	    if (y > MAP_HEIGHT-1)
		continue;

	    x = px + dx;
	    if (x < 0)
		continue;
	    if (x > MAP_WIDTH-1)
		continue;

	    // See if we can go there...
	    if (// canMove(x, y, move, true, true, true) ||
		(glb_squaredefs[getTile(x, y)].movetype & move) ||
		getTile(x, y) == SQUARE_SECRETDOOR ||
		getTile(x, y) == SQUARE_DOOR ||
		getTile(x, y) == SQUARE_BLOCKEDDOOR)
	    {
		nextdist = 1;
		nextdist += dist;
		// Check if it is strictly faster...
		if (nextdist < ourDistanceMap[y * MAP_WIDTH + x])
		{
		    // Store it.
		    ourDistanceMap[y * MAP_WIDTH + x] = nextdist;
		    // Add to our stack.
		    stackx[stacktop] = x;
		    stacky[stacktop] = y;
		    stackdepth++;
		    stacktop++;
		    stacktop &= STACK_SIZE-1;
		    UT_ASSERT(stackdepth < STACK_SIZE-2);
		}
	    }
	}
    }

    return true;
}

bool
MAP::buildDistance(int px, int py)
{
    s8		stackx[STACK_SIZE], stacky[STACK_SIZE];
    int		stackdepth = 0;
    u16		dist, nextdist;
    int		dx, dy, x, y;
    
    // Initialize to infinity.
    memset(ourDistanceMap, 0xff, MAP_WIDTH * MAP_HEIGHT * sizeof(u16));

    // Zero distance to self.
    ourDistanceMap[py * MAP_WIDTH + py] = 0;
    
    // Add to our distance stack...
    stackx[stackdepth] = px;
    stacky[stackdepth] = py;
    stackdepth++;
    
    // And recurse...
    while (stackdepth)
    {
	// Pull top guy off the stack...
	stackdepth--;
	px = stackx[stackdepth];
	py = stacky[stackdepth];

	// Now, see if anyone will have a shorter distance if they came
	// from here...
	dist = ourDistanceMap[py * MAP_WIDTH + px];

	for (dy = -1; dy <= 1; dy++)
	{
	    y = py + dy;
	    if (y < 0)
		continue;
	    if (y >= MAP_HEIGHT-1)
		break;
	    for (dx = -1; dx <= 1; dx++)
	    {
		if (!dx && !dy)
		    continue;

		x = px + dx;
		if (x < 0)
		    continue;
		if (x >= MAP_WIDTH-1)
		    break;

		// See if we can go there...
		if (!isMapWall(x, y))
		{
		    nextdist = (getTile(x, y) == SQUARE_EMPTY) ? 2 : 1;
		    //nextdist = 1;
		    nextdist += dist;
		    // Check if it is strictly faster...
		    if (nextdist < ourDistanceMap[y * MAP_WIDTH + x])
		    {
			// Store it.
			ourDistanceMap[y * MAP_WIDTH + x] = nextdist;
			// Add to our stack.
			stackx[stackdepth] = x;
			stacky[stackdepth] = y;
			stackdepth++;
			UT_ASSERT(stackdepth < STACK_SIZE);
		    }
		}
	    }
	}
    }

    return true;
}

//
// Draw path using a distance function.
//
bool
MAP::drawPathStraight(int sx, int sy, int ex, int ey, bool lit)
{
    u16		dist, dp, dn;
    int		d[2];
    int		dir;
    int		s[2], e[2];
    int		rev = 0;
    
    buildDistance(ex, ey);
    UT_ASSERT(!"Got to draw...");

    // Check to see if a path is possible....
    if (ourDistanceMap[sy * MAP_WIDTH + sx] == 0xffff)
    {
	UT_ASSERT(!"Impossibly map!");
	return false;
    }

    s[0] = sx;
    s[1] = sy;
    e[0] = ex;
    e[1] = ey;
    
    // Initial random direction.
    dir = rand_choice(2);

    setPathTile(s[0], s[1], lit, false);
    
    while (s[0] != e[0] || s[1] != e[1])
    {
	// Determine which way is down in dir....
	dist = ourDistanceMap[s[1] * MAP_WIDTH + s[0]];

	d[!dir] = 0;
	dp = 0xffff;
	dn = 0xffff;
	if ((s[dir] + 1) < MAP_WIDTH)
	{
	    d[dir] = 1;
	    dp = ourDistanceMap[(s[1] + d[1]) * MAP_WIDTH + s[0] + d[0]];
	}
	if ((s[dir] - 1) >= 0)
	{
	    d[dir] = -1;
	    dn = ourDistanceMap[(s[1] + d[1]) * MAP_WIDTH + s[0] + d[0]];
	}
	if (dp >= dist && dn >= dist)
	{
	    // No one has a faster distance!  Change direction.
	    UT_ASSERT(!rev);
	    rev++;
	    dir = !dir;
	    continue;
	}
	if (dp < dist && dn < dist)
	{
	    // Both are shorter, this is a cusp which by definition
	    // cannot last.  Pick a random direction.
	    d[dir] = rand_sign();
	}
	else if (dp < dist)
	{
	    d[dir] = 1;
	}
	else
	{
	    UT_ASSERT(dn < dist);
	    // Dn is smallest.
	    d[dir] = -1;
	}
	rev = 0;

	// Go in this direction until it is unprofitable...
	while (s[0] != e[0] || s[1] != e[1])
	{
	    setPathTile(s[0], s[1], lit, false);
	    s[0] += d[0];
	    s[1] += d[1];

	    // Check if next tile is good...
	    dist = ourDistanceMap[s[1] * MAP_WIDTH + s[0]];

	    if (s[dir] + d[dir] < 0)
		break;
	    if (s[dir] + d[dir] >= MAP_WIDTH)
		break;
	    if (ourDistanceMap[(s[1]+d[1]) * MAP_WIDTH + s[0] + d[0]] >= dist)
	    {
		// No longer profitable, stop moving this way!
		break;
	    }
	}
    }
    setPathTile(s[0], s[1], lit, false);
    return true;
}

//
// Draw a path from the given location to the given location.
// This will avoid walls.
// It will return if it failed.  It shouldn't, but shit happens.
//
bool
MAP::drawPath(int sx, int sy, int ex, int ey, bool lit)
{
    int		d[2];
    int		i, dir, wallhit;
    int		s[2], e[2], n[2];
    int		len = 0;
    int		ncnt = 0;

    s[0] = sx;
    s[1] = sy;
    e[0] = ex;
    e[1] = ey;
    
    // Initial random direction.
    dir = rand_choice(2);

    setPathTile(s[0], s[1], lit, false);
    
    while (s[0] != e[0] || s[1] != e[1])
    {
	// Find our current direction to go...
	for (i = 0; i < 2; i++)
	    d[i] = SIGN(e[i] - s[i]);

	// Switch our direction.
	dir = !dir;
	
	// If we are aligned in that direction, try the opposite.
	if (!d[dir])
	    dir = !dir;

	// Move in the direction dir until a random chance fails,
	// or we get aligned with a destination.
	wallhit = 0;
	while (1)
	{
	    if (rand_chance(40))
	    {
		// Stop digging!
		break;
	    }

	    // Alignment...  This only counts for straight moves,
	    // if bounced off a wall we don't want to trigger this.
	    if (!wallhit && s[dir] == e[dir])
		break;

	    // Calculate the next pos...
	    n[0] = s[0];
	    n[1] = s[1];
	    n[dir] += d[dir];
	    // Check if our current dig direction is valid...
	    ncnt = 0;
	    while (isMapWall(n[0], n[1]))
	    {
		// Not a valid dig direction!  Rotate 90 degrees
		// and go in a random direction...
		// As we never build walls adjacent and they are square,
		// this guarantees a non-wall.
		// Except it doesn't.  WTF?
		dir = !dir;
		if (!d[dir])
		    d[dir] = rand_sign();
		n[0] = s[0];
		n[1] = s[1];
		n[dir] += d[dir];
		wallhit = 1;
		ncnt++;
		if (ncnt > 100)
		{
		    // THis fails when we hit the bottom most wall,
		    // turn to the left,
		    // and then hit the left wall prior to deciding to reset
		    // NOte that alignment will never trigger as wallhit
		    // is true, and we could have been going the wrong
		    // way anyways.
		    // Our abort here is reasonable enough.
		    return false;
		}
	    }
	    // Move in the desired direction...
	    s[dir] += d[dir];
	    // Write out the path tile...
	    setPathTile(s[0], s[1], lit, false);

	    len++;
	    if (len > 100)
		return false;
	}
    }
    return true;
}

void
MAP::drawPath_old(int sx, int sy, int ex, int ey, bool lit)
{
    int		dx = 0, dy = 0, dir, dirlen;
    
    dir = 0;		// 1 is y, -1 is x.
    while (sx != ex || sy != ey)
    {
	// Choose our direction...
	dx = rand_sign();
	if (sx < ex)
	    dx = 1;
	else if (sx > ex)
	    dx = -1;
	dy = rand_sign();
	if (sy < ey)
	    dy = 1;
	else if (sy > ey)
	    dy = -1;

	// Every so often the builder is drunk...
	if (0) // rand_chance(30))
	{
	    dx *= -1;
	    dy *= -1;
	}

	if (dir != 0)
	    dir *= -1;
	else
	{
	    if (dx && dy)
	    {
		dir = rand_sign();
	    }
	    else if (dx)
		dir = -1;
	    else
		dir = 1;
	}

	if (dir < 0)
	    dy = 0;
	else
	    dx = 0;

	// Find max len...
	if (dir < 0)
	    dirlen = abs(ex - sx);
	else
	    dirlen = abs(ey - sy);

	if (dirlen > 3)
	{
	    // Move at least 3, but choose a randome length otherwise...
	    dirlen = rand_range(3, dirlen);
	}

	// Move dirlen or a wall, whatever is first...
	while (dirlen)
	{
	    setPathTile(sx, sy, lit, false);
	    if (isMapWall(sx + dx, sy + dy))
	    {
		// Don't want to tunnel, so quit this path.
		if (!(dx && dy))
		    return;
		break;
	    }
	    // Move forward...
	    sx += dx;
	    sy += dy;
	    dirlen--;
	}
    }
    // Hit the end, draw the last square...
    setPathTile(ex, ey, lit, false);
}

bool
MAP::drawCorridor(int sx, int sy, int sdx, int sdy,
	     int ex, int ey, int edx, int edy,
	     bool lit)
{
    bool		success;
    
    success = drawPath(sx+sdx, sy+sdy, ex+edx, ey+edy, lit);
    
    // Draw our doors.  We only do this if our path creation
    // was successful.
    if (success)
    {
	setPathTile(sx, sy, true, false);
	setPathTile(ex, ey, true, false);
    }
    return success;
}

//
// Checks to see if we can build the specified room.
// The room itself must be filled with void, for one space
// around the room we should have no walls (don't want touching rooms
// as that will annoy the path builder)
// The boundary of the map counts as a wall for this purpose.
//
bool
MAP::checkRoomFits(const ROOM &room)
{
    int		x, y;

    for (y = room.l.y; y <= room.h.y; y++)
        for (x = room.l.x; x <= room.h.x; x++)
	    if (getTile(x, y) != SQUARE_EMPTY)
		return false;
    
    // Test the border...
    for (x = room.l.x-1; x <= room.h.x+1; x++)
    {
	if (isMapWall(x, room.l.y-1))
	    return false;
	if (isMapWall(x, room.h.y+1))
	    return false;
    }
    // And the x sides...
    for (y = room.l.y-1; y <= room.h.y+1; y++)
    {
	if (isMapWall(room.l.x-1, y))
	    return false;
	if (isMapWall(room.h.x+1, y))
	    return false;
    }

    // Everything passes...
    return true;
}

const ROOM_DEF *
MAP::chooseRandomRoom(int depth)
{
    int		 prob[NUM_ALLROOMDEFS];
    const ROOM_DEF	*def;
    int		 i, totalprob = 0, offset;

    for (i = 0; i < NUM_ALLROOMDEFS; i++)
    {
	def = glb_allroomdefs[i];

	prob[i] = def->rarity;

	if (def->minlevel >= 0 &&
	    def->minlevel > depth)
	    prob[i] = 0;
	if (def->maxlevel >= 0 &&
	    def->maxlevel < depth)
	    prob[i] = 0;

	// Mandatory rooms are always built on any level that
	// they are legal.
	if (prob[i] && def->mandatory)
	    return def;

	totalprob += prob[i];
    }
    
    offset = rand_choice(totalprob);
    for (i = 0; i < NUM_ALLROOMDEFS; i++)
    {
	if (offset < prob[i])
	    break;
	offset -= prob[i];
    }
    if (i >= NUM_ALLROOMDEFS)
    {
	UT_ASSERT(!"Could not find a room!");
	i = NUM_ALLROOMDEFS-1;
    }

    return glb_allroomdefs[i];
}

void
MAP::buildRandomRoom(ROOM &room)
{
    // We don't let the room lie on a map boundary as then if it gets
    // an exit on that side, the corridor won't be able to propogate.
    room.l.x = rand_range(1, MAP_WIDTH-4);
    room.l.y = rand_range(1, MAP_HEIGHT-4);
    room.h.x = rand_range(room.l.x + 3, MIN(room.l.x + 8, MAP_WIDTH-2));
    room.h.y = rand_range(room.l.y + 3, MIN(room.l.y + 8, MAP_HEIGHT-2));
    room.definition = 0;
}

void
MAP::buildRandomRoomFromDefinition(ROOM &room, const ROOM_DEF *def)
{
    UT_ASSERT((int)def);
    if (!def)
    {
	buildRandomRoom(room);
	return;
    }

    int			width, height;

    room.rotation = rand_choice(8);

    if (room.rotation & ROOM_FLOP)
    {
	width = def->size.y;
	height = def->size.x;
    }
    else
    {
	width = def->size.x;
	height = def->size.y;
    }
    
    // We do a bit of a border on these rooms to ensure
    // that we can always force exits on the maze levels.
    room.l.x = rand_range(3, MAP_WIDTH - 3 - width);
    room.l.y = rand_range(3, MAP_HEIGHT - 3 - height);

    // If the room overrides x or y, override the value.
    if (def->x >= 0)
	room.l.x = def->x;
    if (def->y >= 0)
	room.l.y = def->y;
    
    // Note room's are INCLUSIVE coords, while size defines
    // exclusive.
    room.h.x = room.l.x + width - 1;
    room.h.y = room.l.y + height - 1;

    UT_ASSERT(room.l.x >= 0);
    UT_ASSERT(room.h.x < MAP_WIDTH);
    UT_ASSERT(room.l.y >= 0);
    UT_ASSERT(room.h.y < MAP_HEIGHT);

    room.definition = def;
}

void
MAP::closeUnusedExits(const ROOM &room, bool force)
{
    if (room.definition)
    {
	// Only close on special rooms.
	int		x, y, rx, ry;
	int		lastx = 0, lasty = 0;
	int		lastdx = 0, lastdy = 0;
	SQUARE_NAMES	lastsquare = SQUARE_FLOOR;

	for (x = room.l.x; x <= room.h.x; x++)
	{
	    mapToRoomCoords(rx, ry, room, x, room.l.y);
	    if (isRoomExit(room, rx, ry))
	    {
		lastx = x;	lasty = room.l.y;
		lastdx = 0;	lastdy = -1;
		lastsquare = getTile(x, room.l.y);
		if (!isMapPathway(x, room.l.y-1))
		    setTile(x, room.l.y, 
			    getTile(x-1, room.l.y));
		else
		    force = false;
	    }
	    mapToRoomCoords(rx, ry, room, x, room.h.y);
	    if (isRoomExit(room, rx, ry))
	    {
		lastx = x;	lasty = room.h.y;
		lastdx = 0;	lastdy = 1;
		lastsquare = getTile(x, room.h.y);
		if (!isMapPathway(x, room.h.y+1))
		    setTile(x, room.h.y, 
			    getTile(x-1, room.h.y));
		else
		    force = false;
	    }
	}
	for (y = room.l.y; y <= room.h.y; y++)
	{
	    mapToRoomCoords(rx, ry, room, room.l.x, y);
	    if (isRoomExit(room, rx, ry))
	    {
		lastx = room.l.x;	lasty = y;
		lastdx = -1;		lastdy = 0;
		lastsquare = getTile(room.l.x, y);
		if (!isMapPathway(room.l.x-1, y))
		    setTile(room.l.x, y, 
			    getTile(room.l.x, y-1));
		else
		    force = false;
	    }
	    mapToRoomCoords(rx, ry, room, room.h.x, y);
	    if (isRoomExit(room, rx, ry))
	    {
		lastx = room.h.x;	lasty = y;
		lastdx = 1;		lastdy = 0;
		lastsquare = getTile(room.h.x, y);
		if (!isMapPathway(room.h.x+1, y))
		    setTile(room.h.x, y, 
			    getTile(room.h.x, y-1));
		else
		    force = false;
	    }
	}

	// TODO: Have option to wipe room if doesn't work out
	// nicely.

	if (force)
	{
	    // We must force at least one exit.
	    // We dig continuously in the direction given by our last exit
	    // until we find a way out.
	    UT_ASSERT(lastdx || lastdy);
	    if (lastdx || lastdy)
	    {
		bool			found = false;
		SQUARE_NAMES		square = SQUARE_WALL;
		int			pass;
		int			curdx = 0, curdy = 0;

		for (pass = 0; pass < 3; pass++)
		{
		    found = true;

		    // Determine initial x & curdx & curdy.
		    switch (pass)
		    {
			case 0:		// Straight
			    curdx = lastdx;
			    curdy = lastdy;
			    break;
			case 1:		// Turn
			    curdx = !lastdx;
			    curdy = !lastdy;
			    break;
			case 2:		// Other turn.
			    curdx = -!lastdx;
			    curdy = -!lastdy;
			    break;
		    }
		    // Always move in last delta direction because
		    // that is the one that will get us outside of the
		    // container.
		    x = lastx+lastdx;
		    y = lasty+lastdy;

		    // Only prefetch this if it has a chance of being valid.
		    if (isMapPathway(x, y))
			square = getTile(x, y);
		    while (!isMapPathway(x, y))
		    {
			if (x < 0 || x >= MAP_WIDTH ||
			    y < 0 || y >= MAP_HEIGHT)
			{
			    // complete failure.
			    found = false;
			    break;
			}
			// Check adjacent squares to see if this opened up.
			if (isMapPathway(x + !curdx, y + !curdy))
			{
			    square = getTile(x + !curdx, y + !curdy);
			    break;
			}
			if (isMapPathway(x - !curdx, y - !curdy))
			{
			    square = getTile(x - !curdx, y - !curdy);
			    break;
			}
			x += curdx;
			y += curdy;
			if (isMapPathway(x, y))
			    square = getTile(x, y);
		    }

		    if (found)
		    {
			lastx += lastdx;
			lasty += lastdy;
			break;
		    }
		}
		
		if (found)
		{
		    // We found a direction!  Fill it in!
		    while (x != lastx || y != lasty)
		    {
			setTile(x, y, square);
			x -= curdx;
			y -= curdy;
		    }
		    setTile(x, y, square);

		    // Restore the last square.
		    {
			x -= lastdx;
			y -= lastdy;
			setTile(x, y, lastsquare);
		    }
		}
	    }
	}
    }
}

void
MAP::populateRoom(const ROOM &room)
{
    if (!room.definition)
	return;

    // It is very important we apply the room flags before we test
    // if loading as we want reloaded rooms to have the same flags
    // Otherwise populate traps will behave differently as it will
    // think it can make holes (and players can zap wands all of a 
    // sudden)

    // Apply the flags from the room definition.
    if (!room.definition->allowgeneration)
	myGlobalFlags &= ~MAPFLAG_NEWMOBS;
    if (!room.definition->allowdig)
	myGlobalFlags &= ~MAPFLAG_DIG;
    if (!room.definition->allowitems)
	myGlobalFlags |= MAPFLAG_NOITEMS;
    if (!room.definition->allowtel)
	myGlobalFlags |= MAPFLAG_NOTELE;

    // If we are loading from disk, we've already populated the room
    // from disk.
    if (ourIsLoading)
	return;

    RAND_STATEPUSH	saverng;

    int		x, y;
    const PT2	*pt;
    MOB		*mob;
    ITEM	*item;
    MOBSTACK	 roommobs;

    // Create listed mobs.
    for (pt = room.definition->moblist; pt->data != MOB_NONE; pt++)
    {
	mob = MOB::create((MOB_NAMES) pt->data);
	
	roomToMapCoords(x, y, room, pt->x, pt->y);
	mob->move(x, y, true);
	registerMob(mob);
	roommobs.append(mob);
    }

    int			i;
    MOB			*leader = 0;

    // Create mobs of the given level.
    for (pt = room.definition->moblevellist; pt->data != MOBLEVEL_NONE; pt++)
    {
	int			threat;

	// If there is already a mob here, uniquify it.
	if (pt->data == MOBLEVEL_UNIQUE)
	{
	    roomToMapCoords(x, y, room, pt->x, pt->y);
	    mob = getMob(x, y);
	    if (mob)
	    {
		mob->makeUnique();
		continue;
	    }
	}

	threat = getThreatLevel();
	threat += glb_mobleveldefs[pt->data].maxlevel;

	mob = MOB::createNPC(threat);

	if (pt->data == MOBLEVEL_UNIQUE)
	    mob->makeUnique();
	
	roomToMapCoords(x, y, room, pt->x, pt->y);
	mob->move(x, y, true);
	registerMob(mob);
	roommobs.append(mob);
    }

    // Apply intrinsics to any mobs:
    for (pt = room.definition->intrinsiclist; pt->data != INTRINSIC_NONE; pt++)
    {
	MOB		*mob;

	roomToMapCoords(x, y, room, pt->x, pt->y);
	mob = getMob(x, y);
	if (mob)
	{
	    mob->setIntrinsic((INTRINSIC_NAMES) pt->data);
	    if (pt->data == INTRINSIC_LEADER)
	    {
		leader = mob;
	    }
	}
    }

    // If there is a leader, tame all the room's mobs to it.
    // Ideally we'd do something tad smarter to allow multiple
    // groups to be made.
    if (leader)
    {
	for (i = 0; i < roommobs.entries(); i++)
	{
	    // Don't self tame :>
	    if (roommobs(i) == leader)
		continue;

	    roommobs(i)->makeSlaveOf(leader);
	}
    }

    // Create the listed items.
    for (pt = room.definition->itemlist; pt->data != ITEM_NONE; pt++)
    {
	item = ITEM::create((ITEM_NAMES) pt->data);

	roomToMapCoords(x, y, room, pt->x, pt->y);
	acquireItem(item, x, y, 0);
    }
    
    // Create the listed item types.
    for (pt = room.definition->itemtypelist; pt->data != ITEMTYPE_NONE; pt++)
    {
	item = ITEM::createRandomType((ITEMTYPE_NAMES) pt->data);

	roomToMapCoords(x, y, room, pt->x, pt->y);
	acquireItem(item, x, y, 0);
    }

    // Create the signposts
    for (pt = room.definition->signpostlist; pt->data != SIGNPOST_NONE; pt++)
    {
	roomToMapCoords(x, y, room, pt->x, pt->y);
	addSignPost((SIGNPOST_NAMES) pt->data, x, y);
    }
}

void
MAP::addSignPost(SIGNPOST_NAMES post, int x, int y)
{
    if (!mySignList)
	mySignList = new SIGNLIST;

    mySignList->append(post, x, y);
}

void
MAP::chooseRandomExit(int *entrance, int *delta, const ROOM &room)
{
    if (room.definition)
    {
	// We need to find valid door squares on the boundary
	// only these can be exits.
	int		x, y;
	int		*estack, *dstack;
	int		numexit = 0, choice;

	// Maximum size of the stacks is the perimeter of the room.
	estack = new int[ 2 * (room.h.x - room.l.x + 1) +
			  2 * (room.h.y - room.l.y + 1) ];
	dstack = new int[ 2 * (room.h.x - room.l.x + 1) +
			  2 * (room.h.y - room.l.y + 1) ];

	for (x = room.l.x; x <= room.h.x; x++)
	{
	    if (isMapExit(x, room.l.y))
	    {
		estack[numexit*2] = x;
		estack[numexit*2+1] = room.l.y;
		dstack[numexit*2] = 0;
		dstack[numexit*2+1] = -1;
		numexit++;
	    }
	    if (isMapExit(x, room.h.y))
	    {
		estack[numexit*2] = x;
		estack[numexit*2+1] = room.h.y;
		dstack[numexit*2] = 0;
		dstack[numexit*2+1] = 1;
		numexit++;
	    }
	}
	for (y = room.l.y; y <= room.h.y; y++)
	{
	    if (isMapExit(room.l.x, y))
	    {
		estack[numexit*2] = room.l.x;
		estack[numexit*2+1] = y;
		dstack[numexit*2] = -1;
		dstack[numexit*2+1] = 0;
		numexit++;
	    }
	    if (isMapExit(room.h.x, y))
	    {
		estack[numexit*2] = room.h.x;
		estack[numexit*2+1] = y;
		dstack[numexit*2] = 1;
		dstack[numexit*2+1] = 0;
		numexit++;
	    }
	}

	UT_ASSERT(numexit);
	choice = rand_choice(numexit);

	entrance[0] = estack[choice*2];
	entrance[1] = estack[choice*2+1];
	delta[0] = dstack[choice*2];
	delta[1] = dstack[choice*2+1];
	
	delete [] estack;
	delete [] dstack;

	return;
    }
    
    switch (rand_choice(4))
    {
	case 0:
	    entrance[0] = room.l.x;
	    entrance[1] = rand_range(room.l.y+1, room.h.y-1);
	    delta[0] = -1;
	    delta[1] = 0;
	    break;
	case 1:		
	    entrance[0] = room.h.x;
	    entrance[1] = rand_range(room.l.y+1, room.h.y-1);
	    delta[0] = 1;
	    delta[1] = 0;
	    break;
	case 2:
	    entrance[0] = rand_range(room.l.x+1, room.h.x-1);
	    entrance[1] = room.l.y;
	    delta[0] = 0;
	    delta[1] = -1;
	    break;
	case 3:		
	    entrance[0] = rand_range(room.l.x+1, room.h.x-1);
	    entrance[1] = room.h.y;
	    delta[0] = 0;
	    delta[1] = 1;
	    break;
    }
}

void
MAP::buildBigRoom()
{
    ROOM		room;
    int			x, y;

    room.l.x = 1;
    room.l.y = 1;
    room.h.x = 30;
    room.h.y = 30;
    room.definition = 0;
    drawRoom(room, true, false, false);

    // Build random up & down stair cases.
    while (1)
    {
	x = rand_range(2, 29);
	y = rand_range(2, 29);

	if (getTile(x, y) == SQUARE_FLOOR)
	{
	    setTile(x, y, SQUARE_LADDERUP);
	    // setTile(x-1, y, SQUARE_LADDERDOWN);
	    break;
	}
    } 
    while (1)
    {
	x = rand_range(2, 29);
	y = rand_range(2, 29);

	if (getTile(x, y) == SQUARE_FLOOR)
	{
	    setTile(x, y, SQUARE_LADDERDOWN);
	    break;
	}
    } 
}

void
MAP::buildRoguelike()
{
    // Draw some rooms...
    ROOM	rooms[20];
    int		numroom = 0;
    int		fails = 0;
    int		i;
    int		src;
    int		room, x, y;
    int		maxdark, numdark;
    bool	isdark;

    // Track number of dark rooms.
    numdark = 0;
    // Only have up to depth - 1 dark rooms.  This prevents
    // start levels from having lots of dark rooms.
    maxdark = myDepth-1;
    
    // Build as many rooms as fits, up to twenty.
    while (fails < 40 && numroom < 20)
    {
	if (!numroom)
	{
	    buildRandomRoomFromDefinition(rooms[numroom],
			      chooseRandomRoom(myDepth));
	}
	else
	{
	    buildRandomRoom(rooms[numroom]);
	}
	if (checkRoomFits(rooms[numroom]))
	{
	    isdark = false;
	    // Decide if it should be dark.
	    if (numdark < maxdark)
	    {
		isdark = rand_chance(10);
	    }
	    if (isdark)
		numdark++;

	    drawRoom(rooms[numroom], !isdark, false, false);
	    numroom++;
	}
	else
	    fails++;
    }

    // Now, build corridors...
    // We want every room to be connected.
    // Thus, we have a pool of i connected rooms.  We each
    // round take i+1 and connect it to one of our connect rooms
    // at random.

    // If we fail to connect 40 times, we declare this dungeon sucky
    // and go again...
    fails = 0;
    for (i = 0; i < numroom - 1; i++)
    {
	int		cs[2], ce[2], ds[2], de[2];
	src = rand_range(0, i);
	
	chooseRandomExit(cs, ds, rooms[src]);
	chooseRandomExit(ce, de, rooms[i+1]);
	
	// Draw a corridor between these two rooms.
	if (!drawCorridor(cs[0], cs[1], ds[0], ds[1],
			  ce[0], ce[1], de[0], de[1]))
	{
	    // Failed to draw a corridor, try again.
	    i--;
	    fails++;
	    if (fails > 40)
		break;
	    
	    continue;
	}
    }
    if (fails > 40)
    {
	UT_ASSERT(!"Failed to build a dungeon, retrying!");
	build(true);
	return;
    }

    // Now we close any unused exits in our special rooms...
    for (room = 0; room < numroom; room++)
    {
	closeUnusedExits(rooms[room], false);
	populateRoom(rooms[room]);
    }
    
    // Now, we pick a random up and down stair case...
    while (1)
    {
	room = rand_choice(numroom);

	// If there was only one room, we trivially allow so we 
	// can't get an infinite loop if said rooms doesn't allow stairs.
	if (numroom > 1 &&
	    rooms[room].definition && !rooms[room].definition->allowstairs)
	    continue;
	
	x = rand_range(rooms[room].l.x+1, rooms[room].h.x-1);
	y = rand_range(rooms[room].l.y+1, rooms[room].h.y-1);

	if (getTile(x, y) == SQUARE_FLOOR ||
	    getTile(x, y) == SQUARE_CORRIDOR)
	{
	    setTile(x, y, SQUARE_LADDERDOWN);
	    break;
	}
    } 
    while (1)
    {
	room = rand_choice(numroom);

	if (numroom > 1 &&
	    rooms[room].definition && !rooms[room].definition->allowstairs)
	    continue;
	
	x = rand_range(rooms[room].l.x+1, rooms[room].h.x-1);
	y = rand_range(rooms[room].l.y+1, rooms[room].h.y-1);

	if (getTile(x, y) == SQUARE_FLOOR ||
	    getTile(x, y) == SQUARE_CORRIDOR)
	{
	    setTile(x, y, SQUARE_LADDERUP);
	    break;
	}
    } 
}

static int
findCell(int *cells, int c)
{
    int		n;

    n = cells[c];
    if (n == c)
	return c;

    n = findCell(cells, n);
    cells[c] = n;
    return n;
}

void
MAP::smooth(SQUARE_NAMES floor, SQUARE_NAMES wall)
{
    int			x, y;
    int			n;

    for (y = 1; y < MAP_HEIGHT-1; y++)
    {
	for (x = 1; x < MAP_WIDTH-1; x++)
	{
	    if (getTile(x, y) == floor)
	    {
		// If we have 3 non floor neighbours, delete.
		n = 0;
		if (getTile(x-1, y) == wall)
		    n++;
		if (getTile(x+1, y) == wall)
		    n++;
		if (getTile(x, y-1) == wall)
		    n++;
		if (getTile(x, y+1) == wall)
		    n++;

		if (n >= 3)
		{
		    setTile(x, y, wall);
		}
	    }
	}
    }
}

void
MAP::fillWithTile(int x, int y, SQUARE_NAMES newtile, SQUARE_NAMES oldtile)
{
    int			stackpos;
#define STACKSIZE 500
    int			stack[STACKSIZE];

    stackpos = 0;
    stack[stackpos++] = y * MAP_WIDTH + x;
    while (stackpos)
    {
	stackpos--;
	x = stack[stackpos] & 31;
	y = stack[stackpos] >> 5;

	if (getTile(x, y) == oldtile)
	{
	    setTile(x, y, newtile);

	    if ((x > 0) && getTile(x-1, y) == oldtile)
		stack[stackpos++] = (x-1) + (y * MAP_WIDTH);
	    if (stackpos >= STACKSIZE)
		continue;
	    if ((x < MAP_WIDTH-1) && getTile(x+1, y) == oldtile)
		stack[stackpos++] = (x+1) + (y * MAP_WIDTH);
	    if (stackpos >= STACKSIZE)
		continue;
	    if ((y > 0) && getTile(x, y-1) == oldtile)
		stack[stackpos++] = x + (y - 1) * MAP_WIDTH;
	    if (stackpos >= STACKSIZE)
		continue;
	    if ((y < MAP_HEIGHT-1) && getTile(x, y+1) == oldtile)
		stack[stackpos++] = x + (y + 1) * MAP_WIDTH;
	    if (stackpos >= STACKSIZE)
		continue;
	}
    }
}

void
MAP::drawQixWall(int sx, int sy, int dx, int dy, bool islit)
{
    int		x, y;
    int		range;

    // It is possible that we were given an out of range start
    // value.  This is not a problem, but we should not go
    // writing.
    if (!compareTile(sx, sy, SQUARE_FLOOR))
	return;

    range = rand_range(5, 20);

    x = sx;
    y = sy;
    while (range)
    {
	setTile(x, y, SQUARE_WALL);

	// See if now adjacent.
	// These are intentionally crossed over!
	if (!compareTile(x+dy, y+dx, SQUARE_FLOOR))
	    break;
	if (!compareTile(x-dy, y-dx, SQUARE_FLOOR))
	    break;
	if (!compareTile(x+dx, y+dy, SQUARE_FLOOR))
	    break;

	// Keep building.
	x += dx;
	y += dy;
	range--;
    }

    // If we didn't hit anything, rotate.
    if (!range)
    {
	// Rotate...
	x -= dx;
	y -= dy;
	if (dx)
	{
	    dy = dx;
	    dx = 0;
	}
	else
	{
	    dx = -dy;
	    dy = 0;
	}
	x += dx;
	y += dy;
	drawQixWall(x, y, dx, dy, islit);
    }
}

void
MAP::buildQix(bool islit)
{
    int			x, y, cx, cy, dx, dy;
    int			i;
    ROOM		room;
    int			numwalls, tries, dir;

    // Build a drunken cavern to use as our guide.
    buildDrunkenCavern(islit, false, false, false);

    smooth(SQUARE_CORRIDOR, SQUARE_EMPTY);

    // Set the entire map to normal ground:
    // Boundary becomes walls
    for (y = 0; y < MAP_HEIGHT; y++)
    {
	for (x = 0; x < MAP_WIDTH; x++)
	{
	    int		oldtile;

	    oldtile = getTile(x, y);
	    if (oldtile == SQUARE_CORRIDOR)
		setTile(x, y, SQUARE_FLOOR);
	    else if (oldtile == SQUARE_EMPTY)
		setTile(x, y, SQUARE_WALL);

	    // For debugging:
	    // setFlag(x, y, SQUAREFLAG_MAPPED);
	}
    }

    // Create the special room:
    buildRandomRoomFromDefinition(room,
			  chooseRandomRoom(myDepth));
    drawRoom(room, true, true, false);
    populateRoom(room);

    numwalls = rand_range(17, 28);
    while (numwalls--)
    {
	// Find a valid wall position.
	tries = 100;
	while (tries--)
	{
	    cx = rand_range(1, MAP_WIDTH-1);
	    cy = rand_range(1, MAP_HEIGHT-1);

	    // Ensure we are not in the special room.
	    if (cx >= room.l.x && cx <= room.h.x &&
		cy >= room.l.y && cy <= room.h.y)
	    {
		continue;
	    }

	    if (getTile(cx, cy) != SQUARE_FLOOR)
		continue;
	    
	    // Verify we are not adjacent to a wall.
	    if (getTile(cx, cy+1) != SQUARE_FLOOR)
		continue;
	    if (getTile(cx, cy-1) != SQUARE_FLOOR)
		continue;
	    if (getTile(cx+1, cy) != SQUARE_FLOOR)
		continue;
	    if (getTile(cx-1, cy) != SQUARE_FLOOR)
		continue;

	    // Valid wall, done.
	    break;
	}

	// Couldn't find a valid space.
	if (!tries)
	    break;

	dir = rand_choice(4);
	getDirection(dir, dx, dy);
	
	// Now draw walls in two directions until they hit a wall
	// or become adjacent to a wall
	drawQixWall(cx, cy, dx, dy, islit);

	dir += rand_range(1, 3);
	dir &= 3;
	getDirection(dir, dx, dy);
	
	drawQixWall(cx+dx, cy+dy, dx, dy, islit);
    }

    int		*cutout = ourCutOuts;
    int		*cell = ourCells;
    int		numcuts = 0, c1, c2;
    
    // Find all possible cuts
    for (y = 1; y < MAP_HEIGHT-1; y++)
    {
	for (x = 1; x < MAP_WIDTH-1; x++)
	{
	    // Ensure we are not in the special room.
	    if (x >= room.l.x && x <= room.h.x &&
		y >= room.l.y && y <= room.h.y)
	    {
		continue;
	    }

	    // To be a cut, we must be a wall.
	    if (getTile(x, y) != SQUARE_WALL)
		continue;
	
	    // To be a valid cut, we need to have a floor
	    // on either side and walls on the opposite sides.
	    if ((getTile(x-1, y) == SQUARE_FLOOR) &&
		(getTile(x+1, y) == SQUARE_FLOOR) &&
		(getTile(x, y-1) == SQUARE_WALL) &&
		(getTile(x, y+1) == SQUARE_WALL))
	    {
		cutout[numcuts++] = y * MAP_WIDTH + x;
	    }
	    if ((getTile(x-1, y) == SQUARE_WALL) &&
		(getTile(x+1, y) == SQUARE_WALL) &&
		(getTile(x, y-1) == SQUARE_FLOOR) &&
		(getTile(x, y+1) == SQUARE_FLOOR))
	    {
		cutout[numcuts++] = y * MAP_WIDTH + x;
	    }
	}
    }
    UT_ASSERT(numcuts < 512);

    // Initialize cell array:
    for (i = 0; i < 1024; i++)
	cell[i] = i;

    // Connect anything already connected
    for (y = 1; y < MAP_HEIGHT-1; y++)
    {
	for (x = 1; x < MAP_WIDTH-1; x++)
	{
	    if (getTile(x, y) != SQUARE_FLOOR)
		continue;

	    c1 = findCell(cell, y * MAP_WIDTH + x);

	    if (getTile(x+1, y) == SQUARE_FLOOR)
	    {
		c2 = findCell(cell, y * MAP_WIDTH + (x + 1));
		if (c1 < c2)
		    cell[c2] = c1;
		else if (c1 > c2)
		    cell[c1] = c2;
	    }

	    if (getTile(x, y+1) == SQUARE_FLOOR)
	    {
		c2 = findCell(cell, (y+1) * MAP_WIDTH + x);
		if (c1 < c2)
		    cell[c2] = c1;
		else if (c1 > c2)
		    cell[c1] = c2;
	    }
	}
    }
    
    // Now, randomize our cut list:
    rand_shuffle(cutout, numcuts);

    for (i = 0; i < numcuts; i++)
    {
	// Determine direction of cut
	x = cutout[i] % MAP_WIDTH;
	y = cutout[i] / MAP_WIDTH;

	// Find direction.
	if ((getTile(x+1, y) == SQUARE_WALL) ||
	    (getTile(x-1, y) == SQUARE_WALL))
	{
	    dx = 0;
	    dy = 1;
	}
	if ((getTile(x, y+1) == SQUARE_WALL) ||
	    (getTile(x, y-1) == SQUARE_WALL))
	{
	    dx = 1;
	    dy = 0;
	}

	// Check to see if the cells are different.
	c1 = findCell(cell, (y+dy)*MAP_WIDTH+(x+dx));
	c2 = findCell(cell, (y-dy)*MAP_WIDTH+(x-dx));

	if (c1 != c2)
	{
	    setTile(x, y, SQUARE_DOOR);
	    if (c1 < c2)
		cell[c2] = c1;
	    else if (c1 > c2)
		cell[c1] = c2;
	    
	    // Add the door itself to the include list.
	    c1 = findCell(cell, y * MAP_WIDTH + x);
	    if (c1 < c2)
		cell[c2] = c1;
	    else if (c1 > c2)
		cell[c1] = c2;
	}
	else if (rand_chance(5))
	{
	    setTile(x, y, SQUARE_SECRETDOOR);
	}
    }

    // Now destroy any walls that are unconnected.
    int		c1cnt, c2cnt;
    c1cnt = 0;
    c1 = -1;
    for (y = 0; y < MAP_WIDTH; y++)
    {
	for (x = 0; x < MAP_WIDTH; x++)
	{
	    if (x >= room.l.x && x <= room.h.x &&
		y >= room.l.y && y <= room.h.y)
	    {
		continue;
	    }

	    if (getTile(x, y) == SQUARE_FLOOR || getTile(x, y) == SQUARE_DOOR)
	    {
		if (c1 < 0)
		{
		    c1 = findCell(cell, y * MAP_WIDTH + x);
		    c1cnt = 0;
		    for (i = 0; i < 1024; i++)
		    {
			if (findCell(cell, i) == c1)
			    c1cnt++;
		    }
		}
		
		c2 = findCell(cell, y * MAP_WIDTH + x);
		if (c1 != c2)
		{
		    if (c2 == y * MAP_WIDTH + x)
		    {
			c2cnt = 0;
			for (i = 0; i < 1024; i++)
			{
			    if (findCell(cell, i) == c2)
				c2cnt++;
			}

			if (c2cnt > c1cnt)
			{
			    c1 = c2;
			    c1cnt = c2cnt;
			    // Restart so we rescan earlyer
			    // parts.
			    y = 0;
			    x = 0;
			    continue;
			}
		    }
		
		    // Isolated region!  Reject!
		    setTile(x, y, SQUARE_WALL);
		}
	    }
	}
    }

    closeUnusedExits(room, true);

    // Now, we pick a random up and down stair case...
    while (1)
    {
        findRandomLoc(x, y, MOVE_WALK,
			true, false, false, false, false, false);

	if (!room.definition->allowstairs &&
	     x >= room.l.x && x <= room.h.x &&
	     y >= room.l.y && y <= room.h.y)
	    continue;
	
	if (getTile(x, y) == SQUARE_FLOOR)
	{
	    setTile(x, y, SQUARE_LADDERUP);
	    break;
	}
    }

    while (1)
    {
        findRandomLoc(x, y, MOVE_WALK,
			true, false, false, false, false, false);
	
	if (!room.definition->allowstairs &&
	     x >= room.l.x && x <= room.h.x &&
	     y >= room.l.y && y <= room.h.y)
	    continue;
	
	if (getTile(x, y) == SQUARE_FLOOR)
	{
	    setTile(x, y, SQUARE_LADDERDOWN);
	    break;
	}
    }
}

void
MAP::buildMaze(int stride)
{
    // A 32x32 room as 16x16 horizontal cuts and 16x16 vertical cuts,
    // for a max cut list of 512.
    int			*cutouts;
    // The cell tracks connected sets.  Each cell points to the
    // cell it is connected to, or to itself if it is the root of
    // the tree.
    int			*cell;
    int			numcuts;
    int			x, y, cx, cy, dx, dy;
    int			i;
    int			cut;
    int			c1, c2;
    ROOM		room;

    cell = ourCells;
    cutouts = ourCutOuts;

    // Set the entire map to normal walls:
    for (y = 0; y < MAP_HEIGHT; y++)
    {
	for (x = 0; x < MAP_WIDTH; x++)
	{
	    setTile(x, y, SQUARE_WALL);
	    // It would be very cruel not to light the maze.
	    setFlag(x, y, SQUAREFLAG_LIT);

	    // For debugging:
	    // setFlag(x, y, SQUAREFLAG_MAPPED);
	}
    }

    // We want every other square to be a hole.
    for (y = 1; y < MAP_HEIGHT-stride; y += stride + 1)
    {
	for (x = 1; x < MAP_WIDTH-stride; x += stride + 1)
	{
	    for (dy = 0; dy < stride; dy++)
	    {
		for (dx = 0; dx < stride; dx++)
		{
		    setTile(x+dx, y+dy, SQUARE_FLOOR);
		}
	    }
	}
    }

    // Create the special room:
    buildRandomRoomFromDefinition(room,
			  chooseRandomRoom(myDepth));
    drawRoom(room, true, true, false);
    populateRoom(room);

    // We also want to initialize the cutout array here (which
    // is a list of all possible wall cuts.)
    // We do not include any cuts that will bridge the room - ie, either
    // side of the cut is inside of the room.
    numcuts = 0;
    for (y = 1; y < MAP_HEIGHT-stride; y += stride+1)
    {
	for (x = 1; x < MAP_WIDTH-stride; x += stride+1)
	{
	    for (dx = 0; dx < stride; dx++)
	    {
		if (x+stride < MAP_WIDTH-2)
		    if (x+stride+1 < room.l.x || x > room.h.x ||
			y+dx < room.l.y || y+dx > room.h.y)	
			cutouts[numcuts++] = ((y+dx) * MAP_WIDTH) + x + stride;
		if (y+stride < MAP_HEIGHT-2)
		    if (x+dx < room.l.x || x+dx > room.h.x ||
			y+stride+1 < room.l.y || y > room.h.y)	
			cutouts[numcuts++] = ((y+stride) * MAP_WIDTH) + x + dx;
	    }
	}
    }
    UT_ASSERT(numcuts < 512);

    // Initialize cell array:
    for (i = 0; i < 256; i++)
	cell[i] = i;
    
    // Now, randomize our cut list:
    rand_shuffle(cutouts, numcuts);

    // And cut all the cutouts that won't join an existing pair...
    for (i = 0; i < numcuts; i++)
    {
	cut = cutouts[i];

	y = cut / MAP_WIDTH;
	x = cut - y * MAP_WIDTH;
	cx = (x-1) / (stride+1);
	cy = (y-1) / (stride+1);
	c1 = findCell(cell, cy * (MAP_WIDTH / 2) + cx);
	if (cut & 1)
	{
	    // Vertical cut...
	    c2 = findCell(cell, (cy+1) * (MAP_WIDTH / 2) + cx);
	}
	else
	{
	    // Horizontal cut...
	    c2 = findCell(cell, cy * (MAP_WIDTH / 2) + cx + 1);
	}

	// We only connect if they are different.  This ensures
	// we have a fully branching corridor.   It would also
	// prevent any loop backs and make for lots of backtracking.
	// Thus, to be kind, we add some extras...
	if (c1 != c2 || rand_chance(10))
	{
	    // We have two different cells that would be joined
	    // by this cut, so make it.
	    setTile(x, y, SQUARE_FLOOR);
	    // And mark the cells the same:
	    cell[c2] = c1;
	}
    }

    closeUnusedExits(room, true);

    // Now, we pick a random up and down stair case...
    while (1)
    {
        findRandomLoc(x, y, MOVE_WALK,
			true, false, false, false, false, false);

	if (!room.definition->allowstairs &&
	     x >= room.l.x && x <= room.h.x &&
	     y >= room.l.y && y <= room.h.y)
	    continue;
	
	if (getTile(x, y) == SQUARE_FLOOR)
	{
	    setTile(x, y, SQUARE_LADDERUP);
	    break;
	}
    }

    while (1)
    {
        findRandomLoc(x, y, MOVE_WALK,
			true, false, false, false, false, false);
	
	if (!room.definition->allowstairs &&
	     x >= room.l.x && x <= room.h.x &&
	     y >= room.l.y && y <= room.h.y)
	    continue;
	
	if (getTile(x, y) == SQUARE_FLOOR)
	{
	    setTile(x, y, SQUARE_LADDERDOWN);
	    break;
	}
    }
}

void
MAP::buildDrunkenCavern(bool islit, bool allowlakes, bool allowroom, bool buildstaircase)
{
    // This time the drunk in the title refers to the algorithm, not
    // my state when writing it.

    // int			numdrunks, i;
    int			rum, j;
    int			x, y;
    int			dx, dy;
    int			numcuts = 0;
    SQUARE_NAMES	tunneltype;

    if (islit)
    {
	for (y = 0; y < MAP_HEIGHT; y++)
	{
	    for (x = 0; x < MAP_WIDTH; x++)
	    {
		setFlag(x, y, SQUAREFLAG_LIT);
		// For debugging:
		// setFlag(x, y, SQUAREFLAG_MAPPED);
	    }
	}
    }

    ROOM			room;
    room.definition = 0;

    if (allowroom)
    {
	buildRandomRoomFromDefinition(room,
			  chooseRandomRoom(myDepth));
	drawRoom(room, islit, false, false);
	populateRoom(room);
    }
    
    // 10-30 drunken walks.
    //numdrunks = rand_range(20, 30);
    //rum = rand_range(20, 30);
    //numdrunks = 1;
    //rum = 900;

    // We want numdrunks + sqrt(rum) == 20
    // The sqrt is because each drunk will move a distance on average
    // of sqrt(rum).

    // We may want to:
    // 1) Bias the birth of drunkards near tunnel terminuses
    // 2) Turn on back tracking to allow creation of deadends
    // 3) Tunnel until a certain percentage is execavated.
    /*
    numdrunks = rand_range(1, 17);
    rum = 20 - numdrunks;
    rum *= rum;
    */
    rum = 300;
    
    //BUF		buf;
    //buf.sprintf("Drunk: %d, Len: %d.  ", numdrunks, rum);
    //msg_report(buf);
    //for (i = 0; i < numdrunks; i++)
    while (numcuts < (MAP_WIDTH * MAP_HEIGHT / 2))
    {
	// Pick a random drunk starting location.
	//if (i)
	if (numcuts)
	{
	    findRandomLoc(x, y, MOVE_STD_SWIM,
			    true, false, false, false, false, false);
	    if (isMapWall(x, y))
		continue;
	    tunneltype = SQUARE_CORRIDOR;
	}
	else
	{
	    while (1)
	    {
		x = rand_range(3, MAP_WIDTH-3);
		y = rand_range(3, MAP_HEIGHT-3);
		if (isMapWall(x, y))
		    continue;
		if (getTile(x, y) == SQUARE_EMPTY)
		    break;
	    }

	    // We get free cuts corresponding to the size of the room.
	    if (allowroom)
		numcuts += (room.h.x - room.l.x) * (room.h.y - room.l.y);

	    if (allowlakes)
	    {
		tunneltype = SQUARE_WATER;
	    }
	    else
		tunneltype = SQUARE_CORRIDOR;
	}

	// Now start carving out the dungeon...
	// Initial dig direction:
	rand_direction(dx, dy);
	for (j = 0; j < rum; j++)
	{
	    // Dig out this square...
	    if (getTile(x, y) == SQUARE_EMPTY)
		numcuts++;

	    // Don't cut out special rooms.
	    if (getTile(x, y) != SQUARE_CORRIDOR &&
		getTile(x, y) != SQUARE_EMPTY &&
		getTile(x, y) != SQUARE_WATER)
	    {
		break;
	    }
	    
	    if (getTile(x, y) != SQUARE_WATER)
		setTile(x, y, tunneltype);

	    // Move drunkenly...
	    x += dx;
	    y += dy;

	    // Stumble against the walls.
	    if (x < 1)
		x = 1;
	    if (x >= MAP_WIDTH-2)
		x = MAP_WIDTH-2;
	    if (y < 1)
		y = 1;
	    if (y >= MAP_HEIGHT-2)
		y = MAP_HEIGHT-2;

	    // Change our direction...
	    switch (rand_choice(3))
	    {
		case 0:
		    // Unchanged.
		    break;
		case 1:
		    // Turn, +1
		    dx = !dx;
		    dy = !dy;
		    break;
		case 2:
		    // Turn -1
		    dx = -!dx;
		    dy = -!dy;
		    break;
	    }
	}
    }

    if (allowroom)
	closeUnusedExits(room, true);

    // Build the staircases..
    while (buildstaircase)
    {
        findRandomLoc(x, y, MOVE_STD_SWIM,
			true, false, false, false, false, false);
	
	if (room.definition &&
	    !room.definition->allowstairs &&
	     x >= room.l.x && x <= room.h.x &&
	     y >= room.l.y && y <= room.h.y)
	    continue;
	
	if (getTile(x, y) == SQUARE_CORRIDOR || getTile(x, y) == SQUARE_WATER)
	{
	    setTile(x, y, SQUARE_LADDERUP);
	    break;
	}
    }

    while (buildstaircase)
    {
        findRandomLoc(x, y, MOVE_STD_SWIM,
			true, false, false, false, false, false);
	
	if (room.definition &&
	    !room.definition->allowstairs &&
	     x >= room.l.x && x <= room.h.x &&
	     y >= room.l.y && y <= room.h.y)
	    continue;
	
	if (getTile(x, y) == SQUARE_CORRIDOR || getTile(x, y) == SQUARE_WATER)
	{
	    setTile(x, y, SQUARE_LADDERDOWN);
	    break;
	}
    }
}

void
MAP::buildRiverRoom()
{
    int		upx = 0, upy;
    int		downx = 0, downy;
    int		minx, maxx;
    int		rx, ry;
    int		i;

    do 
    {
	// Empty the map...
	clear();

	// Clear out our wall map.
	memset(ourWallMap, 0, MAP_WIDTH * MAP_HEIGHT);

	buildDrunkenCavern(false, false, false, true);

	// Find the up and down ladders, try to cut through them with a river.
	if (!findTile(SQUARE_LADDERUP, upx, upy))
	    continue;
	if (!findTile(SQUARE_LADDERDOWN, downx, downy))
	    continue;
    } while (abs(upx - downx) <= 7);

    // We are now guaranteed that we have a 5 space room for our river.
    if (upx < downx)
    {
	minx = upx;
	maxx = downx;
    }
    else
    {
	minx = downx;
	maxx = upx;
    }
    minx += 3;
    maxx -= 3;

    rx = (upx + downx) / 2;
    for (ry = 0; ry < MAP_HEIGHT; ry++)
    {
	// Move rx randomly to left or right.
	rx += rand_choice(3) - 1;
	if (rx < minx)
	    rx = minx;
	if (rx > maxx)
	    rx = maxx;

	// Draw the river here.
	for (i = -2; i <= 2; i++)
	{
	    // We only want to draw over corridor and normal walls.
	    // Otherwise we could write over a special room.
	    switch (getTile(rx+i, ry))
	    {
		case SQUARE_CORRIDOR:
		case SQUARE_EMPTY:
		    setTile(rx+i, ry, SQUARE_WATER);
		    break;
		default:
		    break;
	    }
	}
    }
}

void
MAP::buildSurfaceWorld()
{
    int		elevation[MAP_HEIGHT+1][MAP_WIDTH+1];
    int		scale, step, average, e;
    int		x, y, pass;
    SQUARE_NAMES	tile;

    // Set our flags appropraitel
    myGlobalFlags &= ~MAPFLAG_DIG;
    myGlobalFlags &= ~MAPFLAG_NEWMOBS;
    myGlobalFlags |= MAPFLAG_NOITEMS;

    for (scale = 5; scale >= 0; scale--)
    {
	step = 1 << scale;

	for (pass = 0; pass < 2; pass++)
	{
	    for (y = 0; y <= MAP_HEIGHT; y += step)
	    {
		for (x = 0; x <= MAP_WIDTH; x += step)
		{
		    // Clamp boundaries:
		    if (!x || !y || (x == MAP_WIDTH) || (y == MAP_HEIGHT))
			elevation[y][x] = 256;
		    else if (x == MAP_WIDTH/2 && y == MAP_HEIGHT/2)
			elevation[y][x] = 0;
		    else
		    {
			// First pass we want only edges
			// Second pass the centers.
			if (pass)
			{
			    if (!(x & step) || !(y & step))
				continue;

			    average = elevation[y - step][x] +
				      elevation[y + step][x] +
				      elevation[y][x - step] +
				      elevation[y][x + step];
			    average = (average + 2) / 4;
			}
			else
			{
			    if (!((x & step) ^ (y & step)))
				continue;

			    if (x & step)
			    {
				average = elevation[y][x - step] +
					  elevation[y][x + step];
				average = (average + 1) / 2;
			    }
			    else
			    {
				average = elevation[y - step][x] +
					  elevation[y + step][x];
				average = (average + 1) / 2;
			    }
			}

			average += rand_range(-step*10, step*10);

			elevation[y][x] = average;
		    }
		}
	    }
	}		// for pass
    }

    for (y = 0; y < MAP_HEIGHT; y++)
    {
	for (x = 0; x < MAP_WIDTH; x++)
	{
	    e = elevation[y][x];

	    if (e < 50)
		tile = SQUARE_GRASS;
	    else if (e < 100)
		tile = SQUARE_WATER;
	    else if (e < 150)
		tile = SQUARE_GRASS;
	    else if (e < 200)
		tile = SQUARE_FOREST;
	    else if (e < 240)
		tile = SQUARE_HILLS;
	    else
		tile = SQUARE_MOUNTAIN;

	    setTile(x, y, tile);
	    setFlag(x, y, SQUAREFLAG_LIT);
	}
    }

    // One upstairs in the center...
    setTile(MAP_WIDTH/2, MAP_HEIGHT/2, SQUARE_LADDERDOWN);

    // Warning sign post
    setTile(MAP_WIDTH/2+2, MAP_HEIGHT/2, SQUARE_SIGNPOST);
    addSignPost(SIGNPOST_WON, MAP_WIDTH/2+2, MAP_HEIGHT/2);

    // Elder
    y = MAP_HEIGHT/2;

    for ( ; y < MAP_HEIGHT; y++)
    {
	x = MAP_WIDTH/2;
	for ( ; x < MAP_WIDTH; x++)
	{
	    if (!canMove(x, y, MOVE_STD_SWIM))
		break;
	}
	if (canMove(x-1,y, MOVE_WALK))
	{
	    x--;
	    break;
	}
    }
    if (y >= MAP_HEIGHT)
    {
	// Failed to place far away
	x = MAP_WIDTH/2-1;
	y = MAP_HEIGHT/2;
    }
    // If we are loading from disk, we've already populated the room
    // from disk.
    if (!ourIsLoading)
    {
	MOB *mob;

	mob = MOB::create(MOB_ELDER);

	// interlevell so no traps
	// but what do we do about failure???
	// currently move never fails with interlevel.
	if (mob->move(x, y, true))
	    registerMob(mob);
	else
	    delete mob;
    }
}

void
MAP::buildTutorial()
{
    // Find the appropriate room...
    int			i, nummatch, match = -1;

    nummatch = 0;
    for (i = 0; i < NUM_ALLROOMDEFS; i++)
    {
	if (!strcmp(glb_allroomdefs[i]->name, "tutorial"))
	{
	    nummatch++;
	    if (!rand_choice(nummatch))
		match = i;
	}
    }

    if (match == -1)
    {
	// No matching god!
	buildRoguelike();
	return;
    }

    // Only have to build the room.  It is assumed to have
    // the required crap in it.
    ROOM		room;

    buildRandomRoomFromDefinition(room, glb_allroomdefs[match]);
    drawRoom(room, true, false, false);
    populateRoom(room);
}

void
MAP::buildQuest(GOD_NAMES god)
{
    // Set our flags appropraitely
#if 0
    myGlobalFlags &= ~MAPFLAG_DIG;
    myGlobalFlags &= ~MAPFLAG_NEWMOBS;
    myGlobalFlags |= MAPFLAG_NOITEMS;
#endif

    // Find the appropriate room...
    int			i, nummatch, match = -1;

    nummatch = 0;
    for (i = 0; i < NUM_ALLROOMDEFS; i++)
    {
	if (glb_allroomdefs[i]->quest == god)
	{
	    nummatch++;
	    if (!rand_choice(nummatch))
		match = i;
	}
    }

    if (match == -1)
    {
	// No matching god!
	buildRoguelike();
	return;
    }

    // Only have to build the room.  It is assumed to have
    // the required crap in it.
    ROOM		room;

    buildRandomRoomFromDefinition(room, glb_allroomdefs[match]);
    drawRoom(room, true, false, false);
    populateRoom(room);
}

class CIRCLE
{
public:
    CIRCLE() {}
    CIRCLE(int r)
    {
	CIRCLE::r = r;
    }
    int		x, y;
    int		r;

    bool	overlaps(const CIRCLE &circle) const;
};

bool
CIRCLE::overlaps(const CIRCLE &circle) const
{
    int		dx, dy, r2, cr2;

    dx = circle.x - x;
    dy = circle.y - y;
    
    r2 = dx * dx + dy * dy;
    cr2 = circle.r + r + 2;	// Extra two is to get a wall between them.
    cr2 *= cr2;

    // See if combined radii of circle is within r2.
    if (cr2 >= r2)
	return true;

    return false;
}

typedef PTRSTACK<CIRCLE> CIRCLELIST;

bool
circleFits(int x, int y, int r, const CIRCLELIST &list)
{
    int		i, n;
    CIRCLE	test;

    test.x = x;
    test.y = y;
    test.r = r;

    n = list.entries();
    for (i = 0; i < n; i++)
    {
	if (test.overlaps(list(i)))
	{
	    return false;
	}
    }
    return true;
}

bool
createCircle(CIRCLE &circle, int r, const CIRCLELIST &list)
{
    int		x, y, numchoice = 0;

    for (y = r+1; y < MAP_HEIGHT - (r+1); y++)
    {
	for (x = r+1; x < MAP_WIDTH - (r+1); x++)
	{
	    if (circleFits(x, y, r, list))
	    {
		numchoice++;
		if (!rand_choice(numchoice))
		{
		    circle.x = x;
		    circle.y = y;
		    circle.r = r;
		}
	    }
	}
    }
    if (numchoice)
	return true;
    return false;
}

MOB *
MAP::createGoldenTridudeLair(int x, int y)
{
    MOB		*leader, *mob;
    ITEM	*artifact;
    int		 i;
    const int	 numslaves = 9;
    int		 placedx[numslaves] =
    { 0, 0, 0, 1, 2, 3, -1, -2, -3 }; 
    int		 placedy[numslaves] =
    { 2, 3, 4,-1,-2,-3, -1, -2, -3 };
    MOB_NAMES	 placetype[numslaves] =
    { 
	MOB_REDTRIDUDE, MOB_REDTRIDUDE, MOB_REDTRIDUDE,
	MOB_BLUETRIDUDE, MOB_BLUETRIDUDE, MOB_BLUETRIDUDE,
	MOB_PURPLETRIDUDE, MOB_PURPLETRIDUDE, MOB_PURPLETRIDUDE
    };

    leader = MOB::create(MOB_GOLDTRIDUDE);
    leader->setIntrinsic(INTRINSIC_LEADER);
    leader->move(x, y, true);
    registerMob(leader);

    // The leader gets a tasty artifact.
    artifact = ITEM::createRandomType(ITEMTYPE_ARTIFACT);
    acquireItem(artifact, x, y, 0);

    for (i = 0; i < numslaves; i++)
    {
	mob = MOB::create(placetype[i]);
	mob->makeSlaveOf(leader);

	mob->move(x + placedx[i], y + placedy[i], true);
	registerMob(mob);
    }

    return leader;
}

void
MAP::createColouredTridudeLair(int x, int y, MOB_NAMES tridude, MOB *trueleader)
{
    MOB		*leader, *mob;
    int		 i;
    const int	 numslaves = 6;
    int		 placedx[numslaves] =
    { 0, -1,  1, 0, -2,  2};
    int		 placedy[numslaves] =
    { 1, -1, -1, 2, -2, -2};

    leader = MOB::create(tridude);
    leader->makeUnique();
    leader->setIntrinsic(INTRINSIC_LEADER);
    leader->move(x, y, true);
    if (trueleader)
	leader->makeSlaveOf(trueleader);
    registerMob(leader);

    for (i = 0; i < numslaves; i++)
    {
	mob = MOB::create(tridude);
	mob->makeSlaveOf(leader);

	mob->move(x + placedx[i], y + placedy[i], true);
	registerMob(mob);
    }
}

void
MAP::buildSpaceShip()
{
    int			x, y, r, dx, dy, i;
    SQUARE_NAMES	square;
    CIRCLELIST		list;
    CIRCLE		circle;

    // Set our appropriate flags.
    myGlobalFlags &= ~MAPFLAG_DIG;
    // We'll do our own populating.
    myGlobalFlags &= ~MAPFLAG_NEWMOBS;

    // This is random placement so we try until we get the required mandatory
    // rooms
    while (1)
    {
	bool		created = false;
	clear();

	list.clear();
	
	while (1)
	{
	    // Dimension door.
	    if (!createCircle(circle, 2, list))
		break;
	    drawCircle(circle.x, circle.y, circle.r, SQUARE_METALFLOOR, SQUAREFLAG_LIT);
	    list.append(circle);
	    setTile(circle.x, circle.y, SQUARE_DIMDOOR);

	    // Giant tridude
	    if (!createCircle(circle, 5, list))
		break;
	    list.append(circle);
	    drawCircle(circle.x, circle.y, circle.r, SQUARE_METALFLOOR, SQUAREFLAG_LIT);

	    // Tri coloured tridude lairs
	    for (i = 0; i < 3; i++)
	    {
		if (!createCircle(circle, 4, list))
		    break;
		drawCircle(circle.x, circle.y, circle.r, SQUARE_METALFLOOR, SQUAREFLAG_LIT);
		list.append(circle);
	    }
	    if (i != 3)
		break;

	    // Some bonus rooms.
	    // We don't care if these fail.
	    for (i = 0; i < 6; i++)
	    {
		if (!createCircle(circle, 2+rand_choice(2), list))
		    break;
		drawCircle(circle.x, circle.y, circle.r, SQUARE_METALFLOOR, SQUAREFLAG_LIT);
		list.append(circle);
	    }
	    
	    created = true;
	    break;
	}

	if (created)
	    break;
    }

    // Populate rooms.
    if (!ourIsLoading)
    {
	RAND_STATEPUSH		saverng;
	const int		numlair = 3;
	MOB			*goldtridude;
	MOB_NAMES		lairtype[numlair] =
	{
	    MOB_REDTRIDUDE,
	    MOB_BLUETRIDUDE,
	    MOB_PURPLETRIDUDE
	};
	// Create the golden lair.
	goldtridude = createGoldenTridudeLair(list(1).x, list(1).y);
	// Rooms 2, 3, 4 are all tridude lairs
	for (i = 0; i < numlair; i++)
	{
	    // Each lair is a feudal system.  Knock out the local
	    // leader and they will fight the other packs.
	    createColouredTridudeLair(list(i+2).x, list(i+2).y, lairtype[i],
				    goldtridude);
	}

	// Now a smattering of regular tridudes.
	for (i = 0; i < 10; i++)
	{
	    MOB		*mob;
	    
	    // Abort if no more room for some reason.
	    if (!findRandomLoc(x, y, MOVE_WALK,
			    false, false, false, false, false, false))
		break;
	    
	    mob = MOB::create(MOB_TRIDUDE);
	    
	    mob->move(x, y, true);
	    // These all owe allegiance to the giant tridude.
	    mob->makeSlaveOf(goldtridude);
	    registerMob(mob);
	}
    }

    // Connect all rooms.
    // We have two sets: connected, and unconnected.
    // We find the closest pair between the two sets and connect them
    // then add the new room to the connected set.
    for (i = 1; i < list.entries(); i++)
    {
	int		j, k;
	int		minr2 = MAP_WIDTH*MAP_WIDTH*4;
	int		minid1 = i, minid2 = 0;

	for (j = 0; j < i; j++)
	{
	    for (k = i; k < list.entries(); k++)
	    {
		dx = list(j).x - list(k).x;
		dy = list(j).y - list(k).y;
		r = dx * dx + dy * dy;
		if (r < minr2)
		{
		    minid2 = j;
		    minid1 = k;
		    minr2 = r;
		}
	    }
	}
	
	// Draw a line between the centers.
	drawLine(list(minid1).x, list(minid1).y,
		 list(minid2).x, list(minid2).y,
		 SQUARE_METALFLOOR);

	// Min pair is minid2 and minid1.
	// Swap i with minid1 to mark it connected.
	circle = list(i);
	list.set(i, list(minid1));
	list.set(minid1, circle);
    }

    // Outline all rooms with walls.
    for (y = 0; y < MAP_HEIGHT; y++)
    {
	for (x = 0; x < MAP_WIDTH; x++)
	{
	    if (getTile(x, y) == SQUARE_EMPTY)
	    {
		// If a eight way neighbour is not empty and not
		// a metal wall, convert.
		for (dy = -1; dy <= 1; dy++)
		{
		    for (dx = -1; dx <= 1; dx++)
		    {
			if (!dx && !dy)
			    continue;
			if (x+dx < 0 || y + dy < 0)
			    continue;
			if (x+dx >= MAP_WIDTH || y + dy >= MAP_HEIGHT)
			    continue;
			square = getTile(x+dx, y+dy);
			if (square != SQUARE_EMPTY && square != SQUARE_METALWALL)
			{
			    setTile(x, y, SQUARE_METALWALL);
			    dx = dy = 2;
			}
		    }
		}
	    }
	}
    }
    
    // Create viewports anywhere which is bordered on one half by
    // stars and the other by non-stars and is a metalwall.
    for (y = 1; y < MAP_HEIGHT-1; y++)
    {
	for (x = 1; x < MAP_WIDTH-1; x++)
	{
	    const int viewportchance = 15;

	    if (getTile(x, y) != SQUARE_METALWALL)
		continue;

	    if (getTile(x-1, y) != SQUARE_METALWALL &&
		getTile(x+1, y) != SQUARE_METALWALL)
	    {
		if (getTile(x-1, y) == SQUARE_EMPTY ||
		    getTile(x+1, y) == SQUARE_EMPTY)	
		{
		    if (rand_chance(viewportchance))
			setTile(x, y, SQUARE_VIEWPORT);
		}
	    }
	    if (getTile(x, y-1) != SQUARE_METALWALL &&
		getTile(x, y+1) != SQUARE_METALWALL)
	    {
		if (getTile(x, y-1) == SQUARE_EMPTY ||
		    getTile(x, y+1) == SQUARE_EMPTY)	
		{
		    if (rand_chance(viewportchance))
			setTile(x, y, SQUARE_VIEWPORT);
		}
	    }
	}
    }
    
    const int		numstars = 5;

    // Mark everything lit & having a random star.
    // We also turn off the mob generation inside stars
    // to stop you from being teleported there.
    const SQUARE_NAMES starlist[numstars] =
    {
	SQUARE_STARS1,
	SQUARE_STARS2,
	SQUARE_STARS3,
	SQUARE_STARS4,
	SQUARE_STARS5
    };
    for (y = 0; y < MAP_HEIGHT; y++)
    {
	for (x = 0; x < MAP_WIDTH; x++)
	{
	    setFlag(x, y, SQUAREFLAG_LIT);
	    // For debugging:
    	    // setFlag(x, y, SQUAREFLAG_MAPPED);

	    if (getTile(x, y) == SQUARE_EMPTY)
	    {
		setTile(x, y, starlist[rand_choice(numstars)]);
		setFlag(x, y, SQUAREFLAG_NOMOB);
	    }
	}
    }
}

void
MAP::buildHello()
{
    int			x, y, r;
    int			numcirc;
    SQUARE_NAMES	square;
    SQUAREFLAG_NAMES	flag;

    // Set our appropriate flags.
    myGlobalFlags &= ~MAPFLAG_DIG;

    clear();

    ROOM			room;

    // I'm just typing this to note I am currently flying first class
    // Woohoo!
    buildRandomRoomFromDefinition(room,
		      chooseRandomRoom(myDepth));
    drawRoom(room, true, false, false);
    populateRoom(room);
    
    for (numcirc = 0; numcirc < 20; numcirc++)
    {
	x = rand_range(1, MAP_WIDTH);
	y = rand_range(1, MAP_HEIGHT);
	r = rand_range(1, 6);

	switch (rand_choice(3))
	{
	    case 0:
		square = SQUARE_CORRIDOR;
		flag = SQUAREFLAG_NONE;
		break;
	    case 1:
		square = SQUARE_LAVA;
		flag = SQUAREFLAG_LIT;
		break;
	    case 2:
		square = SQUARE_WATER;
		flag = SQUAREFLAG_NONE;
		break;
	    default:
		UT_ASSERT(0);
		square = SQUARE_EMPTY;
		flag = SQUAREFLAG_NONE;
		break;
	}

	drawCircle(x, y, r, square, flag);
    }

    closeUnusedExits(room, true);
    
    // Build the staircases..
    while (1)
    {
        findRandomLoc(x, y, MOVE_STD_SWIM,
			true, false, false, false, false, false);
	
	if (!room.definition->allowstairs &&
	     x >= room.l.x && x <= room.h.x &&
	     y >= room.l.y && y <= room.h.y)
	    continue;
	
	if (getTile(x, y) == SQUARE_CORRIDOR || getTile(x, y) == SQUARE_WATER
	    || getTile(x, y) == SQUARE_LAVA)
	{
	    setTile(x, y, SQUARE_LADDERUP);
	    break;
	}
    }

    // There is no down stairs from hello.
#if 0
    while (1)
    {
        findRandomLoc(x, y, MOVE_STD_SWIM,
			true, false, false, false, false, false);
	
	if (!room.definition->allowstairs &&
	     x >= room.l.x && x <= room.h.x &&
	     y >= room.l.y && y <= room.h.y)
	    continue;
	
	if (getTile(x, y) == SQUARE_CORRIDOR || getTile(x, y) == SQUARE_WATER
	    || getTile(x, y) == SQUARE_LAVA)
	{
	    setTile(x, y, SQUARE_LADDERDOWN);
	    break;
	}
    }
#endif
}

void
MAP::drawLine(int x1, int y1, int x2, int y2,
		SQUARE_NAMES square,
		bool overwrite)
{
    int		cx, cy, x, y, acx, acy;

    cx = x2 - x1;
    cy = y2 - y1;
    acx = abs(cx);
    acy = abs(cy);


    // Start and beginning are done separately as this code
    // is stolen from the LOS code that ignore start and end.
    if (overwrite || getTile(x1, y1) == SQUARE_EMPTY)
	setTile(x1, y1, square);
    if (overwrite || getTile(x2, y2) == SQUARE_EMPTY)
	setTile(x2, y2, square);
    
    if (acx > acy)
    {
	int		dx, dy, error;

	dx = SIGN(cx);
	dy = SIGN(cy);

	error = 0;
	error = acy;
	y = y1;
	for (x = x1 + dx; x != x2; x += dx)
	{
	    if (error >= acx)
	    {
		error -= acx;
		if (overwrite || getTile(x, y) == SQUARE_EMPTY)
		    setTile(x, y, square);
		y += dy;
	    }

	    error += acy;
	    if (overwrite || getTile(x, y) == SQUARE_EMPTY)
		setTile(x, y, square);
	}
    }
    else
    {
	int		dx, dy, error;

	dx = SIGN(cx);
	dy = SIGN(cy);

	error = 0;
	error = acx;
	x = x1;
	for (y = y1 + dy; y != y2; y += dy)
	{
	    if (error >= acy)
	    {
		error -= acy;
		if (overwrite || getTile(x, y) == SQUARE_EMPTY)
		    setTile(x, y, square);
		x += dx;
	    }

	    error += acx;
	    if (overwrite || getTile(x, y) == SQUARE_EMPTY)
		setTile(x, y, square);
	}
    }

}

void
MAP::drawCircle(int cx, int cy, int rad, 
		SQUARE_NAMES square, SQUAREFLAG_NAMES flag,
		bool overwrite)
{
    int		x, y, r2;

    // Expand radius by .5 so we don't get pimply circles.
    r2 = (int) ((rad + 0.5) * (rad + 0.5));

    for (y = cy - rad; y <= cy + rad; y++)
    {
	if (y < 0)
	    continue;
	// Leave blank tile
	if (y >= MAP_HEIGHT-1)
	    break;

	for (x = cx - rad; x <= cx + rad; x++)
	{
	    if (x < 0)
		continue;
	    // Leave blank tile
	    if (x >= MAP_WIDTH-1)
		break;

	    // Only overwrite earth tiles.
	    if (!overwrite && getTile(x, y) != SQUARE_EMPTY)
		continue;

	    // Determine if this is in range.
	    // My world for a bressenham circle algorithm!
	    // Okay, not my world.
	    // I've written enough of them that this code is ar esult
	    // of extreme laziness/drunkness, rather than a lack of awareness
	    // of a perfectly fine and fast appraoch.
	    if ((y - cy) * (y - cy) + (x - cx) * (x - cx) < r2)
	    {
		setTile(x, y, square);
		setRawFlag(x, y, flag);
	    }
	}
    }
}