<commit_before>DG_CONNECTION_UL = 1<<3;
DG_CONNECTION_UR = 1<<2;
DG_CONNECTION_DR = 1<<1;
DG_CONNECTION_DL = 1<<0;

DG_MASK_U = DG_CONNECTION_UL | DG_CONNECTION_UR;
DG_MASK_R = DG_CONNECTION_UR | DG_CONNECTION_DR;
DG_MASK_D = DG_CONNECTION_DR | DG_CONNECTION_DL;
DG_MASK_L = DG_CONNECTION_DL | DG_CONNECTION_UL;

DG_DIRECTION_U = 0;
DG_DIRECTION_R = 1;
DG_DIRECTION_D = 2;
DG_DIRECTION_L = 3;

DG_FLAG_U = 1 << DG_DIRECTION_U;
DG_FLAG_R = 1 << DG_DIRECTION_R;
DG_FLAG_D = 1 << DG_DIRECTION_D;
DG_FLAG_L = 1 << DG_DIRECTION_L;

DG_TILE_BIG_ROOM	= DG_CONNECTION_UL | DG_CONNECTION_UR | DG_CONNECTION_DR | DG_CONNECTION_DL;
DG_TILE_SMALL_ROOM	= DG_CONNECTION_UL;
DG_TILE_HALL		= DG_CONNECTION_UL | DG_CONNECTION_DL;
DG_TILE_CORNER		= DG_CONNECTION_UR | DG_CONNECTION_DR | DG_CONNECTION_DL;

DG_OVERLAY_STAIRS_DN = "overlay_stairsdown";
DG_OVERLAY_STAIRS_UP = "overlay_stairsup";
DG_OVERLAY_DOOR = "overlay_door"

