Epic Fails in City Road Generation

This is a follow-up to my previous post on city generation where I show some of the fun bugs I had in the code and other failed attempts at placing roads. This first set shows off some actual bugs, though I had to go back and re-break the code in order to take these screenshots. Keep in mind that I did, in fact, encounter these problems when coding this stuff up. Roads aren't easy!

Here we have a road connecting two cities that are on opposite sides of this city shown in the screenshot. It was some problem with the tracking of which city the road is supposed to connect to. Roads are placed after city plots, so they have final say in what the terrain height should be.

But sir, you told me you wanted an express lane THROUGH the city!

This one was a failed intersection test between two connector roads. I was checking for overlap in all three dimensions (x, y, z). These roads don't overlap in z, but there's still an intersection. Just because they don't overlap in z doesn't mean they're okay! Only dimensions x and y should be checked. I had to print all sorts of debug text to the terminal to figure this one out. Doh!

We ran over budget constructing all these elevated roadways, and we didn't have the funds to dig the tunnel. We'll just have to put it on CA Proposition 39 in June for voter approval of a $9 parcel tax.

This is some problem with setting the height of the small 90-degree bend section at the wrong place in the control flow. The two 90-degree straight segments cause some interference here, and the bend has to smooth it over in a postprocessing pass. It took a while to come up with a fix for this one. I had to make several attempts before I got something that fixed all variants of this problem.

If you're not going to add a guard rail, can you at least post a warning sign? On second though, this might be good for drift racing!

Here's what happens when the slope direction Boolean is inverted. A number of different variables are XOR-ed together here to determine the sign of the slope of each road segment. It took a lot of trial-and-error to come up with the right conditionals. Maybe I shouldn't have been so greedy, trying to pack this info into a single byte in memory for each road segment. Ah well, I got it working in the end.

"Speed Bumps"

In this case, the two roads don't overlap, but their sloped boundaries do. The road on the right is created first. The road on the left is going to a higher altitude destination city. It creates a sharp cliff that falls to the right, then the smoothing pass smooths it out - right on top of the other road. The fix is to expand the road by its smoothing border before checking for intersections with other roads. It's a good change anyway, as it spaces roads out better. Bonus: the texture is all squished in that road segment in the lower left corner between the two intersections.

I'll take the high road and you take the low road. Sucker.

A similar problem can occur with cities, since they also have smoothing borders. I had to fix the problem in the same way as roads, by padding city bounding cubes by the smoothing distance prior to checking for intersections.

Someone forgot to build a retaining wall. Oops. I guess the 5th floor tenants get their backyard gardens after all.

I'm not sure exactly what caused steep roads to dip under the terrain. It's probably a floating-point rounding issue when converting to/from integer grid points/texels, or maybe during the 16-bit height <=> floating-point value calculation. One fix is to shift the road up in Z by an amount equal to (dz/dx)*pixel_size_in_x. I'm not sure if this is the correct solution as it causes steep roads to "float" above the terrain, but it's one of the only things I tried that works. As long as the steepness of the road is limited, it's not too noticeable.

Landslide!

At one point early in road development, I had a problem where the grass and roads were using two different coordinate systems. Grass is owned by the terrain tiles and is in tile-relative coordinates, which change as the player moves. Roads, cities, and buildings are always in constant global coordinates so that their vertex data can be stored on the GPU once and reused. A bit of math was required to fix this problem.

Can someone send a landscaping crew out to cut the grass growing on I-101? Maybe that will keep the cows from grazing in the middle of the road.

These next four screenshots weren't actual problems I ran into, but they still look interesting. This is the insanity resulting from disabling the connector road intersection tests so that they can go anywhere they want without restrictions.

Connecting every city directly to every other city is now possible, but not a good idea:

Ready for some off-road action? I think the engineer was off his meds when designing this.

A road was routed underneath this city. Presumably, it connects together two lower elevation cities on opposite sides of this one. I can't really tell in all the chaos. Some buildings have decided that they want to use the mesh height from the road rather than the mesh height for the rest of the city.

To protect against nuclear attacks, this shopping mall was built under the city. Or maybe it's a secret spy lair (with a big road leading up to it)?

This is the same problem, but inverted. Here the road connects together two higher elevation cities, dragging some buildings up with it. I could fix both of these issues by using the city elevation for buildings rather than terrain elevation. But this is just an experiment; this situation shouldn't come up, so why bother trying to handle it?

Now guests on every floor can have a room with a view! I just hope the kids don't decide to roll tires down that hill.

