WORK IN PROGRESS Updates Soon!

Binary Trees Applied to Procedural Generation#

While standard binary trees allow efficient searching and ordering of scalar data, partitioning trees generalize this concept to multidimensional space. It acts simultaneously as a hierarchical search structure and a precise geometric representation. The core mechanism involves recursive subdivision by hyperplanes. Unlike grid-based approaches, this method has no restriction on the orientation of cuts, allowing for the exact representation of polytopes and convex sets.

A hyperplane is the subspace of dimension that divides the space into two half-spaces. Mathematically, in $\mathbb{R}^d$ , it is defined by the implicit equation $n \cdot x + d = 0$ , where $$ n $$ is the normal vector and $$ d $$ is the distance from origin. The classification of any point $$ p $$ is determined by the dot product. If $n \cdot p + d > 0$ , the point is in the front child. Conversely, if the result is negative, it is in the back child.

Procedural Application#

If we have the intent to generate the map of a dungeon, the use of a partitioning tree is appropriate. The root node represents the entire map’s canvas and the leaf nodes become potential zones for rooms. Because the split is binary, rooms generated in leaf nodes will never unintentionally overlap, creating mathematically guaranteed disjoint sets.

However, in practical engineering, the concept of disjoint sets faces challenges due to floating point arithmetic. Since computers approximate real numbers, a situation where $0.0000001 \neq 0$ can occur, creating “cracks” in the geometry. Robust implementations must replace direct equality checks with an epsilon threshold comparison. Furthermore, edge cases such as co-planar geometry, where objects lie exactly on the cut, require specific handling logic to assign the object to one side or duplicate it across both.

As a recursive limit, a size heuristic is necessary, such as stopping the split if a node is smaller than a certain unit size. For dungeon maps, the hyperplane is typically limited to axis-aligned cuts using orthogonal X and Y axes. This specific subset is known as a k-D Tree, which simplifies the dot product vector calculation into a fast scalar comparison, drastically improving generation speed for grid-based layouts.

To control the dungeon’s architecture, we avoid uniform distribution for the split positions. Applying a Gaussian distribution allows us to bias the generation, creating larger, denser rooms at the center and smaller, sparser rooms at the peripheries, simulating a more organic structure as everything in the real life have tendency to follow non-constant patterns.

Why Gaussian vs. Uniform Noise?

Uniform distribution (Standard Random) maximizes entropy or similar. In procedural topology, max entropy results in a "Swiss Cheese" layout—unstructured, sprawling, and lacking a focal point. By using a Gaussian (Normal) distribution, we mathematically force a hierarchy. The "Bell Curve" ensures that ~68% of the splits happen within one standard deviation of the center. This naturally creates a density distribution, mimicking organic structures without requiring complex heuristic scripts.

Structural Limitations and Topology#

Beyond numerical precision, the method imposes distinct topological constraints. By definition, a binary tree generates a hierarchical structure without cycles. In the dungeon example, this results in a branching map where the player must constantly backtrack to explore different paths, lacking the interconnected loops typical of organic level design.

Furthermore, axis-aligned partitioning inherently biases the layout towards long, strictly orthogonal corridors. Consequently, the BSP algorithm must be viewed strictly as a space allocation tool, not a complete level generator.