All Quiet for now, but we're working in the background

These blogs tend to look like a one-shot wonder if they start with many posts, and then suddenly stop, so this is just a quick update.

We've been looking far ahead and scoping out the rest of the project. A lot of work has been done on the gameplay mechanisms and balance (but we won't be revealing that until the very late stages, because we think it's going to be good, and worthwhile stealing!). We've also looked extensively at rendering, in particular how the view is prepared for a player, and the rendering of different types of game object in the same view (for example, mixing custom rendering with conventional hardware-rendered 3D geometry).

So although this blog will seem to slow down, be assured that we're doing lots of planning in the background. When we're certain of a design direction, or when we're confident we can write a balanced article about design choices, we'll post more.

Stripping the Zeros

This implements nodes of a sparse voxel octtree (SVO), with optimizations that enable optional attributes to be stored frugally.

SVOs are fairly efficient at storing volumes where most of the voxels are identical for large chunks of landscape, but when we try to associate different types of data as a 'variant' or 'union' record in each node, the structure suffers from unnecessary bloat because variant records take the length of the largest variant; the unused fields still take memory.

Our code identifies a small number of 'parts' that may be included in a node. If we have three parts, then there are eight possible composite combinations of these parts (by binary combination: {fff, fft, ftf, ftt, tff, tft, ttf, fff} ), and each of these composites may have a different record length.

If we then store each combination (variant) in its own array or list, we avoid the wastage of unused records. The best improvements are found in scenarios that mix long records with short records.

Cons: it's possible that fragmentation can occur with the reallocation of memory when up-sizing a list. We have not addressed this potential problem, which may disappear with the virtual addressing that exists in most modern OSs, or be solved by adopting a simple hierarchical memory manager for the list or array.

Example

In the following, we present a simple example of the technique, which uses three attributes. Note that our actual code will include more structure, and some details are omitted:

1. Basic (TCNV_Part_Basic), which contains:
   • a pointer to the parent node,
   • information about which attributes are set in this node (remember, just 1 byte!)
   • information about which attributes are set in sub-nodes (also 1 byte).
2. Material (TCNV_Part_Material), which contains:
   • just a reference to an entry in the list of materials.
3. Children (TCNV_Part_Children), which contains:
   • 8 × octtree pointers to sub-nodes. Null values mean that there is no sub-detail in that sub-volume, and the volume is accurately represented by the current node.
   • ...[and so on]...

Any data that is missing from the children may be obtained from parent nodes. We note which attributes are stored in the node using a set (a row of bits, of type TCubeFeatures where each bit denotes whether the attribute is present).

These are typed, fixed-length records, named with prefix "TCNV_Part_" to denote "Type: Cube Node Variant - Part"

 TCNV_Part_Basic    = record
  Parent:           PCubeNode;     // 32 bits
  FeaturesThis:     TCubeFeatures; //  8 bits
  FeaturesChildren: TCubeFeatures; //  8 bits
 end;
 
 TCNV_Part_Material = record       // 16 bits
  Material:         TMaterialID;
 end;
 
 TCNV_Part_Children = record       // 8 × 32 bits
  ChildNodes:       array[TUnitDirectionEnum] of PCubeNode;
 end;

Code 1: 'Part' types.

These types are then combined into composite records:

 TCNV = record                   // 48 bits
  Basic:      TCNV_Part_Basic;
 end;
 
 TCNV_M = record                 // 64 bits
  Basic:      TCNV_Part_Basic;
  Material:   TCNV_Part_Material;
 end;
 
 TCNV_C = record                 // 244 bits
  Basic:      TCNV_Part_Basic;
  Children:   TCNV_Part_Children;
 end;
 
 TCNV_MC = record                // 304 bits
  Basic:      TCNV_Part_Basic;
  Material:   TCNV_Part_Material;
  Children:   TCNV_Part_Children;
 end;

Code 2: Composite types, which combine the Part types.

...each of the Composite types can be stored in arrays where the elements are of fixed length. With sensible re-sizing of the allocated memory, we can minimize the amount of memory that would otherwise have been wasted by conventional variant records. In Code 2 (above), the largest record is 304 bits (38 bytes), and the smallest record is 48 bits (6 bytes), which gives a 'saving' of 256 bits (32 bytes, or 84%) for every 'leaf' node.

Because the data types and field offsets are different in each case for any given field (like 'Material' for example), we'll need to wrap these structures in methods that allow requests to be mapped into our non-standard variant structures.

It will be interesting to see whether this works in practice. If it does, then we'll be able to add many types of sparse data to existing matter in the world model, with very little penalty. This is how we'll inject lighting data into our world.