In this next case, the upper road was created first, and the lower roads were created later. Once a road is routed, it's done. The lower roads will modify the height of the terrain, but not the height of the upper road. In this particular case, it looks like a pretty cool bridge, though it needs some actual structure to be more realistic. Maybe I'll try to come up with a way to make this work. We still need to get rid of that road in the very front though.

A marvel of modern engineering, or a waste of our tax dollars?

That's all. I'll spare you the dozen or so screenshots of misaligned and incorrectly oriented road textures, which was another big time sink.

Cities With Roads

It's been over a month since my last post. I had been working on fixing the ship AI for universe mode planet colonization, which required me to constantly run simulations on my PC. That topic doesn't make for a very interesting blog post because it's too technical and there aren't any good screenshots. However, in the past two weeks I've switched back to working on terrain and cities. This time I'm trying to combine the work I did with city generation and eroded terrain to create an environment that's a mix of natural and man-made structures. The end goal of the 3DWorld project is to generate a procedural universe that the player can seamlessly explore, from galaxies all the way down to individual trees and buildings. There's still so much work to do. The new addition to 3DWorld is city road networks.

I'm starting with the same 7Kx7K heightmap output from the erosion process described in a previous post. I exported it to a 65MB, 16-bit PNG image so that I can reload it without redoing the erosion simulation. This scene is huge, around 14km on a side. The cities are currently all placed in the relatively flat area in the bottom center of the map, between the ocean to the south and the mountain range to the north. Remember that this is an island, even though there's very little water in the screenshots below.

The steps I'm using to generate and connect cities are:

1. Determine city location(s) by looking for relatively flat areas of the terrain, away from water
2. Flatten a rectangular area of terrain to the city elevation (avg terrain elevation)
3. Select the location of X and Y roads based on user-specified parameters
4. Split roads into road segments, 2/3/4 way intersections, and building plots in between
5. Create road networks that connect all cities (straight roads and roads with one 90-deg bend)
6. Smooth the mesh around roads and intersections so that they're slightly above the terrain
7. Generate procedural buildings and place them into the city plots

Items 1-6 are described here. Procedural building generation was explained in some previous blog posts and won't be discussed again. Look here and here for reference. All of these steps take less than one second of runtime: heightmap texture <=> floating-point array (330ms on 4 cores/8 threads), road network generation (70ms), and building generation/placement (185ms). This is much faster than the 2.1s actually spent loading the heightmap image as a texture.

City generation first reads a configuration file that specifies the size and number of cities, road length/width/spacing, max slope, terrain smoothing parameters, building parameters, etc. In total, there are 12 city parameters and 45 building generation parameters. These can all be edited by the user to customize city generation.

The first procedural generation step is selecting a site for each city. A few thousand locations are randomly chosen from the user-selected region of the heightmap, and the best one is selected. Locations are scored based on the RMS height difference between the average height and each height value around the perimeter of the city. I chose to use the perimeter rather than the full site area because it's more efficient to compute. Its unlikely for the player to notice if the city happens to flatten an entire hill or fill an entire valley anyway. It's more noticeable when there are steep slopes at the edges of the city. Each site must also not overlap a previous city, and must contain no water. I could have it fill in the water with land, but I do like to keep all of those small rivers and lakes.

Once the best site has been selected, that area is flattened to an elevation equal to the average elevation around the city perimeter. Note that the heightmap is normally stored as 16-bit integer values, but is converted to/from a floating-point array for the purposes of city generation. This conversion process takes about half the total city generation time. A boundary region is used to gradually transition from the city's elevation to the original terrain elevation to avoid sharp cliffs at the edge of the city. A smoothstep function is used to prevent slope discontinuities that would otherwise be obvious and appear unnatural to the player. Roads are flattened and smoothed in a similar way, but with a more complex function that handles fixed (but nonzero) slopes. The flattening step also replaces any grass inside the city perimeter with dirt.

Roads are placed on a uniform grid that exactly fills the city area, and are oriented in both the X (east-west) and Y (north-south) directions. The config file defines road width and spacing values. 4-way intersections are created in the interior of the city, 3-way intersections along the edges, and 2-way intersections at the corners. The space between roads is filled with a tiled concrete sidewalk texture that matches the border of the road and intersection textures. Buildings will be placed in these areas in the final step.

Intersections, plots, and road segments between intersections are sorted into the terrain tiles that contain their center points for drawing. This also serves as a useful spatial subdivision for later collision queries. For each visible tile, the city objects associated with it are drawn using the tile's shadow maps. This system is meant to scale to very large maps with potentially hundreds of cities, where only a subset of the cities is visible at any one time. I've tested it with 49K buildings and 90K road segments and still get 136 FPS (frames per second).

