Map Making and Model Batching

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.

Posted Image

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)

    // Add the new mesh to the queue

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.

Tagged with: , , ,
Posted in Engine, Graphics

First video, and more collision response

Started off the new year well with my game. I finally got to the point where my collision box code works almost the way I want it to! I say “almost” because there is one slight bug but nothing really game-breaking. Adapting some code from the XNA platform game sample really helped also. The most difficult part is adding in the Z axis for proper collision response with horizontal movement, and last night I was fudging around with the code a lot until I got it to work predictably and sensibly.

Also, I have uploaded the first video of my voxel engine in action (in 60 FPS to boot). This recording is actually 2 days old, so no collision box demo here.

Since the phsyics code is based on a platforming game sample, I’m also left with many arbitrary numbers for variables to compute things such as drag, jumping time, acceleration, etc. I understand the code in which these numbers affect the movement but I don’t like how the numbers don’t seem to have any meaningful relation with each other. Oh well, at least I can use them for many things, like reducing the drag when you’re on slippery surfaces.

Other updates include some changes to the graphics code to get it to work with the XNA Reach profile. This didn’t involve many changes, just limiting the number of vertices in each buffer to a 16-bit amount and changing some shader semantics. I really want to keep this compatibility, because I want the visuals to be simple yet still look great while running on low-powered graphics cards, in order to attract more potential players. The video above might as well be running on the Reach profile, as it looks exactly the same.

Back to the collision code- the slight bug I found is that when you collide with a wall, you keep sliding in one direction until the bounding box touches the edge of the next block. This only happens moving in one direction along each axis (eg. I can slide indefinitely while increasing on the X axis but not decreasing), but you do not get stuck on the wall, you just stop.

So I can now render a bounding box that moves around in the world and can jump. The camera is still not tied to player movement, and makes movement awkward. So that’s next on the list of things to fix. After that, I will post another video showing it.

Tagged with: ,
Posted in Engine, Game Physics, Graphics

Better trees, lighting, and now, collision detection

This is probably the last entry I’ll add this year, so I hope it’s a good enough one! My SeedWorld engine has now reached a milestone- the first physics code. Also, the trees are generated more realistically and lighting is much improved.

I have raycasting code for emitting rays from every visible voxel and shade it a different darkness, with falloff applied for distance. This is all done on the CPU for now but I would like to use the GPU if possible. Here is a visual example of the ray casting stepped in cubes.

Ray projection

The code still has the limitation of not being able to check voxels of neighbor chunks, but the falloff of shade is so great you’d hardly notice these inconsistencies unless you look straight up at the bottom of an overhang (such as under a tree). I want to correct that later.

Also, some normal-based ambient lighting! It is simple but can have a drastic effect on the image. Each side of the cube can be lit with a different ambient color, so it is like sampling indirect lighting from a sky box texture but much simpler since cubes have only 6 sides. This Wolfire article gives a simple explanation of how it works. It looks much better than having the same dull gray color on all sides. Diffuse colors are also gamma corrected on the shader.

Here is a scene showing just the ambient lighting added to the regular shading from the normals:


And the same scene with the diffuse color multiplied:


Colors pop out a lot more now, everything looks more vivid which is the look I am going for. The ambient colors are hardcoded for now, but will be dynamic when I get a day/night system going. Colors are still too bright, but that was fixed. The lighting was adjusted some more.


Also you may notice that the trees are a bit more complex in shape, at least with the leaves. I generate the “boughs” in random sizes from the center, going in a fixed radial pattern. Each tree can have from 4 to 7 of them. This makes better looking trees than just randomly positioning them from the center, which made some trees look very unbalanced.

Shader code is also refined and the vertex data as well. Up until yesterday, all the chunk meshes are rendered with the absolute positions sent to the shader. Now I just send the local positions and transform with a matrix. To be honest, I peeked at the graphics in Cube World for an idea on how it does things, using PIX. Its approach is interesting, because none of the vertices in view exceeded absolute values of 300 in world coordinates, after the vertex shader is applied. It seems that not only does it just use local coordinates but also makes the world “scroll” around the character so as to keep everything near the origin.

Since the cubes are all located in integer coordinates and chunks are all 32 units in size I was able to greatly reduce the number of vertex data to pass to the shader. Each coordinate is now stored in a Byte4 instead of a Vector3, as was the color and normal information. This reduces the vertex size to a svelte 8 bytes. The fourth byte, usually the w component, can be used to store additional information such as AO shading, and possibly material properties that affect how it reflects color. So now the AO is added to the color in the shader instead of “baked in” the vertex. This makes lighting much more flexible to change.

