Longest Road

For the next few articles, I'm going to switch from talking about isometric projection and instead talk about orthographic projection. Instead of the map tiles being viewed 'sideways', they are viewed 'top-down', and are actually square instead of diamond-shaped. The material discussed in these articles is equally applicable in either projection, but the concepts are a bit easier to grasp in orthographic projections.

Consider the following two tiles I have whipped up: a red brick road, and some comfortable-looking picnic grass:

I wish to use them to create a pathway winding through a village, and so I arrange them like so:

As in my previous tileset post, the results look fairly seamless between two road tiles or between to grass tiles, but the edges between road and grass are perfectly straight and perfectly right-angled. I would like to create more road tiles that are a bit irregular to reduce the impact of the otherwise-rigid nature of the tiles I am creating.

The question is, how many more tiles would I need to create in order to allow me to construct any road I can imagine?

Cue Final Jeopardy theme here.

If you need a hint, consider the board for the classic board game the aMAZEing Labyrinth.

For another hint, consider the number of edges of a square, and Pascal's Triangle.

Give up?

The answer is sixteen.

For a particular square on your map that is meant to be a road, the tile you use to represent it depends on whether or not the four tiles directly north, east, south and west are also meant to be roads. Since each is either meant to be road or not, there must be 2^4 = 16 required tiles.

These sixteen tiles can be grouped into five categories, based on how many adjacent squares are also road squares:

• All four adjacent squares are road (4 choose 4 = 1 option). This is a four-way intersection.
• Three adjacent squares are road (4 choose 3 = 4 options). These are three-way intersections.
• Two adjacent squares are road (4 choose 2 = 6 options). Four of these are right-angled bends, and the other two are north-south and east-west road segments.
• One adjacent square is road (4 choose 1 = 4 options). These are 'dead ends'.
• No adjacent squares are road (4 choose 0 = 1 option). This one is just a single cobblestone, standing by itself. Whether or not you want to actually include it is a matter of personal preference.

To make the example concrete, here are the sixteen road tiles required for the green grass and red brick above:

I will go over exactly how to create these tiles in another post.

Using these tiles, we can recreate the earlier town path with roads that are not as harshly aligned:

These tiles are sufficient if we wish to build roads which are a single square thick. However, they break down if we want to build roads multiple tiles thick. The closest we can get is this:

The problem here is that, due to the way we have constructed the tiles to only consider adjacent tiles in the four cardinal directions, they don't 'connect diagonally'.

The question is, how many tiles would I need to be able to create roads of any thickness?

Forty-seven.

"Seriously?", I hear you ask, incredulously. Forty-seven isn't a multiple of two like sixteen is. It's not even even. Hell, it's not even composite! How can that possibly be the correct answer?

Think about it. The answer will be revealed in the thrilling conclusion.