Learn to Make Procedural Buildings in Houdini Using Wave Function Collapse Algorithm

Introduction

Hello everyone! My name is Jin Jin, a tool and pipeline technical artist. While my day-to-day work doesn't involve Houdini, my fascination with it remains strong. Recently, my attention has been captured by the wave function collapse algorithm, especially in the context of applying it within Houdini for procedural modeling.

I've gathered some insights and experiences that I believe could be valuable to others. In this article, I'd like to share what I've learned and the progress I've made with those who are curious about this intriguing algorithm and its applications.

Overview

Procedural modeling has the potential to drastically improve the efficiency of artists in creating environments such as buildings, cityscapes, and natural landscapes. While working on a personal project using procedural modeling, I explored using the Wave Function Collapse algorithm to generate a variety of these types of buildings. This article aims to describe how to utilize the wave function collapse algorithm to create procedural buildings in Houdini and how to export HDA files to Unreal. 

Wave Function Collapse

The wave function collapse algorithm, widely discussed in various articles, offers a unique approach to procedural generation. In this section, I will simplify the concept for easier understanding rather than delving into all its technicalities.

You can imagine the whole process like constructing building blocks or putting together a jigsaw puzzle. Within this process are four main steps: 

• Calculate entropy
• Entropy, a term borrowed from physics, describes the randomness state of an object; the higher the entropy, the more chaotic. In our jigsaw puzzle analogy, entropy at each location indicates how likely we can determine which piece to place based solely on shape. For example, at the beginning, the locations with the lowest entropy are typically the four corners, as only four pieces meet the corner requirements.
• Collapse
• Collapse refers to determining which specific pieces or blocks are to be placed at certain locations.
• Propagate
• Propagate builds upon the 'Collapse' step. It involves the influence that predetermined blocks have on adjoining spaces. For instance, if a predetermined block has a triangular face, only blocks with a matching triangular face can be positioned adjacent to it.
• Reset 
• Reset involves returning all the blocks or pieces to their unplaced state.

The whole process looks like this:

1. Calculate the entropy of all the undetermined locations.

2. Collapse: Find all the locations with the minimum entropy, and put the blocks into them. (Mark these locations as collapsed).

3. Propagate: Constrain the nearby location to only allow certain blocks based on the collapsed blocks.

• If certain blocks exist: go back to Step 1
• If certain blocks do not exist: Reset all the blocks, and then go back to step 1

4. Loop the above steps until all the locations are placed with a block.

Houdini Setup

Now let’s see how these steps are set up in Houdini.

In my personal project, the workflow I envision involves inputting a single box or a combination of multiple boxes into Houdini, which then outputs a complete building based on their shapes. Since designers usually use white boxing to prototype their levels, I hope the tool can finally benefit the level design workflow.

Here are the steps:

Step1: Create slots

The first step involves creating slots, which are placeholders for the building blocks. In our jigsaw puzzle analogy from the previous section, if a puzzle is 10x10, it comprises 100 slots. Similarly, in Houdini, I use a cube to represent a slot. Note that the shape of a slot depends on the shape of your building blocks. For instance, if your building blocks are tetrahedrons, the slots should match this shape.

1. We can use the Points from Volume node, which is used to generate points within a given volume, based on the shape input. This forms the basis of our slots. 

2. I set the side length of each slot to 1 unit and adjust the Point Separation parameter in the node to 1, ensuring each slot is spaced evenly. 

3. Then, the Copy to Points node is utilized to replicate the slot geometry at each point created previously. Setting the box size to 2, for example, results in a structure containing 27 slots, as demonstrated in the figure.

Step 2: Pre-define slot types

After creating the slots, the next crucial step is to pre-define the slot types and then we can assign slot types to each of the slots we created. This involves categorizing slots based on their positional relationships and determining the types of building blocks they can accommodate.

For instance, consider a scenario where interior modeling isn't required. In such a case, a slot completely surrounded by other slots (i.e., six surrounding slots) wouldn't require any block placement as it would be invisible in the final structure. Conversely, corner slots, which are exposed on three sides, are specifically designated for blocks that have three connectable faces.

