function box_intersect(box1, box2) local ax1,ay1,ax2,ay2=box1[1],box1[2],box1[1]+box1[3],box1[2]+box1[4] local bx1,by1,bx2,by2=box2[1],box2[2],box2[1]+box2[3],box2[2]+box2[4] -- Disallow single-corner intersections if bx1==ax2 and by1==ay2 then return false end if bx2==ax1 and by1==ay2 then return false end if bx2==ax1 and by2==ay1 then return false end if bx1==ax2 and by2==ay1 then return false end if bx1<=ax2 and bx2>=ax1 and by1<=ay2 and by2>=ay1 then return true else return false endendfunction group_intersect(group1, group2) local i,j for i=1,#group1.boxlist,1 do local b1=group1.boxlist for j=1,#group2.boxlist,1 do local b2=group2.boxlist[j] if box_intersect(b1, b2)==true then return true end end end return falseendfunction calc_bounding_box(group) local i minx,miny=100000, 100000 maxx,maxy=-100000, -100000 for i=1,#group.boxlist,1 do local box=group.boxlist if box[1]1] end if box[2]2] end if box[1]+box[3]>maxx then maxx=box[1]+box[3] end if box[2]+box[4]>maxy then maxy=box[2]+box[4] end end group.minx,group.miny,group.maxx,group.maxy=minx,miny,maxx,maxy group.cx=minx+((maxx-minx)/2) group.cy=miny+((maxy-miny)/2)endfunction merge_group(group1, group2) local i for i=1,#group2.boxlist,1 do table.insert(group1.boxlist, group2.boxlist) end calc_bounding_box(group1)endfunction translate_group(group, xinc, yinc) local i for i=1,#group.boxlist,1 do local box=group.boxlist box[1]=box[1]+xinc box[2]=box[2]+yinc end calc_bounding_box(group)endfunction calc_grouplist_bounding_box(grouplist) -- Calculate bounding box and local center of a list of groups local i local minx,miny,maxx,maxy=100000,100000,-100000,-100000 for i=1,#grouplist.groups,1 do local group=grouplist.groups if group.minx if group.maxx>maxx then maxx=group.maxx end if group.miny if group.maxy>maxy then maxy=group.maxy end end grouplist.minx, grouplist.miny, grouplist.maxx, grouplist.maxy=minx,miny,maxx,maxy grouplist.cx=minx+((maxx-minx)/2) grouplist.cy=minx+((maxy-miny)/2)endfunction intersect_groups(grouplist, group) -- Test all groups in grouplist for intersection with group, and merge, then repop grouplist local holdlist={} for i=1,#grouplist.groups,1 do local thisgroup=table.remove(grouplist.groups) if group_intersect(group, thisgroup) then -- Groups intersect, merge into group merge_group(group, thisgroup) else table.insert(holdlist, thisgroup) end end -- Intersected groups should now be in group, repopulate grouplist with the holdlist for i=1,#holdlist,1 do table.insert(grouplist.groups, holdlist) end table.insert(grouplist.groups, 1, group) calc_grouplist_bounding_box(grouplist)endfunction move_group(grouplist, group, dir) -- Move the given group 1 unit in the given direction, test for intersections with other groups, and merge local xinc, yinc=0,0 if dir==1 then xinc,yinc=0,-1 elseif dir==2 then xinc,yinc=0,1 elseif dir==3 then xinc,yinc=-1,0 else xinc,yinc=1,0 end translate_group(group, xinc, yinc) intersect_groups(grouplist, group)endfunction move_one_group(grouplist) local group=table.remove(grouplist.groups) local cx,cy=group.cx,group.cy local dir if math.abs(cx)>math.abs(cy) then -- Horizontal direction if cx<0 then dir=4 else dir=3 end else if cy<0 then dir=2 else dir=1 end end move_group(grouplist, group, dir)end function move_all_groups(grouplist) local i local holdlist={} while #grouplist.groups > 1 do move_one_group(grouplist) endendfunction new_group(box) -- Create a group from a box local group={} group.boxlist={} table.insert(group.boxlist, box) calc_bounding_box(group) return groupendfunction new_grouplist() -- Create a new grouplist local grouplist={} grouplist.groups={} grouplist.minx,grouplist.maxx,grouplist.miny,grouplist.maxy=0,0,0,0 grouplist.cx,grouplist.cy=0,0 return grouplistendfunction add_group(grouplist, group) table.insert(grouplist.groups, group) calc_grouplist_bounding_box(grouplist)endfunction swap_elements(whichlist, a, b) local temp=whichlist[a] whichlist[a]=whichlist whichlist=tempendfunction shuffle_list(whichlist) for i=1,#whichlist,1 do local a=randRange(1,#whichlist) swap_elements(whichlist, i, a) endendfunction seed_boxes(grouplist, numx, numy, minwidth, maxwidth, minheight, maxheight, startx, starty) -- Seed a grouplist with groups. -- Each group is a single box. Boxes are placed in rows and columns, spaced by maxwidth/maxheight local holdlist={} local x,y for x=0,numx-1,1 do for y=0,numy-1,1 do local bx,by = startx+x*(maxwidth+3), starty+y*(maxheight+3) local bw,bh=randRange(minwidth,maxwidth), randRange(minheight, maxheight) local group=new_group({bx,by,bw,bh}) table.insert(holdlist, group) end end shuffle_list(holdlist) for i=1,#holdlist,1 do add_group(grouplist, holdlist) end end function draw_box(box, buffer, tx, ty, v) 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,v) 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 local v=i while v>20 do v=v-20 end v=v/20 draw_box(boxtable.boxlist, buffer, tx, ty,v) endendfunction draw_group(group, tx, ty, buffer) for i=1,#group.boxlist,1 do draw_box(group.boxlist, buffer, tx, ty, 0.5) endendfunction draw_grouplist(grouplist, buffer) local tx=-grouplist.minx local ty=-grouplist.miny local w=(grouplist.maxx-grouplist.minx)+2 local h=(grouplist.maxy-grouplist.miny)+2 buffer:init(w,h) for i=1,#grouplist.groups,1 do draw_group(grouplist.groups, tx, ty, buffer) end buffer:set(tx,ty,0.6)endThe script is executed in the Accidental Noise Library Lua interpreter, then groups of boxes can be made and collapsed:
gl=new_grouplist()-- Seed boxes-- Parameters are: grouplist, number_of_boxes_wide, number_of_boxes_high, minwidth, maxwidth, minheight, maxheight, starting_x, starting_yseed_boxes(gl, 10, 10 10, 60, 10, 60, -300, -300)-- Collapse all the boxes inwardmove_all_groups(gl)b=CArray2Dd()draw_grouplist(gl,b)saveBufferToTGA(b,"grouplist.tga")The code functions by splitting the collection of boxes into groups. Initially when the grouplist is seeded with boxes, each box is a separate group. The function move_all_groups iteratively selects a group to move, and translates it toward the center along either the X or the Y axis, depending on whether it is further from the center along the X axis or the Y axis. It moves the group 1 unit at a time, then tests for intersection with all other groups in the list. Any groups it intersects with are removed from the main list and merged into the current group. The intersection test ignores intersection cases where only 1 corner of each box intersects, to prevent degenerate intersections that would not result in a shared edge between two boxes. This sort of layout depends on boxes sharing edges, so that doorways or passages between box sections may be generated later in the process.
The algorithm continues selecting groups and moving them inward toward (0,0) until there is only 1 group left, at which point it exits and the layout is done.
Here is a sample seeded grouplist:
and here is the same group collapsed inward until intersection:
As can be seen, there isn't as much tendency for the layout to develop 'tentacles'; the layout tends to be more compact, and fit more into the shape of the original seeded array.
Of course the algorithm as presented could use some tuning, but there are again a few ways to tweak it's behavior. The initial shape of the starting array has an effect on the shape of the final version. Here is a layout that begins wide:
and collapsed:
Once you have the layout, you can analyze the intersections to produce a graph of edge info, showing which boxes connect with which other boxes, where their shared edges are, etc... Then types for each section can be assigned, and the final sections with connection and type data can be passed to the next level of refinement for room generation.
Procedural level generation is one of those topics that never loses its interest. Anyone can whip up a simple dungeon, but interesting levels are much more difficult to produce. Not because you need complex algorithms, but because you need genuinely creative algorithms. This is one of those cases ;)
I suggest you drop this description in the RGRD group at http://groups.google.com/group/rec.games.roguelike.development/topics , the folks there would be very interested. Despite the crudeness of the ASCII displays used by most roguelikes, there is a strong emphasis on dungeon generation and discussions on this topic are common.