/*
 * Licensed under BSD license.  See LICENCE.TXT  
 *
 * Produced by:	Jeff Lait
 *
 *      	7 Day Band Development
 *
 * NAME:        builder.h ( 7 Day Band, C++ )
 *
 * COMMENTS:
 *	Verbish class to build ascii maps
 */

#include "builder.h"
#include "roomdata.h"
#include "vec2.h"
#include "grid.h"
#include "gamedef.h"
#include "config.h"
#include <fstream>

BUILDER::BUILDER(u8 *data, GRIDI *metadata, int width, int height, int stride, int depth)
{
    myData = data;
    myMetaData = metadata;
    myW = width;
    myH = height;
    myStride = stride;
    J_ASSERT(myStride >= myW);

    myDepth = depth;
    myGoalTiles = -1;
}

template <typename OP>
void
BUILDER::drawBorderedRect(RCT rect, const OP &op)
{
    for (int x = rect.x; x < rect.x+rect.w; x++)
    {
	for (int y = rect.y; y < rect.y+rect.h; y++)
	{
	    if (!isValid(x, y))
		continue;
	    op(IVEC2(x, y),
		(x == rect.x) ||
		(x == rect.x+rect.w-1) ||
		(y == rect.y) ||
		(y == rect.y+rect.h-1));
	}
    }
}

template <typename OP>
void
BUILDER::drunkExcavate(IVEC2 p, int maxdist, const OP &op)
{
    for (int dist = 0; dist < maxdist; dist++)
    {
	int		dx, dy;
	rand_direction(dx, dy);

	p.x() += dx;
	p.y() += dy;

	if (!op(p))
	    return;
    }
}

template <typename OP>
void
BUILDER::drunkExcavateBetween(IVEC2 start, IVEC2 end, int drunkness, const OP &op)
{
    IVEC2	p = start;
    while (1)
    {
	IVEC2	delta = end - p;

	// Success
	if (delta.x() == 0 && delta.y() == 0)
	    return;
	
	// Correct direction to go
	int 	dx = SIGN(delta.x());
	int 	dy = SIGN(delta.y());

	// Zero one if it loses the fight
	int 	chancex = rand_choice(ABS(delta.x()));
	int 	chancey = rand_choice(ABS(delta.y()));
	if (chancex > chancey)
	    dy = 0;
	else if (chancex < chancey)
	    dx = 0;
	else
	{
	    // Tied, might even be both zero, but to avoid bias select one.
	    if (rand_sign() < 0)
		dx = 0;
	    else
		dy = 0;
	}

	// Throw that away for pure randomness if drunk
	if (rand_chance(drunkness))
	    rand_direction(dx, dy);

	// Ensure we are a valid new location..
	IVEC2		np = p;
	np.x() += dx;
	np.y() += dy;

	if (!isValid(np)) continue;
	// Don't carve empty space
	if (get(np) == ' ') continue;

	p = np;

	if (!op(p))
	    return;
    }
}

template <typename FILTER>
bool
BUILDER::testRect(RCT test, const FILTER &filter) const
{
    for (int x = test.x; x < test.x + test.w; x++)
    {
	for (int y = test.y; y < test.y + test.h; y++)
	{
	    if (!filter(IVEC2(x,y)))
		return false;
	}
    }
    return true;
}

template <typename FILTER>
RCT
BUILDER::findLargestRoom(IVEC2 startpos, const FILTER &filter) const
{
    RCT		result{startpos.x(), startpos.y(), 0, 0};
    // Verify starting position works.
    if (!filter(startpos))
	return result;
    result.w = result.h = 1;
    // Repeatedly grow until we hit walls on all sides.
    while (1)
    {
	bool		expanded = false;

	int		angle_xor = rand_choice(4);
	for (int angle = 0; angle < 4; angle++)
	{
	    int		dx, dy;
	    rand_getdirection(angle ^ angle_xor, dx, dy);

	    // Try to expand this way...
	    RCT		test;
	    if (dx == 1)
		test = RCT{result.x+result.w, result.y, 1, result.h};
	    else if (dx == -1)
		test = RCT{result.x-1, result.y, 1, result.h};
	    else if (dy == 1)
		test = RCT{result.x, result.y+result.h, result.w, 1};
	    else if (dy == -1)
		test = RCT{result.x, result.y-1, result.w, 1};
	    else
	    {
		J_ASSERT(!"Terrible drunk logic error.");
	    }
	    if (testRect(test, filter))
	    {
		expanded = true;
		result.doUnion(test);
	    }
	}

	if (!expanded)
	    break;
    }
    return result;
}


void
BUILDER::clear(int x, int y, int w, int h, u8 val)
{
    for (int i = 0; i < h; i++)
	for (int j = 0; j < w; j++)
	    set(x+j, y+i, val);
}

void
BUILDER::replace(RCT rct, u8 val, u8 newval)
{
    int		x, y;
    FORALL_RCT_XY(rct, x, y)
    {
	if (get(x, y) == val)
	    set(x, y, newval);
    }
}

void
BUILDER::replace_chance(RCT rct, u8 val, u8 newval, int chance)
{
    int		x, y;
    FORALL_RCT_XY(rct, x, y)
    {
	if (get(x, y) == val)
	{
	    if (rand_chance(chance))
		set(x, y, newval);
	}
    }
}

void
BUILDER::build(ROOMTYPE_NAMES type)
{
    switch (type)
    {
	case ROOMTYPE_ROGUE:
	    buildRogue();
	    break;
	case ROOMTYPE_FACE:
	case ROOMTYPE_CORRIDOR:
	case ROOMTYPE_ATRIUM:
	case ROOMTYPE_BARRACKS:
	case ROOMTYPE_GUARDHOUSE:
	case ROOMTYPE_THRONEROOM:
	case ROOMTYPE_VAULT:
	case ROOMTYPE_KITCHEN:
	case ROOMTYPE_DININGROOM:
	case ROOMTYPE_PANTRY:
	case ROOMTYPE_LIBRARY:
	    buildFace(type);
	    break;
	case ROOMTYPE_DARKCAVE:
	case ROOMTYPE_CAVE:
	    // These use same generator, just change up the
	    // floor tiles
	    buildCave();
	    break;
	case ROOMTYPE_MAZE:
	    buildMaze();
	    break;
	case ROOMTYPE_MAGE:
	    buildMage();
	    break;
	case ROOMTYPE_CAVEROOMS:
	    buildCaveRooms();
	    break;
	case ROOMTYPE_PALACE:
	    buildPalace();
	    break;
	case ROOMTYPE_BIGROOM:
	    buildBigRoom();
	    break;
	case ROOMTYPE_LABYRINTH:
	    buildLabyrinth();
	    break;
	case ROOMTYPE_WILDERNESS:
	{
	    TERRAIN_NAMES	terrain[9];
	    for (int i = 0; i < 9; i++)
		terrain[i] = TERRAIN_PLAINS;
	    buildWilderness(terrain);
	    break;
	}
	default:
	    J_ASSERT(!"Unhandled roomtype!");
	    break;
    }
    // savemap("badconnect.map");
}

void
BUILDER::buildRogue()
{
    int		minrooms = 4;
    int		maxrooms = 30;
    while (1)
    {
	clear(' ');

	PTRLIST<RCT> 	roomlist;

	// Try to place rooms until failures accumulate.
	while (1)
	{
	    if (roomlist.entries() >= maxrooms)
		break;

	    int 		fails = 0;
	    int			ntry = 50;
	    RCT		rect;
	    
	    // Pick the room size, then the position, so we
	    // don't bias to small rooms.
	    rect.w = rand_range(3+3, 5+3) + rand_choice(4) + rand_choice(3);
	    rect.h = rand_range(3+3, 4+3) + rand_choice(3);
	    
	    while (fails < ntry)
	    {
		// We need walls and a single border on the + side
		// to ensure no two rooms abutt.
		// Our min size is a 2x2

		rect.x = rand_range(1, width()-rect.w-1);
		rect.y = rand_range(1, height()-rect.h-1);

		// See if we overlap
		bool		overlap = false;
		for (int i = 0; i < roomlist.entries(); i++)
		    if (rect.overlap(roomlist(i)))
		    {
			overlap = true;
			break;
		    }

		if (overlap)
		{
		    fails++;
		}
		else
		{
		    roomlist.append(rect);
		    break;
		}
	    }
	    if (fails == ntry)
		break;
	}

	// If too few rooms, quit.
	if (roomlist.entries() < minrooms)
	    continue;

	// Stamp all the rooms.
	for (int i = 0; i < roomlist.entries(); i++)
	{
	    clear(roomlist(i).x, roomlist(i).y, roomlist(i).w-1, roomlist(i).h-1,
		    '#');
	    clear(roomlist(i).x+1, roomlist(i).y+1, roomlist(i).w-3, roomlist(i).h-3,
		    '.');
	}

	// Ensure we are unbiased.
	roomlist.shuffle();

	// Connect all pairs
	bool		ok = true;
	for (int i = 1; i < roomlist.entries(); i++)
	{
	    RCT		a = roomlist(rand_choice(i));
	    RCT		b = roomlist(i);
	    // Remove padding
	    a.w--; a.h--;
	    b.w--; b.h--;
	    ok &= connectRooms(a, b);
	}

	// Failed to connect?
	if (!ok)
	    continue;

	if (!dressLevel())
	{
	    continue;
	}
	break;
    }
}

