Paving the way

Hello world.

Today, let’s talk about tilings! More precisely, let’s talk about the work that paved the way toward the current implementation of regular and semi-regular tilings in my MML and Stream projects (a maths library and a tower defense game using it). Let’s talk about how it started, about implementation constraints, about game rules regarding such tilings, about the bugs I’ve faced along the way, about the changes that were required…

This article has more than one goal. Of course, the main one is to talk a bit about what I do, to go behind the scenes. But it’s also an opportunity for me to look back on the work I’ve accomplished and put things in perspective.

In the beginning, there was the Square

Someday, a few months ago, while gathering ideas about what would soon be nicknamed Stream, one stood out: what about trying to use other tilings that the overused square one? What about a tower defense game on a triangular or an hexagonal grid? Before trying to implement things right away, time for some Wikipedia browsing. It was then that I found this beautiful page.

To think I had never heard those names before! Snub square tiling, rhombitrihexagonal tiling… I hastily declared I wanted to implement them all, if only for the pleasure of creating images with those.

But this choice already meant some technical and architectural difficulties.

Cheating considered harmful

Of course, when facing something a bit tedious, the first thing that comes to mind is: how can I cheat my way around that? A prime example of that is the aforementioned square tiling. If one wishes to implement a square grid, it is useless to store in memory the full (and verbose) list of all squares. It is indeed far simpler and easier to just abstract the square gird as a 2D matrix; each cell of the matrix corresponds to one of the game squared cells.

This abstraction is perfect because the Cartesian coordinates of each square can easily be deduced from its position in the matrix. For a given square size n, the cell at row y and column x would correspond to:

points (Ox + n *  x,      Oy + n *  y     ) (Ox + n * (x + 1), Oy + n *  y     ) (Ox + n * (x + 1), Oy + n * (y + 1)) (Ox + n *  x,      Oy + n * (y + 1))	neighbours (x + 1, y    ) (x - 1, y    ) (x,     y + 1) (x,     y - 1)
Square tiling matrix.

To summarize: a simple pair of coordinates (x, y) is enough to represent / abstract each square of a square tiling. That information is enough to deduce worth knowing about a given square: the coordinates of its four points, which squares are its neighbours…

The same thing can be done with triangular and hexagonal tilings, although in a less intuitive fashion: it only requires to “skew” the “vertical” axis. Therefore it is still possible to abstract such a tiling as a 2D matrix and to associate a simple pair of coordinates to each of its cells.

However, this can only be done with the three regular tilings (triangular, square, hexagonal), because of their uniformity. Semi-regular tilings, however, are made of more than one kind of regular polygons, which means no matrix representation. Which, in turn, means I had no choice: for all those tilings I had to generate a real set of polygons and not just a bunch of coordinates.

No way to cheat.

Repeat after me

So, how should one generate tilings? The solution I chose seemed easy at first: make each tiling into a “square” one! This can be done by identifying a specific meta-shape (made of adjacent polygons) in the original tiling. Such a meta-shape must only exhibit the property of being repeatable on two perpendicular axes.

With this meta-shape, generating a given tiling is easy: I just had to use it as a pattern and repeat it as much as needed. The process is as follows:

• generate the pattern according to the given parameters (center point, orientation, deformation parameters if any);
• compute an estimation of the number of repetitions needed to cover the entire given enclosing shape;
• iterate on all polygons of all repetitions of the pattern.

Due to performance concerns, the tiling generator does not output a container of copied polygons but provides an iterator based interface. Polygons are therefore generated on the fly during the iteration. Furthermore, each iterator gives access to additional meta-information for each polygon; for instance, each polygon “knows” the list of all previous polygons to which it is linked, something which is needed in order to generate a graph.

I won’t speak here about how to represent polygons in memory and how to implement intersection / overlapping algorithms: that could be the subject of another entire article, half of it being a collection of bugs I’ve encountered. (Yes, that’s because I rewrote them instead of using a library. As I said: NIH!)

Le First Bug

Of course, it did not magically work right out of the box. Of course, there has been a few compilation issues: the lengthy compilation logs that meta-meta-programming can create are sometimes a bit unreadable (BOOST_PP, I’m looking at you). Of course, there were also a lot of small mistakes (such as coordinate issues), but nothing a small test suite can’t catch. But then there was the First Major Bug, the one that caused the First Rewrite.

A particular technical choice in Stream made it easy to spot: I wanted all coordinates in Stream to be integer values. Of course this means losing a lot of precision, but I was hoping that could therefore mean less weird rounding bugs (I might have been a bit too hopeful). Anyway, this is not what caused the bug, but merely how I got the chance to spot it.

