Fuel: Roads

 By Shamus Sep 28, 2009 34 comments

This shows the zooming in, just to give you a sense of scale of the world.
This shows the zooming in, just to give you a sense of scale of the world.
I mentioned earlier that I wrote a road-generating program. I want to talk about that project a bit and then compare it to what we see in Fuel.

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:

fuel_heightmap.jpg

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.
Top: The road system on perfectly flat terrain. Bottom: The road system in pervasively hilly country.
Fuel seems to take a similar approach. It works out a network of roads. It begins with a couple of backbone highways that cut across the zone. Between those, it will form a loose grid of evenly spaced secondary roads. And between those it makes a network of dirt roads. It deliberately tries to make them a bit convoluted. You can see this in action in White Flats, one of the last zones in the game to be unlocked. (I cheated, as unlocking this zone would have been way beyond my skill.) The land is, as the name suggests, perfectly flat. Yet the road system doesn’t just default to an axis-aligned grid. Roads intersect at odd angles and form a plausible network. However, the individual roads are perfectly straight. This suggests that the road system works not unlike the one I came up with, where roads bend due to topography. This means the bends in the road are emergent, which is pretty cool. (As opposed to the programmer trying to force the road to bend around arbitrarily to make it more “realistic”.)

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.
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.
It's hard to see, but just above my driver there is a staircase-shaped seam where the two roads were stitched together.
It seems like team Asobo ran into the exact same problems. They have all the seam issues I anticipated, although they to manage to make a bulk of the road joins look passable by blurring and fading the textures where they meet. Still, every once in a while you’ll see a spot where it just couldn’t solve the splice, and you’ll get all sorts of strange artifacts. (Although to be fair, you won’t notice these bits if you’re just roaring along at 100mph, which is more likely than not.) There are a pair of extra-large four-lane highways in Fuel, and they join just southeast of the center of the map. The texture mapping is predictably wonky, but the real hilarity is that one of them brings its guard rail into the merge, thus cutting off a lane of traffic with a completely inappropriate guard rail:

Guardrail fail.
Guardrail fail.

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.
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.
There are no over passes in Fuel, and no clover leaf intersections. I can understand why. Knowing when to place one or the other, and making them look acceptable on arbitrary topography, is a huge problem to solve. Engineers design these things do so on a case-by-case basis, and in games these things are made by hand, by artists. This is the first game I’ve seen where someone took a crack at doing this with code. Sometimes you need to take away earth. Sometimes you need to build up. Often you need to do quite a bit of both. You need enough clearance on the bridge yet the ramps of a cloverleaf can’t be too steep nor turn too sharply. And of course, cloverleafs would look naked without the copious signage required to make use of them, and placing those signs where they will look right and not cause problems for either of the intersecting roads is a non-trivial problem.

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.

