In the last years I have been developing a game engine called Wurfel Engine. A big part of the following is an excerpt of this paper (in German) explaining some algorithms and solutions I discovered during my final exams in school and improved in the last two years.

Most of the following algorithms can be found in the Wurfel Engine SDK, an open source game engine written in Java I have been developing the last years. Currently I am working on the commercial title Caveland using the engine.

Storing the map data with chunks

An easy approach for storing the tiles is to use a diamond map. A diamond map is just a rotated regular grid (fig. 1). 

fig. 1

This is great if the whole game takes place on a small map. However, if you require to implement a huge (open) game world or generate the map content, you need to stream the data. To do so you must be able to load the data in chunks. But does streaming work with diamond maps? If you use a diamond map format, your chunks will only align seamlessly if aligned like this:

fig. 2

The gray rectangle represents the screen. As you can see you need more chunks to cover the screen. However you want to have the chunks aligned like this:

fig. 3

Therefore Wurfel Engine uses a row shifted grid, usually called „staggered map“, which is great for map streaming. In a staggered map each second row is shifted by half a tile. 

fig. 4

When having only the blocks in RAM which are near the camera one encounters the problem that one can only simulate the entities which are also near the camera. This works for most games. If something outside the area currently covered should happen, which may be important for the gameplay, you must keep more chunks in RAM.

Accessing and storing the chunks

There are several ways to store data, in this case the chunks containing the blocks. We want the fastest access to the data possible which means access in O(1). An easy way to achieve this for voxel worlds is by using a 3D array. For a very long time I had been using one big 3d array. Newly streamed data, the chunks, which  are some smaller 3d arrays, would be inserted into the big map matrix and the rest of the data moved or was removed from memory if they were now moved outside the visible area. I used this design for a long time because it worked fine.

This solution has a flaw as it allows only one viewport. What happens if you want to implement split screen play in an open world? Both cameras can be at completely different places, but the map does only work if you are at the same place. I solved this by storing the chunks each with a 3D matrix in a pool (currently I’m using a simple list). In order to find and get the content of the cell belonging to a game coordinate you only need to store a fixed point for each chunk and the chunk dimensions. You can then iterate over the list and check if the chunk covers this coordinate. If this is the case, you can calculate the index position by subtracting the fixed point at the corner.

Custom iterators are a good tool to traverse the whole map comfortably.

fig. 5

Reducing the RAM usage for mass storage

Depending on the game you need to store a lot of chunks and / or blocks in memory. Storing each block with dozens of fields at each several bytes big can grow very fast in memory consumption if you have thousands of blocks in each chunk. Currently I am experimenting with a version where I store only three byte to represent a block. If they are covered by the viewport of the camera, they get transformed into richer objects with more fields needed for the rendering methods. This method saves so much space that it should be possible to have an area of 1800 km² in memory with only 200 MB.

A better way to implement Screen to Game

If you are using a diamond map, your rows are not shifted and you are not in need for the following method because you can get the selected cell by rotating and distorting your screen space coordinates to game space and then discretize the values. 

Using a staggered map discretizing screen space’s x and y coordinates results in ambiguous  results between two tiles. 

Two common approaches exist to identify the correct tile. One uses some color coded graphic (fig. 6) to identify the corner of your mouse click. This is rather a hack which is not easy to implement and very static for changes to the tiles dimensions and can result in wrong results if anti-aliasing mixes colors. The other calculates the euclidian distance between the center of the tiles and takes the closest one. I found another simple way to do this which has some nice side effects. It is dynamic and supports different tile sizes by using some inequations to detect the side.

fig. 6

You can get the same result as in the picture approach in some graphing calculator (fig. 7) if you use the  following equations:

fig. 7

Of course you can also distort the tiles by multiplying x and / or y with a factor.

If you take a look at the graph, you can see overlapping areas. By checking for two fulfilled equations you can identify each of those areas and detect if some point lays in some adjacent neighbor.

Once you have this method implemented you can also use this method for getting the cell-coordinate to any point in game space which makes this a very powerful tool.

Intelligent clipping in isometric worlds

Isometric game worlds are usually flat. Sometimes tiles are also flat, but often three dimensional tiles (blocks) are used because they can be moved in height. Rendering a flat world is usually not a task limited by performance. However, Wurfel Engine uses a cubic volumetric map. You can stack many blocks on top of each other which results in many overlapping blocks. Doing no custom hidden surface detection (HSD) would be fatal because for lots of non visible pixel the fragment / pixel shader is executed.

A simple way to boost the performance is to split each block in three sides with three separate sprites. You render only the top side and both front sides only if no blocks are in front and covering them. For this algorithm a loop over every block is performed and its direct neighbors are checked and according to them the clipping is set.

When using distorted dimetric blocks so that the projected height equals the projected depth (fig. 8) it is possible to perform some efficient clipping.  

fig. 8

I did this by sending three rays for each block (fig. 9), one ray for each side, through the map and check when they hit some visible side. Each ray is split into two more for each half of the side. There are some cases where some block covers one half of the side and some layers deeper the other half of the same side is hidden by another block (fig. 10).
Every hit side then gets a flag („not clipped“). The renderer then only renders the sides which are not marked as clipped.   

fig. 9

fig. 10: the back block has its left side hidden but no direct neighbor block

However, for artistic reasons the dimensions were switched to true isometric blocks. They have the problematic characteristic that they do not align in the projection if you stack them because the projected height is bigger then the projected depth. You can see this in the image (fig. 11): Not every corner is aligned in a grid. The ray tracing clipping only works with the assumption that blocks cover themselves evenly. So the clipping algorithm via ray-casting had to be dropped and replaced with the more simple algorithm I already described. The problem with this one is that it cannot detect the cases where a block is hidden and there is some space between those blocks e.g. when a block is covered by a wall or a ceiling.  

fig. 11

Both of the presented clipping algorithms should only be performed when the map content changes and not at each (update) tick.

Summary

Depending on the use case and the requirements there are several more and different ways to build a similar and efficient game engine. Each design choice should be made with care starting at the dimensions of the blocks. In the field of voxel engines many approaches for fast and memory saving architectures can be found which can be used for further research.

Benedikt S. Vogler is an independent game developer and student of media informatics.
You can follow him on twitter.