First Collision Detection

Another important step forward in the engine is built-in collision detection. So far all I have to show for it is keeping the camera above the surface of the ground. A bounding box is made around the camera, the code compares the position of the box in the world to get the nearby blocks and checks if any of them is solid for a collision. See, just like 2D tile collision. The collision response is crude- it just moves the camera one unit up when the box collides with the ground. Later on I will add intersection functions to test the depth of intersection, needed to do some meaningful physics with characters and other objects.

The way I get the blocks from the world is kind of crazy. It is a function that actually re-generates all the procedural data required to find out what type of block is in a specific location. For now that just means getting the height value from the noise functions at a particular location, but I’ll add in somehow to check if other objects are being built that will occupy that block so that the camera can collide with the trees as well. The reason it’s done this way is to save time (for now) but also because when chunks are generated, all the block/voxel data stored in the cache falls out of scope after the mesh is made, and is replaced with the data from the next chunk. The chunk objects are mostly left with just the index and vertex buffers to render it.

This way of getting the blocks is actually very quick because the bounding box doesn’t intersect with a lot of them. I’m curious at how well it will work with many moving things on the screen, especially ones almost as big as trees. Fortunately my game will not feature a lot of block creation or destruction, so that helps as well. Eventually, though, I want to store another cache for the nearby block data.

Later on, I’ll start work on the Player class, its collision detection, and also code a camera that can be moved around the player for easy navigation.

Tagged with: , ,
Posted in Engine, Graphics

Proceduralize all of the things! More terrain progress, and trees.

Here’s some more progress on the SeedWorld voxel engine. Last week has been mostly occupied with tweaking stuff- tweaking noise outputs, heightmap parameters, and color gradients. It’s been a ton of trial and error to get a landscape that I was happy with, but I think I needed a new perspective in order to not burn myself out on it.

I added some basic voxel shadow casting code. All it does is, for every X, Z coordinate on the surface, start from the topmost voxel and move down, checking if a voxel is solid or empty. The first solid voxel blocks sunlight and the rest of the voxels are darkened. It’s simple, but with some shadow smoothing the effect will look even better.

I know how to make a landscape that can alternate between long, mostly flat plains and rolling hills and mountain ranges. But the more I looked and moved around it, the more it looked the same. It looked boring. But then I remembered that the environment was far from complete. There are no trees, boulders or other clutter filling up the place. So I decided to start adding trees. The first step I took was making a function that can produce a voxel sphere. These were the leaves for the tree. Then I added a square pillar for the stump.

Posted Image

Now at least I’m getting somewhere. Here are a bunch of spheres casting shadows on the ground.

Posted Image

Enjoy that green while it lasts, because I soon removed it. This helped me just look at the details of the landscape and not think of how repetitive it looks with everything being grass green. All the code for coloring voxels was hard-coded into the Chunk class, and this had to be moved sooner or later. Voxel color of natural features will probably be controlled by Biome classes or something similar.

So for now, everything is colored white with AO and directional lighting. Here are some screenshots of Grayscale Land.

Posted Image

Posted Image

The only condition for the tree-generation code is that they are to be placed where the elevation is lower than 80. But trees don’t naturally occur in such an orderly fashion, so it’s time to mix it up. My tree generation code consists of finding a surface voxel to “plant” it, and then use some loops to place cubes near the bottom for the trunk. For the leaves, a function to determine whether a location is inside a sphere is used. Leaf cubes are placed anywhere it’s in the sphere.

The placement now needs to be randomized. Each chunk can be identified by its location in the world, and I can use a pseudo-random number generator that will have a different seed for each chunk. Here is how I determined the seed:

chunkSeed = ((chunkOffsetX << 16) + chunkOffsetY) ^ worldSeed;

The chunk’s 2D location creates a 32 bit int that then is XOR’ed with the seed that is used everywhere for generating the surface of the world. You might notice that if you walk 65536 blocks in one direction (maybe if you’re a voxel granddad) the same seeds will be produced again. I don’t think it’s an issue for now, as that’s a very far distance to travel and repeated object placement will likely go unnoticed if you are moving around the world for that long. The world seed will still have an influence on this item placement later on, so things may not even be 100% the same then.