201434 comments. Hurry up and add yours before it becomes passé.


  1. Maldeus says:

    Shamus, has it ever occurred to you that you’re a hop, skip, and a jump away from being able to single-handedly create a procedurally generated game with potentially infinite content? Okay, granted, the reason this hasn’t occurred to you is probably because it’s not actually true, but you do so much procedural stuff anyway, why not make a checklist of everything you’d need to make a procedural game of X genre, and then whenever you’ve got the time for something like the Terrain Project, pick something off the list and have at it?

    EDIT: Also, first.

    • noahpocalypse says:

      You, my friend, can predict the future. (More or less.) (Or maybe you gave him the idea. So perhaps if we’re expecting something to happen, it happens. Or you just planted the idea.)

  2. Randy Johnson says:

    @Maldeus If he did do the highway project, he could easily mix it with the Procedural City to make a nice Truck Driver game. I would play it.

  3. Kerin says:

    The funny thing is, you can actually see issues like* this in Dwarf Fortress, especially if you have multiple biomes right up against one another.

    *sort of, but really not all that similar. It’s friggin’ text, for chrissakes.

  4. karmuno says:

    Of course the real challenge would be procedurally generated physics, gameplay, and intuitive user interface. Which would be totally awesome.

    And Shamus, you mentioned in one of your Oblivion posts (I think) that it would be easier to make the world if the artists procedurally generated it first, then added details. A similar thing could work for intersections, signs, etc. Simply build the world procedurally, then go through and make everything look pretty. Unless procedural content is the purpose of the game (for an exploration-type thing which is different for each person) or part of a larger system that would be impossible to do otherwise (Spore creature animations, Civ IV’s map generator I think), simply using procedural generation as a design tool would work. Although it may make the file sizes prohibitively large.

  5. Tom H. says:

    There actually are multiple academic research projects doing procedurally generated cities, some of which have tried to deal with the road problem, and at least two of them have spun off commercial companies:

    pixelactive.com has a gallery; look at image 6 to see both some decent joins and some mild fails

    procedural.com also has a gallery; see for example http://www.procedural.com/cityengine/provided-examples/modern-streets.html. Pascal Mueller is probably the best-known researcher in the area; most of his more recent work has focused on buildings, rather than city layouts.

    IT Blanchardstown, Ireland was doing work on this a couple of years back. They wrote a survey paper at the time that is one of the few good collections of ongoing work I’ve seen.

  6. Deoxy says:

    If you watch one of the bonus features in Finding Nemo (or maybe it’s one of the commentaries on the movie? been a while), they talk about how they made a lot of the ocean, with the particular example of the anemone. It was a simulation (current to make it move, etc), but it made little mistakes every once in a while, which they fixed manually. They ended up calling it “99% simulation, 1% animation” (or something like that – it was a high percentage).

    Sounds very similar, and it worked great for that… but in something this big, they would have to go through the whole game world carefully, and that would take a long time… still better than making the whole thing by hand, mind you, but still…

    I think it would be better to go through the game, find the problem areas, determine why the code fails there, and fix the code instead. But that would be EVEN MORE time-consuming (at least, if you only use it for that one game).

  7. bbot says:

    You “cheated” by just driving into it? FUEL throws up no invisible walls, you just can’t see any of the events in a zone you haven’t unlocked yet.

    Which would be absolutely terrible, if I did any of those events.

  8. Doug Sundseth says:

    In the real world, road systems sometimes default to a rectilinear grid. This normally occurs where roads are a late development and is particularly common in areas of the US largely settled by homesteading. (For examples, search for Bennett, Colorado, or Enderlin, North Dakota, on Google Maps.)

    The roads are so aligned to the grids that they will occasionally jog 1/8 mile or so to match the surveyors’ correction lines required by imposing a flat grid on the (mostly) spherical planet.

    An odd detail (caused by costs of construction and use) is that the major roads are less likely to follow the grid than the minor (often dirt roads).

  9. Stormcaller says:

    My understanding of how they generally do overpasses/underpasses IRL is to put one over, one under, repeat. This way the dirt dug out for the underpass is used for the approach ramps on the overpass.

    Of course it could be different in the US.

  10. SatansBestBuddy says:

    @Shamus: A half hour?

    As in 30 minutes of just nonstop driving?

    … I kinda want to try this game now just to see how big it is, cause the biggest open world game I’ve ever played took 20 minutes to drive from one end to the other. (San Andreas, and I did it cause I had good music and a motorcycle so I felt badass just cruising down the highway)

    • Shamus says:

      SatansBestBuddy: I think I worked out that if you got the fastest car, jumped on the interstate, and went full-tilt, you’d cross the world in a bit over an hour. (The interstate isn’t quite a straight shot.)

      If you went off-road or even just took secondary roads, you’d likely take a lot longer but see a lot more interesting stuff. The interstates cut through dull wastelands, mostly.

  11. Jeff says:

    Psst, Shamus.

    They have all the seam issues I anticipated, although they to manage to make a bulk of the road joins look passable by blurring and fading the textures where they meet.

  12. Kalil says:

    Shamus: Ever toyed with Daggerfall?
    It’s an old game – the predecessor to Morrowind and Oblivion – and it is primarily composed of humongous fully 3-d maze-like dungeons. While the content is static game-to-game, I’m fairly certain they were originally generated by some manner of procedural program that pieced together a set of pre-made pieces into a coherent maze. The scale of the resulting game is mindboggling – it’d take the better part of a week to traverse the countryside on foot, and there were thousands of dungeons, most of which could take several hours to explore. Granted, much of the content felt repetitive due to the limited number of ‘legos’ the dungeons were composed of, but the mazes themselves were pretty cool.

    With modern graphics, it’d be a lot harder to pull off – daggerfall had ‘seam’ issues even with its far simpler graphics, and falling through the world through a badly joined seam was an uncomfortably common occurrence. Still, the idea of using some form of procedural generation to piece together artist-designed rooms and decorations can be highly effective. There’s a reason that DII remains one of the most popular games of all time.

  13. ehlijen says:

    Seeing as neither your nor fuel’s model seem to account for it, I’m assuming the US doesn’t have highways gently curve just for the sake of it in order to give the driver something to do to avoid road fatigue?

  14. Kalil says:

    Re: Ehlijen,
    Yes, we do, but only highways, and generally only in the countryside. City roads are usually as straight as possible – land values are too high to waste on keeping drivers awake.

  15. jubuttib says:

    Ah, Daggerfall. Around 161,000 square kilometers, over 15,000 towns, cities, villages and dungeons, over 750,000 NPCs. If you haven’t seen it for yourself, hop over to wiki and check out the article, it has two images that explain the scale quite nicely. Every damn area seemed to have more stuff in them than Morrowind and Oblivion combined.

    I do wish they’d do a TES game with the whole of Nirn to explore. And proper scale. The best map I’ve seen using Google Image Search had a proper map legend and scale, which suggested that the Imperial bridge alone is over 20 miles long. Quick travel is ok, but running 20 miles should take time.

    And seeing the picture of dice on the bottom of this page reminded me that I’ve just ordered a 7-piece set of Ruby Precision dice from Gamescience. I can hardly wait for them to get here.

  16. Factoid says:

    @stormcaller: In the midwestern US we have very few underpasses. I’m not sure if that’s just a regional thing, or what.

    The land is pretty flat out here, so we have lots of places to dig up dirt for approach ramps, especially because the flatness usually requires the digging of drainage ditches.

  17. Zerotime says:

    SatansBestBuddy, Shamus: There’s two achievements in the game that involve driving from one corner of the map to its diagonal opposite without using the helicopter transports, and I’ve found myself being a completionist jerk lately. Even in/on the fastest car/bike in the game, it’s like two hours corner to corner – much of that at 130+mph.

  18. Simulated Knave says:

    A point – if you look closely at real roads, there’s a lot of seams where new/old asphalt meets asphalt of another vintage.

    This would seem to be the one kind of road you could get away with it…

  19. ehlijen says:

    Kalil:
    Yeah, that’s what I meant. In europe city streets are only as convoluted as they are because the buildings where usually there first.

    But so despite the US having curving highways, neither the game nor Shamus’ model implemened it? I’m assuming it’s to keep the code simpler, yes?

    Anyway, I learned a new trivial fact! Yay!

  20. Ian says:

    Daggerfall is also now avalible from Bethesda for free

    http://www.elderscrolls.com/downloads/downloads_games.htm

    Does take a little fiddling with DosBox to make it realise you have enough hard disc space but it does work with the full install. I remember reading all about it and desperately wanting it and then somehow missing it entirely.

  21. Unconvention says:

    clover leaf intersections

    Heh. Crazy Americans.

  22. Arquinsiel says:

    You need to visit Ireland. Those images you show of problem joins look perfectly plausible after living here for long enough.

  23. chabuhi says:

    I’d love for Daggerfall to be remade in TES. I know it shouldn’t be all about the eye-candy, but dammit if those DF screens aren’t icepicks to the eyes these days. :(

  24. Kell says:

    @SatansBestBuddy

    I actually did the drive Shamus sort of suggests: the first time I saw White Flats was well before I unlocked it, by simply driving there from an unlocked region further to the west ( the gameworld of FUEL is unlocked roughly from the top left, down, to the middle, down again, along the bottom, and finally back up the right side ).

    I can’t remember exactly how long I took, but half-an-hour sounds about right. There’s a very obvious, artificially placed mountain range that separates White Flats from the land to the east. I travelled to the foothills by bike, then switched to an SUV to climb over the mountains and gain my first view of the salt plain, in the moonlight.

    Anyone who enjoys the heightmap exploration experience in games is well advised to check out FUEL.

  25. Kell says:

    Regarding the guard rail fail: I stumbled across that hilarious clunk in the road system myself, while free riding down the interstate on a very fast bike ( amusingly, the north carriageway of the interstate is free of debris, while the south carriageway has long ramps and jumps every now and then. Pedal to the metal. )

    The funniest thing is witnessing one of the AI trucks that populate the roads slamming into the misplaced barricade and grounding itself. I watched one sit and spin its six wheels ineffectually for a minute or so until gravity finally won out, it listed painfully to one side, and hauled itself free like a geriatric bull.

    Really, aberrations like this are very, very rare in FUEL. There is an incomprehensibly large amount of content, and almost all of it joins up just fine. And even when you do find them, it doesn’t spoil any of the fun.

  26. guy says:

    I’d think that badly screwing up cloverleaf intersections would just make people chuckle knowingly about whatever highway engineer practical joke is in their area.

  27. Jeff says:

    Oh man, Daggerfall.
    A giant place… full of pretty much exactly the same thing. Sometimes when I wasn’t paying attention, unless I checked I wouldn’t even notice if I had circled around back to the same town, or hit an entirely new one. Ugh. A giant expanse full of clones building the exact same buildings.

  28. Anonymoose says:

    I wouldn’t hold Dwarf Fortress up as a zenith of programming and the procedural content still needs some work. Dwarf Fortress has accomplished a LOT, don’t get me wrong, but the programming usually isn’t optimal. The game is 5-6 megabytes, uses ASCII text for graphics and can bring a modern computer to its knees. (Last I checked, it doesn’t support dual-core machines in any significant way, IIRC because Toady doesn’t know how to program such support. Not that I think less of him for it, I am confused by the old “Hello World” exercise.)

    Procedurally, it does a lot right but does still feature some of the clashing terrain Shamus speaks of. It’s just hard to see it without any fancy graphics.

    No offense intended towards Toady, the developer. Like I said, he’s accomplished a lot. However, in terms of code and content, I think procedural games still have lots of uncharted ground to cover and kinks to work out.

  29. Shoku says:

    DF is typically just so vast that other people actually setting out to program something themselves can’t fathom trying to do the same thing.

    Plus there aren’t all that many games where players can pull a switch to flood a room for of npcs they dislike in the first place much less watch an enemy liquefy upon impact with the ground after a long fall. And then you learn that they feel good after complaining to the mayor and can drown in their own blood if they get stabbed in the lungs.

    Anyway, I live in a mountainy area and while we’re all clustered around this mostly flat stretch of land the rich folk all line their houses up on the curve up the mountain as if to look over us and say they can afford to build a house that’s a pain to get to.

    I guess the best way to think of the roads that have much height change is that they came after we had a lot of stuff in place and then said to ourselves “we hate that it’s so hard to go between the cities.”

    The bridges idea seems to mostly handle that but you could do more complicated ramps for the screwy steep slopes that break the rules as well (though only in highway style because I don’t think anyone would bother with this sort of thing for a low traffic road.)

  30. Zak McKracken says:

    Only loosely related, but talking about procedurally generated content:
    http://www.youtube.com/watch?v=9CUmWWqfwV4&feature=related

    the source for this video has 4k! That is 4096 Bytes, and that’s it.
    I stumbled over the videos from this year’s Breakpoint (which will probably be the last ever …), and it’s amazing they’re still teaching the good old C64 new tricks even today, all by the powers of procedural … stuff.

    So if you have too much time on your hands, go looking for “Breakpoint 2010″ (or any other year since 2000, I think) at youtube. Amazing …

  31. noahpocalypse says:

    First, what if you rendered all the roads and the textures and bump maps and stuff first, then went over the middle of every road, laying down a strip of yellow or white? That sound like it would merge perfectly. Of course, you would need to add extra code for the lines on the sides of the roads, but that doesn’t sound too hard.

    A blend of textures designed just for a road would look decent, wouldn’t it?

    Second, epic necroing.

Leave a Reply

Comments are moderated and may not be posted immediately. Required fields are marked *

*
*

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun.

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!