Ludum Dare 38:
Planet of Babel

Post-mortem

I participated in another Ludum Dare (three years / eight LDs in a row!) along with my friend and we made Planet of Babel, a multiplayer tactical strategy game, over the course of 72 hours. While a lot of things did not turn out the way I wanted, I learned new things, so I regret nothing.

Preparations

Prior to this Ludum Dare, I decided to finally compile my Haxe libraries into a more standard form, document them well, and publish them for anyone to use. If you follow my GitHub (haha, of course you do), you might have seen the new repository – plustd. It was quite a bit of work, but the library in its current state has a bunch of useful code for platform-agnostic gamedev. The supported targets are Flash and JavaScript (using HTML5 Canvas). Code written using the library compiles to either platform without having to modify it one bit. I am very happy about that, I feel like this follows the Haxe philosophy and everything.

So, armed with my new library, and an amazing girlfriend to provide food and cute ideas on demand, I went to sleep on Friday, one hour before the theme was announced. I had no favourites among the final themes, nor did I have any premeditated game design ideas. This was fine, seeing as the chosen theme (A small world) would not be among my favourites either way, simply because I discarded it as a duplicate theme (Can you spot it?). Back then I did try to participate, actually starting no less than three different games, but none of them made it. And considering that this last LD had almost four times as many participants as the 23rd, I was not surprised or particularly upset to see this duplicate.

Theme thoughts

Upon seeing the theme Saturday morning, I was not feeling particularly inspired for anything specific. I spent a long time staring into nothingness thinking of something "generic", at least for me. A point 'n click adventure? Set in a quarantined city block? Something very much like one rooms? I was thinking of simply doing that, but trying a new graphical style – less pixel art, more hand drawn art. I have a drawing tablet with a display, but I make little use of it … At this point, my idea was essentially "something like Machinarium".

Fortunately, I decided to rethink my approach to the theme somewhat and take a less safe route. I decided I would make a multiplayer game of some sort. The original idea was a roguelite game which people can play simultaneously. Dying would leave behind all the player's items, so anyone would be able to pick them up later. Basically nethack but simultaneous multiplayer.

I did scratch the roguelite aspect pretty quickly though – my first multiplayer game would be difficult enough, even without mixing procedural generation, RPG stuff, or character creation into the mix. I did not have a concrete idea of what the gameplay was going to be like, but turn-based something on a shared planet sounded good enough for me to just go with it.

Geodesics

It was time to figure out how to divide a sphere-esque 3D surface into a grid of tiles. With some Wikipedia-ing, I found out I should probably go for an icosahedron with subdivided faces. The code turned out ugly and slow (in an academic sort of way, there was no serious impact on performance from this), but it worked. The algorithm is roughly:

  1. Generate the 12 points of the icosahedron. This is done by taking the vector $\begin{bmatrix}0 & 1 & \phi\end{bmatrix}$ ($\phi \approx 1.618$) and finding all of its cyclic permutations and sign flips. The resulting vectors are 3D coordinates of the points.
  2. Find the edges and faces. I did this hackily by declaring two points are joined by an edge if the distance between them is smaller than a certain threshold. Faces were then generated from any edge by finding the shared neighbours for either of the two points forming that edge.
  3. Subdivide faces into 16 smaller triangles. This is achieved by splitting the side of each face into 4 segments, then drawing a triangular grid inbetween the marks. It was important to make sure each geometric point exists only once and that any two neighbouring tiles actually share two points. I was going through complicated solutions for this, but the hackey one I went with in the end was essentially – every time a subdivided triangle would use a point, see if one was already created at roughly the same coordinates. If so, use it, if not, create it and remember it for future reference. Once again, academically suboptimal, but the number of points was small enough that this made no actual difference.
  4. Project the points onto a sphere. An actual icosahedron would look very jagged and too low-rez even for me. So, making advantage of the fact that the center of the icosahedron was the origin, I simply took every point and normalised it. This resulted in points lying on the unit sphere. The faces were, of course, distorted in the process, but not too significantly.

And that was it, a sphere divided into 320 tiles. Until now, I was displaying it as individual points, so it was time to figure out how to display it. Before that, though, let me talk about rotation in 3D space.

Projection and quaternions

