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:
- 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.
- 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.
- 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.
- 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.
- 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.
"the new algorithm does scramble around all of the secondary buildings"
ReplyDeleteAhh, random seed initialization bleed! This is why the pros generate a random seed for each subdivision zone, and initialize the twister with that value instead of using the global random function, so changes in adjacent systems don't bleed over. You might want to implement it soon. It won't get the city back that you're familiar with, but it will ensure you don't keep having these problems. It should also minimize generation "noise" if you ever decide to animate a high-level parameter, like island size. That would be an interesting "shrinking battlefield" game, where instead of the Battle Royale allowed zone shrinking, the generated area itself is shrinking.
I like how the new road system looks even more like a circuit board than before.
It's not a problem with the random seed, since those systems use independent random number generators. It's because the placement of roads affects what areas secondary buildings can be added in, which affects the placement of those buildings, which affects the contents of those buildings. So a town will develop differently if there's a freeway running through the center of it. It all makes sense, and it's not something that can easily be fixed. The only way I can think of fixing it is by placing buildings without checking that the location is valid and removing them later. That way the valid building placements are all independent of what areas are valid. But this tends to break the user's control over the total number of buildings placed. (Note that this doesn't apply to the infinite/tiled placement algorithm, which won't suffer from this problem, but I'm not using that for this scene.) And anyway, making that change also will generate different buildings from what I'm used to. Thanks for the suggestion though.
DeleteOh and yes, there actually is a road running right by the starting location with the new algorithm. There's no way to avoid having the starting area look different. Look at the small red circle on those two overhead map images - that's the player's location. There's a north/south road to the right of the player in the first map, and an east/west road directly under the player in the second map.
Delete