Sign-up for Email Updates:

Help Survive Development:

Development Blog
November 5, 2015 By: David Tse

Over the last few weeks I’ve got quite a lot done on road generation and streaming. I’ve also decided to move from a development update every week to less frequent, but more substantial updates every 2-3 weeks. This way I can give you guys better updates and have more time spend working on the actual game.

I’ll still be doing daily updates about the stuff I’ve been working on over on my twitter if you want more frequent news about development. This update will be larger than future updates because it’s been a month since the last update and there has been a ton of progress. So strap in because there is a lot to talk about.

Generation Improvements

While my focus is still on getting the generation pipeline completely flowing from start to end before working more on the generation algorithms, I did have to go back to generation and make some changes. These changes where necessary for streaming the roads and creating correct meshes for them.

The first thing I had to do was convert the road generation system from creating and saving individual road segments to creating and saving out continuous splines. Having the spline data makes creating the interstates and the actual road meshes much easier. This is also needed to handle different types of roads and their intersections.

Initial Test
High level view of the interstate generation. It's a little hard to tell whats going on, but each Color is a different interstate. You can follow a color to see all the cities it connects. This is before the noise pass so there are just straight lines connecting interstates and it doesn't look that great.

Since we are generating splines now, I also had to change the export of the road data to split up splines along chunk bounds. I then had to add extended point data at the end so splines are still smooth along chunk boundaries. After that it’s just about saving the splines instead of a list of chunks to the custom streaming format I talked about before.

Interstate Generation

After those generation changes I then moved on to doing some improvements to the interstate generation. The Primary problem was all the interstates connected at one point at the city center which made handling of intersections pretty much impossible. So to test the intersection mesh creation I had to split up the interstates into real interstates that are continuous and connect multiple cities.These interstates now pass through cities sort of randomly and intersect other interstates at random points in the city just like they do in real life.

Initial Test
Zoomed in view of a few cities and their interstates. Notice how they flow through cities instead of meeting at one point. I also gave each city a random size which you can see in the screenshot.

To make this happen I had to do a decent amount of work randomly connecting interstate segments inside cities and then creating a doubly linked-list to grow interstates from connecting just two cities to connecting 10s or 100s of cities. It is fairly complicated, but the end result is a list of large continuous interstates that connect many cities. This improvement also has the added benefit of being able to name interstates that you can follow as you explore the world (for example I-10, I-95, etc.).

Initial Test
Screenshot of debug lines from when I was working on mesh creation testing up, right, and look vectors for road segments.

Once the interstates where created and connecting cities I did a quick pass on making them look good. For now I simply took the straight lines that made up the interstates and did a 2D noise similar to what I do for terrain to give each segment both high and low level movement. So interstates do large and small scale deviation from their straight connecting path.

Initial Test
Top down view of a bunch of chunks loaded with their roads. Red chunks actually have data.

This creates pretty realistic looking interstates, but there are still some problems with interstates intersecting outside of cities, intersecting too many times in a close area when they should be combined, and only passing through the outside of some coastal cities. These will be fixed in the future, but for now they get the job done. They connect cities and pass through them in a realistic way allowing me to test intersection mesh creation.

Streaming and Mesh Creation

Once those changes were made I was back in the game to stream all this data. The first step was designing a new data driven entity system. I briefly mentioned it in the last blog post, but I did a good amount of work on it after that post. You can see the details of the new system in the picture of my whiteboard below.

Initial Test
Detailed plan for the new entity system that I did on my whiteboard.

The system is designed to handle streaming large quantities of data in chunks and is the backbone of the streaming system. This system is also designed for maximum speed after stuff is streamed in. Once this entity system was in place I updated the chunk streaming to load data into this and created a chunk prioritization system. As you move through the world new chunks encountered are loaded and chunks in the distance are unloaded to make room.

Initial Test
Actual road mesh loaded into world on test terrain. If you look close you can see if climbing over a hill in the distance.

After the raw spline data was being streamed in I started work on the actual road meshes. For every chunk we go through each spline and create one mesh. So it’s one draw call per spline per chunk. The actual creation of the mesh is done by extending an arbitrary road mesh along the spline.

This lets us create any type of road like country interstates, city highways, city streets, neighborhoods with sidewalks, etc. The system can extend any mesh so there are no limits to the types of roads or even other things like rivers the system can render.

That’s everything I’ve been working on over the last few weeks. There is still work to be done on mesh creation, primarily the placement of intersection meshes. To do this I’ll have to save out the intersection points and push back the splines to the intersection mesh start points and some other complicated stuff. There are also some issues with world shifting when streaming the chunk data that need to be addressed.

So that’s the stuff I’m off to work on right now, let me know what you guys think about the new update schedule or if you have any questions. Don’t forget to checkout my twitter if you want updates more frequently than the blog update every 2-3 weeks.

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!

Previous Page