Connecting Procedural Cities with Roads

It's time to revisit my city connector roads, which I implemented a few years ago but haven't touched since then. The problem statement is that I've generated some number of procedural cities (8 in this example) on the island map, and I want to connect them to each other with roads that cars can use to drive between cities. There are constraints that roads can't intersect each other or the wrong city, can't travel over water, and have a limit on slope when following the terrain. The goal is to find a lowest cost valid path from one city to the other taking into account path length, elevation change, and number of turns. There's also an option to add bridges and tunnels to span areas of high elevation change. Bridges are added when their construction cost (based on span length) is lower than the cost of filling in the terrain under the road, in cases where the terrain is too steep for the road to follow it. Tunnels involve weighing the cost of cutting through terrain vs. leveling it out to a reasonable grade.

The original code created two types of connector roads, a straight road from one city to the other, and a road consisting of an east/west segment and a north/south segment with a single bend between them. These two types of roads were enough to connect most of the cities together. One simple improvement is to allow connecting cities with a path having a single jog consisting of three segments plus two bends. This is just one more segment and one more bend than the previous case, but the existing code is very messy and special cased.

The first task was to separate out the various blocks of code that assign the road points/segments, determine if segments are valid, calculate segment cost, actually place the roads, and connect the segments to the road graph so that cars can navigate them. The goal is to have these different pieces be modular so that I can select between different road assignment algorithms and share the rest of the code. The optimal structure is for these stages to create or take a list of points defining the path of the road, where the road itself is constructed by expanding the segments between points by the half width of the road. This transform replaces the 2D rectangular area math with a simpler points-and-lines system. Since the roads are all a constant width, it's also possible to expand the collision objects by the road half width so that collision tests can use faster point containment checks rather than box overlap checks.

With that refactoring out of the way, I was able to experiment with new routing solutions. I first added the three segment roads and fought to make the road placement system accept that. The results were a bit more optimal in path length and elevation change, but overall didn't look very different. Then I attempted the next big idea of using the terrain heightmap with a path finding algorithm that traced the road across the heightmap grid to connect the endpoints. The plan was to eventually use the A* (A star) algorithm to improve the speed of the brute force force depth first search. I spent many hours trying to get this working, but had to eventually give up and revert the changes. There were several major problems with this approach:

1. It was slow. The heightmap is roughly 7000x7000 pixels, which is 50M elements. While most roads only spanned a small subset of the island's area, walking across hundreds of pixels for each road segment to calculate costs took quite some time. This drove the road routing cost from ~50ms to several seconds. Even using the A* algorithm won't get the time down to what it was.
   
2. Trying to connect the grids was a huge mess. Each city has its own custom spaced grid of roads that's not aligned to the heightmap grid. A single road is something like 2.35 heightmap pixels wide, not an integer value. I had to create short road segments to connect the point on the city road grids at each end of the path to the heightmap grid, where the connectors were odd off-grid segments. This caused a lot of problems with floating-point rounding errors, segment overlap, etc.
3. I never figured out how to correctly account for the slope of road segments. A single segment is on the order of a hundred terrain grid points in length. Each new grid added to the segment changes the elevation of the endpoint of the road, which affects the slope and the amount of material to add or remove under the road for the entire segment length. In theory I have to recalculate the cost of the entire segment after moving an endpoint. It's not easy to place a global constraint on max segment slope when adding one incremental grid at a time.
4. I want to minimize the number of right angle bends in the road to make it more realistic. However, it's not clear how to take the number of bends into account when calculating costs for A*. I don't have a good upper bound on the cost of the best path.
   
5. I don't actually have a plan for this. I have no reason to believe it will create anything better than what the current (simpler) algorithm will create. Are roads with many bends realistic? Maybe only in the mountains. But the current solution, which tries to avoid mountains to begin with, might do a pretty good job already.
   

That's a shame. I was really hoping to get some funny road fails such as in my previous post. It looks like I've added a lot of error checks to prevent those problems since then, and I really can't get the road placer to do anything wrong + interesting. No crazy epic fails. It will either fail to add the connection or exit with an error if I try to force it to add strange or incorrect roads. I even tried to create a serpentine road that switched back and forth between different orientations, but I couldn't get it to successfully place any roads like that. I suppose there could be various reasons why. Those roads take more space and are more likely to collide with something, and have higher cost. Having all those short road segments is probably going to fail the max slope checks for at least one location as well. Sorry, I guess I don't have a silly screenshot to post of random switchbacks in the flat plains next to the city.