Further Optimizations

This is getting ahead of ourselves a little, but we should mention that the above technique still has lots of room for improvement. Further optimizations are possible by abstracting the subdivision and material packing, which we might need for small-scale detail, to bring massive efficiencies in specialized cases.

Material Packing

It's likely that fewer materials will be used within a player-sized cube, so we might be able to (for example) optionally treat sub-detail as an 8 × 8 × 8 array of bits, value 0 representing 'background' material, and 1 representing 'foreground' material. For any of you who know 8-bit computers, some computers (the ZX Spectrum, and the BBC's Teletext mode) allowed the creation of primitive graphics by allowing each 'text cell' to contain a 1-bit image, mapped into foreground and background colours.

Subdivision

At the expense of complicating all the supporting ray-casting routines, we can specify alternate ways of slicing up volume nodes into sub-volumes. It's well-known that octtrees can be very fussy about the placement of a plane surface: if a change of medium corresponds to the boundary of a large node then it is very efficient, but if that plane is just one detail voxel inside the neighbouring large node then the neighbouring node is sliced eight ways for each level of detail until the detail node is reached - very inefficient, especially if your plane happens to be a flat sea or landmass covering the whole map (it can make megabtyes of difference to the storage overhead on a 1024^3 world map).

Edited to provide more detailed examples. We'll revisit this entry if these methods prove to be successful.

Rewind: Some points from our research

There are lots of projects out there that are playing with voxels. Only a few have achieved demonstration state, and most of those seem flawed in some important way. Minecraft seems to be the cleanest implementation so far. I tried running Manic Digger, but it suffered performance problems, kept eating memory to fill 2GB, then hung - looking at the source code, it doesn't use SVOs (the special Octtree structure I worked out before the first Vol post), but instead caches uncompressed chunks of the landscape.

From my basic research, I learned that one needs:

1. OctTrees (or similar) to store a 3D landscape of voxels.
2. To discard parts from memory when they're no longer needed.
3. A procedural landscape generator, which is repeatable, and doesn't depend on what's going on elsewhere - this is limiting, but I can see ways around it.
4. [inferred] Given that the procedural aspect can be generated at any time, we have freedom to discard it as required, because we can always regenerate it on demand. We want a player to be able to dig and build in the landscape, so we'll need to store modifications in a separate octtree. The actual state of the landscape can be ascertained by reading the procedural content, and then overlaying the modification content. Modifications can be paged out as necessary, but never deleted.
5. Using conventional (straightforward) programming, adding attributes to voxels will drastically increase the memory usage for ALL voxels. We need to find a way around this (and we think we have).
6. People seem to think that a multiplayer is much more fun, and most developers have prioritied a networked client-server topology, though I've only seen 'shared enviroments' rather than any true player-to-player interaction or co-op missions. I think I'll ignore this for now, but try not to close the door to this option.

Getting There Quickly

World Geometry

Step 1

As we've outlined in our earlier post on abstraction, these are the options that we'll be choosing to implement first, for renderer and world geometry respectively:

• Low-resolution software rendering,
• A simple if-then-else function to determine the contents of the world geometry, e.g. if (position in [0,0,0],[10,10,10]) or (position in [-30, -5, -30],[30, 2, 30]) then [this is rock], else if (y<=0) then [this is sea], else [this is air].

This allows us to develop player and camera movement, and basic interaction with the world geometry.

Step 2

From there, we'll progress to higher resolution rendering (only where it maintains playable rates, and perhaps using some optimizations to achieve higher resolutions without doing too much work), and a regular array of cubes for the world geometry. Those optimizations can take on a life of their own, our favourite methods being 'local ray cacheing', 'progressive rendering', and picture processing operations (borrowed from video encoding) that avoids re-casting predictable regions for a few frames. We'll try to remain focused!

Steps 3, 4

That gives us some options for terrain modification in step 3, which is a single octtree, along with optimizations that minimize memory usage (more on that later). Step 4 gives us the infinite world using side-links to other nodes, along with the memory management utilities that enable the disposal and paging of world geometry.

Rendering

As we hinted before, there are many possible ways to render the scene. We'll concentrate our efforts on raycasting and polygonal rendering, and the hybrid methods anywhere in between. Our strategy for rendering will be to evolve through several stages, each stage being more polished than the previous stage:

1. Low-resolution software renderer.
2. Simple triangle geometry.
3. Optimized triangle geometry.
4. Optimized software renderer.

Hardware Rendering or Software Rendering?

