Opinion on Dungeon Generator

ID:151980
 
Jul 15 2008, 8:58 am
Some people may already know, but I'm working on a random dungeon generator for a project of mine, and so far I've been able to make a several rooms and such randomly on the map, but I'm having a problem that I need a suggestion on how to do it correctly.

Basically the problem is this: When I am creating the rooms, I create..lets say 7 rooms. What happens is that they tend to overlap and kill each other, sometimes I have 3 rooms in 1 room, or very rarely they go all over the place and make a real dungeon with several rooms and such. When they overlap, a tiny bit of the map is really used and they are all clumped together.
I was thinking about making it so that if they bump into each other that the room is remade, but that causes it to possibly loop infinately. For example, if theres no legit space left to actually make a room, it will loop indefinately, or if theres just barely enough space, the actual ability to get that random chance is so rare, that it will never reach it in any amount of time (Or in the 200 or so loop limit).
A suggestion I was thinking about to myself is to create basically Sectors of the map, and use those. If I have like 6 rooms to create, I cut the map into 6ths and allow it to use only the space in those 6ths.
Any other ideas on this? I'm probably going to try to implement the sectors idea later on and see if that helps, but if anyone has any ideas feel free to let me know.
Thanks
~Polantaris.
Jul 15 2008, 12:12 pm
Rogue uses the sector idea to split up the map into 9 parts. You could however just check before making the room to see if you have a good location. Here's a simple algorithm you can work with:

  • 1. Choose a size for the room.
  • 2. Pick a random location and find out if the room can be placed there. Try N times to do this; if no position is found, go to step 4.
  • 3. Place the room. Continue to step 4 if the room count is just right, otherwise return to step 1.
  • 4. Connect the rooms.

    Steps 1-3 look something like this:
var/list/rooms = new
var/nrooms = rand(5, 15)
while(rooms.len < nrooms)
  var/sx = rand(3,10)
  var/sy = rand(3,10)
  for(var/i=0, i<10, ++i)
    var/x0 = rand(1, world.maxx-sx+1)
    var/y0 = rand(1, world.maxy-sy+1)
    var/x1 = x0+sx-1
    var/y1 = y0+sy-1
    var/room/R
    for(R in rooms)
      // look for overlap--require at least 1 turf of space between
      if(R.x1 >= x0-1 && R.x0 <= x1+1 && R.y1 >= y0-1 && R.y0 <= y1+1) break
    if(R) continue
    R = new(x0, y0, x1, y1)
    rooms += R
    break
  if(i >= 10) break


Lummox JR
Jul 16 2008, 7:21 am
In response to Lummox JR
I didn't even think to put a limit on it (silly me XD). That's a good idea, I might do both and see which works better.

Thanks Lummox,
~Polantaris.