JS13kGames 2015: GeoQuiz

August-September 2015


>>> PLAY THE GAME HERE <<<

Play enhanced version on Github
source code
Reddit discussion

13kb seems small, but actually it's huge... even for a full-featured HTML5 game.
(Last year, despite my efforts, I didn't manage to use more than 9kb).
But rules are rules, and this year again, we have a month to fill a 13kb zip with a high-quality game for... js13kgames.com !

To avoid being annoyed by such a high limit, I decided to make something big, something so big that people will ask themselves how it can fit in just 13kb.
Something big enough that I would also wonder how I will pack it in 13kb... and develop my own tools to achieve that goal.
Then yes, JS13kGames would be a great code-golfing and compression challenge!

Games contain code and data. 13kb of golfed code is very hard to write, so I decided to make a game that uses a lot of data.
Hey... how about putting the whole world in my game?
There was this Flash game that I liked a lot at university: Traveller's IQ challenge.
Its goal was to find famous places (cities, capitols, monuments...) on a World map.
I chose to make a game like that, but with my own style.


A few days before the compo...

The final game doesn't contain any code or data produced before the beginning of the compo. During this couple of days, I just began to develop my design tools and produced dummy data that would be replaced afterwards.

As I was waiting for the compo to start, I started experimenting with different techniques to draw and store efficiently all the countries, capitols and famous places of the world. I chose a good-looking, yet outdated World map (I did not want a Mercator projection - It's too stretched and unrealistic around the poles) and hacked a little tool that would let me draw the outline of each country with my mouse, on a canvas. The logic was a bit similar to what I did for Flappy Dragon during JS1k 2014, but with less precision, because this time, I had to draw more than 197 countries. After many experiments, I chose the following way: I placed the model of my map on a 1024 by 512px canvas. Then, for each country and for each point I clicked, the tool would gather two mouse coordinates on the map (X and Y), and append the value of X/4 and Y/2, converted in Unicode, to a string representing the given country. X/4 and Y/2 turned out to be bounded between 0 and 253, so I could use two chars to represent each point, and the character 255 ("ÿ") as a separator for the countries (like Canada) consisting of multiple islands or territories. The capitol's coordinates are appended at the end. With this technique, I could fill a JSON file that looked like this: 

{
    ...
    'Brazil,Brasilia': '?É?½5¢0¦/™8‡;AŠB‘NšJ»D¿BÎÿD²',
    'Bulgaria,Sofia': '{?€AD|Eÿ|B',

    'Canada,Ottawa': '8"9<\nFOB\nBGA!<(...);A9D3:7?=;A9;.D+7ÿ%)\r11ÿ+\n/4/\rÿ5:4ÿ8<9\r5ÿ3=',
    //   ⬆                      ⬆                           ⬆      ⬆        ⬆           ⬆⬆
    // Country, capitol    Sequence of X/Y coordinates      Islands separators    Capitol coordinates

    'Chile,Santiago': '7ë4È6¹2±4Ý7ï=õ;ï7ëÿ4Ì',
    'China,Beijing': '©7¢I¨W°^·\\ºj¾gÂkÈdÉXÄHËBË8Ã2ÄB¼MÿÁmÃlÂpÁoÿÂI',
    ...
}

You can try the editor here. (use left click to place a point, right click to start a new island and spacebar to start a new country. The coordinates are appended to the text under the map)

Then, I tried to draw the map from that JSON, and it wasn't as easy and straightforward as I imagined... here are a few screenshots of my first tests:


fig. 1: Unicode madness, most countries leak everywhere and half of Russia somehow gets drawn over south America.


fig. 2: Debugging, displaying small dots for the capitols, redrawing countries that had corrupted data...


fig. 3: More debugging... and realizing that many territories like Greenland and Western Sahara are not countries... Damn, Earth! :)

These tests confirmed that this project was possible. Indeed, the names, shapes and capitols of all the countries on Earth can fit in just 6.2kb in JSON. Now I'm sure there is plenty of room left for a more detailed map, plus the game's code, the music and even more data!

But I didn't stop there. I used the unused char U+254 ("þ") as a separator, and made a big string with all my JSON's data... 

Algeria,AlgiersþtfpRqLiOjVc]noÿmNþArgentina,Buenos Airesþ6¸?Ã>Ï@Ö<Ù;ï7ë4Èÿ<ñ=õ@õÿ>Ðþ ...

