Sign-up for Email Updates:

Help Survive Development:

Development Blog
October 5, 2015 By: David Tse

This last week I started work on finally getting the world gen data into the game. There is still a lot of work to be done on efficiently streaming all the data in the background and rendering it efficiently, but I got a significant amount of the ground work done.

World Quad Tree

The first thing I did was rework the world quad tree system so I could very efficiently add and remove generation data as we move through the world. It's also vital for efficiently culling everything in the world when rendering.

This new design also revamps the entity system to use a more data driven and cache friendly approach than the old system. The way it works now is there are arrays of all the different types of data an entity needs and when we add an entity to the quad tree we simply store and index into these arrays.

Initial Test
View of roads loaded into the world quad tree after flying around with no unloading.

I also implemented a custom vector class that can grow at fixed size increments from a shared pool. This makes adding data to the quad tree very fast. With this new data driven design updating and rendering entities is going to get much faster which means more stuff in the world and more zombies!

Generation Data Streaming

Once the new world quad tree system was set up I started working on streaming the actual generated data chunks. This was already half solved when I designed the streaming format that all the data is saved to, so now it's just a matter of using that format to get the data into the world quad tree and remove it when it's out of range.

This streaming format uses two files, a look up table and the actual source gen data. We always keep the lut in memory then when we need a chunk we index into the lut based on the chunk indices to find out where the data is in the source gen data. Then we can load only that data and put it into the world quad tree.

So to stream the data we just load the chunks as they get in range. Once a chunk is loaded it's added to the resident chunk list. As we move through the world we check that all the surrounding chunks are loaded and load any that are not resident.

Right now the streaming chunks is mostly working, but there is still a ton of work to be done. Chunks get loaded as they get close, but they don't get unloaded yet and there are some issues with double loading existing chunks. So this next week is going to be about finishing the streaming stuff so we are loading and unloading chunks and then getting everything else to work again so I can release the update!

September 20, 2015 By: David Tse

This week and last week I was working on finishing up the world generation pipeline so that world data was flowing from one stage to the next and then exported in a stream friendly format. Like I've said before right now it’s all just about getting the data flowing between the stages and then into the game so the actual algorithms still need a lot of work.

Generation Optimizations

The first thing I did was make a change to the way road intersections were optimized. Before roads where split up into a regular grid of blocks spread across the entire world. Then it only intersects with roads in its block and its surrounding blocks. So the smaller the blocks the better the performance, but if we need blocks for the entire planet we are wasting a huge amount of memory and can only make them so small.

Initial Test
Higher level view of a bunch of cities with all their roads completely generated and split into the final export chunks which you can see in the road colors.

Now that the generation is done on a per city basis I give each city its own grid while generating so I can make the blocks really really small. Since it's a regular square grid there is no extra cost for having more blocks and because road intersection is the biggest bottleneck we get an order of magnitude speed up in generation.

City Block Generation

Now that roads are in their own block grid per city I started moving the block generation to its own stage and task. This step is rather straight forward and was just about reformatting a lot of code. The only real change I had to make was to use the city bounding box as the world bounds so blocks could be generated on a per city basis.

Final Export

This step required a little bit more work. Because we are giving each city their own chunk grid all the roads need to be moved to the global chunk grid that the actual game uses for streaming. After that I had to convert that data to the streaming format used by the game to get all this road, building, and terrain data into the game.

Initial Test
Zoomed in view of a few cities completely generated with block roads, and a few in the middle of generating block roads.

Real-Time Fixes

I also got a little work done on loading the data into the game. The first problem I ran into was all the custom binary files for the models and animations where broken. They broke because of the switch to 64-bit. I was only storing 32 bit sizes in the file so they were all incompatible with the new 64-bit binary.

To fix these files I had to get the asset conditioning pipeline that converts the source data to my quick binary formats. Once that was up and running in Atlas I converted all the assets and could actually load into the game! Something I haven't done in weeks because of my focus on the generation pipeline.

That's it for these last two weeks. It feels really good to have the generation pipeline fully functional and exporting the world data to the game. I'm also back into the game and ready to start working on streaming this data which is what I'll be doing next week.

Once the data is in the game I'll be able to start iterating on all the generation algorithms, which is when the development will really start to speed up and updates will start coming out much more frequently as the world gets more robust. The groundwork is almost done and very soon the game will start getting a ton of content on a regular basis.

September 4, 2015 By: David Tse

This week I was focused on getting the last two stages completely working so I could move to real time loading of the generation data. Last week I mentioned that there were some problems with performance when generating the city roads. This week was primarily spent trying to fix that issue.

First Fix

The first thing I tried was just general optimizations and multithreading, but it was still too slow to just sit there and generate the entire world when players are starting a new game. Especially when there was going to be even more time needed when generating the lower level city roads and building placement.

Initial Test
Example of one continent with fully generated cities. This was done in only a few minutes leaving plenty of time for future generation.

While I didn’t optimize the generation enough to be able to generate the entire planet all at once in a reasonable amount of time I did significantly speed up the generation which will help with iteration times in the future. In reality the vast majority of players will not travel to more than a handful of cities because they are all so large and dense so I don’t really even need to generate an entire planet all at once.

New Plan

