canvas - How to find unconnected room groups? -
on process of building dungeon generator need solve several problems involving unconnected rooms, , can't find solution last 1 found:
i can detect unconnected rooms, when comes unconnected rooms groups have no idea of do.
here picture of happens...
if @ top-right corner may see unconnected group of rooms, i need detect , connect unconnected groups of rooms rest.
system
the way works simple, there array contain tile objects , it's properties. change stuff need access objects inside array.
dungeon generation:
- create tiles of type floor(gray blocks).
- place random rooms don't overlap , have minimum distance of 1 tile each other.
- place walls around rooms.
- place walls on floor blocks minimum distance of 1 tile room walls.
- place empty blocks on wall blocks distance of 1 tile 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
use flood fill solve grouped room problem. there plenty of flood fill algorithms out there pick 1 suits you.
then fill room colour , connected rooms filled well. scan find empty rooms, continue until no more empty rooms. list of connected room groups. 1 each every group, or isolated room.
an example of using bitmap flood fill find grouped rooms. click redo rooms. rooms of same group have same colour. array grouprooms holds groups of rooms. array rooms rooms, map bitmap used draw rooms , floodfill floodfill function finds connected rooms.
warning there many while loops rely on correct execution exit, if exit conditions fail code block page. if unsure add counters loops , add exit condition if count goes high. totally safe (well tiny tiny chance run billion years, if use same odds quantum tunnel fix 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 blank image 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 determined number of room fit search fail. greater number more rooms. there limit 50 part fills space, 150 few more 1000 few more , on const wall_colour = "black"; const floor_colour = "#aaa"; const door_colour = "red"; const fill_level = 160; // colour fill 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; < len; ++){ 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){ // doors not added keep trying untill 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 fill; var stack = []; // paint stack find new pixels paint var lookleft = false; // test directions var lookright = false; var w = imgdata.width; // width , height var h = imgdata.height; var painted = new uint8clampedarray(w*h); // byte array mark painted area; var dw = w*4; // data width. var x = posx; // short version of pos because lazy var y = posy; var ind = y * dw + x * 4; // starting pixel index var sp = 0; // stack pointer // function checks pixel colour passes tollerance, painted, or out of bounds. // if pixel on tollerance , not painted set 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; // index of pixel if(data[ind] !== 0 && data[ind] !== 255){ return true; } return false; } // set pixel , flag painted; var setpixel = function(x,y){ var ind = y * dw + x * 4; // index; data[ind] = 255; // set rgba } stack.push([x,y]); // push first pixel paint onto paint stack while (stack.length) { // while pixels on stack var pos = stack.pop(); // pixel x = pos[0]; y = pos[1]; while (checkcolour(x,y-1)) { // finf bottom pixel within tollerance; y -= 1; } lookleft = false; // set directions lookright = false; // pixel left or right blocked while (checkcolour(x,y)) { // move till no more room setpixel(x,y); // set pixel if (checkcolour(x - 1,y)) { // check left blocked if (!lookleft) { stack.push([x - 1, y]); // push new area fill if found lookleft = true; } } else if (lookleft) { lookleft = false; } if (checkcolour(x+1,y)) { // check right blocked if (!lookright) { stack.push([x + 1, y]); // push new area fill if found lookright = true; } } else if (lookright) { lookright = false; } y += 1; // move 1 pixel } } } function findroomsconnectedto(room,mapdata){ var groupid = roomgroups.length + 1; floodfill(room.x + 2,room.y + 2,mapdata); var group = []; for(var = 0; < rooms.length; ++){ 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) --; } } 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 = 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 , size canvas window.addeventlistener("resize",resizecanvas); // add resize event canvas.addeventlistener("click",demo);
Comments
Post a Comment