Then I made a tool that converts this string in a binary file. After gzipping, I saw my data fell from 6.2kb to 5.6kb! 600 bytes saved, that's a great news! If you're wondering why this conversion is so efficient, it's for two main reasons. First, the JSON contained some escape sequences ("\\" instead of "\", "\r" and "\n" instead of line breaks, \' instead of quotes) that became a single byte in binary (the escape was no longer necessary). But most of the savings come from the "code point-to-binary" conversion for all the characters between U+80 and U+FF (these characters take 2 bytes each in UTF-8, as opposed to just 1 byte if we store their code points in binary). You can find more info about how many bytes are used for each character in each charset on this page.

Here's a golfed encoder that does this conversion in about 230b: 

// Unicode to binary encoder
// Input (m) can contain chars between U+0 and U+255
// Output (download) is a binary file
m=m.replace(/\\\\/g,"\\").replace(/\\r/g,"\r").replace(/\\n/g,"\n").replace(/\\'/g,"'");y=[];for(i in m)y.push(m.charCodeAt(i));location="data:application/octet-stream;base64,"+btoa(String.fromCharCode.apply(!1,new Uint8Array(y)))

Of course, at some point, this binary data needs to be read and converted back as a long Unicode string. I made a little JS program that does it in about 160bytes. It's totally worth the overhead, considered the hundreds of bytes that can be saved through binary. 

// Binary to Unicode decoder
// After execution, h contains the decoded string.
with(new XMLHttpRequest)open("GET","data.bin"),responseType='arraybuffer',send(),onload=function(){h="";for(i in u=new Uint8Array(response))h+=String.fromCharCode(u[i])}

Golf tip: instead of data.bin, you can name your binary file "0" (or any number), without extension. It will reduce the name used in open() but also make the quotes unnecessary: 

with(new XMLHttpRequest)open("GET",0), ...



Compo: Day 1

When the compo started, my map editor was functional, and I could start developing my game for real. But before that, I wanted to experiment another thing: to represent the Earth on a 3D-looking sphere instead of always a flat map.

I didn't want to use (or make) a 3D engine just for that. I was looking for a very lightweight solution to give the illusion of a real sphere using a few tricks of trigonometry-fu, like Aemkei did for his 1kb world. I'm not an expert but, by chance, my friend Subzey helped me write these simple equations that turn instantly some map coordinates into a projected globe's coordinates: 

// map_x and map_y placed in the interval [-1:1]
globe_x = Math.sin(map_x * Math.PI) * Math.cos(map_y * Math.PI / 2);
globe_y = Math.sin(map_y * Math.PI/2);

For more info, tke a look at this demo by Subzey.

Here's what I saw when I tried to adapt this technique to my map.

After debugging, here's a demo using my world map (animated)

After long hours fighting with Canada and Russia (because they are too large to behave correctly where the "-1" and the "1" are connected), I managed to hide the back side of the globe and thus, make it much more realistic.

Here's a demo with only the front face of the globe (animated)

Great! Everything works. All that's left to do now is to develop the game in a few kilobytes, use another couple of kb for music, and all the rest of my zip will be used to store as many data as possible.

The first thing I developed in the game was a "Home screen" (featuring the rotating 3D globe in more realistic colors, plus slightly blinking stars scrolling in the background), and a presentation screen for each "level" of the game.






Compo: Day 2

I improved the graphics with better colors and gradients.




I also began to implement a basic interactivity: showing the name of a target and a 10-second timer, clicking on the map, telling if the target has been clicked, and restarting with the next puzzle.


To find if a country is clicked, I use the canvas function "ctx.isPointInPath(mouseX, mouseY)" just after drawing the country in yellow. It's very handy! But when we click outside of the country, I have to loop on all the points of the country, compute which one is the closest (computing distances using Pythagore), and use it for the green flag and the red line.




Days 3 & 4

During this weekend, I started refactoring some code and compressed my data a little bit more (about 200b) by removing some separator bytes in my binary file. (But *spoiler alert* there will be a big data overhaul in a few days, so I'll talk more about it later!).

I also worked on the gameplay and added an distance counter that tells you an idea of how far you are from a target. This number will be used to compute the player's score.


Of course, Pythagore isn't a great solution to compute distances on a sphere projected on a map, it works well enough for a mini-game.

I also worked on the gameplay of the level 2 (finding capitols):



... and worked on the scoring system (your "error gauge" decreases after every mistake and if it reaches 0, the game is over).

Also, with a little help from my friends and my Twitter friends, I produced an important chunk of data: the names and positions of 100 famous places on Earth, separated in 3 categories (easy, medium, hard). The data looks like this in JSON, and of course, it will be part of the final binary file: 

{
  "Christ the Redeemer": "Hº",
  "The Great Chinese Wall": "ÁI",
  "The Great Sphinx": "ƒZ",
  "The Eiffel Tower", "m9"
  ...
}


Days 5-11

I knew I had too much free space, so I spent the spare time I had this week adding the U.S.A. states and capitols to my database. Same format as the World's cities and capitols, but I directly drew the "final map", i.e. with all the little details I could draw. This brought my total data counter to 7.9kb zipped.

I also decided to reorganize and optimize my data once again, to make it as small and compressible as possible:

  • First, I separated the text (the places' names) and the binary data. Having all my names stored in the JS code and all the coordinates stored in a binary file will reduce the effort to retrieve the data I need from the binary file, and will help the compression too (because "just text" or "just random bytes" compresses better than if all is mixed up).
  • I also changed the order of the data to put all the places first, then all the capitols, then all the US capitols, then all the countries, then all the US states. The advantage of this is that I don't need any separators in the first three datasets. I just have to store all the places/capitols/US capitols coordinates sequencially and I'll just read them two by two when I'll try to retrieve the data.
  • Finally, I gathered all my names in a big JS tring, but without any separators: to distinguish them, I'll just use the uppercase letters at the beginning of each name. So the names now look like this: 
    Cape canaveralChrist the redeemerThe great chinese wallThe great sphinxThe eiffel towerTower of pisaMount everestSagrada familiaBig benThe statue of libertyForbidden cityThe pyramids of gizaThe palace of versailles...

    After zipping, I discovered that this overhaul made me lose (I mean, earn) 800 bytes of data, so that's a great news!


    Days 12 - 18

    I spent that week rewriting the game to adapt it to the new data format, and revamped all the code to make it more logic and easy to maintain.


    Days 19 - 25

    I spent that week fixing the gameplay of the 13 levels of the game. and tweeted about it


    Days 26 - 32: Last week

    I spent that last week redrawing the final world map in high quality, debugging all the little artifacts that were remaining, and added some last minute features to respect the theme "Reversed" and make the game a little more interesting: the maps get reversed every five puzzles, and the fronteers disappear during the last 5 puzzles of each level. I also inserted some little last-minute hacks to make the game better and better-looking without spending a lot of time on it. One weird hack I discovered and used, was about the data shuffling. I initially did that on page load and remarked that the puzzles order were often very similar, as if there was no real randomness in the shuffle function. I assumed that Math.random() was influenced by the JS execution time, so I delayed all the data shuffling from the page load to the moment where the player clicks on "START". The puzzles looked much more random after that.

    On friday, I asked my colleagues to test my game, and the result was very good. They loved it, and they played it very well!


    Oh, and... how about the size? Well, it was surprisingly small: 10.9kb. And it still lacked sound or music, because I have absolutely no talent for that. I launched a desperate cry for help on Twitter and a great guy (Anders Kaare) answered my prayers and agreed to compose a musical theme for GeoQuiz in less than 24h. He did such a great job, he also included a reversed variation for the puzzles where the map is reversed, plus a "blacker" variation for the puzzles where the map is black, and without fronteers. Kudos to him!

    I released the final build a few hours before the end of the compo. My final zip weighs 11.9kb... Once again, I failed at filling the whole 13kb allowed by the contest, but I'm happy with the result, even if I could have made it even better with more time... and if these damn Unicode flags were already useable in browsers!


    One week after

    I received a lot of great feedbacks for my game, and it also appeared on some video tests. Some people asked for a little enhancement to make it a better learning tool: in the "capitols" puzzles, they asked me to display the name of the country in which the capitol is located. So I added this feature on the Github version of my game.




    Conclusion

    See you next year, js13kgames! And thanks for existing! It was fun to code for you!

    PS: I invite you to take a look at the entry Mug-Gniwech, it was made by one of my colleagues whom I'm introducing to the fine art of JS code-golfing, and I contributed a little to his game during the brainstorming phase, the graphics creation, and the code's organization. :)

    Cheers,
    @MaximeEuziere