Defining different types of slots is crucial as it significantly reduces the complexity of our procedural generation process. If all slots were treated identically, allowing equal placement possibility for all blocks, it would become challenging to determine the slots with minimum entropy. By categorizing slots and restricting block placement based on their types, we streamline the process and enhance efficiency.

To define the slot type, various methods can be employed, such as categorization based on adjacent faces, points, or other characteristics. In my approach, I focus on using points to determine the slot type. Specifically, slots are defined by their points and their adjacent relationships. For instance, points with seven adjacent points are marked for further classification. The slot type is then determined based on the number of these marked points and their spatial relationships.

Let's consider a practical example to illustrate how we can define different slot types based on their point characteristics:

For a corner slot, a distinct feature is that it has only one point adjacent to seven other points. This characteristic is unique to corner slots and doesn't apply to other types. Hence, we can use this trait to identify and define corner slots.

Here's an example that illustrates how to determine the appropriate blocks for a specific slot type, such as a corner slot. In the figure below, the slot is represented by a large box outlined only in lines. This slot features a point adjacent to seven other points, identifying it as a corner slot. Therefore, only blocks designed with three connectable faces (and those to be connected slots should incorporate the characteristic point) are suitable for placement in this type of slot.

Now that we have determined the method, the following are the implementation steps.

1. To identify these unique points, I use the Attribute Wrangle node in Houdini. Within this node, the nearpoints() method is employed, which returns a list of points including the point itself; therefore, we compare against the number 8. For points meeting this criterion, I assign an integer attribute named 'activated' with a value of 1 to signify their role in defining the slot type.

Each slot in our model is defined by 8 points. Given that each of these points can have an 'activated' attribute with two possible states (0 or 1), the total number of possible combinations for a slot's points is 2^8 or 256. This calculation represents the different potential configurations each slot can have based on its points' activated states. 

2. After the activated attribute of all the points has been determined, we need to figure out a way to quickly identify the slot type. The approach I use is to represent each slot type with an 8-bit binary string. For example, if only the first point in a slot is activated, the corresponding binary name would be '10000000'; if the first and third points are activated, the corresponding binary name would be ‘10100000’.

I use For Each Connected Pieces to iterate each slot and implement the logic in an Attribute Wrangle node.

3. Having identified all the slot types, the next step is to define each slot's additional attributes. These attributes will be crucial for the implementation of the wave function collapse (WFC) algorithm. I'll provide more details in the next section. This part of the process is more hands-on, requiring a manual setup for each slot to ensure accurate attribute assignment.

Given the large number of slots, totaling 256, it's impractical to manually set up each one. Fortunately, many slots can be efficiently defined by rotating and flipping existing configurations. The figures below demonstrate this, showing how a slot can be transformed by simply rotating it around the Y-Axis, thus creating a new slot type from an existing one without the need for manual redefinition.

Here is an example I save the rotate and flip data in detail: The data is structured as a list; The first element of the list identifies the original slot from which the current slot is transformed; The second element indicates the count of rotations around the Y-axis, with each rotation amounting to 90 degrees; The third element denotes whether the slot has been flipped along the X-axis, although the axis of flipping can vary based on specific requirements. These values will be used later when finally instantiating the blocks, I will flip and rotate them accordingly.

In Houdini, the framework I've established involves creating null nodes named 'Slot_{BinaryString}', where each binary string uniquely identifies a slot type. Following this, I will add additional attributes to these nodes later. To efficiently manage and access these slot nodes, I utilize a Python node. This node is programmed to fetch all slot nodes using their prefix. While there are several methods to accomplish this task — such as merging all slots and accessing them through the merge node input — the Python node provides a streamlined approach. Subsequently, an Attribute Wrangle node is employed to generate the names for the rest of the slots. This is achieved by rotating and flipping the pre-defined slots and storing their names in the detail attributes of the node.