Anyway, here is what the city connector road network looked like with the old algorithm. Cities are the regular grids, roads are gray lines, and all the small colored squares are buildings. Bridges are white, tunnels are brown, and parks are green. Roads and cities can't be placed over water (blue) or mountains (gray/white). Note that this isn't the full 7Kx7K island; it's closer to 5Kx3K pixels.

Cities and connector roads using the old algorithm. 12 roads, 2 bridges, and 3 tunnels, cost=19.

And here's what I get with the new algorithm that allows three segment/two bend connectors.

Cities and connector roads using the new algorithm. 16 roads, 0 bridges, and 1 tunnel, cost=26.

I count 7 of the new connector road types. There are more roads, but also a higher road cost. This makes sense because cost is summed across all roads in the scene. The average cost per road has increased from 1.58 to 1.69, likely because of the added cost of road bends and the improved ability to connect two distant cities. There's now only one tunnel and no bridges. I believe that's because the new algorithm has more freedom in placing roads due to the extra segment/jog, so it can avoid the cost of building bridges and tunnels to pass through steep terrain.

Is this result better? I'm not sure, maybe. It depends on whether we're trying to maximize connectivity or minimize cost. However, the new algorithm does scramble around all of the secondary buildings. The new building layout around the starting point is now completely different, which makes it easier for me to get lost. I liked the old layout where I knew which buildings had which interesting layouts, architecture, or items. So I think I'll probably keep the old road network, but leave the option to switch to the new one.

Overall, it's not clear if this was a waste of time or not. I definitely cleaned things up in the code, added error checks, experimented with different solutions, and added more configuration options. Maybe I'll get back to this sometime later. Now it's time to move onto something else.

Procedural Buildings: House Improvements and Residential Neighborhoods

I've been working on improving the look and placement of procedural houses over the past two months. After finishing up the room object placement project, I went back and made some rooms into garages for houses that didn't already have detached garages. Then I converted the chimneys of some houses from roof decorations to exterior chimney geometry with proper fireplaces. Now that houses are nearing completion, it's time to use them to create proper residential neighborhoods with grassy plots placed inside grids of roads. These changes are described in more detail below.

This post is rather long, and maybe should have been split up into two smaller posts. It started out shorter but kept growing in length as I fixed various problems and added text and images for my fixes.

Garages

I've had detached garages as separate buildings off to the side of houses for a while now. They're relatively rare because they can only be added to the inside part of L-shaped houses without going outside the valid building bounds. Most real houses have garages, so I needed to add additional garages to the main floorplan of some houses.

It was difficult to fit this step into building generation in a way that didn't require significantly changing the control flow. The current house generation algorithm determines the exterior walls first, then places windows and doors, then generates the walls, and finally assigns rooms. Garages are special because they're integrated into all of these steps in some way. The garage is an assigned room, and its door replaces windows and is aligned to the side wall. It wasn't clear exactly where garage assignment should be done in this control flow, because it requires knowing the interior walls before a room can be assigned to be the garage. So I had to special case the garage room assignment to happen earlier in the control flow, just after the interior walls are added. The garage door then removes windows that overlap it. I moved the exterior door assignment after garage selection. If the door is placed too close to the garage door, I move it to the opposite side of the house or choose another door location.

I used several different heuristics to weight rooms as garage candidates, and then choose the candidate with the highest weight. Garages must be large enough to fit the largest sized car (but not a truck), and have a higher weight when their aspect ratio is close to 1.75. Garages also have a higher weight if they have exactly one door to the house, and a high weight if they're against an exterior wall on two sides. They must have at least one exterior wall to place the door in.

After several attempts/iterations, I have it working. Some garages have parked cars in them. Some have shelves with objects placed along one or more walls (except the wall adjacent to the door). Here's an example screenshot of the interior of a garage.

A car is parked in a garage attached to this house. There are storage shelves next to the window.

 

Chimneys and Fireplaces

Most of my generate houses have chimneys on the roof, but they're simple placeholders that aren't connected to anything. I wanted to make them look more like real chimneys, and connect to interior fireplaces. The first step was to move some of the chimneys outside the footprint of the house so that they're against the exterior wall. My real house has a chimney like this. The fireplace is a (possibly wider) cube at the bottom of the chimney that spans most of the height of the ground floor.