bool
BUILDER::findRandom(RCT rct, u8 val, int &fx, int &fy) const
{
    int		nfound = 0;
    int		x, y;

    FORALL_RCT_XY(rct, x, y)
    {
	if (get(x, y) == val)
	{
	    if (!rand_choice(++nfound))
	    {
		fx = x;
		fy = y;
	    }
	}
    }
    return nfound > 0;
}

bool
BUILDER::findRandom(u8 val, int &x, int &y) const
{
    int		nfound = 0;

    for (int i = 0; i < height(); i++)
	for (int j = 0; j < width(); j++)
	    if (get(j, i) == val)
	    {
		if (!rand_choice(++nfound))
		{
		    x = j;
		    y = i;
		}
	    }
    return nfound > 0;
}

RCT
BUILDER::rand_rect(int minw, int minh, int maxw, int maxh) const
{
    RCT		result;

    J_ASSERT(minw < width()-2);
    J_ASSERT(minh < height()-2);

    result.w = rand_range(minw, maxw);
    result.h = rand_range(minh, maxh);

    result.w = MIN(result.w, width()-2);
    result.h = MIN(result.h, height()-2);

    result.x = rand_range(1, width()-result.w-1);
    result.y = rand_range(1, height()-result.h-1);

    return result;
}

bool
BUILDER::connectRooms(const RCT &a, const RCT &b)
{
    ROOMDATA<int>		dist(width(), height(), -1);

    // Find our starting location
    IVEC2		p_a, p_b;

    PTRLIST<IVEC2>	valid;
    for (int x = 1; x < a.w-1; x++)
    {
	valid.append(IVEC2(a.x+x, a.y));
	valid.append(IVEC2(a.x+x, a.y+a.h-1));
    }
    for (int y = 1; y < a.h-1; y++)
    {
	valid.append(IVEC2(a.x, a.y+y));
	valid.append(IVEC2(a.x+a.w-1, a.y+y));
    }

    p_a = valid(rand_choice(valid.entries()));

    valid.clear();
    for (int x = 1; x < b.w-1; x++)
    {
	valid.append(IVEC2(b.x+x, b.y));
	valid.append(IVEC2(b.x+x, b.y+b.h-1));
    }
    for (int y = 1; y < b.h-1; y++)
    {
	valid.append(IVEC2(b.x, b.y+y));
	valid.append(IVEC2(b.x+b.w-1, b.y+y));
    }

    p_b = valid(rand_choice(valid.entries()));

    // Ensure start and end are doors
    set(p_a, rand_choice(4) ? 'x' : '.');
    set(p_b, rand_choice(4) ? 'x' : '.');

    // Buid a distance map seeded at p_b
    valid.clear();
    valid.append(p_b);

    dist(p_b) = 0;

    while (valid.entries())
    {
	IVEC2		p = valid.removeFirst();
	int		d = dist(p);
	J_ASSERT(d >= 0);

	// Update four way neighbours.  By doing this we encourage
	// orthogonal lines.
	int		nd = d + 2 + rand_choice(4);

	for (int angle = 0; angle < 4; angle++)
	{
	    int		dx, dy;
	    rand_getdirection(angle, dx, dy);
	    IVEC2	np = p;
	    np.x() += dx;
	    np.y() += dy;

	    if (dist.inbounds(np))
	    {
		// Check walkable!
		int nnd = nd;
		// Cheaper to re-use ,
		if (get(np) == ',')
		    nnd--;

		if (strchr(", x", get(np)))
		{
		    if (dist(np) < 0 || dist(np) > nnd)
		    {
			dist(np) = nnd;
			valid.append(np);
		    }
		}
	    }
	}
    }

    if (dist(p_a) < 0)
    {
	// Failed to connect!
	return false;
    }

    // Starting with p_a we have max steps given by dist(p_a)
    int		maxdist = (dist(p_a) + 2) * 2;
    int		step = 0;
    IVEC2	p = p_a;
    int		dx = 0, dy = 1;

    while (step < maxdist)
    {
	int		curd = dist(p);

	if (p == p_b)
	    break;

	// try last direction.
	IVEC2		np = p;
	np.x() += dx;	np.y() += dy;
	int		nd = dist.inbounds(np) ? dist(np) : -1;

	// 4/5 times try last direction to keep straightish.
	if (rand_choice(5) && (nd >= 0 && nd < curd))
	{
	    if (nd)
	    {
		// Replace
		set(np, ',');
	    }
	    step++;
	    p = np;
	    continue;
	}

	// Look for a new downhill.
	int		angle = rand_choice(4);
	bool		found = false;
	for (int dir = 0; dir < 4; dir++)
	{
	    rand_getdirection(dir+angle, dx, dy);
	    np = p;
	    np.x() += dx;	np.y() += dy;
	    int		nd = dist.inbounds(np) ? dist(np) : -1;
	    if (nd >= 0 && nd < curd)
	    {
		if (nd)
		{
		    // Replace
		    set(np, ',');
		}
		step++;
		p = np;
		found = true;
		break;
	    }
	}

	if (!found)
	{
	    // Nothing downwind???
	    return false;
	}
    }

    return true;
}