It was of course an approximation and rounding bug, as expected. Each point in the patterns I used was computed in relation to the first point of the pattern. But, due to rounding issue, this meant that the “same” point on two opposite sides of the pattern could be rounded differently, meaning that the junction with the next repeated pattern was not made appropriately. The solution was as obvious as painful: I had to rewrite the entire pattern generation code. I now use (in most cases) a pre-computed point grid, which ensures that the vertices of two adjacent polygons are now really the same.

One down, a few more to go.

From tiling to graph

With all those polygons now correctly generated, I was able to generate the graph that would be used by the game’s path finding code. Nothing too fancy: each polygon’s center is a node, lines from one node to its neighbours are the edges.

(Pour those interested, the game currently uses a very specific path-finding algorithm named Lifelong Planning A*, which is based on the well known A* algorithm, but in which each search reuses information from previous searches. More to come on that subject.)

Then, suddenly, there wasn’t any major issue for a while.

But then I decided to implement a new feature in Stream: terrain type and its consequences. I was planning only two alternate terrain type (the default being “plain”):

• forests that slow down but protect foes,
• roads on which foes go faster but are more vulnerable.

It sounded quite easy to implement, at first: I just had to apply a factor to each edge’s length. An edge through forest would seem longer, a road edge would seem shorter, and the path-finder would work without even noticing that anything changed. It would simply use a “perceived” distance rather than a “real” distance. But that was a bit too optimistic. What about an edge going from a forest cell to a road cell? How should the coefficient calculated? Would it even make sense to see foes travelling at the same speed on the road part and on the forest part of the edge? (Protip: it wouldn’t.)

The solution was to add new intermediate points in the graph, by splitting each edge in two segments: one from the center of the polygon to the center of its edge, the other from the center of the edge to center of the next polygon. Each edge is now fully inside one polygon, which solves the problem. Or so it seems.

Point break

A bit later, when working on a level editor for Stream, I added a tool that allowed me to preview the shortest paths from one given polygon to another. This allowed me to immediately see how a given change in the level would impact the path-finding and, therefore, the gameplay. But soon, another issue appeared. Some paths were ignored, while they were strictly equivalent to the non-ignored ones. All paths seemed to favor a few specific points and ignore the paths that didn’t went through them, as shown in the illustration below. Red lines show all the fastest ways from the green cell to the red cell. But some equivalent paths are missing…

The usual suspects were all innocent: points were correctly generated, alternate but ignored edges seemed to have the same length… However, I soon discovered that this kind of bug only occurred when crossing one of the axis, moving from negative to positive values.

I then quickly found that the issue was caused by the intermediate points… The cause was the default rounding method used in the MML: a symmetric method named “round halfway from zero”:

•  13.5 was rounded to  14 ;
• -13.5 was rounded to -14.

But this symmetry was not welcome, as this method would round intermediate points differently according to which side of the axis they laid. Forcing the rounding method to be a “round half up” fixed the problem. It gave me the opportunity to realize how much such a seemingly trivial mathematical operation could hide a world of complexity…

Updating the rounding method meant the intermediate points were correctly generated. Which meant paths weren’t ignored anymore, after a few long weeks of debugging…

Nervous breakdown

In a le sophisticated way: le fu.

The path-finder DOES avoid the black wall, it DOES find a way around it, but it drastically ignores the very same path that goes below the wall.

GOTO 10

After a bit of hair pulling, I finally understood that the issue displayed here was in my code since the very beginning. So rooted in the code that I would almost require a full rewrite. As usual, as always, it was a rounding problem… The issue was in the point grid. Due to the rounding that occurred during the grid generation, in some of the most complex patterns there could be two edges with different sizes although they were supposed to be identical…

The solution was to go back to the drawing board. To compute and add a new information to all edges during the tiling generation: their theoretical length. The code could use this value instead of computing their “real” lengths according to approximated points. This was a rather tedious task.

To check that I didn’t do anything wrong, I generated debug images such as the one included below. At first I started with a set that allowed me to check the consistency of my theoretical values. In this first set, a different color was assigned to each length (chosen amongst a set of fixed and easily identifiable colors). Two edges with the same color would therefore share the same length (down to the very bits: I was comparing values of type double using the == operator).

Before	After
Real computed edge lengths: a dozen of different colors.	Theoretical edge lengths: only three colors remain.

The second set I used to check the “plausibility” of those theoretical distances: the bigger the difference between the theoretical and the computed value, the brighter the edge. No use in showing them now: it was but a debug tool (and since it’s now fixed, the “after” column would only show an empty black picture).

But wait, there’s moar!

Now that I have beautiful tilings and a path-finding that works, there’s but a small thing left to do, and that’s making a game out of it!

Back to work!