"What you can do manually in 5 hours, a developer can automate in 3 weeks." -- Ancient computation proverb

In Build-a-Wizard, you build furniture. But most furniture lives inside houses, not outside. So it's wise to create houses in which furniture can live, so the levels make more sense.

Try and keep up.

The thing is I find it more satisfying to have code do my job for me than me doing any work at all. Except working by coding code which does my work. It makes sense if you've spend years in the tech industry.

I'm building a new demo for Build a Wizard and want to make it bigger and with more gameplay with the last without dying in the process. Thus, this tool!

Quick note, all this code is written for Unreal Engine 5, but I'll attempt to describe the algorithm only.

The requirements

I want to easily create a big amount of levels for a mobile game. Part of this can be done with a house generator. By that, I mean being able to give a few inputs to a function and have it return a handful of meshes in the shape of a building. 

It's okay for it to be generic, as I can dress it later with accessories and atrezzo. I also don't need to generate any game logic, such as level select. By doing this, I can potentially reuse the plugin for other projects.

Inputs and outputs

To have a house, first we need a way to store the data that describes it.

I decided to use graphs. It's a big part of discrete mathematics but for this project, here's what I care about: graphs are vertices (dots) connected with other vertices through edges (lines). In other words, I can structure finite chunks of data and also how they correlate to each other, if at all. In this, case, my vertices will be the room and the data it contains (mostly what type of room it is) and the edges will represent how 2 rooms connect (wall, doored wall, or no connections if they're not neighbors).

There are many ways  I implemented a quick'n'dirty graph structure for Unreal 5, as well as a display made of Draw Debug Point and lines. I also added a text component that billboards towards the camera.

Next, I had to decide what inputs would change the house. If I added no inputs, whatever function I wrote would either always return the same house or return a random one. Randomizing is good, but if I have no control over it, I won't be able to reproduce it again if I lose it.

To make randomization reproducible, I added a random seed to the house. Again, lots of background behind it, but what it means for me: by passing a constant integer into a Random Stream, I can use such stream in other randomizer functions and consistently get the same random results (as long as I call them in the same order every time). It's random -- but reproducible.

This input would be enough to create random houses; but I want a bit more control over its creation. For instance, I would like to control the size of the house while still giving the function some freedom of randomization. To that end, I specified a handful of house size adjectives with an attached window. The window determines the minimum and maximum expected number of rooms for a house of that size.

An added advantage to having an adjective system is that it reduces the amount of choice I have. And, usually, when designing a level, I won't care about the exact number of rooms -- using a more abstract "Small" adjective then playing with the random seed will be plenty enough.

I listed the adjectives with an enum, then implemented the windows with Data Tables. For this project, I understand data tables as static rows of data that can be imported + exported via CSV (so easy to edit in another program such as Excel). They are fast to read and a great way to centralize variable relationships. An RPG shop inventory would probably be stored here instead of in a blueprint.

I've got a randomized, and I can control a house's size, but not so much the content. There exists many rooms with just as many purposes that a house can have in real life. In Build A Wizard this will directly affect which furniture should logically appear in every room.

Given that my house sizes can get up to 30, and the purpose of this is to remove work and tedium from my job, I don't want to describe dozens of rooms every time I am creating a level. I've decided to copy the adjective system for room sizes and apply it to a house's description.

In other words: have a list of adjectives that would describe a house (first takes priority, then second, then...). Then, create a list of rooms (kitchen, bedroom, cellar...). Finally, relate the two concepts. The question I want to answer is: how much does this room contribute to a hous e described with that adjective?

The relation is written in weights. This one's simpler: bigger number means a stronger correlation. In my case, i don't even need to normalize them -- we'll see why later.

With the inputs described, what are the outputs I desire? Honestly, just a bunch of static meshes (3D models) placed nicely and orderly. 

Choosing the rooms

But to do that I require creating a graph from the inputs, then representing that graph in a 2D plane (houses are usually built on the ground), and then using the vertices' positions to add the meshes.

So let's do the first step (in high level pseudo code); how to turn the inputs and data tables into rooms (graph vertices)?

Inputs:
house_size_adjective
house_adjectives
seeded_random_stream # assume this is used very time a randomizer function is called. I won't write it every time
 
Outputs:
room_list
 
Data tables loaded:
room_size_table
room_description_table
 
Algorithm
room_sizes_window = get house_size_adjective value in room_size_table
number_of_rooms = get a random number between the min and max of room_sizes_window
room_adjectives_weight = [] #empty list relating adjective - accumulated house weight
while the room_list.size < number_of_rooms:
    for every adjective in house_adjectives at position_x: #ordered
        if adjective first in room_adjectives_weight is not in position_x:
            # the first adjective should be first in the weight accumulator.
            # if not, add a room to help improve that
            new_room = choose_weighted_random_room(adjective, room_adjectives_weight)
            room_list.add(new_room)
            room_adjectives_weight.add(all weights of new room) # not just the current adjective weight!
            room_adjectives_weight.reorder_by_weight_desc() # first adjective will be the one with
                # more weight
            break the for loop #only one room can be added. If lower adjectives were also in the
                # wrong positions, disregard them. Higher adjectives are prioritary
    if no room was added in the previous for loop: # this can happen if the weights are equal, or
        # if this is the first time a room is added
        room_list.add(purely_random_room())

This algorithm takes advantage of the adjectives being ordered. This was a design choice: to me, describing a house that is spacious and hygienic is different than describing a room that is hygienic and spacious (first adjective is more important if I put it first).

There are 2 gotchas in this code I feel deserve explaining:

room_adjectives_weight.add(all weights of new room) # not just the current adjective weight!

This may mean that a competing adjective also gets added weight and keeps the house imbalanced by adjectives! Yes, indeed! This algorithm will try its best to approximate the house rooms to the adjective description, but it may not always succeed; that is okay. Adjectives are just guidelines.

new_room = choose_weighted_random_room(adjective, room_adjectives_weight)

The what with the random weights? choose_weighted_random_room is a graceful way to combine random and influence. The point of weights is to have a room be more important to a certain adjective than other rooms. But if I always chose the room with the most weight for an adjective, the algorithm would output the same house every time.

To randomize the creation a bit, I use the weighted random selection algorithm. In short: add all the weights, and select a random number between 0 and that maximum. Every room will have a % chance of being chosen equivalent to its weight. So if one room has double the weight than the other, it will have twice the chance to be chosen. But, it is not guaranteed!

Creating floors and walls

The rooms are created. Now how do we distribute them in a 3D space to create the actual model?

This part I admit is still a bit under development, but works well enough for now. I want to create floors that are dependant on the room time, as well as have interior walls and walls with door holes, and other house structures. But this is an algorithm that creates a good enough feel for the buildings for the demo I'm currently creating.

Inputs:
room_list
seeded_random_stream # assume this is used very time a randomizer function is called. I won't write it every time
floor_mesh # floor 3D model, established as a house property
wall_mesh
 
Outputs:
floor_meshes
wall_meshes
 
Algorithm
room_size # constant for now
floor_transforms = [] # transforms is position, rotation, scale
outer_wall_transforms = []
 
number_of_rows, number_of_columns = get_random_window(square_root(room_list.size)) # this makes the 
    # house as rectangular as possible, with some leeway in the form of a window
 
for row_index = from 0 to number_of_rows:
    for column_index = from 0 to number_of_columns:
        new_room_position = position(x=column_index*room_size, y=row_index*room_size, z=0)
        floor_transforms.add(new_room_position)
        if the room is in the first column: outer_wall_transforms.add(left_wall_transform + new_room_position) #add the room position because it needs to be relative to the room
        if the room is in the first row: outer_wall_transforms.add(upper_wall_transform + new_room_position)
        if the room is in the last column or is the last of its row: outer_wall_transforms.add(right_wall_transform + new_room_position)
        if the room is in the last row or is the last of its column: outer_wall_transforms.add(lower_wall_transform + new_room_position)
 
for every transform in floor_transforms:
    floor_meshes.add(floor_mesh, transform)
for every transform in wall_transforms:
    wall_meshes.add(wall_mesh, transform)

This assumes that we want the squarest house possible with no fancy shapes like tetrominoes. There is also no difference between floor types to differentiate the actual rooms nor interior walls; all of these are part of future improvement

The meshes of each house I added as part of an Instanced Static Mesh Component, since they will always probably be all on the mobile screen at the same time.

The results

And with this, I now have a little algorithm that can create a town way quicker! Here's a sketch of a Frontier home which is defending a small road from the wilds out there:

Smaller quality of life notes

While developing, I added a simple UI with which to change the parameters of a specific house at runtime to see how it'd change.

I later discovered you can control parameters at runtime more easily with a Remote Control Web Application without having to create a whole widget. I may use that in the future!

You can make a function Call In Editor so that you can call it while editing (duh). It supports Data Tables pretty well as I understand. Just make sure whatever you're executing doesn't need access to runtime data! (anything that needs construction))

Future improvements

As it is, this is good enough for me for now. I can easily place and generate houses with a couple of clicks instead of 20 minutes of environment design. I can now focus on a new demo and improving the actual game loop.

However, there are multiple improvements to make the houses more realistic, or, at least, provide more level variety

Using a treemap. Multiple approaches (such as this one by Maysam Mirahmadi, Abdallah Shami or this one by Johan Melin, Daniel Bengtsson) suggest using Treemapping to divide a plane in multiple, size varied rooms.

Update weights. The adjective weight table was set by me at the beginning, and can be edited manually. However, I could implement an Approve + Reject system. If a house fits the description given (as judged by a human), then the rooms involved will gain weight to those adjectives, thus biasing the algorithm towards the opinions of the user. The challenge is how to easily update the data in a data table, as it is static at runtime, and Unreal Engine 5 doesn't have a file system like the one Node.js does, as far as I know.

Use room names to add furniture packs. Probably the most ambitious one; by the name of the room, randomly generate a set of buildable furniture and place it sensibly on the room (chairs should go around a table, paintings should go on the wall). It will probably be the finickiest as it involves actual gameplay and balancing a house to not be either too crowded or too empty. But done well, I can generate a big amount of levels easily.