void
BUILDER::buildFace(ROOMTYPE_NAMES type)
{
    while (1)
    {
	clear('#');

	if (type == ROOMTYPE_CORRIDOR)
	{
	    int	w = width()-6;
	    int	h = height()-6;

	    int		midx = width() / 2;
	    int		midy = height() / 2;
	    int		cx, cy;
	    int		hall_width = rand_range(1, 3);
	    int		hall_height = rand_range(1, 3);
	    int		merge_minx, merge_miny;
	    int		merge_maxx, merge_maxy;

	    // Proto portals.
	    cy = rand_range(4, height()-hall_height-4);
	    merge_miny = cy;
	    merge_maxy = cy+hall_height;
	    clear(2, cy, 1, hall_height, '+');
	    clear(1, cy, 1, hall_height, ' ');
	    clear(3, cy, midx-3+1, hall_height, '.');

	    cy = rand_range(4, height()-hall_height-4);
	    merge_miny = MIN(cy, merge_miny);
	    merge_maxy = MAX(cy+hall_height, merge_maxy);
	    clear(width()-3, cy, 1, hall_height, '+');
	    clear(width()-2, cy, 1, hall_height, ' ');
	    clear(midx, cy, width()-3 - midx, hall_height, '.');

	    cx = rand_range(4, width()-hall_width-4);
	    merge_minx = cx;
	    merge_maxx = cx + hall_width;
	    clear(cx, 2, hall_width, 1, '+');
	    clear(cx, 1, hall_width, 1, ' ');
	    clear(cx, 3, hall_width, midy-3+1, '.');

	    cx = rand_range(4, width()-hall_width-4);
	    merge_minx = MIN(cx, merge_minx);
	    merge_maxx = MAX(cx+hall_width, merge_maxx);
	    clear(cx, height()-3, hall_width, 1, '+');
	    clear(cx, height()-2, hall_width, 1, ' ');
	    clear(cx, midy, hall_width, height()-3 - midy, '.');

	    // Ensure central hall is open.
	    clear(merge_minx, merge_miny, merge_maxx-merge_minx, merge_maxy-merge_miny, '.');

	    if (!dressLevel(rand_chance(35), rand_chance(15)))
		continue;
	    break;
	}
	else
	{
	    clear(3, 3, width()-6, height()-6, '.');

	    int	w = width()-6;
	    int	h = height()-6;

	    int		hall_width = rand_range(1, 3);
	    int		hall_height = rand_range(1, 3);
	    if (type == ROOMTYPE_ATRIUM)
	    {
		hall_width = hall_height = 1;
	    }

	    int		midx = width() / 2;
	    int		midy = height() / 2;
	    int		cx, cy;

	    // Proto portals.
	    if (type == ROOMTYPE_ATRIUM)
		cy = height() / 2;
	    else
		cy = rand_range(4, height()-4-hall_height);
	    clear(2, cy, 1, hall_height, '+');
	    clear(1, cy, 1, hall_height, ' ');

	    if (type == ROOMTYPE_ATRIUM)
		cy = height() / 2;
	    else
		cy = rand_range(4, height()-4-hall_height);
	    clear(width()-3, cy, 1, hall_height, '+');
	    clear(width()-2, cy, 1, hall_height, ' ');

	    if (type == ROOMTYPE_ATRIUM)
		cx = width() / 2;
	    else
		cx = rand_range(4, width()-4-hall_width);
	    clear(cx, 2, hall_width, 1, '+');
	    clear(cx, 1, hall_width, 1, ' ');

	    if (type == ROOMTYPE_ATRIUM)
		cx = width() / 2;
	    else
		cx = rand_range(4, width()-4-hall_width);
	    clear(cx, height()-3, hall_width, 1, '+');
	    clear(cx, height()-2, hall_width, 1, ' ');

	    if (type == ROOMTYPE_ATRIUM)
	    {
		set(width()/2, height()/2, '<');

		set(3, 3, 'K');
		set(width()-4, height()-4, 'K');
		set(3, height()-4, 'K');
		set(width()-4, 3, 'K');

		if (!dressLevel(0, 1))
		    continue;
	    }
	    else if (type == ROOMTYPE_BARRACKS)
	    {
		int		nbed = rand_range(2, 4);
		for (int i = 0; i < nbed; i++)
		{
		    int		sx, sy;
		    bool found = findRandom('.', sx, sy);
		    if (found)
			set(sx, sy, '=');
		}
		if (!dressLevel(rand_range(1,3), rand_range(1,3)))
		    continue;
	    }
	    else if (type == ROOMTYPE_GUARDHOUSE)
	    {
		int		nchair = rand_range(2, 3);
		for (int i = 0; i < nchair; i++)
		{
		    int		sx, sy;
		    bool found = findRandom('.', sx, sy);
		    if (found)
			set(sx, sy, 'h');
		}
		if (!dressLevel(rand_range(2,4), rand_range(1, 3)))
		    continue;
	    }
	    else if (type == ROOMTYPE_THRONEROOM)
	    {
		int		nchair = rand_range(4, 6);
		for (int i = 0; i < nchair; i++)
		{
		    int		sx, sy;
		    bool found = findRandom('.', sx, sy);
		    if (found)
			set(sx, sy, 'h');
		}
		nchair = rand_range(0, 2);
		for (int i = 0; i < nchair; i++)
		{
		    int		sx, sy;
		    bool found = findRandom('.', sx, sy);
		    if (found)
			set(sx, sy, 'K');
		}
		if (!dressLevel(1, rand_range(1,5)))
		    continue;
	    }
	    else if (type == ROOMTYPE_VAULT)
	    {
		int		nshelf = rand_range(2, 6);
		for (int i = 0; i < nshelf; i++)
		{
		    int		sx, sy;
		    bool found = findRandom('.', sx, sy);
		    if (found)
			set(sx, sy, '?');
		}
		if (!dressLevel(0, rand_range(7,10)))
		    continue;
	    }
	    else if (type == ROOMTYPE_LIBRARY)
	    {
		int		nshelf = rand_range(3, 6);
		for (int i = 0; i < nshelf; i++)
		{
		    int		sx, sy;
		    bool found = findRandom('.', sx, sy);
		    if (found)
			set(sx, sy, '?');
		}
		if (!dressLevel(rand_range(0,1), 0))
		    continue;
	    }
	    else if (type == ROOMTYPE_KITCHEN)
	    {
		for (int i = 0; i < 1; i++)
		{
		    int		sx, sy;
		    bool found = findRandom('.', sx, sy);
		    if (found)
		    {
			if (get(sx-1, sy) == '.')
			    set(sx-1, sy, 'h');
			else if (get(sx+1, sy) == '.')
			    set(sx+1, sy, 'h');

			set(sx, sy, 'O');
		    }
		    found = findRandom('.', sx, sy);
		    if (found)
		    {
			set(sx, sy, '*');
		    }
		}
		if (!dressLevel(rand_range(1,2), rand_range(1,2)))
		    continue;
	    }
	    else if (type == ROOMTYPE_PANTRY)
	    {
		int		nshelf = rand_range(4, 6);
		for (int i = 0; i < nshelf; i++)
		{
		    int		sx, sy;
		    bool found = findRandom('.', sx, sy);
		    if (found)
			set(sx, sy, '?');
		}
		if (!dressLevel(1 +rand_chance(50), 0))
		    continue;
	    }
	    else if (type == ROOMTYPE_DININGROOM)
	    {
		int		ntable = rand_range(1, 3);
		for (int i = 0; i < ntable; i++)
		{
		    int		sx, sy;
		    bool found = findRandom('.', sx, sy);
		    if (found)
		    {
			int		dx, dy;
			FORALL_4DIR(dx, dy)
			{
			    if (get(sx+dx, sy+dy) == '.')
			    {
				if (rand_chance(75))
				    set(sx+dx, sy+dy, 'h');
			    }
			}
			set(sx, sy, 'O');
		    }
		}
		if (!dressLevel(0, rand_range(0,3)))
		    continue;
	    }

	    if (myDepth >= 5)
	    {
		dressLevel(rand_chance(50), 0);
	    }
	    if (myDepth >= 10)
	    {
		dressLevel(rand_chance(50), 0);
	    }
	    if (myDepth >= 15)
	    {
		dressLevel(rand_chance(50), 0);
	    }

	    break;
	}
    }
}

void
BUILDER::buildBigRoom()
{
    while (1)
    {
	clear('#');
	clear(3, 3, width()-6, height()-6, '.');

	if (!dressLevel())
	    continue;

	break;
    }
}

void
BUILDER::growBushes()
{
    // This is a GS process, so likely should reverse the sweeps.  Make
    // up for it by just randomizing the transition rules below unity.
    for (int y = 0; y < height(); y++)
    {
	for (int x = 0; x < width(); x++)
	{
	    int grass = 0, bush = 0, tree = 0, waste = 0;
	    // Gather neighbour counts.
	    for (int dy = -1; dy <= 1; dy++)
	    {
		for (int dx = -1; dx <= 1; dx++)
		{
		    switch (wrapget(x+dx, y+dy))
		    {
			case '_':
			    waste++;
			    break;
			case '.':
			    grass++;
			    break;
			case '*':
			    bush++;
			    break;
			case '&':
			    tree++;
			    break;
		    }
		}
	    }
	    switch (get(x, y))
	    {
		case '.':
		    // Grass will occassionally switch to *.
		    if (grass == 9)
		    {
			if (rand_chance(1))
			{
			    set(x, y, '*');
			}
			if (rand_chance(1))
			{
			    set(x, y, '_');
			}
		    }
		    else
		    {
			// Probability to * depends on neighbour count
			if (rand_chance( (bush + tree) * 10 ))
			    set(x, y, '*');
			else if (rand_chance( waste * 10 ))
			    set(x, y, '_');
		    }
		    break;
		case '*':
		    // Bushes grow to trees where dense.
		    if (bush == 9)
		    {
			if (rand_chance(90))
			    set(x, y, '&');
		    }
		    else
		    {
			// Trees convert bushes with strength.
			if (rand_chance( tree * 10 ))
			    set(x, y, '&');
		    }
		    break;
		case '&':
		    // Forests die off when crowded.
		    if (tree == 9)
		    {
			if (rand_chance(20))
			{
			    set(x, y, '.');
			}
		    }
		    break;
	    }
	}
    }
}

void
BUILDER::growForests()
{
    // This is a GS process, so likely should reverse the sweeps.  Make
    // up for it by just randomizing the transition rules below unity.
    for (int y = 0; y < height(); y++)
    {
	for (int x = 0; x < width(); x++)
	{
	    int grass = 0, bush = 0, tree = 0, waste = 0;
	    // Gather neighbour counts.
	    for (int dy = -1; dy <= 1; dy++)
	    {
		for (int dx = -1; dx <= 1; dx++)
		{
		    switch (wrapget(x+dx, y+dy))
		    {
			case '_':
			    waste++;
			    break;
			case '.':
			    grass++;
			    break;
			case '*':
			    bush++;
			    break;
			case '&':
			    tree++;
			    break;
		    }
		}
	    }
	    switch (get(x, y))
	    {
		case '.':
		    // Freeze plains...
		    break;
		case '*':
		    // Bushes grow to trees where dense.
		    if (bush == 9)
		    {
			if (rand_chance(90))
			    set(x, y, '&');
		    }
		    else
		    {
			// Trees convert bushes with strength.
			if (rand_chance( tree * 10 ))
			    set(x, y, '&');
		    }
		    break;
		case '&':
		    // Forests die off when crowded.
		    if (tree == 9)
		    {
			if (rand_chance(20))
			{
			    set(x, y, '.');
			}
		    }
		    break;
	    }
	}
    }
}

