In the latest beta update r149 of Construct 2 we've shipped a new official Tilemap plugin, with tilemap editor features and the ability to import TMX tilemaps from Tiled. A few people have already wondered on the forums about some of the details about how it works, so here's an overview of some of the more interesting bits. It also turns out to be quite a good example of the kind of engineering rationale and tradeoffs we make while working on Construct 2 features.
TMX import
When importing from Tiled, Construct 2 currently only supports a subset of its features. What it does support are:
- Orthogonal (square) maps
- Source image with optional margin, spacing and a single transparent color
- Multiple layers of tiles (note a single Tilemap object represents a single layer of tiles, so when importing you're asked which layer to import)
- TMX files using XML, CSV, base64, or zlib-compressed base64 data
However it doesn't support several other features:
- Multiple tileset images (only first is used)
- TMX files using gzip compression (use zlib instead, or none)
- Tile flipping/rotating
- Tiled's non-tile features like shapes, polygons and properties
We will be improving our tilemap support over time, so let us know if any of these missing features are important to you. However hopefully this basic support makes it easy to design levels in Tiled and get them in to Construct 2.
Run-length encoding
While Tiled supports a number of different formats, Construct 2 only uses one internally: CSV (comma-separated values). When running your game, the tile numbers making up the tilemap are joined in a big comma-separated list which looks something like this:
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 23, 24, 24, 24, 24, 24, 24, 24, 24, 25, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0...
Even a moderately sized tilemap can have thousands of tiles, and you can imagine this string getting very long. Then you might have lots of levels, and before you know it the engine is dealing with hundreds of kilobytes of data in this format. As you can see, there's also a lot of repetition - tilemaps very frequently have the same tiles across a small area.
This goes in to the c2runtime.js file. Most servers compress text files for transmission, and that would reduce the impact of these long strings of numbers on the download size (especially since repetitive data compresses well). However large javascript files can take a while to parse on startup, or use up lots of memory, which can be especially problematic on mobile. So it would be wise to try and keep this as efficient as possible.
A really simple compression solution is run-length encoding. Construct 2 uses a sort of 'run-length encoded comma separated values' scheme to store the tilemap data at runtime. We could have used zlib compression, but this would involve some complexity and dependency on a new Javascript library in the runtime - and besides, as mentioned servers probably already compress it like that for transmission. So this scheme serves to be firstly as simple as possible, and secondly to eliminate some of the redundancy. (In many years of writing software, time and time again I've learned how important it is for things to be simple. Simple is usually best!)
Run-length encoding means instead of saying "zero, then a zero, then a zero, then a zero..." you say "ten zeros, then a 23, then eight 24's...". In our format, this looks like "a x b", where 'a' is how many times to repeat 'b'. In other words, "10x0, 23, 8x24...".
Note the 23 stands by itself. If there is one number by itself, pre-prending it with a "1x" actually just increases the size. So in between commas, if there is an "x" it involves repetition, otherwise it's just a number by itself.
So now the previous example in full using this scheme looks like this:
10x0, 23, 8x24, 25, 11x0...
It already looks a lot smaller! In practice there are no spaces (to save those bytes as well). In a simple practical test a small level taking about 5kb as plain CSV was reduced to just 944 bytes in this scheme. That kind of ratio of saving should extend to much larger games as well, significantly reducing the script size to improve startup and memory use.
Rendering
Here's an example of a little tilemap you might have in a game:
This particular tilemap has a faint grid drawn in to it so you can see the size of each tile. When the engine has to render this tilemap, each individual tile in the tilemap must be drawn to the screen. Suppose we did this naively: for each tile, we make a separate call to draw the tile. Let's highlight in red each rectangle that is being drawn if we do this.
In this case, 120 draw calls are made. This requires the CPU to make 120 separate "go and draw this" requests. In extreme cases this will show up as a high percentage in the "draw calls" section of Construct 2's profiler. However we have the ability to render areas of repeated images in one go. We already recommend using Tiled Background where possible for this same reason: despite the fact the Tiled Background object repeats its image, it can be drawn with a single draw call, which is far more efficient than using a grid of sprites. Obviously if possible we want to make a single draw call to draw repeated areas in the tilemap as well, rather than repeatedly doing a tiny bit of work over and over again.
Therefore to optimise this, the Tilemap plugin searches the tilemap for areas of repeated tiles. It identifies the largest rectangles it can where the same tile is repeated, and remembers these. When it comes to be drawn, it draws the whole rectangles at a time rather than going tile-by-tile. We can see how this works by outlining each identified repeating rectangle in red:
Previously this tilemap took 120 draw calls; now it takes just 22. It's like using tiled backgrounds wherever possible across your level design, but done automatically for you in the most efficient way possible. Again, this type of optimisation is important to help squeeze out the most performance on mobile devices, especially when canvas2d rendering is used where each draw call is a lot more expensive than with WebGL.
It is possible to use shaders to render tilemaps even more efficiently in WebGL mode. However, again the simplicity tradeoff kicks in. A benefit of this method is it can be applied equally to the canvas2d and WebGL renderers. On top of that we've already done lots of optimisation work in our WebGL renderer, and our performance benchmarks show individual draw calls in WebGL mode are incredibly fast. Modern phones can get thousands of sprites on-screen without dropping below 30 FPS - and 22 draw calls of a budget of thousands should not be a big impact. As with run-length encoding, we've eliminated most of the inefficiency with a simple scheme, and further work would get increasingly complicated and take longer to develop, all while providing diminishing returns. So we'll keep it simple! Performance should still be good like this, and I'm happy we've gone far enough.
Collision testing
For testing collisions against tilemaps, we apply a similar optimisation as with rendering. Construct 2 tilemaps count any tile as colliding - only empty spaces without a tile don't register a collision. You can design levels where just a few tiles collide by stacking multiple Tilemap objects on layers, and only checking for collisions with a tilemap on a particular layer. To demonstrate collision testing, let's change the point of view and pretend we're making a platformer:
Applying the rendering optimisation, we end up with 24 rectangles to draw:
However when testing for a collision, this is still 24 rectangles to test. If you look at it on a larger scale, there are just four rectangular areas that register collisions there. Certain games like platformers make a lot of collision tests, and in some cases several tests per tick, so it's important to make this as fast as possible.
To optimise this we basically run the same optimisation as for rendering, but ignoring the types of tile. In other words, we just find the largest rectangle areas of tiles. Empty spaces stay empty spaces. Then when testing collisions we simply check against the collision rectangles that were found. Highlighting the collision rectangles for this example, we can clearly see it's identified just four rectangles:
This is actually more efficient than testing for collisions with the optimal arrangement of tiled backgrounds. It's more like using invisible tiled backgrounds over areas of your level to check collisions with (which is still a useful technique despite this) - but as with rendering, done automatically in the optimal manner.
The details of the collision testing are likely to change in future. We intend to stop Construct 2 brute-forcing collisions and implement a quadtree or at least a simple "collision buckets" system in future. Also we're aware of the fact not every tile should collide across the whole tile. We may add some kind of support for collision shapes for tiles in future, or at least something which does the same job. However that would stop making this optimisation quite so effective since it can't just go ahead and cover a custom shape with a larger rectangle. In the mean time, hopefully for some games this is already fast enough and good enough, especially with the optimisation.
Conclusion
Hopefully this gives you some kind of insight to the engineering process involved when adding new Construct 2 features. There's a few tradeoffs made, and efficiency especially with regards to mobile is one of the main concerns. In the case of the Tilemap plugin, it should be very efficient with both rendering and collision testing - and it is doing the optimisation automatically behind-the-scenes, so you don't have to worry about it. Just design your levels as beautifully as you can, and it will figure out the best way to render and collision test it!