The new plan is to generate all the cities for about one continent offline and then while you are playing it will generate more cities on a background thread when you need them. In addition to the significant time saving when creating a new world/game it will also save a huge amount of memory because only a subset of the world is being created initially. This plan will be adjusted and tweaked as we go on, but like I’ve been saying right now it’s all about getting this stuff in game so we can test it.

Initial Test
View of the entire map showing how much is actually going to be generated offline.

To actually be able to generate the cities both offline and in real time a number of changes had to be made and that was the focus of this week. The main thing I did was actually for multithreading the generation, but also really helps with offline/realtime setup. This was making all the cities generate completely isolated and on their own. This way they can be done completely in parallel and we can just do one city at a time in the background in real time.

To get this isolated city generation I had to make a number of changes and create a new system that manages launching the multithreaded tasks for each city. I also had to rework the stages so that the main city road stage would just run its own task and create the roads then pass that data to another task for the block generation. There is still some work to be done on the block generation integration and that’s one thing I’ll be working on next week.

So that’s everything I was working on this last week. In the next week I should be able to finish the offline stuff now that I know for sure how exactly I want to generate the cities. After that I’ll finally be able to start getting all this data in game and running around in huge procedurally generated cities!

August 27, 2015 By: David Tse

This last week I was mostly moving and setting up all my stuff at my new place, but the week before that I made some significant progress on the world generation pipeline. I missed the last weekly because of the moving so I’ll talk about the progress I made the week before. I’ll also be doing the daily updates on twitter again starting today now that I’m done moving and back to full time work on the world generation pipeline.

Initial Test
Picture of my new room/office.

Road Scale Preparations

If you remember in the last video I posted the cities were being generated as if they were the size of continents. That was just for testing the generation to get it to an ok point, but now this week was focused on squeezing all that down and getting them to generate at their proper scale.

Initial Test
Screen of terrain tiles all jumbled.

The first thing I had to do to get that working was split the terrain generation into tiled chunks so I could actually render them at the proper scale because opengl generally frowns upon anything over 16k and the world size right now just for testing is 1,000,000 meters by 1,000,000 meters. I will probably scale it up in the future after everything is working, but for now a million feels like a good number.

Initial Test
Same tiles now correctly placed.

Once the terrain was tiled and rendering I had to spend a little time on the debug rendering. Being able to move around the map and zoom all the way down to one city is vitally important when working on the generation algorithms. After all that was finished I shifted to moving all the city road generation code into its own stage and getting it to render at the proper scale.

Road Scale and Interstate Integration

The first step in scaling the roads down was integrating the interstates and the previous stages of the generation pipeline. So just like the rest of the work I’m doing right now I created a temporary, but working, population map. Right now it is just a simple circle around every city. In the future they will be randomized with noise like everything else.

Initial Test
Zoomed in screenshot of city road generation. Green Circles are temporary population, connecting lines are temporary interstates, and yellow lines are the roads.

In addition to exporting the population map I also exported the temporary high level interstates which need integrating with all the city roads. For now the high level interstates are just lines connecting cities. In the future they will wind through the map avoiding mountains, elevation change, and other terrain factors.

Initial Test
Same generated world as previous screenshot, but with view of the whole world instead of really zoomed in.

After that I just had to move over the system to its new stage in the generation pipeline and add a catalyst road at every city. There were some bugs and system issues that came up when changing the scale, but it was designed with this massive scale in mind so it wasn’t too hard. The only issue is generation speed. When we need 10s of millions of road segments generation efficiency starts to become a problem. That’s what I’m going too focused on next, moving the generation to multiple threads and optimizing the gen algorithms.

That’s pretty much what I did the week before last. It was a shorter week because of the move, but now I’m all set up and back at it 100%. So this next week I’m continuing the work on the pipeline integration and I should be moving back into the actual game world testing pretty soon now. Like I said at the beginning of the update I’ll be starting the daily updates again on twitter so be sure to head over and follow me!

August 13, 2015 By: David Tse

This week I focused on formatting the generation pipeline so each stage could be run on its own and save ALL of its output needed by other stages to disk. This is really important when I’m working on the generation algorithms because it allows me to only run the stage I’m actually working on. When some stages like continent generation take a few minutes to complete saving out that data and reusing it for future stages is a massive improvement to iteration times.

Right now all the stages are correctly loading and saving their inputs and outputs respectively and the next step is to do the final offline stage that takes all that data and efficiently packages it for steaming in-game. Like I said before all the stages are doing the bare minimum generation so don’t expect any huge improvements in generation over what I’ve already shown off. Right now it’s all about getting the data from start to finish and working in-game.

Initial Test
Very exciting screenshot of world generation pipeline intermediate files!

Again this week I spent most of my time on getting the pipeline flowing with all the correct inputs and outputs so all my progress is internal and there is no fancy stuff to show off yet. While this stuff is much less glamorous, getting the iteration time really low and setting up this infrastructure is vitally important to generating the realistic world the game needs.

So that’s it for this small weekly update. I don’t really like doing these small updates, but that’s just the reality of game development. Some weeks you need to do internal stuff and there just isn’t that much to talk about or show off. I did a little bit of the streaming work so I should hopefully be able to show off some of this world generation stuff in-game next week.

Previous Page