Chimneys turned out to be more work than I expected. Adding exterior chimneys changed the house's bounding cube slightly, which lead to various minor issues that I came across a week later. Removing windows and doors that overlapped the chimney and fireplace was also tricky, because it lead to some window strips with odd lengths that couldn't fit an integer number of windows. The existing window placement system was coupled with the exterior wall generation so that it created whole windows, but I didn't want to try and stuff the chimney generation code into that control flow as well. Instead, I simply removed the partial windows, so that short walls sections next to chimneys were windowless.

The next problem I ran into was placing the fireplace. The easy part was adjusting room assignment to not make rooms with fireplaces into bathrooms, garages, laundry rooms, etc. While fireplaces usually go in the living room, I allowed them in bedrooms, dining rooms, and kitchens as well. This took some pressure off the room assignment algorithm and made it more likely to succeed.

The difficult part was handling walls that intersected the fireplace. It's certainly not correct to have a fireplace that's split across two rooms. However, when I got to this step in the control flow, it was too late to move the chimney/fireplace because then I would have to update the windows and doors again. I considered moving the walls instead, but that would invalidate things like garage placement. I'm sure I could always give up and regenerate a new house until the fireplace can be successfully placed, but that wasn't a great solution. All of these different constraints are too complex to manage. In the end I settled on only adding fireplaces when there's no wall in the way. This means that some chimneys still connect to nothing, but it's better than when they always connected to nothing. I don't think this would be too obvious to the player anyway since this case doesn't happen very frequently.

Here's an example of a fireplace placed in a living room. I also had to update the algorithm that placed rugs and furniture in the rooms so that they didn't block or intersect the fireplace. Maybe sometime in the future I'll place objects on top of fireplaces or otherwise improve their looks.

A fireplace has been added against the exterior wall of this living room.

Residential Neighborhoods

At this point I had two types of areas: cities full of office buildings placed in a grid of roads, and randomly placed houses and other secondary buildings with no roads. I've been trying to connect the secondary buildings with roads, but so far haven't been successful. What I have are buildings placed in a rural setting, but too close together. There are too many hills and not enough straight line spaces between buildings to place roads. I'm sure I could squish some windy roads between everything, but it wouldn't look very natural. No city planner does something that insane.

I gave up on that approach and decided instead to use the existing city road grid system to create residential neighborhoods. The main change was to place a large number of houses rather than a small number of large office buildings, but I had to make many other changes as well. The concrete sidewalks and pavement was replaced with grass lawns. Benches were removed. Parking lots were replaced by driveways. I kept the scattered trees, rows of trees along the streets, and city parks though because they seem to work with residential neighborhoods as well.

Here's a screenshot of an early attempt at a residential neighborhood. It was a good start.

Early attempt at a residential neighborhood with houses placed in the grassy areas between a uniform grid of roads.

Here you can see several issues, and there are more that aren't visible in the screenshot. Some houses are missing driveways, or have garages facing the wrong way. Others have streetlights blocking their driveways. I suppose having garages on the wrong side is the biggest problem. I'll explain how I handled that below. As for streetlights, I added a check for driveway intersections and moved the streetlight to the side of the driveway closest to its starting position.

I suppose another issue is that there are too many roads and too few houses. Most blocks have between 6 and 10 houses, which isn't very many. However, if I make the blocks larger, then the placer does some strange things. I already add an area in the center of the block where no houses can be placed to prevent interior houses that don't share an edge with a road where a driveway can be added. That works to some extent, but when the block is large enough other bad things can happen. Maybe it would be better if I made the road spacing different in X vs. Y so that the blocks are long an thin, with two long rows of houses on either side? Maybe it would work better if I divide the block into plots ahead of time such that each plot borders a road, and then place a single house on each plot. This is how city planning usually works, so it must be a good idea, right? That required significant changes to the building generation code, but gave me some interesting results.

Dividing city blocks into a uniform grid of house plots produces evenly spaced small houses.

Well that looks okay but not great. The houses are relatively small and have a very regular placement with 8 houses on most blocks. The reason they're small is because I had to add some spacing between the individual plots to make sure I can fit driveways and other details. Maybe there's too much spacing, and houses should be larger, or placed more densely per block? How about decreasing the spacing:

Uniform blocks again, but this time with less space between houses so that they can be larger.

Does that look better? I think so, but it's not obviously better than the original random house placement. I think I like the previous look of the houses because there's more variety in their sizes and placement. Maybe this plot assignment would look better if I insert some sort of border between the plots such as fences, hedges, or even slightly different colored grass. I added a config file option to switch between random placement and uniform plot placement. I'll get back to experimenting with this later, and maybe enable it if/when I space the roads further apart.