void
BUILDER::buildOvermap()
{
    while (1)
    {
	clear('.');

	for (int i = 0; i < 5; i++)
	{
	    growBushes();
	}
	for (int i = 0; i < 5; i++)
	{
	    growForests();
	}

	if (!dressLevel())
	    continue;

	break;
    }
}

struct TILE_WEIGHTS
{
public:
    TILE_WEIGHTS()
    {
	grass = bush = dirt = tree = 0;
    }
    TILE_WEIGHTS(TERRAIN_NAMES terrain)
    {
	grass = GAMEDEF::terraindef(terrain)->grass;
	bush = GAMEDEF::terraindef(terrain)->bush;
	dirt = GAMEDEF::terraindef(terrain)->dirt;
	tree = GAMEDEF::terraindef(terrain)->tree;
    }

    TILE_WEIGHTS &operator*=(int factor)
    {
	grass *= factor;
	bush *= factor;
	dirt *= factor;
	tree *= factor;
	return *this;
    }
    TILE_WEIGHTS &operator+=(const TILE_WEIGHTS &b)
    {
	grass += b.grass;
	bush += b.bush;
	tree += b.tree;
	dirt += b.dirt;
	return *this;
    }

    u8		pickRandom()
    {
	int		total = grass + bush + tree + dirt;
	int		choice = rand_choice(total);

	if (choice < grass)
	    return '.';
	choice -= grass;

	if (choice < bush)
	    return '*';
	choice -= bush;

	if (choice < tree)
	    return '&';
	choice -= tree;

	J_ASSERT(choice < dirt);
	return '_';
    }

    int		grass;
    int		bush;
    int		tree;
    int		dirt;
};

inline TILE_WEIGHTS operator*(const TILE_WEIGHTS &v1, int factor)
{ TILE_WEIGHTS result(v1);
  result *= factor;
  return result;
}

void
BUILDER::buildWilderness(const TERRAIN_NAMES *terrain)
{
    while (1)
    {
	TILE_WEIGHTS	corners[4];

	int		idx = 0;
	for (int dy = -1; dy <= 1; dy += 2)
	{
	    for (int dx = -1; dx <= 1; dx += 2)
	    {
		corners[idx] += TILE_WEIGHTS(terrain[ dx + dy * 3 + 4 ]);
		corners[idx] += TILE_WEIGHTS(terrain[ dx + 0  * 3 + 4 ]);
		corners[idx] += TILE_WEIGHTS(terrain[ 0  + dy * 3 + 4 ]);
		corners[idx] += TILE_WEIGHTS(terrain[ 0  + 0  * 3 + 4 ]);
		idx++;
	    }
	}

	int 		x, y;
	FORALL_XY(x, y)
	{
	    TILE_WEIGHTS	weight;
	    weight = corners[0] * (width() - x) * (height() - y);
	    weight += corners[1] * (x) * (height() - y);
	    weight += corners[2] * (width() - x) * (y);
	    weight += corners[3] * (x) * (y);

	    set(x, y, weight.pickRandom());
	}

	if (!dressLevel())
	    continue;

	break;
    }
}

struct WALLCUT
{
    WALLCUT() { x = -1; y = -1; horizontal = true; }
    WALLCUT(int _x, int _y, bool hor) { x = _x; y = _y; horizontal = hor; }

    int		x, y;
    bool	horizontal;
};

int
findClass(int search, PTRLIST<int> &classifier)
{
    if (search < 0)
	return search;

    int		rootclass = classifier(search);

    if (rootclass == search)
    {
	// Root!
	return search;
    }
    if (rootclass < 0)
    {
	// Invalid, done
	return rootclass;
    }

    // Now see if this is the proper root yet...
    int		newroot = findClass(rootclass, classifier);

    // Write back the new root
    classifier(search) = newroot;

    return newroot;
}

void
BUILDER::cutWall(int basex, int basey, int tilesize, u8 floorsym, u8 doorsym, const WALLCUT &cut)
{
    // Not too many doors.
    bool	usedoor = !rand_choice(5);

    cutWall(basex, basey, tilesize, floorsym, doorsym, cut, usedoor);
}

void
BUILDER::cutWall(int basex, int basey, int tilesize, 
		u8 floorsym, u8 doorsym,
		const WALLCUT &cut, bool usedoor)
{
    if (cut.horizontal)
    {
	int x = cut.x * tilesize + basex + tilesize-1;
	int y = cut.y * tilesize + basey;

	// Ignore already cut.
	if (get(x, y) == floorsym)
	    return;

	if (usedoor)
	{
	    y += rand_choice(tilesize-1);
	    set(x, y, doorsym);
	}
	else
	{
	    for (int i = 0; i < tilesize-1; i++)
		set(x, y+i, floorsym);
	}
    }
    else
    {
	int x = cut.x * tilesize + basex;
	int y = cut.y * tilesize + basey + tilesize-1;

	// Ignore already cut.
	if (get(x, y) == floorsym)
	    return;

	if (usedoor)
	{
	    x += rand_choice(tilesize-1);
	    set(x, y, doorsym);
	}
	else
	{
	    for (int i = 0; i < tilesize-1; i++)
		set(x+i, y, floorsym);
	}
    }
}

void
BUILDER::buildMaze()
{
    PTRLIST<int>	classifier;
    PTRLIST<WALLCUT>	wallcuts, unusedcuts;
    while (1)
    {
	clear('#');

	// Determine number of maze blocks.
	// EAch one is 3x3 and start 2 in on each side.
	int		tw = (width()-4) / 3;
	int		th = (height()-4) / 3;

	wallcuts.clear();
	unusedcuts.clear();

	for (int ty = 0; ty < th; ty++)
	{
	    for (int tx = 0; tx < tw; tx++)
	    {
		clear(tx * 3 + 2, ty * 3 + 2, 2, 2, '.');
		if (tx < tw-1)
		{
		    wallcuts.append(WALLCUT(tx, ty, true));
		}
		if (ty < th-1)
		{
		    wallcuts.append(WALLCUT(tx, ty, false));
		}
	    }
	}

	classifier.resize(tw * th);
	classifier.constant(-1);

	// Start with each cell connected to itself.
	for (int i = 0; i < tw * th; i++)
	    classifier(i) = i;

	wallcuts.shuffle();
	for (int i = 0; i < wallcuts.entries(); i++)
	{
	    WALLCUT	cut = wallcuts(i);
	    int		dx = 0, dy = 0;
	    if (cut.horizontal)
		dx = 1;
	    else
		dy = 1;

	    int		thisclass = findClass(cut.x + cut.y * tw, classifier);
	    int		otherclass = findClass(cut.x+dx + (cut.y+dy)*tw, classifier);
	    if (thisclass != otherclass)
	    {
		cutWall(2, 2, 3, '.', 'x', cut);
		classifier(otherclass) = thisclass;
	    }
	    else
	    {
		unusedcuts.append(cut);
	    }
	}

	unusedcuts.shuffle();
	// Extra cuts to make it less tree like.
	for (int i = 0; i < 8; i++)
	{
	    if (i >= unusedcuts.entries())
		break;
	    cutWall(2, 2, 3, '.', 'x', unusedcuts(i));
	}

	if (!dressLevel())
	    continue;

	break;
    }
}

class CLASSIFIER
{
public:
    CLASSIFIER(int w, int h)
    {
	myWidth = w;
	myHeight = h;
	myClass.resize(w * h);
	myClass.constant(-1);
    }

    void		initSelfConnect()
    {
	for (int i = 0; i < myClass.entries(); i++)
	    myClass(i) = i;
    }

    void		linkByClass(int target, int source)
    {
	myClass(target) = source;
    }

    void		linkByPos(int x1, int y1, int x2, int y2)
    {
	linkByClass(resolve(x1, y1), resolve(x2, y2));
    }

    int			resolve(int x, int y)
    {
	return ::findClass(x + y * width(), myClass);
    }

    bool		selfConnect(int x, int y) const
    {
	return myClass(x + y * width()) == x + y * width();
    }

    int			width() const { return myWidth; }
    int			height() const { return myHeight; }
protected:
    PTRLIST<int>	myClass;
    int			myWidth, myHeight;
};

