Room Generation Algorithm Help

I would like to have a system that randomly generates rooms (for something like a house that you only see the inside of). Something that would look like this from a top-down view:

Example 1
357a9b867a8b37c4a8eae49c8e76bc12db6c5608.png

Example 2
999a135dba217a16f97ceebfaa001a248c9491b5.png

Either example would work for me. I spent a large portion of today trying out different ways of generating random rooms, but I could not come up with anything that worked the way I would have liked it to. It would be cool if it could be set up in a Spelunky-esque way where you can make different rooms and the generator will randomly pick five different rooms and put them together. (That’s why I’ve been trying to make).

Any nudges in the right direction would be greatly appreciated.

Thanks,

  • Alex.

Both methods could use a Binary Space Partitioning algorithm. This one has code to translate into blueprints.

There is a training stream by Ian Shadden that comes with test materials that you should check out as well.

How exactly would someone turn those splits and branches into the dungeons & variables for that 1st method?

You could either do it procedurally or create a large set of “puzzle piece” rooms of different sizes, check the size of the partitioned space and select an appropriately sized room to spawn into that area.

But how would you store the locations & sizes of the rooms? How would you get those into variables?

Think about it in terms of objects.

If your binary tree is building “rooms” you can store whatever data you want about a particular “room” when it gets generated and placed in the tree.

Think about the structure of a binary tree, or at least research it a bit, the links provided in a post above are quite useful.

The leafs of the tree at the bottom of the structure will be your final iteration on the tree, thus the final “version” of the generated dungeon. If you use objects to represent your rooms, upon generation you can store perhaps the width and height of the room within the object thats held in the tree.

I very well understand the logic behind it, just not how someone would implement this into blueprints :\

Just woke up and see all these replies. Thanks everybody, I will have a mess around and see what I can achieve. :slight_smile:

I wrote a quick BP based on the algorithm explained herein. It only includes the portion to for building BSP. I’ll post it as soon as I work out the bugs.
I created a box structure that contains 4 Vectors: Start, Stop, (Size, Center for future extension). For 2D, I only use the X,Y values.

Building the BSP

  1. I start with a Box that is the maximum size and store into a array. For this example the its 9x9

https://arcadekomodo.com/home/wp-content/uploads/2015/07/bsp1.png

  1. I then split into two sub-boxes by doing the following operation:
  • a. Randomly select split direction : horizontal or vertical psuedocode: switch(rnd(1)){case 0:horizontal;case 1: vertical}
    For this example, its a Vertical Split
  • b. Randomly select a position between start and stop (X for vertical, Y for horizontal)
  • c. Calculate the new box dimensions, splitting into two sub-boxes.

Vertical Split Math below:

https://arcadekomodo.com/home/wp-content/uploads/2015/07/bsp2.png

Now we have two sub-boxs Left (A) and Right (B). Add to to BSP Tree.

  1. I then repeat the operation (Step 2) on the all the boxes in the array for a specified number of iterations.

Horizontal Split Math below:

https://arcadekomodo.com/home/wp-content/uploads/2015/07/bsp3.png

Thats it,

Additional random factors could be applied to the boxes in the array to not be split. Once this generates the boxes, you can then use the dimensions of the boxes to add/remove walls actors, etc.

At the end of the day doing this only results in an Array with the final layout which is what you probably intended. Though building a Binary Tree properly has its uses, you may want to perform operations on different levels of the tree after its generated the rooms.

Well done on the explanation of the algorithm though.

Scrap that part. I ran into issues: a infinite loop. I’m now implementing a Tree data structure per this tutorial. I’ll update that section when I get it finished.

https://arcadekomodo.com/home/wp-content/uploads/2015/07/Screenshot-2015-07-09-04.54.24-150x150.pnghttps://arcadekomodo.com/home/wp-content/uploads/2015/07/Screenshot-2015-07-09-04.59.00-150x150.pnghttps://arcadekomodo.com/home/wp-content/uploads/2015/07/Screenshot-2015-07-09-05.02.25-150x150.png
**BSP Room Generator [SIZE=1](2D,Exploded,Multi Color View Modes)
**[SIZE=2]Just Add the BSPGenerator Actor to the Level and presto![/SIZE]](https://arcadekomodo.com/home/wp-content/uploads/2015/07/Screenshot-2015-07-09-05.04.17.png)[/SIZE]
Blueprints DOWNLOAD BSPGenerator.zip (181k)

I will have to take a look at it when I get home, but thank you in advance.

Wow, very cool stuff, thank you for that.
:slight_smile: