Boxes in Space: procedural generation of abstract worlds in Avoyd

Juliette Foucaut - Doug Binks - 21 Jun 2019

The first part of this post describes how we use procedural generation to create environments in our game, Avoyd, out of simple boxes. It is an extension of the 'Boxes in Space' talk Juliette gave at Feral Vector.

The second part shows the trial and error process we went through to create Avoyd's procgen worlds and how we procedurally generate the light and atmosphere.

The third part consists of procedural generation demos, giving complete instructions to create the boxes in space worlds, Menger sponges, trees that avoid obstacles, and how to change the lighting and atmosphere in Avoyd. The worlds created can be saved and used in game.

1. Boxes in Space

To generate large abstract worlds in our game, Avoyd, out of simple boxes, we use a walk inspired from brownian motion to position the voxel boxes in space and define grouping by colour palettes, box proportions and orientation. We employ random functions to implement local details: hollowing the boxes, colouring them and applying greeble. We use the order of creation to implement features such as bridges between boxes which benefit from overwriting parts of existing structures.

1.1. Why use procedural generation?

We need a large environment navigable in any direction: easy to fly around and conducive to players moving on any surfaces. Procedural generation brings some variety to the environment whilst ensuring the game reliably produces worlds within a range of acceptable parameters: not too large, not too small, not too porous nor monolithic, etc.

This is what Avoyd currently looks like. AI controlled drones flying in a very large, abstract world that's procedurally generated when the game starts. The world is entirely editable. you can destroy or build anything in it. It takes place in space, in zero gravity. This means you can fly in any direction, you have 6 degrees of freedom: you can move horizontally, sideways, vertically, yaw, pitch and roll.

Players can fly but can also move on any surface. There's no up or down, any wall can become the floor.

Generating the environment procedurally when the game starts helps keep the download size small since the worlds don't need to be included with the game. This allows players to experience large, complex environments which would otherwise be time and bandwidth consuming to download. An added benefit is it keeps the costs down for us as we host the free demo of Avoyd for download on our website.

For the record, this is not the first time we've used procedural generation for creating environments. In the 2003 version of Avoyd (Avoyd-1999) the world was generated using a crystal growth algorithm. We couldn't make it very big: 128 voxels a side maximum in theory. However due to the technical limitations at the time the largest playable worlds were only 32 voxels a side.

Avoyd-1999's game start screen. The world was generated using a crystal growth algorithm. In this video I've toggled the wireframe on and off a few time to reveal the voxels.

1.2. The tech behind the world

The world in Avoyd is made of voxels placed on a grid defined by an octree. This section explains what they are.

1.2.1. Voxels are data in a grid

Voxels are commonly defined as 3D pixels or cubes. A better definition of a voxel is data attached to a 3D grid. Since they're data, they can be represented any way we want in the grid: spheres, lego bricks, cubes of dirt, etc. It's shown very well in the first 50s of the video about MagicaVoxel rendering or in Sean Barrett's video about his stb_voxel_render.h library.

In Avoyd we've decided that each voxel stores a material and an amount. The material is represented on-screen by the colour of the voxel. The amount is represented by the size of the cube within the grid. A voxel with a small amount looks like a small cube. The more material is added the more it grows, until it fills its position in the grid. We've added a morphing effect so if a voxel has a neighbour, id becomes deformed to stick to it. This can give the voxels a smoother look when they're side by side. You can read more about Avoyd's constrained morphing voxels in devlog post 'Voxel Editor Evolved', and see them in action in the video about building in Avoyd.

1.2.2. The octree defines the grid

We use an octree to define the grid and store the world data. An octree is a compressed 3D array. To visualise it, imagine the octree represents an empty world as a single huge box. When something is added, we subdivide the box into 8 smaller boxes (hence oct-tree), then repeat this for each box until we have small enough boxes to represent our data. The smallest subdivision is one voxel.

In this video, Doug's scanning the world to reveal the octree. You can see a lot of little shiny cubes where the environment is very detailed, and much larger ones where there's an empty space. This is the compression: any space that's homogeneous (empty or full of identical voxels) can be represented by a single cube.

1.3. Procedural Generation of a world

1.3.1. Basic building element: the AABB

Let's move on to the procedural generation. The basic volume we'll use to generate the world is a box full of voxels. It's called an Axis Aligned Bounding Box. It's aligned to the grid I mentioned above. We'll add and remove AABBs of various shapes to create the world. I'll refer to them simply as boxes in the explanations that follow.

AABB size 8 x 12 x 16 voxels, wireframe only on the left and wireframe + voxels on the right.

1.3.2. Positioning boxes

Two ways to generate and position boxes in space are to distribute them randomly in a volume, or place them one after the other in a 'walk'.

1.3.2.1. Random cloud of boxes

We can place many boxes at random positions around an origin using a random function. The distance from the origin is proportional to their dimension along the same axis. This means every box we generate will be placed in a volume that is, in our example, a larger box with the same proportions.

Random clouds of 10, 100, 1000 boxes

1.3.2.2. Walking boxes

Another way to place many boxes is a random walk. This is where each box's position is based on the position of the previous box, with a random modification. This is the same mechanism as brownian motion. One way to imagine the walk is you take a step, drop a box, then choose a direction and distance at random and take another step, drop a new box, and so on. This is the method we'll use to position our boxes.

Four runs of several hundred walking boxes

1.3.3. Modifications to individual boxes: size, hollowing, colours and greeble

So far all the boxes we've created are identical. Let's introduce some variations for each box.

1.3.3.1. Random size

First, we randomise the boxes' size, within limits: we make them proportional to their original dimensions.

Three runs of several hundred walking boxes of various sizes.

1.3.3.2. Holes

We can hollow each box. First we draw the box, then, inside it, we randomly delete box-shaped holes. Repeat for each box with a new cloud of random holes.

Four examples of hollowed purple boxes.

1.3.3.3. Colour

We use the same principle as the holes, except we use a cloud of box-shaped paint volumes to colour the original box.

Four examples of coloured white boxes.

1.3.3.4. Combining holes and colour

As you can see it's a little difficult to read the image and differentiate between holes and colours.

Four examples of hollowed, coloured white boxes.

1.3.3.5. Colour inside only

To help with the legibility of the environment we decided to only paint the inside of the box, leaving the surfaces colour intact. To do this we first draw the original box, then calculate a slightly shrunken box inside, and generate the cloud of paint boxes inside that smaller volume instead of the whole box. This leaves the outer shell unpainted.

Four examples of hollowed boxes, with coloured decorations excluded from the outer shell of the white box.

1.3.3.6. Combining size variations, hollowing and colour decorations

This is the result of combining three modifications on boxes: size, holes and colour.

Several examples of boxes of various sizes, procedurally hollowed and painted with colours on the inside.

1.3.3.7. Greeble

Greebling is a technique used in movies special effects. It consists in adding small details to make things look big. For example it was used on spaceships in the Star Wars movies.

To decorate boxes with greeble we randomly add smaller flat metal panels (boxes) to the sides of the main box. Then, for some of them, we delete their centre (using a box-shaped hole). The result is a filigree effect with some metal surfaces.

Five examples of greebled boxes. We've used a metal-coloured material to make the greeble.

1.3.3.8. Combined size, hollowing, colours and greeble

This is the result of combining size variations, hollowing, colours and greeble. It's varied, quite garish but it feels a little too amorphous and messy.

Random boxes, each with randomly picked size, main colour and decorations, hollowing pattern and greeble.

1.3.4. Structuring the randomness

We're going to add patterns to structure the world we've creared. We'll use palettes of colours, 'preferred' dimensions and distance to create clusters of boxes.

1.3.4.1. Fewer Colours

We've been picking colours at random from a large selection. Let's reduce the range and choose an arbitrary subset of colours. In this example we'll pick three groups: oranges, whites and blues. For each group I made a palette of similar colours (to make the effect more visible).

Three palettes: oranges; whites; blues.

Every time we draw a box, we choose one of the three palettes at random and use it to set the box colour and add the painted decorations. The result is a random distribution of three groups of colour.

Random distribution of three groups of colour. Each box's colours are constrained to one palette: oranges, whites or blues.

1.3.4.2. Colour clusters

To add more structure, we use palettes to group the colours together. During the walk, as we generate and place new boxes, we periodically pick a colour palette and stick with it for a few iterations. Then pick another palette, and so on.

Boxes clustered by colour palette

1.3.4.3. Shape and distance

Beyond colours, there are other properties we can use to differentiate each cluster. One of them is the shapes of the boxes. One cluster may have more elongated boxes along one of the axes, the next one may have slightly flatter boxes, and so on.

In addition, to further differentiate the clusters, we position them further apart from each other. In other words, when we start a new cluster, we travel a little further than usual before we place the first box.

Boxes clustered by colour palette and dimension 'preference'. Clusters are separated from each other by increased distance (not always visible, especially when the walk folds back on itself).

1.3.5. Navigation features: bridges

I've mentioned above that Avoyd is set in zero gravity. Although one can fly, moving on surfaces is safer and gives more control to the player. So we decided to link the boxes using bridges to help moving from one box to the next.

To build a bridge, we first make a start and an end box. Then we build a bridge between them (a long box), then punch a hole along the whole length of the bridge (a long box-shaped hole). The hole helps players reach the insides of boxes, which is more sheltered

Procedurally generated bridges linking the insides of the boxes.

A set of clusters with bridges, each box is connected to the next by a bridge.

How the procedural bridges are made: every time a box is generated, we store the bridge that connects to it in a list. After all the boxes are created, make all the bridges.

First the boxes, then the bridges

1.4. Conclusion

In conclusion simple combinations of simple shapes (boxes) work, but you need to add structure: grouping by shape, position, using palettes to group colours etc. to make the result interesting.

If you'd like to re-create and play with the boxes in space in Avoyd, follow the instructions below.

2. A changing world

The rules we use to generate the worlds in Avoyd are a little more complicated and are still evolving. For instance the palettes of colour are more confused due to the need to include weak and strong materials. We also build bridges to smaller safe rooms made of strong materials (metal). Inside boxes we've made shielded crates: hollow boxes made of metal, to be used as a refuge. All these features are subject to change in future versions of Avoyd.

2.1. Trial and error

In reality we went through many iterations and tweaks to make the environment in Avoyd. The earlier version of 'Boxes in Space' we wrote for the procjam zine, Seeds, gives an overview of the trial and error process we went through.

towers of greebled boxes

hollowing greebled boxes

deforming boxes, adding bridges and metal rooms

introducing colours

grouping boxes into clusters

colouring clusters

looks messy when there are many boxes

lenghtening boxes in some clusters

clusters grouped by colours and dominant axis

in-game drones damage the boxes

2.2. Atmosphere and lighting

Another area we've used procedural generation for is the lighting and atmosphere parameters.

Our initial attempts at procedural atmosphere and lighting for our worlds was to simply randomize the parameters within some 'sane' fixed ranges. This looked interesting, but the results never quite worked as well as hand picked parameters.

The secret addition which solved this also ended up improving results from manually setting up the lighting and atmosphere - we calculate an approximation of what the ambient lighting should be from the atmosphere parameters and direct lighting.

This gels the scene by matching the colour in shadows with the 'away from sun' sky colour. In our case the sky colour is calculated by a simple approximation using a Rayleigh and Mie type scattering equation, modified to represent an abstract infinite gas filled space. Normally this calculation is done in shader code per-pixel for our rendering, but for a fast rough solution to a global ambient we set the ambient colour and intensity on the CPU in game code based on the scattering calculations for a direction orthogonal to the sun direction.

Ambient lighting as an independent variable can create results that feel incorrect, but can be interesting

Ambient lighting calculated automatically

Currently the ambient occlusion used in Avoyd is not directional, but we hope to introduce directional occlusion and eventually diffuse bounced lighting which should really improve how solid the scene looks.

3. World generation demo

Video showing procedural generation of worlds and lighting and atmosphere in Avoyd.

To play with the boxes in space and other procedural examples,

download the latest version of Avoyd

and follow the instructions below.

3.1. World generation at game start

You can explore the procedural worlds simply by starting a game in Avoyd. To do so, start Avoyd and select 'Create Game'.

Avoyd splash screen, Create Game selected

A new world and its atmosphere and lighting are generated every time a new game is created or when you click on 'Generate World' in the 'World' section. Each world has a unique seed you can save and use to re-create it. It can be useful as worlds get damaged during play.

CREATE GAME > World - generate random world seeds to create the world from or use a custom seed. In this example, the seed is 9E3BE641.

3.2. World generation in the Voxel Editor

To access the Voxel Editor, start Avoyd and select 'Voxel Editor'.

Avoyd splash screen, Voxel Editor selected

The procgen tools are slightly hidden. To access them select 'Tools > Edit Tool...'.

In the 'Edit Tool', ensure you have 'Set' selected in the left-handside list.

Then in the 'Shape' drop-down find the items prefixed with 'Procgen: ...'.

In Avoyd's voxel editor, open the edit tool and procgen shapes selector.

Tip - performance - when doing procgen, start small by using the recommended values below. Depending on your machine you may notice a considerable slowdown as you procedurally generate larger and more objects.

Tip - editor - to empty the world select 'Edit > Clear'.

Tip - editor - to toggle the camera movement on or off in the editor press 'Tab' or hold the righ-mouse button. See 'Help > Control' for further information about the user interface and controls.

Tip - editor - you can save the worlds you create by selecting 'File > Save'. (Saved worlds can be used in-game by going back to the main menu and selecting 'CREATE GAME > World > Load Existing World'.)

3.2.1. Boxes in Space

To reproduce the environments created in our example procedural generation, follow the instructions above to open the Voxel Editor's Edit Tool in Set mode.

In the Edit Tool's 'Shape' drop-down pick 'Procgen: Boxes In Space'.

