Typically, I have used pre-generated templates to determine the overall structure of the level, to ensure that the level or dungeon holds to a certain specification. However, for some dungeons I have gotten good results with an accretion-growth algorithm similar to the circle-based particle accretion I described in an earlier article I wrote about generating fractal cave systems. With a modification to use rectangular boxes instead of circular particles, the layouts generated have the feel of a series of connected rooms. Here are a few example layouts this type of generator can construct:
The algorithm lends itself well to customization and constraint. Of course, it still leaves one with the difficult task of parsing the generated layout and determining section patterns, connection patterns, etc... Still, it gives you a jumping-off point. Here is the Lua file I used with the accidental noise binary to generate the samples:
function random_point(boxlist) -- First, choose a box if #boxlist==0 then return end local whichbox=boxlist[randRange(1,#boxlist)] local x1=whichbox[1] local y1=whichbox[2] local x2=x1+whichbox[3] local y2=y1+whichbox[4] local dx=x2-x1 local dy=y2-y1 return randRange(0,dx-1)+x1, randRange(0,dy-1)+y1endfunction add_box(boxtable, box) local x1=box[1] local y1=box[2] local x2=x1+box[3] local y2=y1+box[3] if x1 if x1>boxtable.maxx then boxtable.maxx=x1 end if x2 if x2>boxtable.maxx then boxtable.maxx=x2 end if y1 if y1>boxtable.maxy then boxtable.maxy=y1 end if y2 if y2>boxtable.maxy then boxtable.maxy=y2 end table.insert(boxtable.boxlist, box)endfunction test_box(boxlist, box) -- Test a box for intersection with any box in the list -- Can do a brain-dead test, since boxes are guaranteed to not intersect at first, and move 1 unit at a time local bx1=box[1] local by1=box[2] local bx2=bx1+box[3] local by2=by1+box[4] for i=1,#boxlist,1 do local t=boxlist local tx1=t[1] local ty1=t[2] local tx2=tx1+t[3] local ty2=ty1+t[4] if bx1tx1 and by1ty1 then return true end if bx2tx1 and by1ty1 then return true end if bx1tx1 and by2ty1 then return true end if bx2tx1 and by2ty1 then return true end if tx1bx1 and ty1by1 then return true end if tx2bx1 and ty1by1 then return true end if tx1bx1 and ty2by1 then return true end if tx2bx1 and ty2by1 then return true end end return falseendfunction find_min_y_on_x(boxlist, x) -- Find the minimum y value of every box for which x lies between x1 and x2 if #boxlist==0 then return nil end local min_y=0 for i=1,#boxlist,1 do box=boxlist x1=box[1] y1=box[2] x2=x1+box[3] y2=y1+box[4] if x>x1 and x -- x lies within the box, test y1 against miny if y1 end end return min_yendfunction find_max_y_on_x(boxlist, x) if #boxlist==0 then return nil end local max_y=0 for i=1,#boxlist,1 do box=boxlist x1=box[1] y1=box[2] x2=x1+box[3] y2=y1+box[4] if x>x1 and x if y2>max_y then max_y=y2 end end end return max_yendfunction find_min_x_on_y(boxlist, y) if #boxlist==0 then return nil end local min_x=0 for i=1,#boxlist,1 do box=boxlist x1=box[1] y1=box[2] x2=x1+box[3] y2=y1+box[4] if y>y1 and y if x1 end end return min_xendfunction find_max_x_on_y(boxlist, y) if #boxlist==0 then return nil end local max_x=0 for i=1,#boxlist,1 do box=boxlist x1=box[1] y1=box[2] x2=x1+box[3] y2=y1+box[4] if y>y1 and y if x2>max_x then max_x=x2 end end end return max_xend function do_box(boxtable, minwidth, maxwidth, minheight, maxheight, dir) -- First, create a box outside range local bwidth=randRange(minwidth, maxwidth) local bheight=randRange(minheight, maxheight) -- Now, choose a point to align with local cx,cy=random_point(boxtable.boxlist) local x1,y1,x2,y2 if dir==1 then -- Do a box above. -- Find x1, x2 and find minimum y's for those. Use the smallest value x1=cx-bwidth/2 x2=cx+bwidth/2 cy1=find_min_y_on_x(boxtable.boxlist, x1) cy2=find_min_y_on_x(boxtable.boxlist, x2) if cy1 else y1=cy2-bheight end elseif dir==2 then -- Do a box below -- Find x1, x2 and find maximum y's for those. Use the largest value x1=cx-bwidth/2 x2=cx+bwidth/2 cy1=find_max_y_on_x(boxtable.boxlist, x1) cy2=find_max_y_on_x(boxtable.boxlist, x2) if cy1>cy2 then y1=cy1 else y1=cy2 end elseif dir==3 then -- Do a box to the left -- Find y1, y2 and find min x's for those. Use smallest value y1=cy-bheight/2 y2=cy+bheight/2 cx1=find_min_x_on_y(boxtable.boxlist, y1) cx2=find_min_x_on_y(boxtable.boxlist, y2) if cx1else x1=cx2-bwidth end else -- Do a box to the right -- Find y1,y2 and find max x's for those. Use largest value y1=cy-bheight/2 y2=cy+bheight/2 cx1=find_max_x_on_y(boxtable.boxlist, y1) cx2=find_max_x_on_y(boxtable.boxlist, y2) if cx1>cx2 then x1=cx1 else x1=cx2 end end -- Now, add the box local box={} box[1]=x1 box[2]=y1 box[3]=bwidth box[4]=bheight add_box(boxtable, box) endfunction first_box(boxtable, minwidth, maxwidth, minheight, maxheight) local bw,bh=randRange(minwidth,maxwidth), randRange(minheight,maxheight) local box={} box[1]=-bw/2 box[2]=-bh/2 box[3]=bw box[4]=bh add_box(boxtable, box)endfunction draw_box(box, buffer, tx, ty) local x1,y1,x2,y2=box[1]+tx,box[2]+ty,box[1]+box[3]+tx, box[2]+box[4]+ty for x=x1,x2,1 do buffer:set(x,y1,1.0) buffer:set(x,y2,1.0) end for y=y1,y2,1 do buffer:set(x1,y,1.0) buffer:set(x2,y,1.0) end for x=x1+1, x2-1, 1 do for y=y1+1, y2-1, 1 do buffer:set(x,y,0.5) end end endfunction draw_box_list(boxtable, buffer) local tx=-boxtable.minx local ty=-boxtable.miny local w=(boxtable.maxx-boxtable.minx)+1 local h=(boxtable.maxy-boxtable.miny)+2 buffer:init(w,h) for i=1,#boxtable.boxlist,1 do draw_box(boxtable.boxlist, buffer, tx, ty) endendfunction new_table() local tbl={} tbl.boxlist={} tbl.minx,tbl.maxx,tbl.miny,tbl.maxy=0,0,0,0 return tblend---------------------------------------------b=CArray2Dd()bt=new_table()first_box(bt, 10,60,10,60)for i=1,20,1 do do_box(bt,10,60,10,60,randRange(1,4)) enddraw_box_list(bt,b)saveBufferToTGA(b,"boxlist.tga")The algorithm works by first creating an initial seed box, then iteratively adding boxes to the structure. To add a box it generates a random point within an existing box, then generates a random direction. 1=top, 2=bottom, 3=left, 4=right It adds the box to the structure in the determined direction, by calculating the furthest-out edge with which the box can connect.
By setting constraints on how rooms are dimensioned and positioned, the structure can be more tightly controlled. For instance, in the examples rooms can be any size from 10x10 to 60x60. However, if rooms are constrained to be, for example, multiples of 5 (ie 15x15, 25x30, etc) then it is more likely that room edges will line up and loops will be formed. Also, some constraints can be added upon selecting the random seed point for adding subsequent boxes. For instance, picking only the centers of existing boxes to start from can ensure greater overlap of added boxes.