So I had a bunch of 3D points, with x, y, and z coordinates represented as floating-point numbers in the range $[-1, 1]$. Projecting 3D points onto a 2D screen is not difficult – the easiest way is to simply forget the z coordinate, and scale the remaining two to fit the screen neatly. There are many ways to improve this model, to take perspective distortion into account and make farther things smaller, for example. For a renderer that would only ever display this one sphere (where perspective distortion is not easy to see, anyway), this was entirely superfluous.

A much more important problem to solve was letting the user rotate the sphere however they wanted, mostly painlessly. If you have ever worked with animations in 3D, you might know about a problem called gimbal lock. Basically, if you represent your rotations as a sequence of rotating around the X axis, then around the Y axis, and finally around the Z axis, you will run into problems in certain orientations.

This would not work very well for my planet. A better way of representing arbitrary rotations in 3D is using quaternions, four-dimensional numbers. This might sound scary, but quaternions actually make many things much simpler than the conventional rotation matrix approach. Also, writing a fully encapsulated implementation can be done relatively easily as there are many code references available. Fully understanding the maths behind the code is a big bonus and it makes your development process less error-prone. Nonetheless, it is not necessary, especially in gamejam-like conditions. There is always time for study afterwards!

Rendering

Then it was time to finally draw all of my triangles to the canvas, preferably at 60 frames per second. This was somewhat daunting and I avoided it for a bit. I even had a "WebGL" as a potential task in my todo list, in case a pure canvas implementation would be too slow.

Luckily, the performance in Chrome was bearable in the end. (Then a one line bug fix made it smooth as butter, yay.) There is a simple way to render triangles on a 2D canvas rendering context, using beginPath(), lineTo(), endPath(), and so on. And there is the needlessly complicated way to render triangles, by drawing them as a series of 1 pixel tall rectangles. Of course, I chose the latter! While it is not a good idea in general to ignore the easy way, I had reasons.

My first version for the renderer consisted of going through the sides of all of the triangles using the Bresenham line algorithm, and setting the beginnings and ends of regions of colour in individual scanlines. Each scanline had a list of these regions, sorted according to the x coordinate. Then all of the scanlines would be, well, scanned in order and the regions would be drawn onto the screen.

This turned out to be too slow. Inserting regions into scanlines at the proper place was essentially an insertion sort, and it had to be done thousands of times per frame. Using a better insertion algorithm (binary search) was possible, along with further optimisations, but I had a bigger problem – the picture was glitchy. The problem was essentially that certain x coordinates would occur in the scanline regions more than once – triangles would overlap at certain places to ensure there were no holes in the planet. The best way to solve this would be to only draw the left "hull" of the triangle. That is, pixels which can be seen directly from the left of the triangle. I could not think of an efficient solution to this.

Then I tried another approach. I knew the planet would be mostly round. In other words, I would not have to worry too much about triangles overlapping, z-buffering, or anything this complicated. The entire reason I started with the scanline approach was to ensure none of these would be too difficult to solve. But, because solving them was quite unnecessary, it was perfectly okay to simply render the triangles scanline by scanline, one triangle at a time, without an intermediate buffer.

There was some random noise added to the height of each point of the planet, so there was, in fact, some triangle overlap happening. However, this generally happened close to the horizon, and did, in my opinion at least, produce a pleasant visual effect, especially with the colour palette I chose.

So, the final algorithm for drawing a triangle:

  1. Find the three edges of the triangle from its three points.
  2. Using the Bresenham line algorithm, find all the points of these edges.
  3. Iterate them in order of increasing y coordinate (top to bottom). For each y line, remember the minimum and the maximum values of x.
  4. Whenever we start a new line (the y coordinate changes), fill a coloured rectangle between the x minimum and the x maximum points.

Because the iterated points were produced by the Bresenham line algorithm, they would always have integer coordinates. Filling a rectangle given integer coordinates (and integer dimensions) is fast and efficient on a canvas. More importantly, it avoids the issue of blurry edges.

Shading

To make the planet look prettier, it needed some colour or shading. The shading could have been based on the angle with respect to a virtual light source somewhere in 3D space. At that point, however, I was still too concerned about the performance of my renderer, so I was not happy about calculating angles for each triangle at every frame. Instead, I used the area of the (projected) triangle. The more area a triangle covered, the lighter it was. Once again, I was happy with the visual effect, so I did not change this.