void
BUILDER::buildMage()
{
    PTRLIST<WALLCUT>	wallcuts, unusedcuts;

    auto cut_wall = [&](const WALLCUT &cut, bool door)
    {
	this->cutWall(2, 2, 3, '.', 'x', cut, door);
    };

    // Mark all as no room
    myMetaData->constant(-1);
    while (1)
    {
	clear('#');

	// Determine number of maze blocks.
	// EAch one is 3x3 and start 2 in on each side.
	int		tw = (width()-4) / 3;
	int		th = (height()-4) / 3;

	CLASSIFIER		classifier(tw, th);
	GRIDB			usedroom(tw, th);
	int			roomtype;

	usedroom.constant(false);
	
	wallcuts.clear();
	unusedcuts.clear();

	// We initialize all the chambers to monomial.
	roomtype = 0;
	roomtype <<= 3;
	roomtype |= 1;

	for (int ty = 0; ty < th; ty++)
	{
	    for (int tx = 0; tx < tw; tx++)
	    {
		clear(tx * 3 + 2, ty * 3 + 2, 2, 2, '.');
		myMetaData->clear(tx*3+2, ty*3+2, 2, 2, roomtype);
		if (tx < tw-1)
		{
		    wallcuts.append(WALLCUT(tx, ty, true));
		}
		if (ty < th-1)
		{
		    wallcuts.append(WALLCUT(tx, ty, false));
		}
	    }
	}

	// Start with each cell connected to itself.
	classifier.initSelfConnect();

	// Now fuse together walls, starting with some 2x2 rooms.
	int		numsquares = 4;
	roomtype = 0;		// directions.
	roomtype <<= 3;
	roomtype |= 4;		// cells
	for (int i = 0; i < numsquares; i++)
	{
	    for (int tries = 500; tries --> 0; )
	    {
		// pick random place
		int x = rand_choice(tw-1);
		int y = rand_choice(th-1);
		if (!usedroom(x, y) &&
		    !usedroom(x+1, y) &&
		    !usedroom(x, y+1) &&
		    !usedroom(x+1, y+1))
		{
		    usedroom(x, y) = true;
		    usedroom(x+1, y) = true;
		    usedroom(x, y+1) = true;
		    usedroom(x+1, y+1) = true;
		    // room for 2x2.
		    classifier.linkByPos(x, y,  x+1, y);
		    classifier.linkByPos(x, y,  x, y+1);
		    classifier.linkByPos(x, y,  x+1, y+1);

		    clear(x * 3 + 2, y * 3 + 2, 5, 5, '.');
		    myMetaData->clear(x*3+2, y*3+2, 5, 5, roomtype);
		    break;
		}
	    }
	}

	// now try and drop some trinomial shapes..
	for (int tries = 500; tries --> 0; )
	{
	    // pick random place
	    int x = rand_choice(tw);
	    int y = rand_choice(th);

	    // Build an L or I shape..
	    int		dx1, dy1;
	    int		dx2, dy2;
	    rand_direction(dx1, dy1);
	    rand_direction(dx2, dy2);

	    // Ignore coincident.
	    if (dx1 == dx2 && dy1 == dy2)
		continue;

	    // Verify in bounds.
	    if (!usedroom.isValid(x+dx1, y+dy1) ||
		!usedroom.isValid(x+dx2, y+dy2))
		continue;

	    // Ensure three are unused.
	    if (usedroom(x+dx1, y+dy1) ||
		usedroom(x, y) ||
		usedroom(x+dx2, y+dy2))
		continue;

	    usedroom(x+dx1, y+dy1) = true;
	    usedroom(x, y) = true;
	    usedroom(x+dx2, y+dy2) = true;

	    classifier.linkByPos(x, y,  x+dx1, y+dy1);
	    classifier.linkByPos(x, y,  x+dx2, y+dy2);
	    
	    roomtype = rand_dir4_toangle(dx1, dy1);
	    roomtype <<= 2;
	    roomtype |= rand_dir4_toangle(dx2, dy2);
	    roomtype <<= 3;
	    roomtype |= 3;

	    WALLCUT cut;
	    cut.x = MIN(x, x+dx1);
	    cut.y = MIN(y, y+dy1);
	    cut.horizontal = dx1 != 0;
	    if (cut.horizontal)
		myMetaData->clear(cut.x*3+2, cut.y*3+2, 5, 2, roomtype);
	    else
		myMetaData->clear(cut.x*3+2, cut.y*3+2, 2, 5, roomtype);
	    cut_wall(cut, false);
	    cut.x = MIN(x, x+dx2);
	    cut.y = MIN(y, y+dy2);
	    cut.horizontal = dx2 != 0;
	    if (cut.horizontal)
		myMetaData->clear(cut.x*3+2, cut.y*3+2, 5, 2, roomtype);
	    else
		myMetaData->clear(cut.x*3+2, cut.y*3+2, 2, 5, roomtype);
	    cut_wall(cut, false);
	}

	// now try and drop some binomial shapes..
	for (int tries = 500; tries --> 0; )
	{
	    // pick random place
	    int x = rand_choice(tw);
	    int y = rand_choice(th);

	    // Build an L or I shape..
	    int		dx1, dy1;
	    rand_direction(dx1, dy1);

	    // Verify in bounds.
	    if (!usedroom.isValid(x+dx1, y+dy1))
		continue;

	    // Ensure three are unused.
	    if (usedroom(x+dx1, y+dy1) ||
		usedroom(x, y))
		continue;

	    usedroom(x+dx1, y+dy1) = true;
	    usedroom(x, y) = true;

	    roomtype |= rand_dir4_toangle(dx1, dy1);
	    roomtype <<= 3;
	    roomtype |= 2;

	    classifier.linkByPos(x, y,  x+dx1, y+dy1);
	    
	    WALLCUT cut;
	    cut.x = MIN(x, x+dx1);
	    cut.y = MIN(y, y+dy1);
	    cut.horizontal = dx1 != 0;
	    if (cut.horizontal)
		myMetaData->clear(cut.x*3+2, cut.y*3+2, 5, 2, roomtype);
	    else
		myMetaData->clear(cut.x*3+2, cut.y*3+2, 2, 5, roomtype);
	    cut_wall(cut, false);
	}

	// Eliminate any wall cuts that are internal walls that
	// we removed.  This way our extra cuts to break tree-ness
	// are all real cuts.
	for (int i = 0; i < wallcuts.entries(); i++)
	{
	    WALLCUT	cut = wallcuts(i);
	    int		dx = 0, dy = 0;
	    if (cut.horizontal)
		dx = 1;
	    else
		dy = 1;

	    int		thisclass = classifier.resolve(cut.x, cut.y);
	    int		otherclass = classifier.resolve(cut.x+dx, cut.y+dy);
	    if (thisclass != otherclass)
		unusedcuts.append(cut);
	}

	wallcuts = unusedcuts;
	unusedcuts.clear();

	wallcuts.shuffle();
	for (int i = 0; i < wallcuts.entries(); i++)
	{
	    WALLCUT	cut = wallcuts(i);
	    int		dx = 0, dy = 0;
	    if (cut.horizontal)
		dx = 1;
	    else
		dy = 1;

	    int		thisclass = classifier.resolve(cut.x, cut.y);
	    int		otherclass = classifier.resolve(cut.x+dx, cut.y+dy);
	    if (thisclass != otherclass)
	    {
		cut_wall(cut, true);
		classifier.linkByClass(otherclass, thisclass);
	    }
	    else
	    {
		unusedcuts.append(cut);
	    }
	}

	unusedcuts.shuffle();
	// Extra cuts to make it less tree like.
	for (int i = 0; i < 4; i++)
	{
	    if (i >= unusedcuts.entries())
		break;
	    cut_wall(unusedcuts(i), true);
	}

	if (!dressLevel())
	    continue;

	break;
    }
}