var DunGen = DunGen || {
    ALL_DIRECTIONS: [DG_DIRECTION_U, DG_DIRECTION_R, DG_DIRECTION_D, DG_DIRECTION_L],
    ALL_TILES: [DG_TILE_BIG_ROOM, DG_TILE_SMALL_ROOM, DG_TILE_HALL, DG_TILE_CORNER],
    ALL_IMAGES: [DG_TILE_BIG_ROOM, DG_TILE_SMALL_ROOM, DG_TILE_HALL, DG_TILE_CORNER,
		    DG_OVERLAY_STAIRS_DN, DG_OVERLAY_STAIRS_UP, DG_OVERLAY_DOOR],

    TILE_NAMES: {},

    TILE_SIZE: 980,

    DOOR_TILE_WIDTH: 350,
    DOOR_TILE_HEIGHT: 140,
    DOOR_OFFSET: 210,
    DOOR_WIDTH: 140,

    MIN_LINE_WIDTH: 2,

    GRID_SIZE: 70,

    init: function(){
	DunGen.TILE_NAMES[DG_TILE_BIG_ROOM]	= "BigRoom";
	DunGen.TILE_NAMES[DG_TILE_SMALL_ROOM]	= "SmallRoom";
	DunGen.TILE_NAMES[DG_TILE_HALL]		= "Hall";
	DunGen.TILE_NAMES[DG_TILE_CORNER]	= "Corner";

	DunGen.TILE_NAMES[DG_OVERLAY_STAIRS_DN]	= "StairsDown";
	DunGen.TILE_NAMES[DG_OVERLAY_STAIRS_UP]	= "StairsUp";
	DunGen.TILE_NAMES[DG_OVERLAY_DOOR]	= "Door";

	if (!state.hasOwnProperty('DunGen')){
	    state.DunGen = { 'sparse': true };
	}
	if (!state.DunGen.TILE_URLS){ state.DunGen.TILE_URLS = {}; }
    },

    rotate: function(tile, n){ // n*90 degree clockwise rotation
	return (tile >> n) | ((tile << (4 - n)) & 0xf);
    },

    hFlip: function(tile){ // flip tile horizontally: swap two high bits and two low bits
	return ((tile & 0x5) << 1) | ((tile >> 1) & 0x5);
    },

    vFlip: function(tile){ // flip tile vertically: swap two outer bits and two inner bits
	return ((tile & 0x1) << 3) | ((tile >> 3) & 0x1) | ((tile & 0x2) << 1) | ((tile >> 1) & 0x2);
    },

    connectionCount: function(c){
	return (c & DG_FLAG_U ? 1 : 0) + (c & DG_FLAG_R ? 1 : 0) + (c & DG_FLAG_D ? 1 : 0) + (c & DG_FLAG_L ? 1 : 0);
    },

    directionsFromMasks: function(m){
	return (m & DG_MASK_U ? DG_FLAG_U : 0) | (m & DG_MASK_R ? DG_FLAG_R : 0) | (m & DG_MASK_D ? DG_FLAG_D : 0) | (m & DG_MASK_L ? DG_FLAG_L : 0);
    },

    trimConnections: function(grid, x, y){
	// trim rightwards connections from the square to the left of x,y
	if ((x > 0) && (!grid[x - 1][y].filled) && (grid[x - 1][y].connections & DG_FLAG_R)){
	    // x-1,y connects to end via x,y; remove that connection
	    grid[x - 1][y].connections &= ~DG_FLAG_R;
	    if (DunGen.connectionCount(grid[x - 1][y].connections) <= 1){
		// removal left x-1,y with at most one connection; this may mean that we got cut off from end; recurse
		DunGen.trimConnections(grid, x - 1, y);
	    }
	}
	// trim leftwards connections from the square to the right of x,y
	if ((x < grid.length - 1) && (!grid[x + 1][y].filled) && (grid[x + 1][y].connections & DG_FLAG_L)){
	    // x+1,y connects to end via x,y; remove that connection
	    grid[x + 1][y].connections &= ~DG_FLAG_L;
	    if (DunGen.connectionCount(grid[x + 1][y].connections) <= 1){
		// removal left x+1,y with at most one connection; this may mean that we got cut off from end; recurse
		DunGen.trimConnections(grid, x + 1, y);
	    }
	}
	// trim downwards connections from the square above x,y
	if ((y > 0) && (!grid[x][y - 1].filled) && (grid[x][y - 1].connections & DG_FLAG_D)){
	    // x,y-1 connects to end via x,y; remove that connection
	    grid[x][y - 1].connections &= ~DG_FLAG_D;
	    if (DunGen.connectionCount(grid[x][y - 1].connections) <= 1){
		// removal left x,y-1 with at most one connection; this may mean that we got cut off from end; recurse
		DunGen.trimConnections(grid, x, y - 1);
	    }
	}
	// trim upwards connections from the square below x,y
	if ((y < grid[x].length - 1) && (!grid[x][y + 1].filled) && (grid[x][y + 1].connections & DG_FLAG_U)){
	    // x,y+1 connects to end via x,y; remove that connection
	    grid[x][y + 1].connections &= ~DG_FLAG_U;
	    if (DunGen.connectionCount(grid[x][y + 1].connections) <= 1){
		// removal left x,y+1 with at most one connection; this may mean that we got cut off from end; recurse
		DunGen.trimConnections(grid, x, y + 1);
	    }
	}
    },

    addSquareToFill: function(squaresToFill, grid, x, y, direction){
	if ((x < 0) || (x >= grid.length) || (y < 0) || (y >= grid[x].length) || (grid[x][y].filled)){ return; } // outside of grid or already filled
	for (var i = 0; i < squaresToFill.length; i++){
	    if ((squaresToFill[i][0] == x) && (squaresToFill[i][1] == y)){
		// x,y already marked to be filled; add new required connections
		squaresToFill[i][2] |= (1 << direction);
		return;
	    }
	}
	squaresToFill.push([x, y, (1 << direction)]);
    },

    justPlaceTile: function(workingGrid, finalGrid, squaresToFill, x, y, tile, orientation){
	var conns = DunGen.directionsFromMasks(DunGen.rotate(tile, orientation));
	if (state.DunGen.sparse){ conns &= workingGrid[x][y].connections; }
	workingGrid[x][y].connections = 0;
	workingGrid[x][y].filled = 1;
	finalGrid[x][y].tile = tile;
	finalGrid[x][y].orientation = orientation;
	return conns;
    },

    placeTile: function(workingGrid, finalGrid, squaresToFill, x, y, tile, orientation){
	var conns = DunGen.justPlaceTile(workingGrid, finalGrid, squaresToFill, x, y, tile, orientation);
	DunGen.trimConnections(workingGrid, x, y);
	if (conns & DG_FLAG_L){ DunGen.addSquareToFill(squaresToFill, workingGrid, x - 1, y, DG_DIRECTION_R); }
	if (conns & DG_FLAG_R){ DunGen.addSquareToFill(squaresToFill, workingGrid, x + 1, y, DG_DIRECTION_L); }
	if (conns & DG_FLAG_U){ DunGen.addSquareToFill(squaresToFill, workingGrid, x, y - 1, DG_DIRECTION_D); }
	if (conns & DG_FLAG_D){ DunGen.addSquareToFill(squaresToFill, workingGrid, x, y + 1, DG_DIRECTION_U); }
    },

    candidateValid: function(workingGrid, finalGrid, x, y, tile, orientation, requiredDirections, possibleConns){
	var tileConns = DunGen.rotate(tile, orientation);
	var hFlippedTile = DunGen.hFlip(tileConns);
	var vFlippedTile = DunGen.vFlip(tileConns);

	// verify candidate tile satisfies all of requiredDirections
	if (requiredDirections & (1 << DG_DIRECTION_L)){
	    if (!(hFlippedTile & DunGen.rotate(finalGrid[x - 1][y].tile, finalGrid[x - 1][y].orientation) & DG_MASK_R)){ return 0; }
	}
	if (requiredDirections & (1 << DG_DIRECTION_R)){
	    if (!(hFlippedTile & DunGen.rotate(finalGrid[x + 1][y].tile, finalGrid[x + 1][y].orientation) & DG_MASK_L)){ return 0; }
	}
	if (requiredDirections & (1 << DG_DIRECTION_U)){
	    if (!(vFlippedTile & DunGen.rotate(finalGrid[x][y - 1].tile, finalGrid[x][y - 1].orientation) & DG_MASK_D)){ return 0; }
	}
	if (requiredDirections & (1 << DG_DIRECTION_D)){
	    if (!(vFlippedTile & DunGen.rotate(finalGrid[x][y + 1].tile, finalGrid[x][y + 1].orientation) & DG_MASK_U)){ return 0; }
	}

	if (!possibleConns){ return 1; } // no outbound paths necessary

	// verify candidate tile satisfies at least one of possibleConns
	if ((possibleConns & (1 << DG_DIRECTION_U)) && (tileConns & DG_MASK_U)){ return 1; }
	if ((possibleConns & (1 << DG_DIRECTION_R)) && (tileConns & DG_MASK_R)){ return 1; }
	if ((possibleConns & (1 << DG_DIRECTION_D)) && (tileConns & DG_MASK_D)){ return 1; }
	if ((possibleConns & (1 << DG_DIRECTION_L)) && (tileConns & DG_MASK_L)){ return 1; }

	// candidate tile does not satisfy any outbound path
	return 0;
    },

    fillSquare: function(workingGrid, finalGrid, squaresToFill, x, y, directions, connected){
	var conns = 0;

	if (!connected){
	    // determine if any direction connects directly to end
	    if ((x > 0) && (finalGrid[x - 1][y].end)){
		directions |= DG_FLAG_L;
		connected = 1;
	    }
	    if ((x < finalGrid.length - 1) && (finalGrid[x + 1][y].end)){
		directions |= DG_FLAG_R;
		connected = 1;
	    }
	    if ((y > 0) && (finalGrid[x][y - 1].end)){
		directions |= DG_FLAG_U;
		connected = 1;
	    }
	    if ((y < finalGrid[x].length - 1) && (finalGrid[x][y + 1].end)){
		directions |= DG_FLAG_D;
		connected = 1;
	    }
	}

	if (!connected){
	    // determine which directions potentially connect to end
	    if ((x > 0) && (!workingGrid[x - 1][y].filled) && (workingGrid[x - 1][y].connections)){ conns |= DG_FLAG_L; }
	    if ((x < workingGrid.length - 1) && (!workingGrid[x + 1][y].filled) && (workingGrid[x + 1][y].connections)){ conns |= DG_FLAG_R; }
	    if ((y > 0) && (!workingGrid[x][y - 1].filled) && (workingGrid[x][y - 1].connections)){ conns |= DG_FLAG_U; }
	    if ((y > workingGrid[x].length - 1) && (!workingGrid[x][y + 1].filled) && (workingGrid[x][y + 1].connections)){ conns |= DG_FLAG_D; }

	    // connection only strictly required if we can't make it through some other square
	    for (var i = 0; i < squaresToFill.length; i++){
		if (workingGrid[squaresToFill[i][0]][squaresToFill[i][1]].connections){
		    conns = 0;
		    break;
		}
	    }
	}

	// determine which tiles could fulfill all our obligations
	var candidates = [];
	for (var i = 0; i < DunGen.ALL_TILES.length; i++){
	    for (var j = 0; j < DunGen.ALL_DIRECTIONS.length; j++){
		if (DunGen.candidateValid(workingGrid, finalGrid, x, y, DunGen.ALL_TILES[i], DunGen.ALL_DIRECTIONS[j], directions, conns)){
		    candidates.push([DunGen.ALL_TILES[i], DunGen.ALL_DIRECTIONS[j]]);
		}
	    }
	}
	//choose tiles which connect in all directions
	if (candidates.length <= 0){
	    candidates.push([DG_TILE_BIG_ROOM, 0]);
	}

	// randomly select a candidate tile and place it
	var tileIndex = randomInteger(candidates.length) - 1;
	DunGen.placeTile(workingGrid, finalGrid, squaresToFill, x, y, candidates[tileIndex][0], candidates[tileIndex][1]);

	return connected;
    },

    generateMap: function(w, h){
	var grid = [];
	var retval = [];
	var squaresToFill = [];
	var startPoint = [];
	var endPoint = [];

	// initialize working and result grids
	for (var i = 0; i < w; i++){
	    grid[i] = [];
	    retval[i] = [];
	    for (var j = 0; j < h; j++){
		var conns = 0;
		if (i > 0){ conns |= DG_FLAG_L; }
		if (i < w - 1){ conns |= DG_FLAG_R; }
		if (j > 0){ conns |= DG_FLAG_U; }
		if (j < h - 1){ conns |= DG_FLAG_D; }
		grid[i][j] = {'connections': conns, 'filled': 0};
		retval[i][j] = {};
	    }
	}

	// place endpoints
	var startPoint = [randomInteger(w) - 1, randomInteger(h) - 1];
	DunGen.placeTile(grid, retval, squaresToFill, startPoint[0], startPoint[1], DG_TILE_BIG_ROOM, 0);
	retval[startPoint[0]][startPoint[1]].start = 1;
	var endPoint = [randomInteger(w) - 1, randomInteger(h) - 1];
	while ((endPoint[0] == startPoint[0]) && (endPoint[1] == startPoint[1])){
	    // make sure end point isn't same as start point (guaranteed possible because we aborted above if total map area was one or fewer squares)
	    endPoint = [randomInteger(w) - 1, randomInteger(h) - 1];
	}
	DunGen.justPlaceTile(grid, retval, squaresToFill, endPoint[0], endPoint[1], DG_TILE_BIG_ROOM, 0);
	retval[endPoint[0]][endPoint[1]].end = 1;

	// fill the rest of the squares
	var connected = 0;
	while (squaresToFill.length > 0){
	    var square = squaresToFill.shift();
	    connected = DunGen.fillSquare(grid, retval, squaresToFill, square[0], square[1], square[2], connected);
	}

	return retval;
    },

    showHelp: function(cmd){
	sendChat("DunGen", cmd + " WIDTH HEIGHT [TILE SIZE]");
	sendChat("DunGen", "Generate a WIDTHxHEIGHT dungeon from square tiles of the specified size (in pixels)");
	sendChat("DunGen", "TILE SIZE defaults to " + DunGen.TILE_SIZE + "; it should generally be a multiple of " + DunGen.GRID_SIZE);
	sendChat("DunGen", cmd + " sparse [on|off]");
	sendChat("DunGen", "Display or set status of sparse map generation");
	sendChat("DunGen", "If sparse is on, no tiles will be added to paths which cannot connect to the exit");
	sendChat("DunGen", cmd + " setimage TILE_NAME");
	sendChat("DunGen", "Use selected token's image for the specified tile");
    },

    mapConns: function(map, x, y){
	return DunGen.rotate(map[x][y].tile, map[x][y].orientation);
    },

    handleChatMessage: function(msg){
	if ((msg.type != "api") || (msg.content.indexOf("!dungen ") != 0)){ return; }

	var tokens = msg.content.split(" ");
	if ((tokens.length < 2) || (tokens[1] == "help")){ return DunGen.showHelp(tokens[0]); }

	if (tokens[1] == "sparse"){
	    if (tokens.length > 2){
		// set sparse status
		if ((tokens[2] == "on") || (tokens[2] == "yes") || (tokens[2] == "true") || (tokens[2] == "1")){ state.DunGen.sparse = true; }
		else{ state.DunGen.sparse = false; }
	    }
	    // show sparse status
	    sendChat("DunGen", "Sparse Map Generation: " + (state.DunGen.sparse ? "on" : "off"));
	    return;
	}

	if (tokens.length < 3){ return DunGen.showHelp(tokens[0]); }

	if (tokens[1] == "setimage"){
	    if ((!msg.selected) || (msg.selected.length != 1) || (msg.selected[0]._type != "graphic")){
		sendChat("DunGen", "Error: setimage requires exactly one selected token");<commit_msg>Add "tiles" command to make it more obvious what each tile is supposed to be<commit_after>DG_CONNECTION_UL = 1<<3;
DG_CONNECTION_UR = 1<<2;
DG_CONNECTION_DR = 1<<1;
DG_CONNECTION_DL = 1<<0;

DG_MASK_U = DG_CONNECTION_UL | DG_CONNECTION_UR;
DG_MASK_R = DG_CONNECTION_UR | DG_CONNECTION_DR;
DG_MASK_D = DG_CONNECTION_DR | DG_CONNECTION_DL;
DG_MASK_L = DG_CONNECTION_DL | DG_CONNECTION_UL;

DG_DIRECTION_U = 0;
DG_DIRECTION_R = 1;
DG_DIRECTION_D = 2;
DG_DIRECTION_L = 3;

DG_FLAG_U = 1 << DG_DIRECTION_U;
DG_FLAG_R = 1 << DG_DIRECTION_R;
DG_FLAG_D = 1 << DG_DIRECTION_D;
DG_FLAG_L = 1 << DG_DIRECTION_L;

DG_TILE_BIG_ROOM	= DG_CONNECTION_UL | DG_CONNECTION_UR | DG_CONNECTION_DR | DG_CONNECTION_DL;
DG_TILE_SMALL_ROOM	= DG_CONNECTION_UL;
DG_TILE_HALL		= DG_CONNECTION_UL | DG_CONNECTION_DL;
DG_TILE_CORNER		= DG_CONNECTION_UR | DG_CONNECTION_DR | DG_CONNECTION_DL;

DG_OVERLAY_STAIRS_DN = "overlay_stairsdown";
DG_OVERLAY_STAIRS_UP = "overlay_stairsup";
DG_OVERLAY_DOOR = "overlay_door"

var DunGen = DunGen || {
    ALL_DIRECTIONS: [DG_DIRECTION_U, DG_DIRECTION_R, DG_DIRECTION_D, DG_DIRECTION_L],
    ALL_TILES: [DG_TILE_BIG_ROOM, DG_TILE_SMALL_ROOM, DG_TILE_HALL, DG_TILE_CORNER],
    ALL_IMAGES: [DG_TILE_BIG_ROOM, DG_TILE_SMALL_ROOM, DG_TILE_HALL, DG_TILE_CORNER,
		    DG_OVERLAY_STAIRS_DN, DG_OVERLAY_STAIRS_UP, DG_OVERLAY_DOOR],

    TILE_NAMES: {},
    TILE_DESCS: {},

    TILE_SIZE: 980,

    DOOR_TILE_WIDTH: 350,
    DOOR_TILE_HEIGHT: 140,
    DOOR_OFFSET: 210,
    DOOR_WIDTH: 140,

    MIN_LINE_WIDTH: 2,

    GRID_SIZE: 70,

    init: function(){
	DunGen.TILE_NAMES[DG_TILE_BIG_ROOM]	= "BigRoom";
	DunGen.TILE_NAMES[DG_TILE_SMALL_ROOM]	= "SmallRoom";
	DunGen.TILE_NAMES[DG_TILE_HALL]		= "Hall";
	DunGen.TILE_NAMES[DG_TILE_CORNER]	= "Corner";

	DunGen.TILE_NAMES[DG_OVERLAY_STAIRS_DN]	= "StairsDown";
	DunGen.TILE_NAMES[DG_OVERLAY_STAIRS_UP]	= "StairsUp";
	DunGen.TILE_NAMES[DG_OVERLAY_DOOR]	= "Door";

	DunGen.TILE_DESCS[DG_TILE_BIG_ROOM]	= "Room which spans full tile";
	DunGen.TILE_DESCS[DG_TILE_SMALL_ROOM]	= "Room in upper-left quarter of tile";
	DunGen.TILE_DESCS[DG_TILE_HALL]		= "Hallway which spans left half of tile";
	DunGen.TILE_DESCS[DG_TILE_CORNER]	= "Hallway corner which spans right and bottom three-quarters of tile";

	DunGen.TILE_DESCS[DG_OVERLAY_STAIRS_DN]	= "Full-tile sized overlay which includes stairs down from end room";
	DunGen.TILE_DESCS[DG_OVERLAY_STAIRS_UP]	= "Full-tile sized overlay which includes stairs up from start room";
	DunGen.TILE_DESCS[DG_OVERLAY_DOOR]	= "Reduced-size overlay which contains a door (possibly embedded in a wall)";

	if (!state.hasOwnProperty('DunGen')){
	    state.DunGen = { 'sparse': true };
	}
	if (!state.DunGen.TILE_URLS){ state.DunGen.TILE_URLS = {}; }
    },

    rotate: function(tile, n){ // n*90 degree clockwise rotation
	return (tile >> n) | ((tile << (4 - n)) & 0xf);
    },

    hFlip: function(tile){ // flip tile horizontally: swap two high bits and two low bits
	return ((tile & 0x5) << 1) | ((tile >> 1) & 0x5);
    },

    vFlip: function(tile){ // flip tile vertically: swap two outer bits and two inner bits
	return ((tile & 0x1) << 3) | ((tile >> 3) & 0x1) | ((tile & 0x2) << 1) | ((tile >> 1) & 0x2);
    },

    connectionCount: function(c){
	return (c & DG_FLAG_U ? 1 : 0) + (c & DG_FLAG_R ? 1 : 0) + (c & DG_FLAG_D ? 1 : 0) + (c & DG_FLAG_L ? 1 : 0);
    },

    directionsFromMasks: function(m){
	return (m & DG_MASK_U ? DG_FLAG_U : 0) | (m & DG_MASK_R ? DG_FLAG_R : 0) | (m & DG_MASK_D ? DG_FLAG_D : 0) | (m & DG_MASK_L ? DG_FLAG_L : 0);
    },

    trimConnections: function(grid, x, y){
	// trim rightwards connections from the square to the left of x,y
	if ((x > 0) && (!grid[x - 1][y].filled) && (grid[x - 1][y].connections & DG_FLAG_R)){
	    // x-1,y connects to end via x,y; remove that connection
	    grid[x - 1][y].connections &= ~DG_FLAG_R;
	    if (DunGen.connectionCount(grid[x - 1][y].connections) <= 1){
		// removal left x-1,y with at most one connection; this may mean that we got cut off from end; recurse
		DunGen.trimConnections(grid, x - 1, y);
	    }
	}
	// trim leftwards connections from the square to the right of x,y
	if ((x < grid.length - 1) && (!grid[x + 1][y].filled) && (grid[x + 1][y].connections & DG_FLAG_L)){
	    // x+1,y connects to end via x,y; remove that connection
	    grid[x + 1][y].connections &= ~DG_FLAG_L;
	    if (DunGen.connectionCount(grid[x + 1][y].connections) <= 1){
		// removal left x+1,y with at most one connection; this may mean that we got cut off from end; recurse
		DunGen.trimConnections(grid, x + 1, y);
	    }
	}
	// trim downwards connections from the square above x,y
	if ((y > 0) && (!grid[x][y - 1].filled) && (grid[x][y - 1].connections & DG_FLAG_D)){
	    // x,y-1 connects to end via x,y; remove that connection
	    grid[x][y - 1].connections &= ~DG_FLAG_D;
	    if (DunGen.connectionCount(grid[x][y - 1].connections) <= 1){
		// removal left x,y-1 with at most one connection; this may mean that we got cut off from end; recurse
		DunGen.trimConnections(grid, x, y - 1);
	    }
	}
	// trim upwards connections from the square below x,y
	if ((y < grid[x].length - 1) && (!grid[x][y + 1].filled) && (grid[x][y + 1].connections & DG_FLAG_U)){
	    // x,y+1 connects to end via x,y; remove that connection
	    grid[x][y + 1].connections &= ~DG_FLAG_U;
	    if (DunGen.connectionCount(grid[x][y + 1].connections) <= 1){
		// removal left x,y+1 with at most one connection; this may mean that we got cut off from end; recurse
		DunGen.trimConnections(grid, x, y + 1);
	    }
	}
    },

    addSquareToFill: function(squaresToFill, grid, x, y, direction){
	if ((x < 0) || (x >= grid.length) || (y < 0) || (y >= grid[x].length) || (grid[x][y].filled)){ return; } // outside of grid or already filled
	for (var i = 0; i < squaresToFill.length; i++){
	    if ((squaresToFill[i][0] == x) && (squaresToFill[i][1] == y)){
		// x,y already marked to be filled; add new required connections
		squaresToFill[i][2] |= (1 << direction);
		return;
	    }
	}
	squaresToFill.push([x, y, (1 << direction)]);
    },

    justPlaceTile: function(workingGrid, finalGrid, squaresToFill, x, y, tile, orientation){
	var conns = DunGen.directionsFromMasks(DunGen.rotate(tile, orientation));
	if (state.DunGen.sparse){ conns &= workingGrid[x][y].connections; }
	workingGrid[x][y].connections = 0;
	workingGrid[x][y].filled = 1;
	finalGrid[x][y].tile = tile;
	finalGrid[x][y].orientation = orientation;
	return conns;
    },

    placeTile: function(workingGrid, finalGrid, squaresToFill, x, y, tile, orientation){
	var conns = DunGen.justPlaceTile(workingGrid, finalGrid, squaresToFill, x, y, tile, orientation);
	DunGen.trimConnections(workingGrid, x, y);
	if (conns & DG_FLAG_L){ DunGen.addSquareToFill(squaresToFill, workingGrid, x - 1, y, DG_DIRECTION_R); }
	if (conns & DG_FLAG_R){ DunGen.addSquareToFill(squaresToFill, workingGrid, x + 1, y, DG_DIRECTION_L); }
	if (conns & DG_FLAG_U){ DunGen.addSquareToFill(squaresToFill, workingGrid, x, y - 1, DG_DIRECTION_D); }
	if (conns & DG_FLAG_D){ DunGen.addSquareToFill(squaresToFill, workingGrid, x, y + 1, DG_DIRECTION_U); }
    },

    candidateValid: function(workingGrid, finalGrid, x, y, tile, orientation, requiredDirections, possibleConns){
	var tileConns = DunGen.rotate(tile, orientation);
	var hFlippedTile = DunGen.hFlip(tileConns);
	var vFlippedTile = DunGen.vFlip(tileConns);

	// verify candidate tile satisfies all of requiredDirections
	if (requiredDirections & (1 << DG_DIRECTION_L)){
	    if (!(hFlippedTile & DunGen.rotate(finalGrid[x - 1][y].tile, finalGrid[x - 1][y].orientation) & DG_MASK_R)){ return 0; }
	}
	if (requiredDirections & (1 << DG_DIRECTION_R)){
	    if (!(hFlippedTile & DunGen.rotate(finalGrid[x + 1][y].tile, finalGrid[x + 1][y].orientation) & DG_MASK_L)){ return 0; }
	}
	if (requiredDirections & (1 << DG_DIRECTION_U)){
	    if (!(vFlippedTile & DunGen.rotate(finalGrid[x][y - 1].tile, finalGrid[x][y - 1].orientation) & DG_MASK_D)){ return 0; }
	}
	if (requiredDirections & (1 << DG_DIRECTION_D)){
	    if (!(vFlippedTile & DunGen.rotate(finalGrid[x][y + 1].tile, finalGrid[x][y + 1].orientation) & DG_MASK_U)){ return 0; }
	}

	if (!possibleConns){ return 1; } // no outbound paths necessary

	// verify candidate tile satisfies at least one of possibleConns
	if ((possibleConns & (1 << DG_DIRECTION_U)) && (tileConns & DG_MASK_U)){ return 1; }
	if ((possibleConns & (1 << DG_DIRECTION_R)) && (tileConns & DG_MASK_R)){ return 1; }
	if ((possibleConns & (1 << DG_DIRECTION_D)) && (tileConns & DG_MASK_D)){ return 1; }
	if ((possibleConns & (1 << DG_DIRECTION_L)) && (tileConns & DG_MASK_L)){ return 1; }

	// candidate tile does not satisfy any outbound path
	return 0;
    },

    fillSquare: function(workingGrid, finalGrid, squaresToFill, x, y, directions, connected){
	var conns = 0;

	if (!connected){
	    // determine if any direction connects directly to end
	    if ((x > 0) && (finalGrid[x - 1][y].end)){
		directions |= DG_FLAG_L;
		connected = 1;
	    }
	    if ((x < finalGrid.length - 1) && (finalGrid[x + 1][y].end)){
		directions |= DG_FLAG_R;
		connected = 1;
	    }
	    if ((y > 0) && (finalGrid[x][y - 1].end)){
		directions |= DG_FLAG_U;
		connected = 1;
	    }
	    if ((y < finalGrid[x].length - 1) && (finalGrid[x][y + 1].end)){
		directions |= DG_FLAG_D;
		connected = 1;
	    }
	}

	if (!connected){
	    // determine which directions potentially connect to end
	    if ((x > 0) && (!workingGrid[x - 1][y].filled) && (workingGrid[x - 1][y].connections)){ conns |= DG_FLAG_L; }
	    if ((x < workingGrid.length - 1) && (!workingGrid[x + 1][y].filled) && (workingGrid[x + 1][y].connections)){ conns |= DG_FLAG_R; }
	    if ((y > 0) && (!workingGrid[x][y - 1].filled) && (workingGrid[x][y - 1].connections)){ conns |= DG_FLAG_U; }
	    if ((y > workingGrid[x].length - 1) && (!workingGrid[x][y + 1].filled) && (workingGrid[x][y + 1].connections)){ conns |= DG_FLAG_D; }

	    // connection only strictly required if we can't make it through some other square
	    for (var i = 0; i < squaresToFill.length; i++){
		if (workingGrid[squaresToFill[i][0]][squaresToFill[i][1]].connections){
		    conns = 0;
		    break;
		}
	    }
	}

	// determine which tiles could fulfill all our obligations
	var candidates = [];
	for (var i = 0; i < DunGen.ALL_TILES.length; i++){
	    for (var j = 0; j < DunGen.ALL_DIRECTIONS.length; j++){
		if (DunGen.candidateValid(workingGrid, finalGrid, x, y, DunGen.ALL_TILES[i], DunGen.ALL_DIRECTIONS[j], directions, conns)){
		    candidates.push([DunGen.ALL_TILES[i], DunGen.ALL_DIRECTIONS[j]]);
		}
	    }
	}
	//choose tiles which connect in all directions
	if (candidates.length <= 0){
	    candidates.push([DG_TILE_BIG_ROOM, 0]);
	}

	// randomly select a candidate tile and place it
	var tileIndex = randomInteger(candidates.length) - 1;
	DunGen.placeTile(workingGrid, finalGrid, squaresToFill, x, y, candidates[tileIndex][0], candidates[tileIndex][1]);

	return connected;
    },

    generateMap: function(w, h){
	var grid = [];
	var retval = [];
	var squaresToFill = [];
	var startPoint = [];
	var endPoint = [];

	// initialize working and result grids
	for (var i = 0; i < w; i++){
	    grid[i] = [];
	    retval[i] = [];
	    for (var j = 0; j < h; j++){
		var conns = 0;
		if (i > 0){ conns |= DG_FLAG_L; }
		if (i < w - 1){ conns |= DG_FLAG_R; }
		if (j > 0){ conns |= DG_FLAG_U; }
		if (j < h - 1){ conns |= DG_FLAG_D; }
		grid[i][j] = {'connections': conns, 'filled': 0};
		retval[i][j] = {};
	    }
	}

	// place endpoints
	var startPoint = [randomInteger(w) - 1, randomInteger(h) - 1];
	DunGen.placeTile(grid, retval, squaresToFill, startPoint[0], startPoint[1], DG_TILE_BIG_ROOM, 0);
	retval[startPoint[0]][startPoint[1]].start = 1;
	var endPoint = [randomInteger(w) - 1, randomInteger(h) - 1];
	while ((endPoint[0] == startPoint[0]) && (endPoint[1] == startPoint[1])){
	    // make sure end point isn't same as start point (guaranteed possible because we aborted above if total map area was one or fewer squares)
	    endPoint = [randomInteger(w) - 1, randomInteger(h) - 1];
	}
	DunGen.justPlaceTile(grid, retval, squaresToFill, endPoint[0], endPoint[1], DG_TILE_BIG_ROOM, 0);
	retval[endPoint[0]][endPoint[1]].end = 1;

	// fill the rest of the squares
	var connected = 0;
	while (squaresToFill.length > 0){
	    var square = squaresToFill.shift();
	    connected = DunGen.fillSquare(grid, retval, squaresToFill, square[0], square[1], square[2], connected);
	}

	return retval;
    },

    showHelp: function(cmd){
	sendChat("DunGen", cmd + " WIDTH HEIGHT [TILE SIZE]");
	sendChat("DunGen", "Generate a WIDTHxHEIGHT dungeon from square tiles of the specified size (in pixels)");
	sendChat("DunGen", "TILE SIZE defaults to " + DunGen.TILE_SIZE + "; it should generally be a multiple of " + DunGen.GRID_SIZE);
	sendChat("DunGen", cmd + " sparse [on|off]");
	sendChat("DunGen", "Display or set status of sparse map generation");
	sendChat("DunGen", "If sparse is on, no tiles will be added to paths which cannot connect to the exit");
	sendChat("DunGen", cmd + " setimage TILE_NAME");
	sendChat("DunGen", "Use selected token's image for the specified tile");
	sendChat("DunGen", cmd + " tiles");
	sendChat("DunGen", "Show list of tiles, their sizes, and a description of each");
    },

    mapConns: function(map, x, y){
	return DunGen.rotate(map[x][y].tile, map[x][y].orientation);
    },

    handleChatMessage: function(msg){
	if ((msg.type != "api") || (msg.content.indexOf("!dungen ") != 0)){ return; }

	var tokens = msg.content.split(" ");
	if ((tokens.length < 2) || (tokens[1] == "help")){ return DunGen.showHelp(tokens[0]); }

	if (tokens[1] == "sparse"){
	    if (tokens.length > 2){
		// set sparse status
		if ((tokens[2] == "on") || (tokens[2] == "yes") || (tokens[2] == "true") || (tokens[2] == "1")){ state.DunGen.sparse = true; }
		else{ state.DunGen.sparse = false; }
	    }
	    // show sparse status
	    sendChat("DunGen", "Sparse Map Generation: " + (state.DunGen.sparse ? "on" : "off"));
	    return;
	}

	if (tokens[1] == "tiles"){
	    function showTileDesc(tile, sizeStr){
		sendChat("DunGen", "<b>" + DunGen.TILE_NAMES[tile] + "</b> " + sizeStr + ":");
		sendChat("DunGen", DunGen.TILE_DESCS[tile]);
	    }
	    var tileSize = "(" + DunGen.TILE_SIZE + " x " + DunGen.TILE_SIZE + ")";
	    for (var i = 0; i < DunGen.ALL_TILES.length; i++){
		showTileDesc(DunGen.ALL_TILES[i], tileSize);
	    }
	    showTileDesc(DG_OVERLAY_STAIRS_DN, tileSize);
	    showTileDesc(DG_OVERLAY_STAIRS_UP, tileSize);
	    showTileDesc(DG_OVERLAY_DOOR, "(" + DunGen.DOOR_TILE_WIDTH + " x " + DunGen.DOOR_TILE_HEIGHT + ")");
	    return;
	}

	if (tokens.length < 3){ return DunGen.showHelp(tokens[0]); }

	if (tokens[1] == "setimage"){
	    if ((!msg.selected) || (msg.selected.length != 1) || (msg.selected[0]._type != "graphic")){
		sendChat("DunGen", "Error: setimage requires exactly one selected token");
{'fraction_non_alphanumeric': 0.1602738275874237, 'fraction_numerical': 0.016373195949045485, 'mean_word_length': 4.033747779751332, 'pattern_counts': {'":': 1, '<': 138, '<?xml version=': 0, '>': 47, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2512718', 'n_tokens_mistral': 11790, 'n_tokens_neox': 10588, 'n_words': 2609}