Coding In Transit: A Whole New World

Wow! It's been a long time since my last blog post, sorry readers it's just been a busy couple weeks. With a baby here it's a lot tougher to find the time to write for the blog. So, there's been some big changes to what I've been working towards with the engine. It all started when a friend of mine was visiting from out of town. He told me he had an idea for a game, usually I don't take much heed in these kind of suggestions but this one got me thinking. What he suggested was that it would be fun to have a racing game based around Google earth. So you could essentially race anywhere in the world. He thought it'd be fun to get the GPS coordinates for his morning commute to work and be able to create a virtual race out of it which he could post the coordinates online and then use it as a race track online.

So this got me thinking, someone must have created something like this before! Sure enough there's a few basic flash games, but not much substantial. So I started digging into what google provides as an API for querying their map data. Unfortunately its very very restricted, so I pretty much immediately threw that out the window. I started digging into open source alternative datasets and this turned into quite a rabbit hole! I found OpenStreetMaps which provides open source maps of the world to do with as you'd like. This gives me all the street data that I'd need to get my project moving but that wasn't enough for me. Given the voxel nature of my engine I wanted elevation data, I wanted to create a virtual voxelated earth!!

So essentially the game would be a cross of 3 different games.

Cube World( for the visuals ) http://wollay.blogspot.com
Outterra( earth simulator ) http://outerra.com
Final Lap Twin( for the gameplay ).http://en.wikipedia.org/wiki/Final_Lap_Twin

So the first step was to have a look at the data available from Open Street maps. I downloaded the data for British Columbia and it was huge! 5 gigs of data! It was tough trying to find anything that would open it so the first step was to split it up into some smaller files. I wrote some quick code to split it up and had a look. The data was stored in an xml format so it should compress quite nicely when I convert it to a binary format. Since Tiny XML would choke on this giant file I put the OSM data aside for now and started digging into elevation data, there's a lot of different options. GMTED, SRM, after more digging I found this site http://www.viewfinderpanoramas.org/dem3.html. It's pretty much the goto place for elevation data.

My goal is 1 meter by 1 meter resolution and the DEM files are roughly 20 meters by 20 meters with a 1 meter resolution on height. My inital attempt was to render the DEM files as voxel sprites. Needless to say trying to render a 1201x1201 * 20 voxel sprite blew up immediately, not enough memory to create the vertex buffer. I figured as much, so my next attempt was to split things up into 128x128 chunks. I was able to get 5 chunks rendering at a time, this wasn't really enough to make this plausible.

So I had to rethink how I was going to render this massive amount of data, thats when I thought to try splitting the data up into a quad-tree structure. So the closest chunks would be at 1m x 1m, next set would be 2mx2m, then 4mx4m and so on and so on. I split the terrain up into 32x32 blocks and this worked great. There was 2 downsides though, memory usage was still way too high and it took about 6 seconds to regenerate all the blocks every time the camera moved to a new chunk.

The first thing to do was to throw the generation into a separate thread. This at least got rid of the massive 6 second hitch everytime things had to be regenerated, but it still meant we had to wait 6 seconds to see the new terrain data. So I had to start optimizing my voxel generation code. This was kind of a win win because it also meant that my regular voxel sprite generation would get the benefits. So I started rejigging how the data was stored and trying to optimize for maximum cache efficiency, this was about a 2 week process that resulted in a drop from 6 seconds to 1 second! This was much more reasonable but it still wasn't quite what I was looking for! I wanted real time generation at most a frame of lag. So I had a goal 33ms generation time, maximum!

This meant it was time to rethink using voxelsprites for the terrain. I created a new class called TerrainVoxelSprite which initially was a duplicate of voxel sprite. I had an idea to speed things up. Since I was using DEM's for the terrain and they're just a height why not just store a set of height values rather than a true chunk of voxel data. Then when rendering, still render everything as boxes so it looks voxelated. Not only does this cut down on memory but it also sped things up consiiiiderably. I decided to cut out the color data out of the vertex, to improve memory usage even more. With a few more optimizations I finally had my 33 ms generation time and I was able to load the entire 1201x1201 dem into memory as voxelated data. But wait you say, it's not really voxels anymore!! True but my plan is that if the user wants to edit a chunk that chunk of data can be swapped out to a voxel sprite without anyone the wiser. With the massive amount of space it would take a loooong time for users to change everything into voxel sprites.

Now that I had things running the way I wanted at the speeds I wanted I could finally spend some time on the shaders. I went to work implementing some initial lighting, applying some color based on height and an initial distance fog implementation. It's not much to look at yet, but it's a start.

So that's kinda the quick gloss over of what I've been up to for the last two months. Moving forward I'll try to go into more detail on the various parts of the new codebase. If you guys have any questions or interest in a particular area of the dev, let me know in the comments!