I enabled cars and pedestrians to test out how they worked. Cars can drive on the roads (as usual) or park in driveways. People walk to houses and parked cars. They really like to cut through the yards though, so maybe I need to add some fences around the properties to prevent them from trespassing. I suppose they would be less interesting to watch with that change.

Here's an updated screenshot with some of the fixes and improvements. I don't see anything obviously wrong here, though there are still some issues if you look for them in other parts of the city.

Residential neighborhood with cars on the roads, cars parked in driveways, and people walking around. I placed a Ferris wheel at the end of the street in the distance.

Placing driveways turned out to be challenging, and I still don't have it completely worked out. The driveway placement code first attempts to connect a garage to the road. Since garages currently are placed on a random side of the house, this is only successful 25% of the time, or 50% of the time for houses placed on the corner that can connect to either road. If this fails, or the house doesn't have a garage, then it attempts to connect the driveway to the nearest edge of a cube of the house, taking care to avoid chimneys/fireplaces. (I should probably move the outdoor AC units off driveways as well.) If this placement step fails it will instead add a driveway along either the left or right side of the house. Houses are placed such that there's always room for a side driveway, though two adjacent houses can have their side driveways between them overlapping each other. I suppose this is okay, because it creates what looks like a single wider driveway. Then I have to check for two overlapping cars on those driveways.

I haven't quite decided how I want to handle garages that are placed on the wrong side of the house. I guess I can start by calculating the edge(s) of the house closest to the road and passing that into the house generation code. Then at least I know if the garage is on the wrong side. If it is, I can use the brute force solution of regenerating the house until the garage is on the correct side. If that turns out to be too slow or messy, maybe I can rotate or mirror the house to put the garage on the proper edge? Or maybe choose a less optimal room as the garage, for attached garages? I'm not sure, I'll have to experiment with it.

... Okay, after experimenting, I've improved it somewhat. First of all, I can make sure detached garages are placed on the side nearest the road by mirroring them to the opposite side of the house if needed. If their entrances are in the wrong dimension (X/Y), I can make the driveway come out and make a right angle turn to meet the road. It seems like there's enough space between the houses to fit the turn, though it sometimes looks a bit odd. For interior garages, I can limit them to the side of the building facing the road, relax the constraints on size a bit, and not add a garage if this fails.

Here's what one of these right angle driveways looks like. I tried swapping the garage direction, but that causes other issues with placement and I gave up on that approach. It's not the best solution, though I suppose it's better than not having a garage or having the driveway unconnected.

One of those funny right angle driveways that has to be used because the garage isn't facing the street and there's not enough space to rotate it 90 degrees.

I really should add fences between some of the houses, at least when using a uniform grid of plots where the fence location can follow the plot boundaries. Maybe I should add swimming pools and other yard objects. That's a good task for some later time. I have such a long list of features to add! Every time I implement something, I add one or more items to the list.

Here are some screenshots of a somewhat overhead view of a residential neighborhood during the day and at night. I have cars, pedestrians, and people in buildings enabled. The night scene includes light from streetlights and dynamic car headlights. Everything I mentioned above has been fixed, including the garages connected to driveways and the streetlights blocking driveways.

A residential neighborhood show during daytime.

The same residential neighborhood show at night time. The moon is out so it's not as dark as it could be.

I also made overhead map view work correctly with residential cities, including drawing of driveways and parked cars. Here's an example showing the same city as the above images. This map is interactive and shows the cars moving in realtime. I can pan and zoom to inspect the layout of houses, driveways, etc. It may look like some driveways are missing, but I believe all houses have driveways.

Overhead map view of the same residential neighborhood, showing houses, driveways, and cars. The green square at the top is a park.

Oh, and just for fun, here's the result of incorrectly setting the house size too small compared to the plot size. This produces tiny square houses with a single room and multiple floors.

Tiny single room, multi floor houses resulting from a bug in the building generation logic.

In theory this system should scale to residential neighborhoods out to the horizon over multiple square miles. The most I've attempted so far is 18,000 buildings + 8,000 cars + 60,000 people. Keep in mind that all buildings have procedural interiors, and (non parked) cars and people are dynamic with their own AIs. I'm not sure how much higher I can make these numbers before I run into issues with memory usage and frame rate. I'll likely experiment with this later to see how large and how many cities 3DWorld can handle.