4. Now the slot transform framework is built, we can initialize the additional attributes of all the slots. A key attribute I've defined is 'faces': it represents the combination of faces on potential blocks that can be placed in each slot. In this context, each face is assigned a unique ID, and only faces with matching IDs can connect.

For illustrative purposes, consider the example shown in the figures: two different blocks can be placed in a particular slot. These two blocks have almost identical face IDs, except for the face on the +Y axis. The first block features a face with an 'L' shape, while the second has a '/' shaped face. Due to the difference in shapes, they are assigned different IDs, signifying that they cannot connect to each other. This distinction in face IDs is crucial for ensuring that only compatible blocks are placed adjacent to each other in the procedural building model.

I use the following approach to define the 'faces' attributes: connect an Attribute Wrangle node to each slot node and define the faces attribute there.

5. The final step in defining slots is to import the building blocks that correspond to each slot type. The shape and structure of these building blocks must align with how we've defined the faces attribute for each slot. This alignment ensures that when blocks are placed into slots during the procedural generation process, they fit perfectly. 

This step is key in bringing the procedural model to life, as it bridges the gap between abstract slot definitions and tangible building block forms.

You can simply use a File node to import the geometry of the building blocks and link them to a null node with the proper naming convention. 

Since I am going to export the tool as an HDA to Unreal Engine, I add a few more nodes, so I wrap up them into a subnet for convenience.

Step 3: Assign slots

In the above section, we predefined all the slot types. In this section, we need to assign the slot types to our created slots and pass the slot attributes correspondingly. I use a Python node to get the `faces` and other attributes of the slot and I link the `slot_libaray` node as a spare input so that I can fetch the data more efficiently.

Step 4: Apply the WFC to determine all the blocks

Now that all the preparations are complete, we're ready to apply the WFC algorithm in a Python node (though it's also feasible to use VEX nodes).

1. The first step involves calculating the entropy for all the slots. For this, I utilize a version of the Information Entropy formula:

H = -p(x)log10p(x)

In this formula, base 10 is used for the logarithm (log10), but it's worth noting that other bases can be chosen based on your specific needs. The p(x) in the formula represents the probability of a block being placed in a slot.

Assuming a slot has four possible blocks and the possibility of them is 0.25, then the entropy of this slot is around 0.6.

Assuming a slot has two possible blocks and the possibility of them is both 0.5, then the entropy of this slot is around 0.3.

Assuming a slot only has one possible block, it means the possibility of the block is 1, so the entropy of it is 0. 

It's clear from these calculations that lower entropy indicates a higher level of certainty.

The crucial aspect of this calculation is determining the probability of each block, which is influenced by the adjacent, already collapsed slots. We need to factor in these influences when calculating probabilities. If it turns out that no blocks are suitable (i.e., none of them can connect with the adjacent collapsed slots), then a Reset() is performed.

2. Once I iterate through all the un-collapsed (i.e., undetermined) slots and identify those with the minimum entropy, I execute the collapse() function over them – this involves randomly selecting from the potential blocks for each slot. After a block is selected, the slot is marked as ‘collapsed,’ and I then proceed with the propagate() function for that slot. The propagation process involves spreading specific attributes to adjacent slots.

a. For the random selection, we can use a seed to control the output:

b. For propagate() function: When a slot is marked as 'collapsed', it spreads an attribute named adjacent face ID to its neighboring, uncollapsed slots. This attribute plays a crucial role in determining the block possibilities for these adjacent slots. 

c. To better illustrate the process, I use a 2D view to describe: The red square is the collapsed slot, and adjacent to it are two uncollapsed slots. Suppose one face of the collapsed slot has a face ID of 1 and another face has a face ID of 2. The adjacent slots will then receive these face IDs as their adjacent face ID values, 1 and 2, respectively. These assigned IDs are critical in the next step of the algorithm (step 1), as they influence the block placement possibilities. Specifically, if a potential block for an adjacent slot does not have a matching face ID, its probability of being placed in that slot will be set to 0. This mechanism ensures that only blocks with compatible face IDs are considered for placement next to the collapsed slot, thereby maintaining the integrity and logic of the overall structure.