Parameters:

pick the number of boxes 'Nr of boxes' you want to generate. 60 is a good number to start with: you'll be able to see the clusters.
set the base box dimensions: 'Size' and 'Orientation'. They're used to draw the first box and as the reference all subsequent boxes are calculated from. 60x60x60 is a good size to start with.
pick a material 'Amount'. Reducing the amount of material reveals the morphing effect, smoothing angles. Materials with a reduced amount are destroyed faster during gameplay. Start with the maximum amount: 255.

Finally press the green 'Do Set' button or use the mouse to place the green witreframe which will be the first box in space, then left-mouse click to start the procedural generation.

To explore further, increase the size and number of boxes.

3.2.2. Linked Boxes

The instructions below let you generate the same type of world we use in-game.

In the Edit Tool's 'Shape' drop-down pick 'Procgen: Linked Boxes'.

Parameters:

'Nr of boxes': 20 to start with.
'Size' and 'Orientation': try 60x60x60 to start with. (If you use smaller sizes the result looks like shrapnel.)
'Amount': 255 to start with.
Colour (Material): you have two choices
1. pick a material from the 'Materials Palette' and the generation script will choose all materials with adjacent material IDs, or
2. tick 'Use preset material clusters' and the script will cluster boxes by colours. There are 5 types of clusters: whites (most frequent), ochres, reds, greens and blues. This is the setting used to create the world when the game starts.

3.2.3. Menger Sponge Fractal

For something a little different but still procedurally generated and made of boxes, you can create Menger Sponge fractals.

Menger sponges - blue: size 9, unit size 1; orange: size 81, unit size 3; white: size 243, unit size 1.

In the Edit Tool's 'Shape' drop-down pick 'Fractal: Menger Sponge'.

Parameters:

'Size': 9 (start small)
'Unit Size': 1. This is the size of the smallest units of solid, and also the smallest holes.
'Amount': 255 to start with. (If you reduce the amount, the voxels will morph and make the holes appear more circular.)

To explore further, increase both the Size and the Unit Size, then decrease the Unit Size.

3.2.4. Raytracing Trees

We can make tree-like structures out of boxes.

The procedural tree in the foreground (orange) was generated from a starting cube of size 10 voxels. The yellow tree in the background was generated from a starting cube of size 64.

In the Edit Tool's 'Shape' drop-down pick 'Procgen: Tree'.

Parameters:

'Size': start with 10. This is the size of the cube at the base of the tree. The trunk and branches grow from it, getting progressively smaller.
'Axis Orientation' and 'Axis Direction': the orientation and direction the tree grows
'Amount': 255 to start with. Lower amounts will result in smoother-looking trees.
Colour (Material): any

3.2.4.1 How the trees grow

The procedural tree grows by aligning identical cubes along an axis to form branches. Each branch also sprouts two smaller branches, creating an 'F' shape: the first sub-branch starts half-way up the branch; the second sub-branch is added at the tip (end) of the branch. Each sub-branch repeats the same process, growing in a smaller 'F' shape, and so on.

Sub-branches are made of smaller-sized cubes than the branch they grow on. They also have a different orientation in space. We stop generating new branches when the cubes used to create it are smaller than an arbitrary dimension.

3.2.4.2 Collision detection

In order to avoid collision with surfaces, before a cube is added at the tip of a branch, we do a raytracing test to check there is no obstacle in the way. If there is, we add a random rotation to the branch. Repeat until we run out of attempts or, if nothing is detected anymore, carry on growing the branch in the new direction.

Procedural tree (green) growing out of a Menger sponge (white). When growing a branch a raytracing test detects potential collision with the walls of the Menger sponge and avoids them. (Note on why the Menger sponge holes are circular: this is due to neighbouring voxels morphing as we only used half the maximum material amount.)

3.2.5. Atmosphere and Lighting

Finally if you'd like to tweak the atmosphere and lighting of your world, open 'Tools > Light and Atmosphere...'

From there, you can tweak the parameters manually or click on 'Random' to procedurally generate them. (As mentioned above you can set the Ambient light to be automatically calculated, or deselect it to change it independently.)

Randomly generated atmophere and lighting with ambient lighting calculated automatically.

Tip - editor - when you save a world with 'File > Save', the light and atmosphere settings are saved with it.

› Python Google App Engine debugging with PyCharm CE
› Lighting voxel octrees and procedural texturing
› Patterns and spheres
› Python Google App Engine debugging with PyTools
› Interview
› Domain masking using Google App Engine
› Octree streaming - part 4
› Black triangles and nervous_testpilot
› Presskit for Google App Engine
› Octree streaming - part 3
› Octree streaming - part 2
› Octree streaming