Last week, you may have noticed that we released a facelift for our interactive maps. Our Deal Score markers have finally been brought up to 2014 design standards to match the Omnibox. However, what may not be as apparent is that our maps are now between 10 and 100 times faster, depending on the device.
Background
This blog post from March gives a good overview of how our maps used to work. Our maps consisted of three different layers: an image tile layer, an SVG layer, and a Leaflet marker layer.
This is how our map used to look. The actual stadium is an image tile, the blue section outline is an SVG layer, and the green dot is a Leaflet marker, an HTML element containing an image. There are a couple drawbacks to this approach…
Performance
While Leaflet markers work well for maps with a small number of markers, we were pushing the limits how many markers could be drawn on the map. At a row-level zoom, we can have thousands of markers on the screen at a given time. Since each marker is an individual DOM element, the browser must move around thousands of DOM elements at the same time when panning and zooming. This meant slow performance on even the fastest of computers and even worse performance on mobile.
Code Complexity
With the addition of section and row shape interactions, our code became incredibly complex. We were listening to mouse events coming from the tile layer, the SVG layer, and the marker layer. This resulted in a mess of code trying to handle every corner case, e.g. we receive a mouseout event from a marker and a mouseover event from the SVG layer.
Marker Clustering
A common way to handle large numbers of markers is to use clustering, such as the Leaflet markercluster plugin.
This is an effective way to reduce the number of DOM elements on screen. Unfortunately, clustering like this does not work for our use case. In our maps, the markers need to be specific to either a row or a section. Marker clusters, which are based only on marker positions, could result in some unintuitive ticket groupings, e.g. a VIP box and the front row of an upper level section. Therefore, we needed to come up with a solution that would maintain the section and row level detail views, while achieving the same performance as marker clusters.
HTML5 Canvas
A few months ago, we made the decision to drop support of Internet Explorer 8. In addition to making every engineer here very happy, this also opened up the possibility of using canvas for our map markers, something we have been looking forward to for a long time.
The HTML5 canvas element is basically a low-level drawing region. It supports basic drawing operations, but does not have the concept of a scene graph or event handling for anything drawn to it. Most importantly for us, modern browsers are incredibly fast at drawing to canvas elements, often using hardware acceleration.
Canvas Tiles
Our plan was to move from using SVG section outlines and Leaflet markers to using tiled canvas elements. This means that instead of forcing the browser to move thousands of DOM elements when panning and zooming the map, we can draw the markers to the canvas tiles once per zoom level and move the canvas tiles themselves around. Browsers are much better at moving 16 elements around on the screen than 2,000.
Here is what the canvas tiles look like (with debugging on) at our lowest zoom level:
And at our highest zoom level:
This is by no means a new idea. Leaflet itself supports basic canvas tiling and some cool things have been done with it. However, using canvas tiles for our purposes presents some very interesting challenges.
Hit Testing
By consolidating the SVG and marker layers into a single canvas tile layer, we were able to greatly consolidate our mouse interaction code. The bounding boxes of the section and row shapes as well as the markers were put into our favorite spatial data structure, the R-Tree, for fast lookup. As markers sometimes extend past the edge of the shape they are in, we first check for marker intersect and then fall back to shape intersect.
Drawing
In order to maintain a high frame rate, we need to make the drawing step as fast as possible. Every time Leaflet requests a tile to be drawn, we calculate the bounding box it covers on the map. Then, we look up what markers fall within that bounding box plus a small buffer, to avoid markers right next to the edge of a tile being clipped. We then iterate through the markers and draw them to the tile. We perform a similar process for drawing hovered and selected shape outlines.
Tile Redrawing
There are a couple of events that cause tiles to need to be drawn or redrawn. On zoom, a new set of canvas tiles are requested and drawn at the correct scale. When a shape is hovered or selected, we also must redraw the tile or tiles that contain it. In order to minimize the number of tiles redrawn, we keep track of a redraw bounding box. Between each redraw, we update the redraw bounding box to contain the shapes that need to be drawn or cleared. Then, when the redraw function gets called, we draw only the tiles that contain the redraw bounding box. Now, we could clear and redraw only parts of each tile, but it turned out we got the performance we were looking for without introducing the extra code complexity of sub-tile redrawing.
Here you can see how the canvas tiles are redrawn. Each redraw colors the updated tiles the same color.
And on mobile.
Buffered Marker Drawing
All was going great until we decided the markers needed a slight drop shadow to help visually separate them from the underlying map. Drawing drop shadows in canvas is notoriously slow. However, drawing images or other canvas elements to a canvas element is quite fast. Therefore, while we are waiting for our tickets to load, we create small canvas elements for every marker color (and at two different sizes, since we enlarge the marker on hover). Then, when we need to draw the markers in the canvas tiles, we can pull from these buffered marker canvases. This way, we only incur the cost of shadow blur once and use the comparatively fast drawImage when performance counts.
Results
Flexibility
As the markers are now procedurally drawn, we can now change their styling whenever we want to. Even the legend is a canvas element that correctly spaces the markers if we change their sizes.
Code Complexity
By switching to canvas markers we were able to greatly reduce the complexity of our event handling code. Probably the best thing to ever see in a GitHub pull request, an overall code decrease.
Performance
The Chrome timeline pretty much sums up the staggering performance increase.
Old map.
New map.
As you can see, the main performance gain comes from greatly reducing the browser rendering time (purple). Across all devices, the maps now stay comfortably over 60fps, inertial panning works smoothly, and our mobile site is considerably more usable.
If this type of stuff gets you excited, we are always looking for engineers. Come join us!