Как найти несвязанные группы номеров?

В процессе создания генератора подземелий вам нужно решить несколько проблем, связанных с несоединенными комнатами, и я не могу найти решение последней найденной мной проблемы:

Я могу легко обнаружить несвязанные комнаты, но когда дело доходит до групп несвязанных комнат, я понятия не имею, что делать.

Вот картина того, что происходит...

введите здесь описание изображения Если вы посмотрите в верхний правый угол, вы увидите несоединенную группу комнат, мне нужно обнаружить и соединить все несоединенные группы комнат с остальными.< /сильный>


Система

Это работает очень просто: есть массив, содержащий все объекты плитки и их свойства. Чтобы что-то изменить, мне просто нужно получить доступ к объектам внутри массива.

Генерация подземелья:

  1. Создайте все плитки типа пола (серые блоки).
  2. Разместите случайные комнаты, которые не перекрываются и находятся на расстоянии не менее 1 плитки друг от друга.
  3. Поместите стены вокруг всех комнат.
  4. Размещайте стены на напольных блоках на расстоянии не менее 1 клетки от стен комнаты.
  5. Размещайте пустые блоки на стеновых блоках на расстоянии 1 клетки от стен. <час>

Легенда карты

Белый = комнатные блоки

Серый = блоки пола || коридорные блоки

Черный блок, серая рамка = настенные блоки

Браун || красный = дверные блоки

Полностью черный = пустые блоки


person Timerºº    schedule 04.07.2016    source источник


Ответы (2)


Используйте заливку заливкой, чтобы решить проблему сгруппированных комнат. Существует множество алгоритмов заливки, поэтому выберите тот, который вам подходит.

Затем заполните комнату цветом, и все смежные комнаты также будут заполнены. Затем сканируйте, чтобы найти пустые комнаты, продолжайте, пока пустых комнат не останется. Вы получите список подключенных групп комнат. По одному на каждую группу или изолированную комнату.

Пример использования растровой заливки для поиска сгруппированных комнат. Нажмите, чтобы переделать комнаты. Номера одной группы имеют одинаковый цвет. Массив groupRooms содержит группы комнат. Массив rooms — это все комнаты, map — это растровое изображение, используемое для рисования комнат и флудфилл. Функция флудфилл находит соединенные комнаты.

ПРЕДУПРЕЖДЕНИЕ существует множество циклов while, которые полагаются на правильное выполнение для выхода, если условия выхода не выполняются, код заблокирует страницу. Если вы не уверены, добавьте счетчики в циклы и добавьте условие выхода, если счетчик становится большим. Полностью безопасен как есть (ну, есть крошечный шанс, что он будет работать миллиард лет, но если это произойдет, я использую те же самые шансы, чтобы квантово туннелировать исправление для вас).

/** 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);

person Blindman67    schedule 04.07.2016
comment
Спасибо за идею заливки. Я отдал вам должное в своем ответе. - person Timerºº; 13.07.2016

Я создал решение проблемы. Это простая функция, использующая метод заливки.

Как это работает:

Функция сначала определяет, относится ли текущая плитка к указанному типу, если да, она превращает ее в «обнаруженную плитку», затем ищет подходящие плитки вокруг нее, если подходящая плитка найдена, она снова запускает функцию на ней.

Это происходит до тех пор, пока все подходящие плитки не превратятся в «обнаруженную плитку».


Вот функция:

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);
        }
    }
}

Объяснение скрытых данных

  • "id" = позиция плитки внутри массива.
  • Тип плитки и вариант блока = Сделано, чтобы различать плитки, в этом случае единственная плитка, которую я не хочу обнаруживать, это «серая», это тип «1».
  • Функция "getTile" = Получить соседнюю плитку со следующими направлениями >> function getTile(direction, id, DistanceX, DistanceY)

Спасибо Blindman67 за идею заливки, это помогло мне сформулировать этот ответ.

person Timerºº    schedule 13.07.2016