3. Once the above steps are successfully implemented, the process circles back to step 1 and continues until all the slots are collapsed. This iterative approach ensures that each slot is appropriately addressed by the WFC algorithm. 

However, if an error is encountered at any stage, or if a situation arises where no blocks can be placed in a slot (thus violating the algorithm's rules), a reset() function is triggered. This reset() function plays a crucial role: it reverts all slots to their initial state. This includes resetting their collapsed/uncollapsed status and the probabilities of potential blocks being placed in them.

Those are all the necessary steps to determine the appropriate block placement for each slot in our procedural generation process using the Wave Function Collapse algorithm in Houdini. To streamline this workflow, I have encapsulated these steps within a single Python node.

Step 5: Instantiate blocks

Now that we have determined the specific building blocks to be placed in each slot, the next step is to position these block geometries within their corresponding slots, applying the necessary transformations, such as rotation and flipping, as required.

To accomplish this, I start by using the For-Each Connected Pieces node to iterate through each slot. During this iteration, for every slot, I generate the name of the corresponding building block geometry node. This name is then fed into an Object Merge node, which brings the geometry into the scene. Following this, I apply the rotation and flip transformations that were previously saved as part of the slot's data. These transformations are crucial for ensuring that each block aligns correctly within the slot.

Finally, the Copy to Points node is used to accurately place each block at its designated slot position.

Done!

Outcome

I have organized the Houdini setup into two main subnets to streamline the process. The first subnet encompasses the initial step of creating slots, while the second subnet contains all the subsequent steps. To illustrate this workflow visually, I've prepared a gif example that demonstrates the sequence: starting with a Box, transforming into Slots, and finally evolving into Building Blocks. In this animation, you might notice some meshes lacking UV mapping. This is because I have not yet created specific building blocks for those particular slots. In these cases, I've used basic geometries as placeholders.

More Controls

Currently, the building process in our setup is fully random. However, there might be instances where we need more control, such as placing a specific block like a door in a predetermined position.

To address this, I've developed an approach that, while rudimentary, offers a degree of control over block placement. The method involves creating a subnet that acts as a user-defined block. This subnet is essentially a box, but it carries the attributes of the building block I want to place. Using a group node, I select slots that fall within the bounding region of this user-defined block. These selected slots then inherit the attributes defined in the user-defined block. For visual clarity and ease of preview, I also set their color to match that of the user-defined block.

One key aspect of this method is setting these specific slots to the 'collapsed' state right from the start. This ensures that they will always contain the building block I've predefined, regardless of other random elements in the model.

The image below demonstrates this concept in action. You'll notice that no matter how the seed changes, the slot designated for the door always contains the door building block.

HDA to Unreal Engine

In this section, I’ll focus on the key setups in Houdini essential for ensuring the Houdini Digital Assets (HDA) function correctly when imported into Unreal Engine.

The first step involves importing all the building block models into Unreal Engine and assigning appropriate materials to them.

Moving on to Houdini, I employ the Attribute Instances approach to manage the building blocks. For each block, I start by creating an add node, which is used to add a single point. This point serves as a reference for the placement of the block. Following this, I set up an Attribute Create node. The key here is to name the attribute unreal_instance and assign it a String value. This String value is obtained from Unreal Engine by right-clicking the asset in Unreal and selecting 'Copy Reference'. This step essentially links the Houdini asset with its Unreal counterpart, ensuring seamless integration.

Lastly, when it comes to the rotation of the building blocks, a direct transformation approach using a transform node is not suitable. Instead, I use an Attribute Wrangle node to manipulate the @orient attribute. This attribute controls the orientation of the instanced objects in Unreal.

Conclusion

That sums up my exploration and insights into the wave function collapse algorithm, its application in Houdini, and its integration with Unreal. While the process I've described is not the most optimized and certainly isn't the only method available, my hope is that it serves as a source of inspiration for your own creative endeavors. Thank you for taking the time to read, and I wish you the best in your journey with procedural modeling and beyond!

Jin Jin, Tool and Pipeline Technical Artist