We helped build this cool WebGL LEGO®/Google Maps thing, so I thought I’d talk for a bit about it.
Build with Chrome is basically a Google Chrome and WebGL tech demo. The basic premise is to let users build whatever LEGO structures they want in a full 3D environment, using a baseplate that occupies a Google Maps tile. If you haven’t tried playing with it yet, go do so right now; at least for me, it turns out that playing with LEGO bricks is just as fun now as when I was 10 years old.
We got involved in the project as a subcontractor to North Kingdom. We’ve done some pretty cool stuff with them in the past; check out our cases.
Early prototype of the builder mode
We were responsible for the backend system, implementing North Kingdom’s front end designs, and hooking up various components to each other, while North Kingdom and freelancer Mikael Emtinger handled design work and WebGL programming (mostly done via GLOW.js).
Since one of the requirements was to use Google Maps tiles as baseplates, one of the first problems we had to solve was how to LEGO-ify a Google Maps image. In an early stage of the project, the plan was to LEGO-ify the entire map, and much time was spent discussing and testing how to make a LEGO-ified map look good and load quickly enough to make the experience decent for the user. The plan was eventually mostly scrapped, and it was decided to only make the 3D exploration mode (which you get if you zoom in far enough) LEGO-ified. We ended up with a very simple implementation that scales down each 256×256 pixel Google Maps tile to 32×32 (using nearest-neighbor sampling) and then reduces the color depth to a fixed 13-color palette. Fortunately for us, you can use the Python Imaging Library (PIL) on App Engine now, so this was pretty painless to do.
We also tossed around the idea of using topographical height data from the Google Maps API’s in order to make the baseplates “hilly”, but that plan was also scrapped; mostly for timing reasons, but also because the height data wasn’t really in a high enough resolution to make it interesting.
Builder mode as it looks today
The next problem was to find a decent way to automatically give users free plots to build on in some semi-predictable manner. Sounds easy enough, but it gets more complicated when you have many users who want to build in the same area. Checking if a plot is free or not in a race-condition-safe manner is a somewhat expensive operation (requiring a database read), so you can’t do too many checks in a single request, or the user experience will be terrible. After some experimentation and poking around we found an old simple trick that suited us: each baseplate (map tile) is assigned an integer X/Y coordinate pair (counted from the northwestern corner of the map). The coordinate pair is bitwise interleaved to form a single number (called a Morton code), which is stored in memcache (with database backup), so it’s easy to increment or decrement atomically, forming a Z-order curve. Using a single number as a coordinate made it much easier and faster to look for free plots while keeping the assignment transaction safe.
We have also learned more about Google Maps (and more importantly what you cannot do with Google Maps) than we ever wanted to know. Among other things, it turns out that Google Maps ground overlays are really interesting creatures when they get so big that the curvature of the earth starts to matter; most of us have worked as web developers for our entire careers, which meant our math knowledge was severely rusty and not really up to the task of projecting flat images from onto the surface of an ellipsoid or deprojecting spheroid surface segments to flat images. We ended up scrapping that code path for other reasons, though.
• Number of different coordinate systems used internally: 5 (latitude/longitude in WGS84 datum, Google Maps tile coordinates, Google Maps tile coordinates with the Y axis inverted, Morton code coordinates, “Spherical Mercator” metric coordinates (EPSG:3857)) • JS to Python code lines ratio: ~4.8:1 (~16550 lines of JS, 3400 lines of Python; both excluding third-party libraries other than GLOW) • Number of real LEGO kits built during the development process: 4 (including the Death Star, see photo below) • Number of dragons in the codebase: 3
Google’s official post about the project:
Research for the project (or just an excuse to build cool LEGO stuff)