void
BUILDER::buildPalace()
{
    while (1)
    {
	clear(' ');

	int		carved = 0;
	int		maxcarved = (width()-2) * (height()-2);
	int		numsegments = 10;
	int		buffercarve = 20;

	// 1/3rd clearance.
	if (myGoalTiles < 0)
	    maxcarved = maxcarved / 3;
	else
	    maxcarved = myGoalTiles;

	// Crystal growth...
	PTRLIST<IVEC2> terminals;

	// Ensure we have enough padding:
	RCT bounds{5, 5, width()-10, height()-10};

	auto carve_path = [&](IVEC2 loc)
	{
	    if (get(loc) == ' ')
		carved++;
	    set(loc, ',');
	};

	auto room_blockers = [&](IVEC2 loc) -> bool
	{
	    if (loc.x() >= width()-1 || loc.y() >= height()-1)
		return false;
	    if (loc.x() < 1 || loc.y() < 1)
		return false;
	    u8	sym = get(loc);
	    if (sym == '.' || sym == ',')
		return false;
	    // That not forbidden is permitted
	    return true;
	};

	auto carve_room = [&](IVEC2 loc, bool border)
	{
	    u8 sym = get(loc);
	    if (!border)
	    {
		if (sym == ' ' || sym == '#')
		    carved++;
		set(loc, '.');
	    }
	    else
	    {
		// don't overwrite existing doors.
		if (sym == ' ')
		    set(loc, '#');
	    }
	};

	auto build_room = [&](IVEC2 terminal, int gdx, int gdy, int maxsize) -> bool
	{
	    RCT	maxroom = findLargestRoom(terminal, room_blockers);

	    if (maxsize < 4) return false;

	    // Big enough room?
	    if (maxroom.w < 4 || maxroom.h < 4)
		return false;

	    // Determine what room to actually build...
	    RCT room;
	    // 7 max is a 5x5 max room.
	    // that is a bit too many rooms so try 8?
	    room.w = rand_range(4, MIN(8, maxroom.w));
	    room.h = rand_range(4, MIN(8, maxroom.h));

	    while ((room.w - 2) * (room.h - 2) > maxsize)
	    {
		if (room.w > room.h) room.w--;
		else room.h--;
	    }
	    if (maxroom.w < 4 || maxroom.h < 4)
		return false;

	    // Valid door location in the room has to respect the 1
	    // border on each side (so for 4 size is 2 locs)
	    // The resulting room must also be in the maxroom.
	    if (gdx == 1)
		room.x = terminal.x();
	    else if (gdx == -1)
		room.x = terminal.x() - room.w + 1;
	    else if (gdy == 1)
		room.y = terminal.y();
	    else if (gdy == -1)
		room.y = terminal.y() - room.h + 1;

	    if (gdx)
	    {
		int	min_y = terminal.y() - room.h + 2;
		int	max_y = terminal.y() - 1;
		min_y = BOUND(min_y, maxroom.y, maxroom.y+maxroom.h-room.h);
		max_y = BOUND(max_y, maxroom.y, maxroom.y+maxroom.h-room.h);
		room.y = rand_range(min_y, max_y);
	    }
	    else
	    {
		int	min_x = terminal.x() - room.w + 2;
		int	max_x = terminal.x() - 1;
		min_x = BOUND(min_x, maxroom.x, maxroom.x+maxroom.w-room.w);
		max_x = BOUND(max_x, maxroom.x, maxroom.x+maxroom.w-room.w);
		room.x = rand_range(min_x, max_x);
	    }

	    // We may still be invalid as the maxroom might not allow
	    // the required padding so that a floor is next to the 
	    // source location.
	    IVEC2	testpos = terminal + IVEC2(gdx, gdy);
	    RCT		shrunk = room;
	    shrunk.x++;
	    shrunk.y++;
	    shrunk.w -= 2;
	    shrunk.h -= 2;

	    if (!shrunk.contains(testpos))
		return false;

	    drawBorderedRect(room, carve_room);
	    // We should have floor next to the coming door.
	    J_ASSERT(get(testpos) == '.');
	    return true;
	};

	terminals.append(IVEC2(width()/2, height()/2));
	carve_path(terminals.last());

	for (int i = 0; i < numsegments; i++)
	{
	    bool		found = false;
	    for (int tries = 20; !found && tries --> 0; )
	    {
		// attempt to grow from random terminal.
		IVEC2 start = terminals(rand_choice(terminals.entries()));

		// Try each random dir.
		int		angle_xor = rand_choice(4);
		for (int angle = 0; angle < 4; angle++)
		{
		    int		dx, dy;
		    rand_getdirection(angle ^ angle_xor, dx, dy);
		    IVEC2	delta(dx, dy);

		    if (get(start + delta) != ' ')
			continue;

		    int		dist = rand_range(5, 8);

		    IVEC2		npos = start + delta * dist;
		    // Need enough room for a terminal room.
		    if (!bounds.contains(npos))
			continue;

		    // All good, carve a path.
		    for (int d = 0; d <= dist; d++)
			carve_path(start + delta * d);

		    terminals.append(npos);
		    found = true;
		    break;
		}
	    }
	}

	// Now create terminal rooms.
	terminals.shuffle();
	for (auto && terminal : terminals)
	{
	    int		dx, dy, gdx, gdy;
	    int		empty = 0;
	    FORALL_4DIR(dx, dy)
	    {
		if (get(terminal + IVEC2(dx, dy)) == ' ')
		{
		    empty++;
		}
		else
		{
		    gdx = dx;
		    gdy = dy;
		}
	    }
	    // If three empty, we have a true terminal to build a room on.
	    if (empty != 3)
		continue;

	    // gdx,gdy is the direction of the path, so build in
	    // opposite directoin
	    gdx = -gdx;
	    gdy = -gdy;
	    // Make our actual spot roomable as it will be a doorway.
	    set(terminal, ' ');
	    bool ok = build_room(terminal, gdx, gdy, maxcarved-carved-1-buffercarve);
	    if (!ok)
	    {
		set(terminal, ',');
		continue;
	    }

	    // Restore the door.
	    set(terminal, 'x');
	}

	// Now create a series of additional rooms until our budget
	// is up...
	for (int ntries = 20; ntries --> 0; )
	{
	    int		x, y;
	    findRandom(',', x, y);

	    int		dx, dy, gdx, gdy;
	    int		empty = 0;
	    FORALL_4DIR(dx, dy)
	    {
		if (get(IVEC2(x, y) + IVEC2(dx, dy)) == ' ' &&
		    get(IVEC2(x, y) + IVEC2(dx, dy) + IVEC2(dy, dx)) == ' ' &&
		    get(IVEC2(x, y) + IVEC2(dx, dy) + IVEC2(-dy, -dx)) == ' ')
		{
		    empty++;
		    if (!rand_choice(empty))
		    {
			gdx = dx;
			gdy = dy;
		    }
		}
	    }

	    if (empty)
	    {
		// We had a potential room in gdx, gdy
		IVEC2 startpos(x+gdx, y+gdy);

		if (build_room(startpos, gdx, gdy, maxcarved-carved-1-buffercarve))
		{
		    if (get(startpos) == '#')
			carved++;
		    set(startpos, 'x');
		}
	    }

	    if (carved + buffercarve > maxcarved)
		break;
	}

	// See if we carved to much
	if (carved > maxcarved)
	    continue;

	// Complete our buffer by adding new rooms or connections.
	int		maxtries = 10000;
	while (carved < maxcarved && (maxtries-->0))
	{
	    int		x, y;
	    if (!findRandom('#', x, y))
		break;

	    IVEC2 startpos(x, y);
	    auto is_floor = [&](IVEC2 loc) -> bool
	    {
		if (get(loc) == ',' || get(loc) == '.') return true;
		return false;
	    };

	    // See if a potential door
	    bool		doorable = false;
	    if (is_floor(startpos+IVEC2(1,0)) && is_floor(startpos+IVEC2(-1,0)))
		doorable = true;
	    if (is_floor(startpos+IVEC2(0,1)) && is_floor(startpos+IVEC2(0,-1)))
		doorable = true;

	    if (doorable)
	    {
		set(startpos, 'x');
		carved++;
		continue;
	    }

	    // Check for chain room. Need a double clear spot at destination,
	    // and have a floor to the opposite direction.
	    int		dx, dy, gdx, gdy;
	    int		empty = 0;
	    FORALL_4DIR(dx, dy)
	    {
		IVEC2	delta(dx, dy), norm(dy, -dx);
		if (get(startpos + delta) == ' ' &&
		    get(startpos + delta + norm) == ' ' &&
		    get(startpos + delta - norm) == ' ' &&
		    is_floor(startpos - delta))
		{
		    empty++;
		    if (!rand_choice(empty))
		    {
			gdx = dx;
			gdy = dy;
		    }
		}
	    }

	    if (empty)
	    {
		// Found a satellite room.
		if (build_room(startpos, gdx, gdy, maxcarved-carved-1))
		{
		    if (get(startpos) == '#')
			carved++;
		    set(startpos, 'x');
		}
	    }
	}

	if (carved != maxcarved)
	    continue;

	if (!dressLevel())
	    continue;
	break;
    }
}