The screenshot below shows a pair of adjacent procedurally generated cities with roads and buildings. Note that the buildings all cast correct shadows on the roads and sidewalks. At this point in development, the cities haven't been connected.

Two adjacent cities with roads and 1268 buildings, viewed from above.

The player is free to walk around the city. There are no vehicles yet, but it's possible to walk very fast using the "R" key. The buildings have player collision detection enabled. The terrain can be edited in realtime as well, but the buildings and roads won't move with the terrain height like the vegetation does. Below is a "street view" image showing another city in the background. To give you a sense of the terrain resolution relative to the objects, a city road is slightly larger than 4 terrain texels wide.

View of the road bend at the edge of one city, with another city in the distance.

There are some minor issues visible in this screenshot that I might go back and try to fix later. There are texture seams between some of the intersections and the roads. It might help to rotate or mirror the textures to line them up better. I could look for a different set of road textures, but this set was the best I could find in my initial searching for free textures.

You can see some grass sticking up through the sidewalk at the edge of the city. This has been fixed already. Grass and plants are 5-10x larger than they should be compared to other city elements, and trees are 2-4x larger. I'm not sure if I should make the vegetation smaller, or make the buildings larger. If I make the vegetation smaller, then I have to generate a whole lot more of it to fill the scene, which will hurt scene creation time and frame rate. If I make buildings larger, then they don't look right against the mountains, lakes, and rivers. I'll leave it the way it is for now. Maybe I'll do something about it later.

Here's a shot where I turn the camera around to view the mountains next to the city. Everything shown here is real geometry. The player can walk into the mountains seamlessly.

Road at edge of city with mountains to the left and buildings to the right.

This is what the city footprint looks like without the buildings. The grid of roads can more easily be seen, along with the sidewalk textured plots where buildings will be placed. While cities are level, roads can be sloped to connect two cities of different elevations. The road that cuts through the hills in the back left is sloped upward. I have pine trees enabled since the scale problem isn't as obvious without the buildings. Note that the vegetation placement algorithm will avoid placing grass, trees, plants, and other scenery objects over the city and connector roads. The bounding cubes of cities and roads are used as blockers for scenery placement.

City plots, local roads, and connector roads shown without the buildings.

The image below shows how several nearby cities have been connected by roads. In this example, I configured the road router to connect the first (center) city to each of the other cities with a single straight road. Right now I only have road textures with a single lane in each direction. I'm not sure if I want to add another set of textures for multi-lane highways between cities. I've disabled fog to make the distant city in the back more visible.

Four connected square cities shown without fog or trees to better view the road network.

Here is another screenshot showing how two cities are connected by a road through the hills. The connection algorithm chose to place the road near the edge of the city to minimize the amount of material added/removed (required terrain height change) for placing a straight road. If the road was placed more toward the center of the city, it would have cut deeper into the hills. I like how the pine trees and terrain cast shadows on the roads. These shadows will move with the position of the sun.

Connector road cut into a wooded hillside. This was the location that required the min amount of height change.

This next image shows a view of the downtown area. The camera is on a road in the middle of a city, looking down the length of the road. The large office towers look good here, and seem to be the correct scale relative to the road. Now all I need to add are streetlights, traffic lights, signs, and maybe even moving cars. It would look better if I could fill in all those small empty spaces between the buildings. These spaces are too small to fit additional buildings.

Street view inside a city. It would look better with streetlights, signs, and benches.

Here's a screenshot taken from the roof of a building. Buildings don't have stairs (or any interior), but I can use flight mode to get up here. Once I'm on the roof, I can walk around on it. There are 680 buildings in this city. Trees and mountains can be seen in the distance. Note that this screenshot, and all the others, are running at around 200 FPS.

Rooftop view from a tall skyscraper. Yes, the player can walk around on top of these.

After creating all the images above, I went back and did another pass at connector roads. First, I made the cities smaller so that I could place more of them in the same view area. I also added config options for size ranges of cities, which means that cities can now be different sizes and non-square.

Next, I changed the routing algorithm to try to connect every city to every other city. This isn't possible in general without bridges or tunnels, neither of which have been implemented. I had to add collision detection for roads colliding with the wrong city or other connector roads. If no valid path is found after 50 random attempts, the router gives up and doesn't connect that particular pair of cities. I could have added 4-way intersections in locations where two connector roads crossed, but I decided not to do that. That's a lot of complexity to add, and I was worried it would clutter up the scene with too many roads and intersections. Plus it's difficult to get the elevations of the roads to match at the intersection. I might go back and add a config option for that later.