We believe that writing a full software-driven renderer is not likely to result in a playable frame-rate; indeed to do so would need a lot of low-level optimisations that (frankly) we don't have time to implement. We'd rather get the other elements of the game working, and perhaps return to writing and heavily optimizing the rendering engine later.

Aiming for a Hybrid Approach

Our hybrid approach will be to analyse the world geometry for visible blocks using ray-casting (also face culling, frustrum culling, and outsideness testing), convert those to triangle geometry, and render the triangles.

We think efficiencies can be gained by limiting the amount of ray-casting that we do, using a heirarchical scanning technique. We start by scanning a few points, which correspond to a few widely-spaced point on a grid placed on the screen (the projection plane of the camera's frustrum). Say our screen has 320x200 pixels (that's side-screen, 16:10); we might scan every 16th pixel. This image by itself won't look good, but we can use its data to smartly render the remaining pixels. We do this by interpreting the rays from the coarse grid to decide whether to omit the other rays.

Here's an example: if we look at four rays, cast from a point, through viewing plane in a square formation, we can calculate, for any given distance from the origination point, the largest size of cube that can be enclosed by those four rays, without any of the rays passing through the cube, i.e. all four rays pass around the cube but not through it. What we're doing here is calculating the resolvable real-world resolution of a raycasting grid. It tells us that, for example, the coarse grid will start to miss cubes at a distance of 3 metres from the camera. If we're using Octtrees, then we can obtain a 'level of detail' that a grid can resolve at any given distance, and use that to limit the work that is needed by each ray-casting operation.

This becomes exploitable when a square of four sample points from our coarse grid all hit distant scenery: it tells us that between the camera origin and the 'resolvable distance', there will be no obstructions, because they are big enough to get in the way of at least one of the four rays that we cast using the coarse grid, and we exploit this by not needing to test anything in this span, choosing instead to start the rays from our fine-grid at the resolvable distance instead of starting them from the origin.

There are many variations on this, which can exploit different situations, which can tell us: when we'll hit a cube, when we're likely to hit a cube, and when we're likely not to hit a cube. The most useful optimization will help us tune the level of detail according to the placement of geometry found in nearby rays.

Prototyping

Perhaps the fastest route to prototyping is to write a basic software renderer. We said at the beginning that this wouldn't be practical, but I think it will be useful to have a low-resolution renderer, because it is simpler to write than an optimized triangle pipeline.

The first rendering step is to throw some rays out from the camera position into the scene, and put coloured pixels on the screen corresponding to what those rays find. We choose which materials on the world to regard as transparent, and only return a colour when we hit something that is not transparent. If the ray travels straight through all available data without hitting anything, or reaches a distance that we regard as 'too far to display', then we return a sea or sky colour depending on the direction we're looking in.

Implementation - the start of coding

We've chosen to use Lazarus!

After looking around at several IDEs, languages, and platforms, I've decided upon using Lazarus + Free Pascal. I've been using an old Delphi for many years (and completed projects using it), so Lazarus offers a fairly smooth transition to a more modern IDE (compared to Delphi 2 and 6). It's cross-platform too, working on Linux, Mac, and Windows - my main OSs are Windows and Mac.

I'm not choosing Lazarus simply because it's free and a comfortable transition. I've looked at Java (+JMonkey, etc), JavaScript+HTML Canvas, conventional C/C++ + SDL + GLUT and other libraries, C# + OGRE, C# + XNA, Delphi + GL Scene, and others that I can't remember. I think my best chances are with Lazarus, assuming the compiler generates fast enough code, the IDE is stable enough, and the common APIs are well-supported.

Coding progress

At this point in coding, we've prepared about five units, to various stages of completion. Starting from high level, and working down to low level: Main, Game, World, Materials, and Measures. The Measures unit defines math structures, and sets up any global constants. More units (like View for graphics, Client and Server for command and state processing, Net for networking, and so on) will be added.

In World, we've coded most of the data structures for the first three abstractions for the world geometry: a function-based world, a 3D array world, and an OctTree world (more on that in the next post). We've yet to write the internal utilities and published methods that will query and manipulate the world geometry, but we'll will write a complete set for the simplest method first, and when that's working, we'll work on upgrading them, behind an abstraction switch.

Abstraction

Why this approach?

A quick definition of abstraction is "creating a symbol of something, and hiding its details". The abstracted process is reduced to a descriptive symbol, and is handled in terms of that symbol, rather than having to deal with the complicated internals of the process.

This is usually a sensible approach in programming, because it makes the individual modules more robust: parts that shouldn't be visible to the rest of the program are kept secret, and communication between modules is strictly controlled which improves the quality of the resulting program. Abstraction makes us think about how the modules will appear to a calling program, and define a minimal interface that we can implement in many different ways. In theory, by implementing an interface, we may slot in any compliant module, and the module itself takes care of all the details that make the module's functionality possible.

