next »

[vittorioromeo]

Hello, it's been a long time since my last post, but I've been lurking the community every day.

My next project is a "Tower of the Sorcerer" / "DROD RPG" like game, but with randomly generated items, monsters and levels.

I'm trying to create an algorithm which generates rooms to completely fill a 20x20 dungeon.

Here's what I've accomplished so far.



That works perfectly fine.

When I want to create a new room, there is a big chance it will be created overlapping the pre-existing one.

I want my algorithm to automatically understand where a room can be made without making it overlap any other pre-existing room.

The algorithm should find a good starting point, a width and an height for the room, then create it.

And repeat itself until there is no more space for other rooms.



I'm not sure how to make the algorithm work.

Should I make it randomly select a free tile then create the biggest possible room?
Should I make it build a room with random width/height then find a place to create it in the grid?
Or is there any other easier or better approach?



Thanks for your time.


Can someone help me with the algorithm? I don't know how it should work.

[nikki]

this post on here somewhere has got everything you want!

[hagel]

I'd suggest this thread.

[vittorioromeo]

Thanks for the replies. The first thread is very interesting. I've also used the second thread some months ago and succedeed creating some procedural generated dungeons/caves.

However what I want to do here is fill a 20x20 square completely with rectangular rooms.

[muku]

However what I want to do here is fill a 20x20 square completely with rectangular rooms.

In that case, maybe a subdivision algorithm would be suitable? Start by considering the whole 20x20 grid as one large room. Then, iteratively, choose the largest room (or maybe randomize a bit here) and put a wall randomly somewhere into it, splitting the room into two smaller ones. Repeat to satisfaction.

[vittorioromeo]

However what I want to do here is fill a 20x20 square completely with rectangular rooms.

In that case, maybe a subdivision algorithm would be suitable? Start by considering the whole 20x20 grid as one large room. Then, iteratively, choose the largest room (or maybe randomize a bit here) and put a wall randomly somewhere into it, splitting the room into two smaller ones. Repeat to satisfaction.

That sounds good, but I still want to keep the "Range" setup I posted in the OP. After I finish subdividing a room, do I need an algorithm to find all the "small" rooms, or can I somehow do that during the subdivision?

What I mean is that I still want each room to be a separate entity. I need that for item/enemy placement and also other reasons.

[nikki]

After your algorithm finishes generating this '20x20 world map' you can do everything you can imagine to it, including making entities out of the rooms (rectangles with id's) and put them on a list.. for example.

I don't get all those range-variables, could you enlighten me ?
(as i see it you only need 4 points, since were only talking rectangles at the moment)

for the room layouts my first approach would probably be:
 1) take a finite sized map (20 x 20 tiles for example)
 2) have an algorithm check every tile in that map  and place rectangles (in varying sizes) that occupie tiles (that arent occupied already).
 3) be sure there arent any empty tiles left.
 4) draw your map (and give different rooms all colors of the rainbow)


note: this doesn't take coridors, reachability or balancing in account.

[muku]

However what I want to do here is fill a 20x20 square completely with rectangular rooms.

In that case, maybe a subdivision algorithm would be suitable? Start by considering the whole 20x20 grid as one large room. Then, iteratively, choose the largest room (or maybe randomize a bit here) and put a wall randomly somewhere into it, splitting the room into two smaller ones. Repeat to satisfaction.

That sounds good, but I still want to keep the "Range" setup I posted in the OP. After I finish subdividing a room, do I need an algorithm to find all the "small" rooms, or can I somehow do that during the subdivision?

What I mean is that I still want each room to be a separate entity. I need that for item/enemy placement and also other reasons.

I don't quite understand your concerns here to be honest. Just represent each room as a pair of points, (lowerLeft,upperRight), and keep them in a list. At first your list has only one entry. Whenever you split a room, remove it from the list, and instead push two new rooms onto the list. Do you have troubles coming up with an algorithm to split a room in this way? Or are you worried about these "ranges", as you call them? The latter should be very easy to compute in a postprocessing step, just add a fringe of width 1 to every room.