Random values are used for almost everything in tree generation, from its location in the chunk, trunk height and foliage dimensions. Spheres can now be ellipsoids and I can probably add several of them in one tree to make their forms look more varied and natural.

There will be cases where parts of the tree will intersect other chunks, so other chunks need that tree information. What did I do here? On every chunk, I actually compute the random values for all 8 chunks surrounding it, and then piece together that information by attempting to render parts of the trees on each chunk.

That sounds terribly inefficient on paper, and it probably is, but the chunks are still made as fast as ever. The tree generation code is still fairly simplistic compared to computing 3D simplex noise, plus I do not have to loop through every single voxel to see if something needs to go there (I’d have to check for out of bounds voxels anyways, otherwise the program will crash for trying to access an array element that isn’t there).

So here are the results of how that looks:

Posted Image

(Not Bad image macro goes here)
Keep in mind this is with just one tree randomly placed in each chunk, where elevation is below 80. I first thought I needed 3 or 4 trees per chunk to look decent, but I plan on making the trees bigger anyways. A dense jungle might get away with 2 per chunk, though.

Next, I’ll refine the tree generation to make more interesting shapes for the trunk and leaves, and then work on varying the colors with the trees and terrain!

Tagged with:
Posted in Engine

The Start of a New World Part 2: A first look at my progress

I’ve been working a lot on my voxel game engine. For now it just renders voxels and most of the work has been on adding more rendering features to it, but it’s progressing well. The game is being made with the XNA framework, and eventually I would want to port it to MonoGame in order to get it on non-Windows platforms.

I am still facing a lot of technical issues which is to be expected early in developing something, but still made a lot of progress. I finally have a octave noise function that I am very satisfied with, in creating those very believable rolling hills you see a lot in procedural landscapes. Here is the breakdown of the current technical specs of the voxel world generation.

  • Voxel data is discarded as soon as chunk meshes are made. Chunks store only vertex data at the minimum*
  • Far draw distance (I want to emphasize this in faster PCs)
  • World divided into 32x32x256 chunks, with an area roughly 2000×2000 in size for the visible portion
  • Multi-threaded support for voxel and mesh generation

Future specs include:

  • Material determines the attributes in game, color gradients, and sounds for interaction feedback
  • Persistent storage for voxels only in the player’s immediate surroundings*
  • Different biomes which affect the visuals and interactivity of the materials

*This supports interactivity for making the world destructible, but only where it makes sense (near the player), and keeps the managed memory footprint low.

The First Week

I started working on this on December 6th, and made some decent progress by Sunday night, making a cube world with 3D Simplex noise and some mesh optimization to avoid rendering hidden cubes.  To get a head start I picked out some pre-existing code to make 2D and 3D Simplex noise. I quickly learned how the noise functions readily make a continuous texture without being repetitive, as it’s of huge importance when making a procedurally generated world.

The custom shader is very simple and low bandwidth, taking only a Vector3 for local position and a Byte4 for color. The mesh-building code also adds a shade of green to cubes that are visible from above, and the rest are brownish in color. This creates a somewhat convincing grass-and-dirt look. Finally I implemented some basic brute-force culling to avoid rendering invisible chunks. Quick and dirty procedural world!

Posted Image

Posted Image

Some problems I found with this voxel-cube generator were, I frequently ran into out-of-memory exceptions when I decided to go any higher than 192^3 cubes. I was splitting the world into 32^3 sized chunks but it didn’t really help out the memory problem. My guess is that the triple-nested loops used to calculate the noise values are wounded too tight, and it might benefit from single-dimensional arrays. Also, I was storing the chunks in a resizable list, but it makes more sense to have a fixed sized array to be able to keep track of them. Also, while interesting to look at, the shapes produced by 3D noise weren’t very desirable so I switched to 2D to make a more believable height map. From there, I will then experiment with some 3D noise to get some interesting rock formations and caves going on.

Improvements in Terrain Generation

When I was still tweaking with different combinations of noise patterns, I could only come up with very large smooth, round hills, or many little but very bumpy hills. No repetition, but very bland to look at.

I had the basic idea down- combine many layers of Simplex noise of different frequencies, offsetting the X and Y for each of them just a little. But I had a derp moment when I realized I should be reducing the amplitude (effectively, the height variation) as I increase the frequency for best results. JTippets’ article on world generation really helped here.

Here are some screenshots of various builds, in order of progression. Here is “revision 2”.


Posted Image

Already in this revision I have added optimized mesh generation to remove hidden faces. The wireframe render shows this well.