void
BUILDER::buildRoomMaze(RCT rct, u8 wallsym, u8 floorsym)
{
    PTRLIST<int>	classifier;
    PTRLIST<WALLCUT>	wallcuts, unusedcuts;

    while (1)
    {
	clear(rct, wallsym);
	// Every other becomes a floor.

	// Determine number of maze blocks.
	// EAch one is 2x2
	const int	tilesize = 2;
	const int	tw = (rct.width()) / tilesize;
	const int	th = (rct.height()) / tilesize;

	auto cut_wall = [&](const WALLCUT &cut)
	{
	    this->cutWall(rct.x, rct.y, tilesize, floorsym, 'x', cut,
			    rand_chance(10));
	};

	wallcuts.clear();
	unusedcuts.clear();

	for (int ty = 0; ty < th; ty++)
	{
	    for (int tx = 0; tx < tw; tx++)
	    {
		clear(tx * tilesize + rct.x, ty * tilesize + rct.y, 
		      tilesize-1, tilesize-1, floorsym);
		if (tx < tw-1)
		{
		    wallcuts.append(WALLCUT(tx, ty, true));
		}
		if (ty < th-1)
		{
		    wallcuts.append(WALLCUT(tx, ty, false));
		}
	    }
	}

	classifier.resize(tw * th);
	classifier.constant(-1);

	// Start with each cell connected to itself.
	for (int i = 0; i < tw * th; i++)
	    classifier(i) = i;

	wallcuts.shuffle();
	for (int i = 0; i < wallcuts.entries(); i++)
	{
	    WALLCUT	cut = wallcuts(i);
	    int		dx = 0, dy = 0;
	    if (cut.horizontal)
		dx = 1;
	    else
		dy = 1;

	    int		thisclass = findClass(cut.x + cut.y * tw, classifier);
	    int		otherclass = findClass(cut.x+dx + (cut.y+dy)*tw, classifier);
	    if (thisclass != otherclass)
	    {
		cut_wall(cut);
		classifier(otherclass) = thisclass;
	    }
	    else
	    {
		unusedcuts.append(cut);
	    }
	}

	unusedcuts.shuffle();
	// Extra cuts to make it less tree like.
	for (int i = 0; i < 2; i++)
	{
	    if (i >= unusedcuts.entries())
		break;
	    cut_wall(unusedcuts(i));
	}

	// Success!
	break;
    }
}

void
BUILDER::buildRoomCave(RCT rct, u8 wallsym, u8 floorsym)
{
    while (1)
    {
	clear(rct, ' ');

	int		carved = 0;
	int		maxcarved = (rct.w-2) * (rct.h-2);

	// Goal clearing rate...
	maxcarved = maxcarved / 3;

	clear(rct.inset(1), wallsym);

	auto carve_cave = [&](IVEC2 loc) -> bool
	{
	    if (carved >= maxcarved)
		return false;
	    if (!isValid(loc)) return false;
	    if (get(loc) == ' ')
		return false;
	    if (get(loc) == wallsym)
		carved++;
	    set(loc, floorsym);
	    return true;
	};

	int iter = 0;
	while (carved < maxcarved)
	{
	    IVEC2 p = rct.center();
	    drunkExcavate(p, 10 + iter / 10, carve_cave);
	    iter++;

	    if (iter > 10000)
		break;
	}

	// See if we got correct fraction:
	if (carved != maxcarved)
	    continue;

	// Restore boundaries.
	replace(rct, ' ', wallsym);

	// Success!
	break;
    }
}

void
BUILDER::buildLabyrinth()
{
    while (1)
    {
	clear(' ');

	int		carved = 0;
	int		maxcarved = (width()-2) * (height()-2);
	int		numsegments = 10;
	int		buffercarve = 20;

	const int	tilesize = 12;
	const int	tilew = (width()-2) / tilesize;
	const int	tileh = (height()-2) / tilesize;
	const int	numrooms = 6;
	const int	maxmaze = 2;
	const int	drunkness = 10;

	// Guess what, MSVC 2019 can't run a switch off these :<
	// constexpr int	ROOM_MAZE = 0;
	// constexpr int	ROOM_CAVE = 1;
	enum
	{
	    ROOM_MAZE,
	    ROOM_CAVE
	};

	GRIDB		tileused;
	GRIDI		tiletype;
	tileused.setSize(tilew, tileh);
	tileused.constant(false);
	tiletype.setSize(tilew, tileh);

	int		nummaze = 0;

	auto carve_tunnel = [&](IVEC2 loc) -> bool
	{
	    // Only write over walls, don't write over other 
	    // path types
	    if (get(loc) == '#')
	    {
		set(loc, ',');
	    }
	    return true;
	};

	auto rct_from_tile = [&](int x, int y) -> RCT
	{
	    RCT		rct{x*tilesize+1, y*tilesize+1, tilesize, tilesize};
	    return rct;
	};

	auto connect_room = [&](int ax, int ay, int bx, int by)
	{
	    // Find random location to do the connection
	    // Mazes are always present on even offsets,
	    // so make sure we pick one of those, and avoid
	    // the corner.
	    int		off = rand_range(1, (tilesize/2-1));
	    off *= 2;

	    // Sort are we horizontal or vertical?
	    int		connectx, connecty;
	    RCT		rct;
	    if (ax == bx)
	    {
		// Vertical
		J_ASSERT(ay != by);
		if (ay > by)
		    std::swap(ay, by);

		rct = rct_from_tile(ax, ay);
		connectx = rct.x;
		connecty = rct.y;
		connecty += tilesize-1;
	    }
	    else if (ay == by)
	    {
		J_ASSERT(ax != bx);
		// Horizontal
		if (ax > bx)
		    std::swap(ax, bx);

		rct = rct_from_tile(ax, ay);
		connectx = rct.x;
		connecty = rct.y;
		connectx += tilesize-1;
	    }
	    else
	    {
		J_ASSERT(!"Invalid tile connection");
	    }

	    u8	connectsym = '.';
	    if (!rand_choice(3))
		connectsym = 'x';
	    if (tiletype(ax, ay) == ROOM_CAVE &&
		tiletype(bx, by) == ROOM_CAVE)
	    {
		connectsym = ',';
	    }

	    if (tiletype(ax, ay) == ROOM_CAVE)
	    {
		drunkExcavateBetween(rct_from_tile(ax,ay).centre(), 
			IVEC2{connectx, connecty}, drunkness, carve_tunnel);
	    }
	    if (tiletype(bx, by) == ROOM_CAVE)
	    {
		drunkExcavateBetween(rct_from_tile(bx, by).centre(), 
			IVEC2{connectx, connecty}, drunkness, carve_tunnel);
		
	    }
	    // Ensure the actual square is a door or free, this
	    // also handles maze pairs.
	    set(connectx, connecty, connectsym);
	};

	int		tilex, tiley;
	// Start in center...
	tilex = tilew/2;
	tiley = tileh/2;

	int	room = 0;
	int	roomtype = 0;
	int	lastdx = 0, lastdy = 0;
	RCT	lasttilerct;
	for (room = 0; room < numrooms; room++)
	{
	    RCT		tilerct = rct_from_tile(tilex, tiley);

	    tileused.set(tilex, tiley, true);

	    switch (rand_choice(4))
	    {
		case 0:
		case 1:
		    if (nummaze >= maxmaze)
			roomtype = ROOM_CAVE;
		    else
		    {
			roomtype = ROOM_MAZE;
			nummaze++;
		    }
		    break;
		case 2:
		case 3:
		    roomtype = ROOM_CAVE;
		    break;
	    }
	    // Must end with a cave or it is too mean to find >
	    if (room == numrooms-1)
		roomtype = ROOM_CAVE;

	    tiletype.set(tilex, tiley, roomtype);
	    switch (roomtype)
	    {
		case ROOM_MAZE:
		    buildRoomMaze(tilerct, '#', '.');
		    break;
		case ROOM_CAVE:
		    buildRoomCave(tilerct, '#', '.');
		    break;
	    }

	    // Ensure stairs are in opposite rooms.
	    if (!room)
	    {
		int		x,y;
		if (!findRandom(tilerct, '.', x, y))
		    continue;
		set(x, y, '<');
	    }
	    else if (room == numrooms-1)
	    {
		int		x,y;
		if (!findRandom(tilerct, '.', x, y))
		    continue;
		set(x, y, '>');
	    }

	    // Final room only connects adjacent.
	    if (room == numrooms-1)
		connect_room( tilex, tiley,  tilex-lastdx, tiley-lastdy );
	    else
	    {
		// Connect all directions
		int		dx, dy;
		for (int i = 0; i < 4; i++)
		{
		    rand_getdirection(i, dx, dy);

		    if (tilex+dx < 0) continue;
		    if (tilex+dx >= tilew) continue;
		    if (tiley+dy < 0) continue;
		    if (tiley+dy >= tileh) continue;

		    if (tileused(tilex+dx, tiley+dy))
		    {
			connect_room(tilex, tiley, tilex+dx, tiley+dy);
		    }
		}
	    }

	    // Find a new direction to connect into...
	    int angles[4] = {0, 1, 2, 3};
	    rand_shuffle(angles, 4);
	    bool	found = false;
	    lasttilerct = tilerct;
	    int		dx, dy;
	    for (int i = 0; i < 4; i++)
	    {
		rand_getdirection(angles[i], dx, dy);

		if (tilex+dx < 0) continue;
		if (tilex+dx >= tilew) continue;
		if (tiley+dy < 0) continue;
		if (tiley+dy >= tileh) continue;

		if (tileused(tilex+dx, tiley+dy))
		    continue;

		found = true;
		tilex += dx;
		tiley += dy;
		break;
	    }
	    lastdx = dx;
	    lastdy = dy;
	    if (!found)
		break;
	}
	// See if we quit early.
	if (room < numrooms)
	    continue;

	replace(' ', '#');

	if (!dressLevel())
	    continue;

	// Change to local tiles
	tiletype.foreachXY([&](int x, int y)
	{
	    switch (tiletype(x, y))
	    {
		case ROOM_MAZE:
		    break;
		case ROOM_CAVE:
		    replace(rct_from_tile(x, y), '.', ',');
		    break;
	    }
	});

	break;
    }
}

