How to find unconnected room groups?

Question

On the process of building a dungeon generator you need to solve several problems involving unconnected rooms, and I can't find a solution for the last one I found:

I can easily detect unconnected rooms, but when it comes to unconnected rooms groups I have no idea of what to do.

Here is a picture of what happens...

If you look at the top-right corner you may see a unconnected group of rooms, I need to detect and connect all the unconnected groups of rooms to the rest.

---

System

The way it works is very simple, there is a array that contain all the tile objects and it's properties. To change stuff I just need to access the objects inside the array.

Dungeon generation:

1. Create all the tiles that are of type floor(gray blocks).
2. Place random rooms that don't overlap and have a minimum distance of 1 tile from each other.
3. Place walls around all the rooms.
4. Place walls on floor blocks with a minimum distance of 1 tile from the room walls.
5. Place empty blocks on wall blocks with a distance of 1 tile from the walls.

   ---

Map legend

White = room blocks

Gray = floor blocks || corridor blocks

Black block, gray border = wall blocks

Brown || red = door blocks

Full black = empty blocks

Answer 1

Use a flood fill to solve the grouped room problem. there are plenty of flood fill algorithms out there so pick one that suits you.

Then fill a room with a colour and all connected rooms will be filled as well. Then scan to find empty rooms, continue until no more empty rooms. You will get a list of connected room groups. One each for every group, or isolated room.

An example of using a bitmap flood fill to find grouped rooms. Click to redo rooms. Rooms of the same group have same colour. The array groupRooms holds groups of rooms. The array rooms is all rooms, map is the bitmap used to draw rooms and floodFill The floodFill function finds the connected rooms.

WARNING there are many while loops that rely on correct execution to exit, if the exit conditions fail the code will block the page. If you are unsure add counters to the loops and add a exit condition if the count goes high. Totally safe as is (well some tiny tiny chance that it will run for a billion years, but if it does I will use those same odds to quantum tunnel a fix to you.)

/** SimpleFullCanvasMouse.js begin **/
const CANVAS_ELEMENT_ID = "canv";
const U = undefined;
var canvas, ctx;
var createCanvas, resizeCanvas;
var L = typeof log === "function" ? log : function(d){ console.log(d); }
createCanvas = function () {
    var c,cs;
    cs = (c = document.createElement("canvas")).style; 
    c.id = CANVAS_ELEMENT_ID;    
    cs.position = "absolute";
    cs.top = cs.left = "0px";
    cs.zIndex = 1000;
    document.body.appendChild(c); 
    return c;
}
resizeCanvas = function () {
    if (canvas === U) { canvas = createCanvas(); }
    canvas.width = window.innerWidth;
    canvas.height = window.innerHeight; 
    ctx = canvas.getContext("2d"); 
    if(demo !== undefined){
        demo();
    }
}


// creates a blank image with 2d context
var createImage=function(w,h){var i=document.createElement("canvas");i.width=w;i.height=h;i.ctx=i.getContext("2d");return i;}


