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.