So lately I’ve been working on a city-simulator. I’ve tackled a lot of interesting problems and have been posting some progress shots on Twitter.
Sometimes I get requests for a writeup on my process, this is generally a good thing, people are interested in what I’m making, and I get to spew out my thought process on the internets.
My aversion to this is because I prefer to save writeups like these for post-mortem. There’s a lot more interesting things to tackle that I have yet to tackle, like socio-economics simulation, or culture generators. The technical stuff, that stuff comes pretty easily, to me it’s not as worth that much talking about.
On top of this, I really hate doing “marketing” for a project before it’s ready (blog posts are marketing now, apparently). I’m not a fan of this “release early release often” marketing approach for indies. Yes, there are benefits of doing this, however the surprise factor, the freshness factor in the eyes of people worth seeing it will be diminished. I find the lack of surprise in a transparent development process to be quite the hinderance later on.
During my daily trawls through twitter, I found this curious post about procedurally generating Millennium Falcon style texture maps. I mean, this is really great stuff, I’ve always wondered about doing something like this — how one might actually approach this problem. I can see baking the AO, what about generating the greeble? What about connecting lines across multiple surfaces so they all line up? Defining what parts of the mesh is an exhaust port and giving that the appropriate color? That stuff is fascinating to me.
As an impatient person it also really frustrated me that Howard Day (what a name) didn’t also include a process-post. The nerve! Showing cool shit off on twitter without talking about how it’s made.. that is so annoying.
Wait a minute. That’s exactly what I do. Shit.
So I’ve managed to guilt myself into doing a writeup. This is good, at least it’ll be written down somewhere. The most recently asked topic was about road tiles, so let’s start there.
Where we’re going we actually need roads
This is going to be an awkward writeup since I’ve tackled this exact problem at least three separate times (that I can count) and came up with different approaches each time. There are also numerous inter-connected problems that have to do with game design. I’ll just focus on the direct problem and the solution I ended up at, skipping some seriously circuitous problem solving that will only take you down some nasty rabbit holes.
The premise:
The game is a city simulator, so one has to think about road planning, the veins and skeleton of a city. Making a few gameplay assumptions, this generally means allowing the player to directly draw roads, place them on some surface, connect roads with each other, etc.
The original Sim City by Will Wright was created because he had more fun designing the maps for Raid on Bungeling Bay. The tech at the time only really allowed for tile-based map visualization, it was great because you can get excellent variety with a ton of re-useable assets.
The roads ended up being on a grid, which has some inherent limitations. Diagonal roads are harder to make, and we’ll see why when we break this problem down.
Here the road tiles are represented by R, perhaps a number in our data map. Zones, parks, police stations, they all occupy some space on this map, so they also get separate id numbers as well.
This is not good enough. Just because the data looks like this, road tiles aren’t a uniform graphic that you can just clone stamp across the rendered map. Roads have directionality, the tile that gets drawn needs to care about what tiles they’re connected to.
The simplest variations are pretty straightforward. You have roads that go up and down, so you have these road tiles going from north to south, center divider is vertical. Ditto with horizontal. When these orthogonal directions intersect, you have an intersection, so perhaps this tile connects to all 4 corners, with stop lights. There are more variations, such as a T junction (4 variations).
To know what graphic should be drawn at a particular tile, you have to know its neighboring tiles.
This is a pretty well established gamedev problem. Essentially, an artist draws every possible permutation of connected roads (or whatever, it could even be connected cliffs / ground tiles used for side-scrolling games for example). Then the map designer simply picks the right puzzle piece to use for that particular section of the map.
There are several (annoying) problems with doing this.
Making the assets would be a combinatorial nightmare. Imagine having to create the above just for one version of this tileset. If I wanted to have wider roads, or highways, I have to do the above all over again. Even in the above example image, there would be no way of creating arbitrary turns or intersections on terrain that goes up or down unless I also want to author that! Let’s not forget what if we wanted diagonal roads?
As an aside…
At some point you’ve probably asked yourself why I even bothered to stick with tiles and not just do arbitrary straight-line roads. I guess that’s an article for another day, however I did do that experiment and ended up with some OK results (with a slew of other kinds of problems).
So now we’ve identified the problems:
We need a fast way to generate all possibilities of road connections before the heat death of the universe.
We need a good layout engine that can seek neighbors and pick the right tile to use.
Let’s talk about the layout engine first since we need a plan for this.
The most naive implementation of a world map looks something like this:
Here, 1 represents a road tile, and 0 represent nothing, empty space.
The layout engine that picks the tile would go through the map grid in a 3×3 pattern and examine each tile and its neighbors.
What happens when we only examine orthogonal directions, ignoring diagonal tiles completely?
So for example in the above illustration it would look like.
Top left (tile by itself)
0 010 0
Top right (tile going north)
1 010 0
Bottom left (L shape, north and east)
1 011 0
Bottom right (intersection)
1 111 1
This method is alright so far. In fact, we can then compact this information into a lookup table, so it looks like a binary
Top left (tile by itself)
00100
Top right (tile going north)
10100
Bottom left (L shape, north and east)
10110
Bottom right (intersection)
11111
If we continue this, we can then create a lookup table that contains all combinations of road tile connections and their associated graphic tile.
This is good enough if we only care about orthogonal road maps, however that makes for some boring road layouts. Diagonal roads would make this way more interesting, for instance Sim City 4:
Okay, this should be easy right? We were only examining the orthogonal tiles, we should extend this to the diagonal tiles if we want this feature. Let’s take a look at what happens:
From left to right…
Top left diagonal (going to north-west)
100 010 000
Going north AND north-west (?)
110 010 000
Going north AND west AND north-west (???)
110 110 000
Uh oh.
What’s happening is that the tiles don’t care at all about connectivity, since this whole system relies entirely on a binary switch of their neighbors. When diagonals are connected alongside their orthogonal brethren, you end up in this situation where it’s totally ambiguous how the roads should be formed.
111 111 111
What happens now? Should this be a star intersection? Or a just a big parking lot?
Not to mention, we wouldn’t be able to have roads that run alongside each other.
Check yo bit flags
What we really want is a system that says, road tile, you areconnected to north, south, and north west, and that is all. We can represent this information as such:
So when we touch the map, we have to be aware of what is being connected to what. Each tile needs to connect back to each other in order for this to work.
Now I were really lazy I would just leave it as is and call it a day. Good job Michael.
However, we can improve this code so much more.
For instance, the tile really should have no place carrying 8 pieces of information. It sucks to have to check each boolean here, on top of that it’s a huge waste of memory and manipulating this information would be quite annoying.
Instead, each tile should just carry one unique number to represent any of the possible connections, diagonal or otherwise, just like we had before. To do this we need to use bitflags.
This allows us to create ‘flags’, booleans that can be added to and checked against in a number.
So to continue this, we can build a definition of directions
And now each tile has some notion of what neighboring tile it’s connected to!
This has some pretty staggering ramification, not the least path-finding will be quite different. Some of the issues I talked about earlier are now solved quite handedly:
It is now no longer ambiguous which tile is connected to which, since we know for certain that the orange highlighted tile is connected to northwest, west, and east, and nothing else.
We can then do stupid stuff like having that angle tile connect back to its orthogonal neighbor:
Build a neighboring road network that don’t touch the existing ones:
And all manners of weird edge-cases:
What gamedev tumblr post would be complete without an animated gif?
I haven’t even touched the geometry generation aspect of this project yet so perhaps I’ll head there in my next post since there are a lot of issues in the above that I haven’t even mentioned.
If you enjoyed this, please RT me @mflux feel free to ask me questions or give me suggestions and comments. You can also find me lurking as a moderator on reddit.com/r/gamedev, a great community of game developers on reddit.
Finally if you’re curious what tech I’m using, this is all Javascript, using THREE.js running WebGL.