Revision 3 shows the vast improvements in terrain generation that I mentioned previously. The draw distance is improved, and noise patterns create much more natural looking hills and valleys. Color is determined by height variation and whether or not the block is a “surface” block. The white patches you see are sides of steep hills that don’t have the top face visible.

Posted Image

Between revisions 3 and 4 I was trying out ways to speed up voxel generation, mostly with octrees. That didn’t work out as planned, for reasons I will state later in this post. So I went back to my previous way of adding voxels. The biggest feature update here is simple vertex ambient occlusion through extensive neighbor voxel lookups.

Posted Image

Posted Image

It is a subtle update but it greatly improves the appearance of the landscape a lot. I applied the AO method that was discussed in the 0FPS blog. The solution is actually simple to do, but the tedious part was combining the numerical ID lookups for all the neighbor voxels so that each side is lit correctly. I should really change those numbers into Enums for voxel locations so the code is less confusing.

Here is a screenshot just showing just the AO effect.

Posted Image

It is around revision 4 when I also made a Git repo for the project, and it has also been uploaded to a private Bitbucket account.

Performance stats, you say? Unfortunately I am not yet counting the FPS in the engine and I believe my stopwatch use of tracking time for chunk updates is wrong, because when it reads 15 milliseconds (about 67 FPS) the program becomes incredibly slow, as if it was updating only twice per second, but at 10 milliseconds or less, the program runs silky smooth without any jerky movement.

What I can tell you, though, is that currently I am sticking to update just one 32x32x256 chunk per frame in order to keep that smooth framerate. At 60 chunks per row, It’s still quick enough for the world generation to catch up to movement up to around 25 blocks/second. This is throttled by a variable that I can change to tell the program how many “dirty” chunks per frame it should update. My processor is a Pentium G3258- a value CPU but still decent for many modern games (as long as they are not greatly dependent on multi-threading), especially since it is overclockable. I have mine overclocked to 4.2 Ghz. If you have a CPU that can run 4 threads, has 4 cores or more, you should be able to update several chunks per frame very easily.

About using octrees- I did not perceive any performance gains from using them so far. I wanted to use octrees as a way to better find potential visible voxels without the brute force option of going through all the voxels in the array. The good news is: I got the octrees to technically work (also did some nice test renders) and I also learned how to do so using Z-curve ordering and Morton encoding. At least I gained some interesting knowledge there. Bad news: reducing the amount of voxel lookups with octrees did not result in being able to quickly update more chunks per frame, which was the ultimate goal. So I am putting aside the octree-related code for now and maybe it will come in handy later.

Persistent local voxel storage concept, and future updates

The persistent storage for local voxels is definitely something I want to implement, and make a key feature in my engine. Keeping voxel data for the entire visible world is usually wasteful and it only makes sense really to know what you will see immediately around you. After all, if you have a pickaxe, you are not going to reach that block that is 500 meters away. This data storage will update as you move around the world, storing at the most 4 chunks worth of voxels.
This can be applied further with other objects that may interact with the world surface. Say you are a mage that can cast a destructive fireball. Upon impact, you want to calculate the voxel data for the area around the fireball so it can make a crater. Or an ice ball to freeze the surface. Obviously you want these calculations to be done very quickly, so it sounds like a good way to stress test the engine with lots of fireballs and who knows what else being thrown around.

Other more features I want to add soon are the creation of pseudo-random rock formations and measuring slope steepness which will help in generating other pseudo-random elements. Probably gonna add those voxel trees first, in order to add more to the landscape.

Tagged with:
Posted in Engine

The Start of a New World

Welcome to my first post! This blog is made to document the progress of a new game I’m making, codenamed SeedWorld. I have several years of hobbyist game programming experience, and work as a web developer. My previous blog, Electronic Meteor, will give you an idea of what I have done, and this time I decided to start on a new game and dedicate a blog to it.

SeedWorld started out as an inspiration from the game Cube World, which is being worked on by two people, and currently in an alpha stage. However, recent updates have been… lacking to say the least and it has disconcerted a few people. I have an alpha build from 2013 and though I have only recently started playing it, it has shown a lot of promise. Like a few others I was inspired by this game to make my own voxel world engine and then build it up into something more substantial. Also a shout out to Giawa whose blog I just discovered yesterday, it is always nice to find other developers with similar goals as your own.

My next post will start to cover the development of the engine and game. It’s going to be somewhat long of a post, so I hope you enjoy it!

Posted in Uncategorized