var demo = (function(){
    var rooms = [];
    const MAP_WIDTH = 128;
    const MAP_HEIGHT = 128;
    const MAX_WIDTH = 10;
    const MIN_WIDTHHEIGHT = 4;
    const MAX_HEIGHT = 10;
    const OUTLINE = 1;
    const MAX_SEARCH_COUNT = 150; // how many rooms is determined by the number of room fit search that fail. The greater this number the more rooms. but there is a limit 50 part fills space, 150 a few more 1000 a few more and so on
    const WALL_COLOUR = "BLACK";
    const FLOOR_COLOUR = "#AAA";
    const DOOR_COLOUR = "RED";
    const FILL_LEVEL = 160; // the colour to fill as grey
    const RAND_BELL = function(min,max){return Math.floor(((Math.random() + Math.random() + Math.random()) / 3) * (max - min)) + min;}
    const RAND = function(min,max){return Math.floor(Math.random() * (max - min)) + min;}
    var map;
    var roomGroups;
    function canRoomFit(x,y,w,h){
        var i,len;
        len = rooms.length;
        for(i = 0; i < len; i ++){
            r = rooms[i];
            if(!(r.x + r.w < x || r.x > x + w || r.y + r.h < y || r.y > y + h)) {
               return false;
            }
        }
        return true;
    
    }
    function createRoom(){
        var found = false;
        var x,y,w,h;
        var searchCount = 0;
        while(!found && searchCount < MAX_SEARCH_COUNT){
            
            w = RAND_BELL(MIN_WIDTHHEIGHT, MAX_WIDTH);
            h = RAND_BELL(MIN_WIDTHHEIGHT, MAX_HEIGHT);
            x = RAND(OUTLINE, map.width - (w + OUTLINE));
            y = RAND(OUTLINE, map.height - (h + OUTLINE));
            found = canRoomFit(x,y,w,h);
            searchCount += 1;
        }
        if(found){
            var room = {
                x: x, y : y, w : w, h : h,
                doors : [],
                groupID : 0,
            };
            var perm = w * 2 + h* 2;
            var doorMinSpace = 4;
            while(room.doors.length === 0){ // sometimes doors are not added keep trying untill they are
                var doorAt = 0;
                while(doorAt < perm){
                    doorAt += RAND_BELL(doorMinSpace,7);
                    if(doorAt < w - 1){
                        room.doors.push({x : doorAt, y : 0});
                    }else
                    if(doorAt > w + 1 && doorAt < (w + h)- 1){
                        room.doors.push({x : w-1, y : doorAt-w});
                    }else
                    if(doorAt > w + h + 1 && doorAt < (w + h + w)- 1){
                        room.doors.push({x : doorAt-(w+h), y : h-1});
                    }else
                    if(doorAt > w + h + w + 1 && doorAt < perm - 1){
                        room.doors.push({x : 0, y : doorAt-(w+h+w)});
                    }
                }
                if(doorMinSpace > 0){
                    doorMinSpace -= 1;
                }
            }
            rooms.push(room);
            return true;
        }
        return false;
    }
    function addRooms(){
        var search = true;
        while(search){
            search = createRoom();
         
        }
    }
    function drawRooms(showGroupColour){
        var groups = roomGroups.length + 1;
        var col = function(r){
            return "hsl("+Math.floor((r.groupID / groups)*360)+",100%,50%)"
        };
        var rect = function(r,add,col){
            map.ctx.fillStyle = col;
            map.ctx.fillRect(r.x-add,r.y-add,r.w+add+add,r.h+add+add)
        }
        // draw floors
        rooms.forEach(function(r){
            if(showGroupColour){
                rect(r,OUTLINE,col(r));
            }else{
                rect(r,OUTLINE,FLOOR_COLOUR);
            }
            
        });
        // draw walls
        rooms.forEach(function(r){
            rect(r,0,WALL_COLOUR);
    
        });
        // draw inside floors
        rooms.forEach(function(r){
            if(showGroupColour){
                rect(r,-1,col(r));
            }else{
                rect(r,-1,FLOOR_COLOUR);
            }
        });
        // draw doors
        rooms.forEach(function(r){
            r.doors.forEach(function(d){
                if(showGroupColour){
                    map.ctx.fillStyle = col(r);
                }else{
                    map.ctx.fillStyle = FLOOR_COLOUR;
                    
                }
                map.ctx.fillRect(r.x + d.x,r.y + d.y,1,1)
            });
        });
    
    }
    function floodFill(posX, posY, imgData) {
        var data = imgData.data; // image data to fill;
        var stack = [];          // paint stack to find new pixels to paint
        var lookLeft = false;    // test directions
        var lookRight = false;
        var w = imgData.width;   // width and height
        var h = imgData.height;
        var painted = new Uint8ClampedArray(w*h);  // byte array to mark painted area;
        var dw = w*4; // data width.
        var x = posX;   // just short version of pos because I am lazy
        var y = posY;
        var ind = y * dw + x * 4;  // get the starting pixel index
        var sp = 0; // stack pointer
    
        // function checks a pixel colour passes tollerance, is painted, or out of bounds.
        // if the pixel is over tollerance and not painted set it do reduce anti alising artifacts
        var checkColour = function(x,y){
            if( x<0 || y < 0 || y >=h || x >= w){  // test bounds
                return false;
            }
            var ind = y * dw + x * 4;  // get index of pixel
            if(data[ind] !== 0 && data[ind] !== 255){
                return true;
            }
            return false;
        }
        // set a pixel and flag it as painted;
        var setPixel = function(x,y){
            var ind = y * dw + x * 4;  // get index;
            data[ind] = 255;       // set RGBA
    
        }
        stack.push([x,y]);  // push the first pixel to paint onto the paint stack
            
        while (stack.length) {   // do while pixels on the stack
            var pos = stack.pop();  // get the pixel
            x = pos[0];
            y = pos[1];
            while (checkColour(x,y-1)) {  // finf the bottom most pixel within tollerance;
                y -= 1;
            }
            lookLeft = false;  // set look directions
            lookRight = false; // only look is a pixel left or right was blocked
            while (checkColour(x,y)) { // move up till no more room
                setPixel(x,y);         // set the pixel
                if (checkColour(x - 1,y)) {  // check left is blocked
                    if (!lookLeft) {        
                        stack.push([x - 1, y]);  // push a new area to fill if found
                        lookLeft = true;
                    }
                } else 
                if (lookLeft) {
                    lookLeft = false;
                }
                if (checkColour(x+1,y)) {  // check right is blocked
                    if (!lookRight) {
                        stack.push([x + 1, y]); // push a new area to fill if found
                        lookRight = true;
                    }
                } else 
                if (lookRight) {
                    lookRight = false;
                }
                y += 1;                 // move up one pixel
            }
        }
    }

    function findRoomsConnectedTo(room,mapData){
        var groupID = roomGroups.length + 1;
        floodFill(room.x + 2,room.y + 2,mapData);
        var group = [];
        for(var i = 0; i < rooms.length; i ++){
            var r = rooms[i];
            var ind = (r.x+1) * 4 + (r.y+1) * 4 *  MAP_WIDTH;
            if(mapData.data[ind] === 255){
                r.groupID = groupID;
                group.push(r);
                rooms.splice(i,1)
                i --;
            }
            
        }
        roomGroups.push(group);
    }
    function groupRooms(){
        var mapData = map.ctx.getImageData(0,0,MAP_WIDTH,MAP_HEIGHT);
        while(rooms.length > 0){
            findRoomsConnectedTo(rooms[0],mapData);
        }
    }
    
    function demo(){
        L("Run demo")
        var now = performance.now();
        map = createImage(MAP_WIDTH,MAP_HEIGHT);
        roomGroups = [];
        rooms = [];
        map.ctx.fillRect(0,0,MAP_WIDTH,MAP_HEIGHT)
        addRooms();
        drawRooms();
        var roomTemp = rooms.map(function(r){return r;})
        groupRooms();
        rooms = roomTemp;
        drawRooms(true);
        ctx.clearRect(0,0,canvas.width,canvas.height);
        ctx.imageSmoothingEnabled = false;
        ctx.mozImageSmoothingEnabled = false;
        ctx.drawImage(map,0,0,canvas.width,canvas.height);
        L("Demo complete in "+(performance.now()-now));
    }
    return demo
})();


