Voxels are great for creating dynamic worlds that can be built up and destroyed within a game. Minecraft shows how building environments with voxels can be literal child’s play, but unfortunately voxels lock us into a grid and it is not easy to disguise that grid for the player. Minecraft displays its grid proudly, and a grid can be excellent for building artificial structures, but often we want to build things that are less regimented. We want a system that allows us to build with the ease of Minecraft and yet doesn’t struggle with 45-degree angles.
Constructive Solid Geometry is an approach to modelling which simplifies the process by allowing us to build up complicated shapes using simple operations on simple shapes. For example, we can union a sphere and a cube together to create a cube with a rounded bulge on one side, or we can subtract a sphere from a cube to bite off one of the cube’s corners. We’re saved from being slowed down by the trivial details of vertices and polygons, but even so its far from the point-and-click simplicity of Minecraft because we’re forced to position our solids in 3D space.
The next step in simplicity is planar constructive solid geometry. Just as in Minecraft, we can build a world out of stacked horizontal layers, but instead of each layer being a regular grid, we can build each layer out of constructive solid geometry. This way we gain point-and-click building because each solid is constrained to its own layer, so we only need to give it an (x,y) position within its layer, and the operations of constructive solid geometry are far less computationally intensive when restricted to two dimensions. Instead of having to perform Boolean operations on polyhedrons, all we need to do is perform Boolean operations on polygons, and that can easily be done while the game is running.
We can create a maze with a few quick strokes of the mouse, because each stroke can create a complete hallway for the player to explore. We store each stroke as a list of vectors and we apply some smoothing so it doesn’t look like it was done by hand, then we apply thickness to the stroke and construct a polygon outline for the stroke. The union of all those polygons together forms the maze. We turn the sides of the polygons into walls, add a floor and ceiling, and we’re done.
Give the player some mining equipment and she’ll be able to dig her own passages through the maze. Since the maze is made of horizontal polygons, we can assign a building material to each polygon that will not only determine how the polygon is rendered, but also determine how hard it is to dig through. When the player swings a pickaxe at a wall, we check which polygon that wall belongs to, check that we’re allowed to dig through it, then subtract a small polygon from the big polygon to represent a hole being created by the pickaxe. For a bomb we can subtract a circle from all the nearby polygons to represent the blast radius.
Naturally we can create a multi-level maze just as easily by stacking together multiple layers and installing ladders to move between layers. Unfortunately sloped surfaces like ramps and stairways are awkward to handle. Even though we’ve made it far easier to build things at any angle horizontally, creating vertical angles is even harder in this plan than it is in voxels. Where a simple sloped block can naturally connect two layers of a Minecraft world, there’s no obvious equivalent in a planar constructive solid geometry world.