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.
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.
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.
The world in Avoyd is made of voxels placed on a grid defined by an octree. This section explains what they are.
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.
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.
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.
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'.
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
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
So far all the boxes we've created are identical. Let's introduce some variations for each box.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Random distribution of three groups of colour. Each box's colours are constrained to one palette: oranges, whites or blues.
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
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).
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
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.
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.
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.
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.
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.
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.
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.
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'.)
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:
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.
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:
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:
To explore further, increase both the Size and the Unit Size, then decrease the Unit Size.
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:
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.
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.)
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.