As with all of my games, however, I went with a limited palette. The planet itself had 8 colours to use. To make intermediate colours, I would mix them in various proportions on 4x4 patches, according to an ordered dithering matrix. I converted these patches into CanvasPatterns, and then was very pleasantly surprised with the fast performance of canvas filling rectangles using a pattern. I am sure there are many ways to leverage this performance, especially when mixing CanvasPattern with a SVGMatrix of some sort to translate, scale, and rotate patterns. Might have to return to this at some point.

Actual gameplay

At some point, I could delay it no further. I had a planet, but no game to play on it. It was time to decide on the actual rules of the game. I dedicated some time to writing up a reasonably interesting set of rules. The rules, along with the unit list, are available on GitHub. I was quite happy with them, but there were too many things that did not make it into the final game, simply because I ran out of time.

A huge part of the game should have been a karma system. The problem was essentially that there is a shared planet to which players can arrive at any point. Players who started playing sooner would have an obvious advantage – more land, resources, units, etc. The karma system was supposed to be a solution to this. Players would be rewarded for helping newcomers, for forming alliances, for sharing resources. They would be punished for seizing land, eliminating enemies, or destroying towers (which would be a structure built by one or multiple players together). "Evil" players would get instant rewards, in the form of resources for destroyed units, or the seized lands, etc. Long-term, however, they would have bad luck when it comes to gathering starlight, a resource randomly split across the planet every turn. "Good" players would then have good luck with starlight, but it would be at the cost of having to negotiate alliances, and playing a generally less aggressive game.

The turns should have been two (or five) minutes in length. That seems like a long time, but the point was that the game would be played in the background – players could join the game, close it, then come back to it again at some point.

Another important aspect of the original idea was that turns would be taken simultaneously. That is, any move a player planned for a turn would be evaluated, all at the same time. This would mean very specific rules for situations where two units are trying to move to the same spot, where multiple units attack one unit, which could be actually moving away, and so on and so forth. The game ended up resolving turns differently – iterate all attacks in a random order, then all movement in a random order, then builds, then captures. Nothing fancy, relatively fair, and simple. But not what it should have been!

The world was supposed to have multiple layers – the surface, and the underground. The surface would have starlight falling onto it, the underground would have mines. The two parts of the world would be connected via tunnels on certain spots of the map. Many other crazy ideas came to mind – the surface would be bombarded with meteorites (players crashing into the planet, aliens serving as generic NPC enemies). These would cause the surface to break, tile by tile. Over time, every couple of hours for example, the surface would be completely broken and would simply disintegrate and be replaced with the underground. A new underground would open up at that point.

Not making it

Obviously I dreamt big. Actually doing most of the above was obviously not going to happen. I was reasonably happy with my progress in the morning of the second day, even though I spent most of the first day just on the renderer. I decided to stay up overnight, with no sleep between the second and the third day. This was not a very wise decision. The night went okay, but the morning of the third day was not manageable at all, and I was making no progress. Eventually I took a ten minute nap. I still felt quite groggy afterwards, but the need to sleep was not as bad. Nonetheless, the third day was slow and not very productive. It got to me a couple of hours before the deadline, when I felt like throwing in the towel. My friend did motivate me to at least make the release. So, I cut off everything else, made sure the multiplayer server worked at least a little bit, and released.

Unfortunately, I could not find the time to put in the music for the game. My friend, who also did the sound effects, lost a lot of sleep and study time just before important exams making the music. Hopefully we will get to put that music to good use, either in a Planet of Babel-like game, or in an entirely different project. Part of the reason I could not make it happen just before the deadline was that it was in the form of various loops which could be mixed and matched together, according to the player's non-existent karma. This was upon my request, but it meant the loops would have to be looped seamlessly, which is not super easy to accomplish reliably with JavaScript. So, no music …

Conclusion

Even though it was a bumpy ride, and I was very happy when the jam was over (so I could finally sleep), it was not all that bad. I am happy to have learned some new things along the way, although I expect my ratings will be quite low this time around, certainly not as high as one rooms. The game is somewhat fun to play with friends when you are all connected at the same time and skyping or talking, but as it is, the server is generally deserted, and it will probably be that way for most of the judging period. I could twist the rules and modify the server, to make the ticks longer, to spawn bots, etc., but I feel this would be cheating. The server is not technically part of the game client, but it is still a component of the game, so I will keep it running in its current buggy form, for the duration of judging. More importantly, I have exams coming up in two days as well, so I should probably focus on that. I hope you found some entertainment in this blog post!

Bonus: Food log