We want the option to be able to get running quickly, by implementing features at a basic level, and then develop more complicated versions later. In programming terms, we're using 'stubs with switches' that let us choose between ways of implementing the functionality of the stubs. With this type of abstraction, we aim to be able to switch between alternative methods by just 'throwing a switch' by setting a compiler flag, or setting an in-game option.

Tighter Development Cycles

Doing this means that we can quickly build a test environment, upon which we may build more detailed functionality, and commit to short development cycles because there is less code to 'get right' before the individual elements work as intended within the whole. Additionally, there is less chance of being distracted with details that are not relevant to the core game. This is especially important when we're just trying to see if the game concepts themselves will work (it's always best to reveal potential feasibility problems as quickly as possible!)

Major Abstractions

World Geometry

We aim to play the game in potentially massive worlds, but the programming to enable a very large or seemingly infinite world will take some time. If we implement the simplest structure for the world geometry, then we'll be able to quickly write the other aspects of the game. Given that the world geometry will take up lots of memory in this simple form, we'll be limited to small worlds.

Closely associated with the world geometry is the memory management and streaming. Whether the world is stored as a 3D array of cubes or an octtree structure, there will be a number of functions that are common to both approaches, which can be used by the other parts of the game.

For example, we might want to access the block that is adjacent to the block we're currently working on, so we'd write a function to do this called GetAdjacent(). To do this, we first define the common interface (the specification that the rest of the program will use to access the geometry), as TGeometry (we're using Pascal/Delphi notation, the "T" prefix indicating a type, so this name means "this object/class is a geometry type"). Then our alternate approaches inherit from the TGeometry abstraction: TGeometryArrays, and TGeometryOcttree, which will both have a GetAdjacent(direction) function, but will implement them differently internally, because they don't use the same internal structures.

We'll also need to specify some storage methods, ready for an 'infinite worlds' model. These methods allow the game to 'generate', 'forget', and 'remember' various parts of the world as they are needed. Conventionally, this is called 'streaming', and if we do this well, it will ease the implementation of client-server networking (should we choose to branch that way).

Rendering

There are lots of ways that a world can be rendered from its data. One approach is to convert the data into conventional triangle geometry, and render it like most conventional games would. The other approach is to ignore the conventional rendering pipeline, and write a renderer that casts its own rays into the scene, and writes pixels to the display based on what is found by each ray (there are hardware implementation of this approach, but they're mostly proprietary, and we don't have the resources to implement another abstraction level to cater for all manufacturers of graphics hardware).

We'll be doing a lot of trail-and-error testing here. If performance is good enough, it's likely that we'll adopt a hybrid approach, using low-resolution ray casting to query the world geometry to generate a optimized display list of conventional triangle geometry, and have the hardware do what it's been finely tuned to do: render triangles.

Wrapping up

I hope that provides some insight into the abstractions we'll be using, and reveals some of our feelings on what we think will work well. In further blog posts, I'll describe some techniques in more detail, and perhaps touch upon gameplay.

Feasibility: passed, with reservations.

I normally do this with any project I find myself ruminating over: the Sanity Check (or more formally, "feasibility study", though I do call it a "sanity check" or "reality check" in case I'm being unrealistic, and just rationalizing an overactive imagination!). Before I go in feet first, I usually wait a few days after the initial desire to make something of an idea. Now is that time.

Did we pass?

In short, I think this passes the sanity check, with reservations. I'll need to remain focused, otherwise I'll be lost in irrelevant detail.

Why do most ideas need a sanity check?

So often on project forums, and for especially sandbox games, you see people with what seems a good idea for the game. They might open up exciting possibilities, but far too often they fail the sanity check. Just as a fiction author has to ensure that all the words are relevant to the story, so must a game designer think carefully before adding irrelevant details. It's very easy to write a two-line specification! Often the implementation will be several orders of magnitude more difficult to write.

Some issues that might lead this project to fail a sanity test:

1. There are already lots of similar projects out there, and this might prove to be a waste of time, unless this project is uniquely successful in some way.
2. This project is mainly driven by the development of technology. This could be a problem, because the resulting game should be compelling because of its benefits, rather than its features.
3. Will it be fun? (stealing a quote from Dwarf Forge material). I believe it will be, but mechanics and background technology alone do not create a game; other aspects must be designed in.
4. Is it likely to be completed? I don't know the answer to this question, and leave it open as a possible cause to close the project. Related to this is the amount of time I can realistically allocate to the project (not much).
5. Writing too much about the project, and not doing enough for the project [hint to self: like now!].
6. Lack of good research. Am I just reinventing a broken wheel?
7. A more successful project elsewhere. Someone might run with my ideas, but it won't stop my interest in this project (see below).

This Blog: Careless Bean-Spilling?

Also included in the sanity check is this blog! I'm aware that if I develop something that's commercially viable, and I've spilled all my intellectual property beans, then I'll have lost out on a good opportunity, and the cash will flow to someone else (after lots of hard work, of course). My reasons for writing this blog are various, but my main hope is that it will keep me focused on essentials, because I'll have to think carefully about how to describe new material (which should help cover all the eventualities when I imagine what pedantic readers might raise as faults), and there is also the possibility that committing this to a public blog will encourage me to continue at a reasonable pace, hopefully without making me a slave of the project. Writing about problems might give me a eureka moment, and I might even get hints from folk who know a lot more than I do!

Source Code: Open Source?

Related to this is source code. In the early stages, I plan definitely not to release source code. Instead, I'll publish illustrative snippets of code that show what I'm trying to do. Late stages: I'm undecided.

I should add that this blog and project are not about planting seeds to make money towards the end; I'm here because I find this interesting to me, and think there's a possibility that others might share my interest. By saying that, I'm not saying that a successful project won't then be commercially viable - I estimate the chances of that happening are slim - just that I'm not starting this as a business venture.

Summary

I think I have the checks and balances in place. My expectations are fairly realistic, and I'm confident that, given enough time, my methods will work, and we can reach a point where we have a fun and playable game. This passes the sanity check.

Next!

We'll describe abstraction, and how it will help us develop a quick prototype, and then allow us to introduce the difficult-to-develop versions that have better functionality. We'll also write about what is to be abstracted, and why.

A related sister-blog that might be of interest

It occured to me that if you're reading this blog, then you might be interested in another blog that I wrote in the past, which covers similar issues about game design, and briefly outlines an earlier (completed!) game project in these terms.

Blog: A Game of Invention, by the same author as Project Vol.

Introducing Project Vol

We'll start here!

After giving you a cosy welcome, I suppose I should get straight to the point, and tell you why this blog is here (jump to the 'Finally' heading if you want to skip the preamble).

I'm starting a programming project named "Vol", which is intended to create a digging game in a large (seemingly infinite) landscape volume.

It's fairly open-ended in terms of objectives, in that I have some objectives in mind, but I'm flexible about what happens.

There should be a nice picture here to give you a break from the text, and to draw you in, but unfortunately I don't yet have a relevant image to show you; I hope to be able to post images soon!

"I think I've seen this before"

If you've come here expecting a clone of something you've seen elsewhere, or think that this is "yet another... [insert name here] game project", then you'll not be far off in your assumption.

I'm fairly late onto the scene of voxel-based games and 'game engines' that incorporate voxels as a way of including complicated scenery, but I've seen good and bad features in projects like Dwarf Fortress (Nethack, etc), Minecraft (Infiniminer, etc), and the various indie and commercial efforts that use related techniques. I have some programming experience, so can read into their strengths and weaknesses, and hope to make good on some ideas that I'm keen to develop, which I hope will ultimately lead to good gameplay.

Specifically?

This project is mostly an exploration of techniques in rendering large solid structures in 3D space, using voxels, and organising them efficiently. I do have a game in mind, which is my impression of what would be an enjoyable game to play. As much as I don't want my game to be an obvious slave to a new technique, I reluctantly admit that the emergence of a playable game, in the form that I think will be most pleasing, depends on the successful development of these methods.

I'm not saying that I can solve all the problems, nor that I can do better than what currently exists; I'm here to explore and develop techniques, some of which might present exploitable opportunities, and lead to good gameplay.

Finally

Given that this is the first post, I'll keep it brief, and save details for further posts, where I hope to cover subjects such as memory-efficient storage, rendering options, gameplay design, procedural generation, lighting models, and programming techniques.

This will not appeal to everyone, but I believe there might be some interest in this subject among indie developers, particularly those jumping on the 'I want to create a game that has an infinite blocky landscape' bandwagon (go on, admit it!) ;o)

If you're eager to see content (videos, screenshots, downloadable working apps), then follow this blog, and your wish might eventually come true.

Last of all, I should warn you of one possible outcome of this project: I might learn that my ideas won't work. I'm not going to flog a dead horse, and I'll try to remember to give an appropriate heads-up warning if I feel that some avenues could be dead-ends, in case you are following a similar path.

Hm... I think I know what to write about next...