Sign-up for Email Updates:

Help Survive Development:

Development Blog
January 21, 2016 By: David Tse

I've been working on some really important stuff since the last update. You may think generating realistic roads is a challenge, but it's nothing compared to trying to get them to cross each other in a believable way. There are many different types of roads and every combination of intersection needs to be handled differently. Then on top of that some roads can intersect at arbitrary angles, different elevations, and at any part of the terrain. While there is still much more to be done handling these intersections, I've made some significant progress.

I should also note that my laptop broke right before I was going to post this. I'm currently not home and I only had my laptop to work on, so all the screenshots I had planed to use for this post are stuck on there. Luckily I'll be home on Saturday and ordered an NVMe reader to get all the stuff off the laptop's SSD. So there will be screenshots that better describe what I'm talking about then. Also I wrote and posted this using iPad so there may be some issues.

Intersection Generation

The first thing that I had to do was determine where these intersections were happening and between what types of roads they were happening between. For city roads this is fairly simple because I'm growing roads out from a start point so I know when a road intersects another road because that's part of the growth algorithm. For interstates I had to split them up into temporary collision chunks and just do basic collision tests to get all the intersections.

Initial Test
Old screenshot of circles around the intersection in generation stage.

All of these intersections are expressed as a 0.0 - 1.0 percentage along the spline for reasons that will be made more apparent later on. So a 0.75 indicates the road spline intersected another road after traveling 75% of the way down the spline.

The problem is this spline can be really large and will need to be split up into world chunks for the game to stream in. This means that when we're splitting up the splines for the export chunks we have to grab the intersection percentage then re-normalize the 0.0-1.0 intersection value to fit the new adjusted smaller spline all while taking into account the buffer spline points at the beginning and end of the spline. It was a huge pain in the ass to get this working and all the intersections to perfectly line up once loaded in-game. It took a little while, but it all works now.

Terrain Mesh Deformation

Before I go into the actual intersection handling and mesh creation let me take a step back and talk about one really important feature I did that is not exactly related to intersections. When we place roads we can't just put them on top of the terrain and hope for the best. Even the most flat terrain will clip through the road.

When roads are placed they need to completely flatten everything under them and cut through any bumps or hills. Then terrain that is progressively further away from the road is smoothly flattened less and less until it's back at the original terrain value. This can be tweaked in a number of different ways depending on how smooth you want the flattening transition to be, how closely you want to road to adhere to the terrain, or how smooth you want the Actual road to be.

Initial Test
Old screenshot of terrain flattening under a road. Notice how the bumps extend through the road.

The way this works is we take a sample at every point along the road mesh to get the pre-deformed terrain height. Then that height is extended perpendicular to the road in both directions to flatten the terrain. The problem is if we are taking a lot of samples, because we want a decently tessellated road mesh, the road gets really bumpy because we're very closely following the underlying terrain which is usually bumpy. To smooth this out we can do x number of smoothing passes that just take the average heights. Then like I said before all this stuff can be tweaked depending on the road.

Initial Test
Same road and terrain as last screenshot, but this time with the road smoothing.

Once we get the desired terrain adjustment for a road we blend it into the road map texture. Every active chunk gets a road map from a universal pool. This creates a smooth map at chunk stream time that the terrain can quickly sample and reuse for all the different LODs. This theoretically could be done offline, but the amount of memory to store a full texture for every chunk would be insane. Because the chunk sizes are 512x512m and the world size right now is set to 1,000,000x1,000,000m. This road map will also be used for flattening the terrain for building foundations. Should probably change the name to city foundation map or something.

The last little thing I did with the terrain was to get the ground to start at about the same height as sidewalk. Something you expect in real life. To do this I just pushed down the entire road into the terrain and then lowered the terrain even more just where the actual road is. This way it looks like the road is sinking into the terrain and the top of the sidewalk is about level with the terrain.

Arbitrary Intersection Mesh Placement

Initial Test
Reference from google earth of what the goal is for the highway overpass with the arbitrary mesh placement.

One way to handle intersections is to place a pre-made mesh at the intersection point that perfectly lines up the connecting road segments. This is useful where roads intersect at predetermined angles. For example a driveway connecting at 90 degrees with a neighborhood road. Or when a highway passes over a road we use this system to place the bridge mesh. This system will also be used to add road marking decals and anything else that needs to be placed along the road like guard rails.

Initial Test
Model I made to test the spline mesh placement.

This system can place the mesh at any arbitrary point along the spline given a percentage distance along the spline. This is why we store intersections as percentages traveled instead of just points in the world. Think of it like a train moving along the tracks. We can slide a mesh up and down the road spline and it will conform to it perfectly.

Initial Test
Working spline mesh placement of highway overpass. This is old screenshot before I figured out how to blend the terrain flattening for multiple roads.

Custom Intersection Mesh Creation

The next way we handle intersections is by automatically creating a custom mesh to connect the roads. While it is possible to create a perfect mesh that connects the roads, I've decided to go with a bit more of a hacky solution that is much simpler.

So when two roads intersect at an arbitrary angle the first thing we do is get the elevation at the intersection point. Then we set the elevation of all the road points that overlap to that intersection elevation. Then we smoothly fade back to the original road elevation as we move away from the intersection. Because the roads are now smoothly meeting at exactly the same elevation we already created the main road intersection mesh!

Initial Test
Only wireframe screenshot I have. Shows how the triangles just overlap.

The way this works is, we render the roads using world space texture coordinates. When you do that can't even see that the road triangles overlap at all because every point in both roads are sampling the exact same color. This does mean that roads need to use a simple tileable asphalt texture and we lose the road markings and any directional detail/wear.

Initial Test
Same screenshot not in wireframe. Notice how you can't see where any of the triangles overlap. You can also see where the sidewalk corner meshed are needed and how the intersection elevation change still needed to be smoothed out.

To fix this the plan is to use a layer of decal meshes that blend into the road. So we can get lane markings and directional details on straight roads then when we get to intersections we can add all the road markings you expect like turn arrows and stop lines. I think this is the best solution even if it's not the most optimal/efficient. Perfect looking intersections, realistic road markings/details, simple algorithm, and only a few wasted triangles where roads overlap.

Initial Test
High level view of everything working. You can also see the terrain smoothing pretty well in this one.

Now the actual road is intersecting just fine, but the sidewalk and anything else traveling alongside the road needs to be connected properly. To do this we need to stop the side mesh at the same point we start flattening the road at the intersection. Then we create a new corner spline at the 4 or 2 corner points depending if it's a 4 way crossing or T intersection.

Initial Test
Close up of the sidewalk corner meshes and everything coming together. Still has some texture UV issues on sidewalk.

Once we have this spline we just extrude the sidewalk mesh along this new spline connecting the two different road sidewalks. We also need to extrude a standard road mesh along this spline to make sure the road extends all the way to the sidewalk corners. This corner spline can also be used to place an arbitrary mesh using the system I mentioned before. So we can create a special corner sidewalk that has a ramp or a different look if we want.

All of this road stuff is starting to get me really excited, and I can't wait to start working on what's next! That next step is to generate some neighborhoods and start placing houses! Now that the holidays are over and there will be much less going on the next update will actually be in 3-4 weeks and will hopefully have some buildings to explore.

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!

Previous Page