resizeCanvas(); // create and size canvas
window.addEventListener("resize",resizeCanvas); // add resize event
canvas.addEventListener("click",demo);

Answer 2

I created a solution for the problem. It is a simple function that uses a flood-fill-like method.

How it works:

The function first detects if the current tile is of the type stated, if yes it turns it into a "detected tile", then it searches for suitable tiles around it, if a suitable tile is found it runs the function again on it.

This happens untill all suitable tiles are made into a "detected tile".

---

Here is the function:

function detect(id) {
    if (tiles[id].type == 1) {
        tiles[id].block.variant = 2;
        if ((getTile("up", id, 0, 1).type == 1) && (getTile("up", id, 0, 1).block.variant == 1)) {
            tiles[getTile("up", id, 0, 1).id].block.variant = 2;
            detect(getTile("up", id, 0, 1).id);
        }
        if ((getTile("down", id, 0, 1).type == 1) && (getTile("down", id, 0, 1).block.variant == 1)) {
            tiles[getTile("down", id, 0, 1).id].block.variant = 2;
            detect(getTile("down", id, 0, 1).id);
        }
        if ((getTile("left", id, 1, 0).type == 1) && (getTile("left", id, 1, 0).block.variant == 1)) {
            tiles[getTile("left", id, 1, 0).id].block.variant = 2;
            detect(getTile("left", id, 1, 0).id);
        }
        if ((getTile("right", id, 1, 0).type == 1) && (getTile("right", id, 1, 0).block.variant == 1)) {
            tiles[getTile("right", id, 1, 0).id].block.variant = 2;
            detect(getTile("right", id, 1, 0).id);
        }
    }
}

Explanation of hidden data

• "id" = Is the tile position inside the array.
• Type of tile and the block variant = Made to differ the tiles, in this case the only tile that I wan't to detect is the "gray", it is type "1" .
• "getTile" function = Get a nearby tile with the following directions >> function getTile(direction, id, distanceX, distanceY)

---

Thank you Blindman67 for the flood fill idea, it helped me to formulate this answer.