Friday, April 20, 2012

Maps and Boardgames (Part 3 - Client Side drawing + Optimizing)

In my previous post I've shown how one may interact with an hexagon layer on top of a Leaflet map.  The particular thing in that example is that it used hexagons embedded in the server-side tile images (created using TileMill). This has some pros and cons:

- great performance
- works on most browsers (even pre-HTML5)
- less "visual noise", as the map is rendered at the same time as the hexagons (heck, they're in the same image tiles)

- by itself it's difficult to have client-side behavior. It's possible using something like the UTFGrid technology, but that brings some additional complexity to the table and some limitations (I've used this approach in my previous post).
- the hexagons are static. So, if for example, we want to generate the hexagons with a different size or color or change them dynamically we're kind of screwed.

In this post I'm going to try a different approach, and return to the HTML5 Canvas implementation that I've started in the first post of this series.

I'll start by creating a sort-of similar example to the one in my previous post:
  • As I've said in my previous post, I've generated a set of tiles with and without the hexagons. The one without was already anticipating this post (+1 for thinking ahead for once).
  • Create a matrix of hexagons in Javascript (just the coordinates without drawing)
  • Paint the hexagons using Leaflet's Canvas Layer and HTML5.
This is the end result. Check the demo here.

It works nicely, and I've tweaked the Canvas code so that the hexagons provide the same cosmetic feeling as before, including the white border, the transparency, etc.

Now to add some basic interaction to it. Let's detect the hexagon that is clicked and change its color. The interesting thing here is the click-detection, because we've got to handle the click event on the map and translate it to a specific hexagon by doing some math.

Result below. Demo here.

Now, the problem with the "Canvas Layer" approach is that it doesn't feel as "snappy" as the one with the server-side tiles. It generates the hexagons fast enough, but has a very small delay that is bothering me.

I'm going to try and isolate this issue on a basic prototype. I've created a very simple page which outputs the following image using Html5 Canvas. You can try a working example here.

100+ milliseconds to draw all these hexagons is not that bad, but it's not negligible by the user. Knowing that we want to pan and zoom the hexagons I would like something below 40-50 ms for each tile.

So, I thought a little bit on the subject and had an epiphany while showering (true story) :P

The hexagons create repeatable patterns. One of the patterns is:


The yellow rectangle contains a pattern that is repeated on the red rectangles. It repeats the hexagons seamlessly.

So, if we can recreate that pattern, we can use the Canvas pattern feature and paint the full canvas with it. The procedure will thus be:
  • Create a very small canvas with the pattern
  • Create a very small pattern from the previous canvas
  • Use the pattern to paint the large canvas   
I've created a new page following these steps that should display the same output as before, but faster. Check it here.

As you can see the displayed image is exactly like the previous one. The main difference: 3 ms vs 111 ms !!! (obviously may vary per computer/browser). IMHO that was blazing fast to render, and I'm including the time it takes to create the pattern.

Applying this technique to a map is not straightforward though, and for now I don't think the gain is enough to justify implementing it (if time permits I'll do it eventually).
Much more could be said about Maps and Boardgames, but I've got some other stuff in my "stack" that I would like to talk about, so I'll wrap up this topic with this post.

Update 16/11/2012

Well, I've received a comment with a better implementation for my first drawing approach. The change seems minor but was enough to drop the time from about 100ms to less than 10ms. You can check the updated example here. Thanks sado


  1. Cool posts, thanks for the examples. The real reason your example 1 takes soo long is because you're drawing too many hexes! (Though on Chrome and a nice computer it only takes me ~50ms)

    When I replace the drawHexagonGrid function like so,
    function drawHexagonGrid(context) {

    var date1 = new Date().getTime();

    var rows = 100;
    var columns = 100;

    var topLeftHex = hex.getReferencePoint(0 - xOffset,0 - yOffset);
    var bottomLeftHex = hex.getReferencePoint(0 - xOffset,600 - yOffset);
    var topRightHex = hex.getReferencePoint(800 - xOffset,0 - yOffset);
    for (var i = 0; i < columns; i++) {
    for (var j = Math.round(0 - (i / 2)); j < Math.round(rows - (i / 2)); j++) {
    drawHex(context, {u:i, v:j});

    var offset = 0;
    for (var i = topLeftHex.u - 1; i <= topRightHex.u + 1; i++) {
    for (var j = topLeftHex.v - 1 - Math.round(offset); j < bottomLeftHex.v + 1 - Math.round(offset); j++) {
    drawHex(context, {u:i, v:j});
    offset = offset + 0.5;

    var date2 = new Date().getTime();

    document.getElementById("result").innerHTML = "Draw Time: " + (date2 - date1) + " ms";

    It only takes in the single digits, I've re-enabled the drag code you had and it works fine.

    1. Ouch, you're right. Thanks a lot, I'm going to update my post ;)

  2. I noticed a small flaw in one of your demos:

    If you click near the right or left most point of a hexagon it does not accurately detect which hexagon you clicked on. Instead it highlights one up or down to the left or the right.