void
BUILDER::buildCaveRooms()
{
    while (1)
    {
	clear(' ');

	int		carved = 0;
	int		maxcarved = (width()-2) * (height()-2);

	// 1/3rd clearance.
	if (myGoalTiles < 0)
	    maxcarved = maxcarved / 3;
	else
	    maxcarved = myGoalTiles;

	clear(1, 1, width()-2, height()-2, '#');

	PTRLIST<IVEC2>		startlist;	

	auto carve_tunnel = [&](IVEC2 loc) -> bool
	{
	    // Only write over walls, don't write over other 
	    // path types
	    if (get(loc) == '#')
	    {
		carved++;
		set(loc, ',');
	    }
	    return true;
	};
	auto carve_cave = [&](IVEC2 loc) -> bool
	{
	    if (carved >= maxcarved)
		return false;
	    if (!isValid(loc)) return false;
	    if (get(loc) == ' ')
		return false;
	    if (get(loc) == '#')
		carved++;
	    set(loc, '.');
	    return true;
	};

	int		seedw = 2;
	int		seedh = 2;
	for (int seedy = 0; seedy < seedh; seedy++)
	{
	    int miny = (seedy * height()) / seedh;
	    int maxy = ((seedy+1) * height()) / seedh;
	    miny = BOUND(miny, 2, height()-3);
	    maxy = BOUND(maxy, 2, height()-3);
	    for (int seedx = 0; seedx < seedw; seedx++)
	    {
		int minx = (seedx * width()) / seedw;
		int maxx = ((seedx+1) * width()) / seedw;
		minx = BOUND(minx, 2, width()-3);
		maxx = BOUND(maxx, 2, width()-3);

		startlist.append(IVEC2(rand_range(minx, maxx), rand_range(miny, maxy)));

		IVEC2 p = startlist.last();
		if (get(p) == '#')
		    carved++;
		set(p, '.');

		const int drunkness = 60;

		// Connect to earlier seed locations.
		if (seedx)
		{
		    drunkExcavateBetween(p,
				startlist(seedx-1+seedy*seedw),
				drunkness,
				carve_tunnel);
		}
		if (seedy)
		{
		    drunkExcavateBetween(p,
				startlist(seedx+(seedy-1)*seedw),
				drunkness,
				carve_tunnel);
		}
	    }
	}

	int iter = 0;
	while (carved < maxcarved)
	{
	    IVEC2 p = startlist(rand_choice(startlist.entries()));
	    drunkExcavate(p, 10 + iter / 10, carve_cave);
	    iter++;

	    if (iter > 10000)
		break;
	}

	if (carved != maxcarved)
	    continue;

	// Fix boundaries.
	replace(' ', '#');

	if (!dressLevel())
	    continue;
	break;
    }
}

void
BUILDER::buildCave()
{
    while (1)
    {
	clear(' ');

	// Try to cut out a certain pecentage of the rock.
	clear(1, 1, width()-2, height()-2, '#');
	// Our seed.
	set(width()/2, height()/2, '.');
	int		cleared = 1;
	int		needtoclear = (width()-2) * (height()-2);

	// 1/3rd clearance.
	if (myGoalTiles < 0)
	    needtoclear = needtoclear / 3;
	else
	    needtoclear = myGoalTiles;

	PTRLIST<IVEC2>		startlist;	

	while (cleared < needtoclear)
	{
	    // Find a new drunk start location bordering a wall.
	    startlist.clear();
	    for (int y = 2; y < height()-3; y++)
	    {
		for (int x = 2; x < width()-3; x++)
		{
		    // Check if there is a neighbouring wall
		    if (get(x,y) == '.')
		    {
			bool	haswall = false;
			int		dx, dy;
			FORALL_4DIR(dx, dy)
			{
			    if (get(x+dx, y+dy) == '#')
			    {
				haswall = true;
				break;
			    }
			}

			if (haswall)
			    startlist.append(IVEC2(x, y));
		    }

		}
	    }

	    // Now we don't want to keep rebuilding that list,
	    // so we will pick a number of walks from this start.
	    for (int walk = 0; walk < 2; walk++)
	    {
		IVEC2	p = startlist(rand_choice(startlist.entries()));

		drunkExcavate(p, 15, [&](IVEC2 loc) -> bool
		{
		    if (!isValid(loc))
			return false;
		    if (get(loc) == ' ')
			return false;
		    if (get(loc) == '#')
			cleared++;
		    set(loc, '.');
		    return true;
		});
	    }
	}

	replace(' ', '#');

	if (!dressLevel())
	    continue;

	// All good.
	break;
    }
}

void
BUILDER::savemap(const char *fname) const
{
    ofstream	os(fname);

    for (int i = 0; i < height(); i++)
    {
	for (int j = 0; j < width(); j++)
	{
	    os << get(j, i);
	}
	os << "\n";
    }
}

bool
BUILDER::dressLevel()
{
    // We need a pretty consistent mob rate as we don't have
    // wandering monsters.
    int		nmob = rand_range(6, 7);
    int		nitem = rand_range(6, 7);
    if (myDepth <= 0)
    {
	nmob = nitem = 0;
    }
    // nitem = 100;

    return dressLevel(nmob, nitem);
}

bool
BUILDER::dressLevel(int nmob, int nitem)
{
    if (myDepth > 0)
    {
	int		sx, sy;
	bool	found;

	// Add stairs if not already created
	// by the generator.
	// We need final staircsae to escape!
	if (!findRandom('>', sx, sy))
	{
	    if (1) // myDepth < GAMEDEF::rules().bosslevel)
	    {
		found = findRandom('.', sx, sy);
		J_ASSERT(found);
		if (!found)
		    return false;
		set(sx, sy, '>');
	    }
	}
	if (!findRandom('<', sx, sy))
	{
	    found = findRandom('.', sx, sy);
	    J_ASSERT(found);
	    if (!found)
		return false;
	    set(sx, sy, '<');
	}
    }

    // Add the boss!
    if (myDepth == GAMEDEF::rules().bosslevel)
    {
	int		sx, sy;
	// Waits at the exit!
	bool found = findRandom('>', sx, sy);

	if (found)
	{
	    int		offset = rand_choice(8);
	    int		dx, dy;
	    found = false;
	    for (int angle = 0; angle < 8; angle++)
	    {
		rand_angletodir(angle+offset, dx, dy);
		if (get(sx+dx, sy+dy) == '.')
		{
		    sx += dx;
		    sy += dy;
		    found = true;
		    break;
		}
	    }
	}

	if (!found)
	    found = findRandom('.', sx, sy);
	if (found)
	    set(sx, sy, 'B');
	else
	    return false;
    }

    // Add monsters
    for (int i = 0; i < nmob; i++)
    {
	int		sx, sy;
	bool found = findRandom('.', sx, sy);
	if (found)
	    set(sx, sy, 'A');
    }

    // Add items
    for (int i = 0; i < nitem; i++)
    {
	int		sx, sy;
	bool found = findRandom('.', sx, sy);
	if (found)
	    set(sx, sy, '(');
    }

    return true;
}
