如何查找未连接的房间组？
How to find unconnected room groups?
在建造地牢生成器的过程中，您需要解决几个涉及未连接房间的问题，我找不到最后一个找到的解决方案：
我可以很容易地检测到未连接的房间，但是当涉及到未连接的房间组时，我不知道该怎么做。
这是发生了什么的图片...
如果您查看右上角，您可能会看到一组未连接的房间，我需要检测所有未连接的房间组并将其连接到其余房间。
系统
它的工作方式非常简单，有一个包含所有图块对象及其属性的数组。要更改内容，我只需要访问数组中的对象。
地下城生成：
- 创建所有类型为地板（灰色块）的图块。
- 放置不重叠且彼此之间的最小距离为 1 格的随机房间。
- 在所有房间周围放置墙壁。
- 将墙壁放置在与房间墙壁至少 1 格的地块上。
- 将空方块放置在距离墙壁 1 格的墙方块上。
地图图例
白色 = 房间方块
灰色 = 积木 ||走廊街区
黑色块，灰色边框 = 墙块
棕色||红色 = 门积木
全黑 = 空方块
使用洪水填充解决分组房间问题。有很多洪水填充算法，所以选择适合您的算法。
然后用一种颜色填充一个房间，所有相连的房间也将被填充。然后扫描找到空房间，继续直到没有更多空房间。您将获得已连接房间组的列表。每组一个，或隔离房间一个。
使用位图泛洪填充查找分组房间的示例。单击以重做房间。同一组的房间颜色相同。数组 groupRooms 包含房间组。数组rooms是所有的房间，map是用来绘制房间的位图，floodFill floodFill函数找到的是相连的房间。
警告有许多 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);
我为这个问题创建了一个解决方案。这是一个简单的函数，使用类似洪水填充的方法。
工作原理：
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.
直到所有合适的方块都被制成 "detected tile"。
函数如下：
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" = 是数组中的瓦片位置。
- 方块类型和方块变体 = 使方块不同，在
在这种情况下，我唯一不想检测的图块是 "gray"，它是
输入“1”。
- "getTile" function = 获取具有以下方向的附近图块 >> function getTile(direction, id, distanceX, distanceY)
感谢 Blindman67 的洪水填充想法，它帮助我制定了这个答案。
在建造地牢生成器的过程中，您需要解决几个涉及未连接房间的问题，我找不到最后一个找到的解决方案：
我可以很容易地检测到未连接的房间，但是当涉及到未连接的房间组时，我不知道该怎么做。
这是发生了什么的图片...
系统
它的工作方式非常简单，有一个包含所有图块对象及其属性的数组。要更改内容，我只需要访问数组中的对象。
地下城生成：
- 创建所有类型为地板（灰色块）的图块。
- 放置不重叠且彼此之间的最小距离为 1 格的随机房间。
- 在所有房间周围放置墙壁。
- 将墙壁放置在与房间墙壁至少 1 格的地块上。
- 将空方块放置在距离墙壁 1 格的墙方块上。
地图图例
白色 = 房间方块
灰色 = 积木 ||走廊街区
黑色块，灰色边框 = 墙块
棕色||红色 = 门积木
全黑 = 空方块
使用洪水填充解决分组房间问题。有很多洪水填充算法，所以选择适合您的算法。
然后用一种颜色填充一个房间，所有相连的房间也将被填充。然后扫描找到空房间，继续直到没有更多空房间。您将获得已连接房间组的列表。每组一个，或隔离房间一个。
使用位图泛洪填充查找分组房间的示例。单击以重做房间。同一组的房间颜色相同。数组 groupRooms 包含房间组。数组rooms是所有的房间，map是用来绘制房间的位图，floodFill floodFill函数找到的是相连的房间。
警告有许多 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);
我为这个问题创建了一个解决方案。这是一个简单的函数，使用类似洪水填充的方法。
工作原理：
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.
直到所有合适的方块都被制成 "detected tile"。
函数如下：
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" = 是数组中的瓦片位置。
- 方块类型和方块变体 = 使方块不同，在 在这种情况下，我唯一不想检测的图块是 "gray"，它是 输入“1”。
- "getTile" function = 获取具有以下方向的附近图块 >> function getTile(direction, id, distanceX, distanceY)
感谢 Blindman67 的洪水填充想法，它帮助我制定了这个答案。