on Sep 28, 2009
|This shows the zooming in, just to give you a sense of scale of the world.|
Roads are interesting because of how organic they look. They bend and twist and split and have overpasses / underpasses, change width and (from a distance) tend to resemble more a circulatory system than a circuit board.
Roads have rules which most of us intuit even when we don’t think about it, and when a virtual road breaks those rules it tends to break immersion as well. Proper public roads generally don’t bank (or only do so very slightly) but are graded such that they are higher in the middle, so rainwater will run off. Roads tend to change direction more readily than elevation. When circumnavigating a hill, the road generally cuts into a hill a bit, (as opposed to jutting out) so you’ll have a steep bank upwards on the inside and a drop downwards on the outside. If that drop is steep enough or the road curves abruptly enough, there’s usually a guard rail. Roads bend all over the place, and it’s not uncommon for you to find yourself on a “northbound” highway heading due east or west. And there is a limit on how steep a road can get.
And these are just the rules for a single road, which is what my program dealt with. (It was eventually going to be a screensaver. If I were to do it again I’d no doubt put the thing on Google code for safekeeping.) The program would load in or generate some hills of dubious realism. (This was before I did my terrain project, so the terrain system here would have been crap.) Then it would plot a road to go from the south edge to the north edge. It would examine the angle between its current location and its desired endpoint, and would try to head in that general direction while staying as level as possible. It ran on a flexible scale: The bigger the deviation between it’s current heading and its desired heading, the more willing it was to go up or down hill. This worked amazingly well at producing a road that wasn’t too hilly but didn’t get lost. It had a “create a bridge” fail-safe for when it just couldn’t find a proper solution, which happened whenever it was cut off by a steep valley. The “bridge” was just a section where the road would run straight and level until it ran into the opposite wall of the valley. All told, it wasn’t a flawless system but it produced some amazingly plausible roads on some challenging topography.
Check out this heightmap I swiped from Google Image Search:
On the left is a straightforward heightmap. It’s like a satellite view, with brighter pixels representing higher elevations. The right is the same thing, but with a particular elevation set to red. If you were standing on that red area, you could obviously go pretty far without needing to go up or down, as long as you didn’t mind swerving around a bit. This swerving is basically the exact behavior you see on a road. My program would basically travel on the red as much as possible. If it was forced to go up or down, then the “red” area would shift radially – outward from the tip of the hill if it was moving down, inward if it was moving up.
|Top: The road system on perfectly flat terrain. Bottom: The road system in pervasively hilly country.|
|While not completely unrealistic, this abrupt curve is a little dubious. (There is actually a turn like this not far from where I live. The people who live on the outside of this bend have placed a row of massive rocks in their front yard, just in case some drunk or fool is careening down the road without paying attention. They’ll be stopped by the rocks instead of the house. In the above picture, note the blank gray area on the outer part of the corner, no doubt that exists to hide the awful distortion in the road lines.|
The one thing that bedeviled me was the difficulty of splicing roads together. This has gotten way, way harder as graphics have gotten better. Merging two strips of flat gray polygons is trivial, but a real road isn’t flat gray. Real roads have a very distinct pattern of light and dark stripes, which I assume are the result of tires depositing slight amounts of rubber into the asphalt. Real roads have white lines at the edges, and dashed lines (or double yellow) down the middle. Splicing two of these together is murderously complex, because you can’t allow the texture to distort at all. If you stretch one texture at the point of the splice, the lines in the road will get longer or shorter, and that will look really, really obviously bad. You can’t do a hard join and simply end one road as it intersects with the other, as the patterns of light and dark won’t match up and you’ll get a huge seam. The problem gets even harder when you take into account the fact that some roads will have different numbers of lanes, and they’ll be joining at unpredictable angles. I never did come up with a way to do it without needing multiple texture passes.
|It’s hard to see, but just above my driver there is a staircase-shaped seam where the two roads were stitched together.|
You could solve this problem by having artists make pre-fab intersections. For example, the artists could make the four-way intersection pieces, the forks, and the merges, and the program could use those the way a plumber uses pipe fixtures: Just bend the roads around and plug them in. But that only works on level land, and flattening the land around every single intersection will instantly make the world a lot more generic and repetitive.
|In many cases you can get away with joining two roads with a hard edge, as is done here. It’s not perfect, but it’s not awful, either.|
To the people that have been pointing to Dwarf Fortress as the zenith of procedural content: Being unfettered by graphics, DF will never have to face the worst of the procedural challenges. That’s fine. It doesn’t need to. But the really humbling challenges will be for programmers who have to work with polygons to realize their world.
One of these days I’d like to take another crack at the highway system problem. It’s a toughie, but if you can solve it you’ll have gone a long way to making game content turnkey. Even in fixed worlds like GTA, I’ll bet the art team would love a tool that let them make roads by drawing simple lines, and having the software work out all the messy details and landscaping.
Shamus Young is an old-school OpenGL programmer, author, and composer. He runs this site and if anything is broken you should probably blame him.