Finally, I added support for connector roads with a single 90-degree bend. It would have looked more natural to use roads that were curved or had multiple smaller bends, but there are several problems with that approach:

• My texture set only includes textures for 90-degree bends, and I haven't found any good curved/shallow bend road textures online that will tile with straight road textures.
• It's not easy to connect non-rectangular roads together. Simple quads don't work well. They would either produce texture distortion/shear, or would leave gaps in the mesh.
• The math is much more complex, and slower. It's difficult to determine intersections.
• Flattening the terrain heightmap is both inefficient and prone to aliasing issues. Straight, axis aligned roads are simple rectangles in texture space, while arbitrary angle roads require complex line drawing algorithms to move in texture space.

I haven't attempted this yet, but it's possible future work. Even getting this far took me a few late nights of programming. For now we just get crazy right angle roads like this.

Small cities connected together by a network of straight and right angle roads.

These roads are all straight and have constant slopes. This means they tend to cut through mountains, creating deep valleys. They also create strange land bridges across low lying areas between two higher elevation cities. This doesn't look very practical. What where those civil engineers thinking! I'll bet these would make for some good runways though, if I decide to add an airport to my map. And as long as the plane can take off before the 90 degree bend. And clear those steep mountains.

Here's another shot. See the mountain pass the algorithm carved in the front right and those two elevated roadways on the left in the distance. The cities and buildings look pretty good though.

Several non-square cities of various sizes connected by some crazy long roads.

I decided that these long straight segments themselves were okay, but the fixed slope was not. I added a segment_length config option to split the connector roads up into multiple runs that could have their own slopes. The elevations of the intermediate points between segments were set equal to the terrain height so that roads roughly followed terrain. This removed the deep valleys and land bridges, but added some very steep road segments. Roads now went up the mountain and down the other side instead of cutting straight through it. This makes sense from an engineering perspective, at least for lightly traveled roads where vehicles can be expected to make it up and down the steep parts.

I decided that a slope limit was needed to prevent very steep segments. I chose a rise-over-run value of 0.3, which removed the small number of very steep segments while keeping the others. In cases where the midpoint between two road segments generated a slope that was too high on one side, the midpoint was moved vertically by either shifting the terrain up or down to try and straighten the segments out in Z (up). In the worst case, the road was converted back into a single segment with constant slope, assuming the overall slope (city elevation difference divided by city horizontal distance) was under the limit. These changes produced a road network as shown below.

Roads split into segments that follow the contour of the terrain. Road segments with slopes >0.3 were rejected. Fog disabled.

The road that's just to the left of center had too high of a slope to go over the hill, so it cut through the hill instead. There are still some strange paths, such as that one in the very back that goes up and down an invisible mountain. Note that the mountain is only invisible because I've turned the fog off and the draw distance of roads is larger than the draw distance of terrain. Overall, the results look acceptable, and are much more practical than the fixed slope roads. I'll keep this set of options for now.

I'll throw in an overhead map image so you can get an idea of what this looks like as terrain. Water is blue (of course), low areas are brown, mid elevation areas are green, and mountains are gray/white. Cities are same-color rectangles. For example, that large greenish-brown square in the bottom left is a low elevation city. Roads are thin horizontal or vertical lines of similar colored pixels. Some roads are sloped, giving them color gradients. Overall, the placement algorithm has done a pretty good job avoiding the mountains and deep valleys. The algorithm has successfully avoided placing cities and roads over water, as expected.

Overhead map view of center of heightmap showing how city plots and connector roads have changed height values.

City generation has been a pretty fun and interesting topic. I definitely want to continue working on it. Results seem pretty good so far, but there's so much more work to do here. Of course, this system is already getting complex, with over 1000 lines of source code. You'll probably see at least one more blog post on this topic. To summarize, future work items include:

• Addition of detail objects within the city (lights, signs, benches, cars, etc.)
• More realistic roads with more/shallower bends, more gradual slopes, less terrain editing.
• Smarter building placement that adds larger buildings to the city interior. (Zoning?)
• Fixing of incorrect size scale for buildings vs. vegetation.
• Fixing of texture seams for different types of road sections.
• Addition of normal maps and detail textures for roads and sidewalks.
• Building interiors! Well, no, probably not any time soon.
• ... But maybe I can add windows and doors to some of those brick and stone buildings.

I definitely think I'm going to work on cars next. It would be awesome to have tiny cars and trucks moving about on the roads within and between cities.