It’s now month two of the development of my SeedWorld engine and the game it will be used for. In the first month I have already made a lot of progress for it. The features I’ve done that month are:

• A voxel rendering system to draw a world out of cubes
• Procedural generation of landscape and trees using noise and shape functions
• Optimized loading and streaming of voxel chunks, including multithreading
• Move a box around the world, interacting via physics and collision detection

The engine is shaping up to be a good tech demo already, so here’s hoping for another productive month. This week I’ve already pushed two more features, one being a rendering code change and the other one is completely new and related to world generation. So get ready for a long post, there is a lot to cover here.

Building a larger world

First I will talk about the world map generation. No doubt many people who wondered how to procedurally generate a world map have ran across Amit P’s article on polygonal map generation. I wanted to run with some of these ideas and kept them in the back of my head. Turns out that someone already made an XNA implementation of Amit’s code to make randomized 3D islands with it. I downloaded the source and ran the program, but in the end the code was too overkill for me. I have to start with something more simple. Here is a picture of a finished map with the results of work I did in one night.

With that said, I did not follow Amit’s approach to make islands, not even closely. But I do know I wanted to generate the map using Voronoi diagrams. Also, I will eventually add specific biomes for the map, which is one of the reasons why I am doing this. The world will be big but finite, and heights and biomes will affect the way voxels are drawn and rendered from the player’s point of view.

I made a new ScreenElement class for my game’s Screen System to put all my code in and test it. The awesome thing about using a system for game states or screen states is that you can experiment with things in a stand-alone state like a mini program. To generate the height map, I use the same Simplex noise functions, but layering on just two noise patterns of different frequencies. Then I add a height mask to lower the elevation on the edges of the map, so all sides are surrounded by ocean.

The noise function and region plotter take a seed to generate the map, and pressing a key generates a new map from a new random seed. They are all made by pseudo random number generator, so the same starting seed gives you the same list of maps every time. The process takes a couple of seconds to make a map of the size above, but this will only be done once per new game when a new seed is chosen.

Batching the models

After deciding I’m good for now on the maps, and get to the biomes later, I moved on to plan rendering of object models other than the chunks of voxels/blocks. Since the beginning, the Chunk class had its own Draw function to render the mesh with. The wireframe box used to test movement in the world is drawn with a BoundingBoxRenderer class.

This was not going to scale well with different kinds of objects like monsters, items or NPCs, so I decided, before I can even begin to turn that wireframe box that represents the player to a solid one, I should refactor my rendering code to be more flexible. I took ideas from the XNA SpriteBatch class to draw models in batches, taking in their transformations and current effect and drawing it in one go. The default way is to defer rendering of sprites until you call SpriteBatch.End().

Similarly I created a ModelBatch class that loads different meshes to a Dictionary structure, using meshes as keys and lists of matrices as the values. This way several transforms can apply to one mesh to render the mesh more than once. Like SpriteBatch, you can start and end it a few times each frame to separate the batches by effect or render state. This gives you a more organized way to render different groups of objects with different effects. The ModelBatch pseudocode is as follows, as briefly as I can describe it:

class MeshData
{
    public IndexBuffer ib;
    public VertexBuffer vb;
    public BoundingBox bBox;
}

class ModelBatch
{
    private Dictionary<MeshData, List<Matrix>> meshInstances, cachedMeshInstances;
    private Queue<MeshData> meshQueue;

    private int initialBatchSize = // some large enough number

    // Other rendering resources such as graphics device, current effect,
    // current camera and renderStates go here

    public ModelBatch(GraphicsDevice)
    {
         // Initialize data structures, reserving a size for each with initialBatchSize
         // Queue gets size initialBatchSize + 1 for insertion purposes
         // Set GraphicsDevice
    }

    public Begin(Camera, Effect, RenderStates etc.)
    {
         // Set current effect, camera and renderStates here.
         // RenderStates can be applied here instead of in Draw()
    }

    public Add(MeshData, Matrix)
    {
         // Matrix is the world transformation for a mesh
         // Search meshInstances for a matching MeshData object
         // If found, add the Matrix transform to its Matrix list

         // If not found, search cachedMeshInstances for a match
         // If found in cachedMeshInstances, clear Matrix list and copy to meshInstances
         // If not found in cachedMeshInstances, add MeshData and new Matrix list
         //    to meshInstances
    }

    public Draw()
    {
         // Set effect parameters that apply uniformly for the whole batch
         // (camera view, projection, etc.) For now, the default technique applies.

         // For each MeshData and Matrix list in meshInstances
         //     set vertex and index buffers

         //     For each Matrix in Matrix list
         //         Set world transform for the effect
         //         If in frustum view, draw the mesh with this transform

         //     Finished rendering instances for this mesh, check if it's present
         //     in cachedMeshInstances. If not found, add it to the cache.

         // Done drawing all meshes, clear meshInstances
    }
}

Some things not mentioned in the code are checking for null index buffers and vertex buffers, frustum culling details and using the meshQueue to limit cache size. The last one is important enough to mention, though.

First, I decided to use caching because frequently emptying and re-filling a Dictionary with a large number of meshes (such as the voxel chunk meshes) adds a lot of memory to the managed heap, calling in the garbage collector every couple of frames. Before switching to this code, the Chunk objects always kept a local copy of the mesh and didn’t need to pass it anywhere else so this wasn’t a problem until now.

This is why the Add function checks the cache Dictionary first, so it can avoid copying a reference to a MeshData object and just reuse the old one. It’s not guaranteed if the matrix transformations remained unchanged from the last frame, though, so these always get newly copied.

The Queue of MeshData is for keeping a constant size for the cache. Without it, the cache won’t function properly and the ModelBatch will continue to grow the cache as it finds more unique meshes to render. This becomes a problem as you move through the world and new Chunk meshes need to be created, as well as other meshes for different monsters and randomly made NPCs.

For it to work properly, the cache should remove the oldest MeshData to make room for a new one. The MeshData queue does this well, removing the object from the start of the queue in order to remove the oldest object from cachedMeshInstances. The code reads like this:

// Done rendering a mesh, release it to the cached list
if (!cachedMeshInstances.ContainsKey(mesh))
{
    // Add to cache if not found already
    cachedMeshInstances.Add(mesh, new List<Matrix>());

    // Limit cache to batch size if it's reaching the size limit,
    // removing the oldest mesh
    if (meshQueue.Count == initialBatchSize)
        cachedMeshInstances.Remove(meshQueue.Dequeue());

    // Add the new mesh to the queue
    meshQueue.Enqueue(mesh);
}

Additionally, the cache must be set a large enough size so that the game will always have a lot of empty positions to fill meshes with. If the cache is too small, there will always be more unique meshes to render than there are items in the cache, causing the cache to change every frame, even if no new meshes are introduced to the batch.

The queue/cache size depends on the implementation of the scene. For instance, if I know I will have about 2000 chunks rendered at maximum (since the view radius is fixed), I might want to reserve a size of at least 3000 for meshes scattered on the ground, characters and items. This sounds like a lot, but the memory increase from these data structures is not really much compared to the actual mesh data, and most important of all, no frequent heap allocations/deallocations.

Those familar with XNA might notice that the behavior for Draw() is similar to SpriteBatch’s End(), and Add() to SpriteBatch’s Draw(). I chose these function names because they make sense to me, but I’ll probably have them changed to the SpriteBatch names for consistency.

Next I’ll start work on adding mesh support to the Player class in order to have something for the player avatar, using the same ModelBatch to render it.