Can’t believe it’s been already a full year! My last post was about JS13K, and a year later, the story repeats itself; not only I participated again this year, but I built a shmup game… again!

While I was quite proud of what I created last year, there were quite many things that I couldn’t include; 13Kb is a very small size, but even more important than that, I couldn’t invest as much time and energy as I would have liked to. During the judging phase of the competition, I was really impressed with many of the entries. At the same time, it dawned on me that real life doesn’t give me the necessary bandwidth to build something similar. So, instead of trying to build everything in a month, I decided to build an “engine”, and then use the competition time to work on the actual game.

Phase 1: Improving the original entry

After the competition was over, I started reworking the 2020 entry, improving every aspect; sound effects, pixel perfect collision detection, gamepad and keyboard support… of Webpack… at the same time, I kept the game mechanics and ship generation almost untouched (with the exception of the new collision system). The end result already felt a lot more polished, but don’t take my word for it; play the original and compare it to the updated oned. Not only that, but it ended up being noticeably smaller, almost 2Kb under the 13Kb limit.

Phase 2: Incompatible changes

After that I went back to the procedural ship generator library I created. The biggest problem updating it is that any ordering change on the pseudo-random number generator causes completely new ships being created, so it was time to work on “version 2”. This included changes like an updated PRNG library, and a number of optimizations that weren’t backwards compatible.

Now that the game was better and smaller, it was time to think about adding new things on top, and I started with the new HUD/menu system. In the original version, everything was painted on a HTML5 Canvas object, but that doesn’t upscale well in larger screens, so after some experimentation I went with a hybrid Canvas/HTML approach. The game now has two layers: a Canvas object, and a HTML panel on top, which use exactly the same scaling factor, but now the text will look perfect even at very high resolutions.

The great thing about working outside of the competition’s time frame is that I could spend as much time as necessary polishing the small details, like choosing the font, playing with different styles (I settled for a skewed, condensed look using CSS transformations), and building a user interface that could be used with a mouse, keyboard and even gamepad.

Phase 3: The actual jam

For the actual game content, I waited until the theme was revealed, as I really wanted to integrate it properly… and it happened to be “Space”! I was secretly hoping to make some sort of weird “fusion” with whatever was announced, but at the same time, being able to keep the space elements of the game gave me more time to focus on the rest.

At this point, most of the “engine” work was done, so I could fully concentrate on the game itself. I decided to name each stage after a star, and decided to build 4 regular stages, a final stage, and a survival mode. I’m definitely not a game designer, but I’m quite happy with the final result; there’s a good variety of enemies, and the difficulty progression is well correlated with the upgrades available. Also, I could add a couple of surprises that I’m not going to spoil!

So, with one week to go, I had a finished game that just fit the size limit. But that wasn’t the end of the story…

Bonus phase: Roadroller

Just before the competition started, I read a tweet that mentioned a new compression tool with very promising results, developed specifically for JS13K games. Until this point I developed the game without it, and running it actually gave me an extra 1.5Kb!! So now I had to decide what to do with it; my first thought was to add some music, but given the game has multiple stages, I’d have had to use the same tune for all of them, and that’s the sort of compromise that will make players aware of the limitations of the competition, which is something I really didn’t want.

After giving it some thought, I decided to add a story in the form of “cutscenes”. 1.5Kb is not a lot, so I implemented the simplest possible system I could think off: a dialog between the different actors in the story. However, the uncompressed dialog text alone is already 3.7Kb! Even so, I tried to make it as interesting as I possibly could, so hopefully that will give an incentive to players to finish the game. After some dialog tweaking and additional optimizations, it went under the size limit, and sent it the night before the competition ended.

Closing thoughts

While it’s highly unlikely I’ll end up working as a game developer (as that needs actual talent), it was really interesting to wear that hat for a little bit, and see things from a different perspective than what I’m used to.

I’m really looking forward to read the comments of the judges and the other developers, as I really think that getting feedback was best part of last year’s competition. And if I get a shirt this year, I’ll be very happy!

Play it here, and the source is on GitHub.

In the last post, I mentioned I may participate in 2020’s JS13K games competition… and I did!

This year’s theme was “404”. I wasn’t really able to come up with a good idea for it, so in the end, I just went and built one similar to the ones I loved as a child. As a Commodore 64 owner, I really enjoyed games like River Raid, Lightforce, Terra Cresta… but I didn’t want to just create a clone; I wanted to modernize the concept while retaining the thrill and playability.

I tied the game to the contest’s theme by naming it “Planet Not Found”, given the player will never find any (even though it could be heading to one!).

My first decision was to design the game to be mobile first, which a lot of people use for casual gaming. Some implications:

• The graphics are relatively large compared to the screen, as the screen in phones is usually a lot smaller than computers
• The controls are kept extremely simple; it can be played with a single finger, just put the finger where the ship should go and it will be there as soon as it can. The lack of fire button is very easy to solve: just keep firing. The downside is that it’s not possible to have actions, like a special attack or weapon change.
• Some portable devices may not have powerful CPUs, so most graphics assets are generated when the game starts Portrait orientation, which is the default in phones

Visuals

Because of the size limit constraint, many JS13K games have very simple graphics, or create them in a “retro” style, which helps quite a bit. However, I really wanted to make the game look “modern”, so I looked into procedurally generated ships. After some research I stumbled upon a monthly challenge entry in Reddit that I really liked, so I contacted its author and then created a JS module from it. I may actually look into creating such library from scratch at some point, but I really liked the generated ship’s variety and detail, and its author definitely put a lot of effort into it.

Even though this library takes 5Kb, it can create ships of basically any size with just a few characters. For instance, the boss is created with:

generateShip(generateFaction("HYj7ADLjQr6icLtO"), "CdiB9N2ZoQWuAxur", 270);

The game uses 14 different ships: the player, the boss, and 12 enemies. Powerups, shield and bullets are generated manually, which is quite easy given their easy shapes.

So now that we have these nice, big ships, what happens when we destroy them? I liked the idea of shattering them, but doing that in regular shapes (like squares) wouldn’t have looked good. Instead, I opted to create a mesh of points that act as the center of each fragment, added a bit of randomness on their position so the fragments are shaped differently, and then group every pixel of the ship to their closest fragment center point. Every time a ship explodes, each fragment is assigned a random speed and rotation, so even if the fragments are the same, the explosion itself will always look different.

Game mechanics

I decided to keep it very simple, with a single “survival” level; it just keeps getting more and more difficult, and a new ship type is introduced every 10 seconds.

The game could have been split in stages, but I didn’t want to put artificial barriers; instead of using extra ships, I added an energy shield, so the ship won’t be destroyed at the smallest touch like most shoot’em ups.

Every 5 seconds a new powerup will appear; it can be either fast fire (orange F), energy shield (blue S) or a bomb (red B).

Approximately every 50 seconds, a boss fight will be triggered. I won’t spoil it, so go check it out; what I can say is that it will get more and more difficult as the game progresses.

What could have gone better

I spent all my available time creating and polishing the game, so it’s not well optimized for size. Perhaps using Rollup instead of Webpack, and Google Closure Compiler with advanced optimizations instead of Terser would have saved quite a bit.

The thing I’m the least satisfied in the collision system; it’s just simple boxes, which is easy to implement, but it can be quite inaccurate in some situations. So, with a bit more time I would add a “second pass” that validates the collision with the actual image pixels.

Last, I should have implemented keyboard controls to provide a different experience and potentially better accessibility. It would take a few extra bytes, but didn’t think of it until after the context.

Closing thoughts

Participating in this contest was really enjoyable, and a big change compared to my past experiences with JS1K, where optimizing the code is probably the most satisfying and time consuming part. It took quite a bit of time and effort, but I’m very happy with the end result, and I’ll be definitely playing it from time to time.

Play it here, and the source is on GitHub.

My second entry for JS1K was an animation: Nyan Cat 2.0.

Why?

So, if I already made one back in 2014, and even wrote a blog post about it, why would I do it again? Well, for me it was really frustrating not to be able to find a way add the twinkling stars in the background.

It took me quite a lot of time to get that starless version down to 1Kb back then, so I just gave up, but from time to time I still thought about it… until one day I had an Eureka moment.

A more efficient encoding

As I described in the 2014 Nyan Cat entry blog post, there sprites were compressed using a run-length encoding system, so a string like AABCCC (which in that case would be “2 cells of the first color, 1 of the second, and 3 of the third”) was compressed to A3BC4.

In this particular animation, the different parts have rather small amount of colors; for instance, the cat’s head only has 6 different colors, while the legs and tail have 3, and this characteristic allows a quite interesting trick: encoding the color and the amount on a single character.

So, let’s say that our basic colors are ABCDEF; that means that we want to paint a single cell with each of those colors; then, the next 6 characters, GHIJKL, are used to represent two cells; then, the next 6 (MNOPQR) three cells, and so on. So, if we had AABCCC, it would be compressed to GBO, 2 bytes smaller. Success!

Not only did it make the data more compact (around 80 bytes), but also the new sprite drawing function ended up being 40 bytes smaller. So now I had some wiggle room in order to add those stars.

What else?

In the previous Nyan Cat blog post I predicted that the stars would take somewhere between 200 and 400 bytes… in the end it was 234 bytes before compression, so quite close.

So, I had to roll up my sleeves and find some additional optimizations; an easy one was to change the cat body, as it was using some custom rectangle fillings in order to make it a perfect copy of the one in the original GIF animation; instead, I made a very close aproximation using the same sprite painter function that it’s used everywhere else, while the other ones mostly involved renaming things around in order to increase RegPack’s efficiency.

Commented source code

b=0;
// Color picker
P=(z,x,d,w,s)=>{
  c.fillStyle="#"+"036#000#999#f99#fff#000#fc9#f9f#f39#f00#f90#ff0#3f0#09f#63f".split("#")[z]
};
// Sprite painter
S=(z,x,d,w,s)=>{
  for(i=0,g="";z[i];i++)
    o=z.charCodeAt(i)-36,g+=Array(2+o/5|0).join(o%5);
  z=g.split("");
  for(i=0,g="";z[i];i++)(v=+z[i])&&(P(v+s),c.fillRect(x+i%w*6,6*(i/w|0)+d,6,6))
};
// Function that paints the star
E=(z,x,d,w,s)=>{
  S("~8%#t%8%$%8%#Q%=%3*$*3%=%#.%=%Q*$%$*Q%=%#.%3%.%G%8%G%.%3%#.%t%8%t%".split("#")[(z+b)%12%6],(w+b)%12*-38+x+224+146,146+d+86,7,3)
};
setInterval((z,x,d,w,s)=>{
  // Paint rainbow
  for(i=0,g=34,P(0),c.fillRect(0,0,999,999),d=2&b;g<999;g+=46,d=!d)
    for(i=0,g=g;6>i;i++)
	  P(9+i),
	  c.fillRect(-(2&b)*3-g+146,146+d+18*i+4*d-3,46,18);
  f=b%6,
  // Paint the stars
  E(3,0,-202,0),
  E(1,6,-129,10),
  E(1,0,-243,4),
  E(2,19,127,5),
  E(4,6,0,7),
  E(13-2*b,27,70,0),
  d=7*(f>1),
  // Paint the cat body parts
  S("4)%+*$*+*$*+%)*+./8%#B*.%+%)%+/$%5)*+3*#~3%)>5%0*$4#o*)*+$%5%+4+%.*#G4)%095%)4&8*#$*.%+/$%5)*+3*".split("#")[f],-36-6*(f==4)+146,146+d+33,1*(f==4)+6,0),
  S("L9$%:$%+*)4#o%5)%+%./#t%0.%+%./#o%5)%+%./#)9$C04+%./#)9$%:%04+%./".split("#")[f],-18+146,146+d+81,7,0),
  S(")%+%8%+%$%+%3/=/)/#)%+%8%+%$%+%./=/)/#.%+%8%+%$%+%./=/)/#)%+%8%+%$%+%./=/)/#%+%8%+%$%+%./=/)/#%+%8%+%$%+%./=/)/".split("#")[f],11+146,146+d+99,21,0),
  S(")u.%v%$%0c0*+@(,(;+*&,(h&*&h(,&*&w&*&@(T&*&w&*&1(m%&E(Y%&'(w%&|'%&;(c%+'(@(O%0c0/v%.u)",+146,146+d+-9,21,4),
  S(")*G*.%+%=%+%)%0%3%0%)%545%)%]%$%g*0(%:(%+*0*0%&*+*&,N,*&,&%+%+%&,%$%0C+%.%S%8R",66-6*(f>3||!f)+146,146+d+21-7*(f==5),16,0),b=(1+b)%12
},70)

Game Over

Sadly, JS1K is now over. This competition was great to motivate myself to create these tiny games and demos, and I was able to work on most of the ideas I had… well, at some point I wanted to build a shoot’em up game, but other than that, I’m satisfied with the work I created. I participated for the challenge and the learning, and certainly entertained me; gave me a excuse to create a plasma effect, a 3D renderer, cat animations, and even some games.

What now? Well, I’ve been thinking about participating in JS13K, but that may be a major time commitment, considering how long it took me to complete some of the single-kilobyte entries… Still, would be nice to do it at least once. Maybe 2020!!

So, sadly 2019’s JS1K edition was the last one, so I decided to participate with two entries! This post is about Fruit Crush Saga.

The game

I’m sure most people know Candy Crush Saga, a very popular cellphone game. It’s gameplay it’s quite close to Bejeweled of back in the day. Since nobody had made a version of that kind of game for the JS1K contest, I decided to take the challenge!

Each of those jewel images easily weights qmore than 1Kb, so what to use? To me, the obvious choice was emojis, and the fruit emoji range is perfect for the task; I decided to use 🍓, 🥝, 🍉, 🍊, 🍇, 🥥 and 🍌, as they are quite visually distinct in most browsers.

The rules are the same as Candy Crush Saga/Bejeweled; exchange two adjacent fruits vertically or horizontally, and if after the change there’s a group of adjacent fruits with 3 or more in a row or column, it’s removed, and new fruits will fall from the top. Chain reactions are really satisfying!

Tricks

Nothing too exotic here.

• Instead of using the provided canvas, the code will build and inject HTML; I borrowed the concept from the excellent Tiny Chess entry by Óscar Toledo G.

• The board data is defined as a single array instead of a bidimensional one, which makes the code clearer but would make the code a bit bigger.

• For the highscore, localStorage is used in order to persist it; however, instead of the usual getItem/setItem API, it uses it as an object, which I wasn’t really aware was possible until I checked other JS1K entries. Also, the highscore key is just 9, so no quotes are needed.

• Functions store their results in globals instead of returning a value.

Commented source code

// Initializing variables
q=r=h=d=z=0,s=99,F=[];
// Find explodable fruits in current board, and store the positions in `o`
O=i=>{
  o=[];
  for(i=0;i<64;i++)i%8<6&&F[i]==F[i+1]&&F[i]==F[i+2]&&o.push(i,i+1,i+2),i<48&&F[i]==F[i+8]&&F[i]==F[i+16]&&o.push(i,i+8,i+16)
};
// Check if there's any available move; `e` will be `1` if the game should end 
E=i=>{
  e=1;
  for(i=0;i<64;i++)j=F[i],i%8<7&&(F[i]=F[i+1],F[i+1]=j,O(),F[i+1]=F[i],F[i]=j,o.length&&(e=0)),F[i]=F[i+8],F[i+8]=j,O(),F[i+8]=F[i],F[i]=j,o.length&&(e=0)
};
// Explode fruits due to correct swap
X=i=>{
  x=[];
  for(i=0;i<64;i++)!F[63-i]&&(F[63-i]=i<56?(j=F[55-i],F[55-i]="",j):["🍓","🥝","🍉","🍊","🍇","🥥","🍌"][7*Math.random()|0],x.push(63-i));
  x.length?(d=6,setTimeout(Y,25)):(O(),o.length?(h=16,setTimeout(Y,25)):(E(),e&&alert(z?" Record!":"Game over"))),B()
};
// Animation that blinks the exploding fruits
Y=i=>{setTimeout(h&&(--h||(r+=5*o.length,o.map(i=>F[i]="")))||d&&d--?Y:X,25),B()};
// Show animation for wrong move, and restore state when finished playing
Q=i=>{setTimeout(q&&q--?Q:(F[l]=F[m],F[m]=k,X),99),B()};
// Interchange cell fruits
I=i=>{
  m=S,l=s,s=99,
  k=F[m],F[m]=F[l],F[l]=k,
  O(),
  B(),
  o.length?setTimeout(X,25):(q=11,setTimeout(Q,99))
};
// Initialize board, ensuring there's at least one valid move
for(i=0;i<64||(E(),O(),o.length+e)&&!(i=0);i++)F[i]=["🍓","🥝","🍉","🍊","🍇","🥥","🍌"][7*Math.random()|0];
// Onscreen HTML board and cell rendering
B=i=>{
  j="<table align=center cellspacing=0 cellpadding=0>";
  // Render every cell in the game
  for(i=0;i<64;j+="<th width=64 height=64 onclick='s="+i+";i=S%8-s%8;j=S-s;(j*j-1||i*i-1)&&j*j-64?B():I()'bgcolor=#"+(i-s?1&(i+i/8|0)?443:554:990)+"><span style='position:relative;font-size:30px;top:-"+(d&&x.includes(i)&&d*8)+"px'>"+(4&h&&o.includes(i)?"":2&q&&(i==l||i==m)?"🙅":F[i])+(++i%8?"":"<tr>"))
    S=s;
  // Update highscore if needed
  r<=localStorage[9]||(z=localStorage[9]=r);
  // Render current score and highscore
  b.innerHTML=j+"<th colspan=4><big>"+r+"<th colspan=4><big>🏆"+localStorage[9]
};
// Start the game
B();

That’s all

This was a fun little game and something I had in my mind for a while, so I’m glad I was able to finally go and implement it for the last edition of JS1K. I’m always amazed on all that can fit in a single kilobyte of JavaScript!

For my second JS1K entry I wanted to do something a bit different, so I created Stars, a 3D puzzle game.

Background

My main objective in the code golfing competitions is to learn and explore concepts that I usually wouldn’t deal with. After finishing the memory game, there was still quite a lot of time left before the competition deadline, so I decided to challenge myself and try to do something different.

Some years ago I played a Flash game named Starlight, which I really enjoyed. While it wasn’t challenging, it was beautiful and I loved it’s simplicity and originality.

So, could it be done in just 1Kb of JavaScript? Well, I had to try!

Concept

The basic idea is quite simple: we have a seemingly random set of stars, which we can rotate using the mouse. Then, once we find the right rotation, a drawing is revealed.

First I planned to precalculate the coordinates of each point that would render the figure at certain rotation, which is probably what the Flash game is doing… but that would be a lot of data for our size limit. Then, I realized that we could use orthographic view.

What is the difference between orthographic and perspective views? When we use perspective, the position of a point in the screen depends on it’s distance from the camera, but that’s not the case when we use an orthographic view; regardless of their distance, all points are painted on the screen based on their coordinates. This is a really bad idea for representing 3D objects, since they’ll look very unnatural at certain angles (for instance, the front view of a wireframe cube will be just a square), but in our case, it’s perfect for representing 2D pictures. In our case, we just paint the dots on the screen using the (X,Y) coordinates, and the Z is only used for rotations.

So, a drawing is composed by a set of dots on a 3D coordinate system. The design is made and stored as a set of 2D integer coordinates, and when it’s loaded, a random Z component is generated for each dot. When there’s no rotation, the original drawing is shown on the screen, but when there’s rotation, the image is obfuscated.

Data structure

So, an efficient way to store a set of 2D coordinates in the (-20,20) range is required. After some investigation and asking around, I decided to store the figures as strings, representing each coordinate with 2 characters (one for X, one for Y). Then, the unpacking code looks like this:

  e=[].map.call(packed,i=>i.charCodeAt(w=0)-77);
  for (i=q=e.length/2;i--;)v.push([e[2*i+1],e[2*i], 30*Math.random()-15]);

So, the packed implemented drawings look like this:

• Star (10 points): “IRJ[QTZVVMZDQFJ?IH@M”
• Cat (28 points): “LTLPTNTLOLOHQFRFRHTHTDMCHCEGFHIELEIHIKLNHNJPJTHVNVPSPQNN”
• Hat (25 points): “UXV[WXXSXKWEVCUETJUMUQTTRSMRJQFOCOAQBOCMFLJKRKSMSQ”

After we load the main dots, we also generate a number of random dots that aren’t actually part of the drawing, and which are rendered as smaller stars.

3D Rotation

In order to control the stars, first we randomly determine a point in the screen at the start of every level (which is our goal, what we need to find in order to complete the level).

Then, the rotation of the stars is determined by the mouse cursor distance to the goal; the distance on the X axis affects the X axis rotation of the stars, and the same with the Y axis. It’s important to never rotate near π radians (180 degrees), as the image would also be revealed due to simmetry.

So, when the mouse is exactly at our goal, the image is rotated 0 degrees on it’s X axis and 0 degrees on it’s Y axis; hence, the image is rendered with exactly the same X and Y coordinates as we defined it!

Rendering

Rendering a constallation of stars is probably one of the simplest scenarios, as we don’t have to deal with Z-ordering or occlusion culling; we just determine the screen position of the 3D point, and we’re done!

With the orthographic view, we don’t even need to project the dots, just apply the 3D rotations, and use the resulting (X,Y) coordinates.

First we iterate the dots, calculating their screen position and painting them; we also store them, on a line buffer, which we use afterwards to paint the lines between the stars if we’re close enough to the goal. Those lines go from the first dot to the last as a single line, but we do some postprocessing depending on the level in order to give it some variety, like some extra lines on the hat, or the cat’s eyes. Here’s an image of the hat without the extra lines:

Tricks

When developing this sort of demos/games, it’s important to keep an eye open for anything that can give an advantage, doing the same with less bytes, or getting some nice feature cheap (or free!). Other than the standard golfing advice, here’s some of the things that I made in this demo:

• Level start/end animation: the initial and final animations use the same scaling variable; when the level starts, looks like a “big bang” as 3D rotation is applied, and when it ends, the same scaling makes it look like the figure moves toward the camera, with exactly the same code.

• ES6 Math.sign function: this new math function just returns -1, 0 or 1 if the number is negative, zero or positive respectively. This was quite useful once the mouse cursor is close enough and the gap is closed automatically, since we can use it to move towards our goal in a way that works quite well with Regpack:

x+=Math.sign(m-x);
y+=Math.sign(n-y);

Commented source code

// Initialize the level
O=function(e) {
  l=e%3;
  // Randomly calculate the goal
  m = a.width * Math.random()|0;
  n = a.height * Math.random()|0;
  f = 30;
  v = [];
  // Unpack star map
  e=v.map.call([
    "IRJ[QTZVVMZDQFJ?IH@M",
	"LTLPTNTLOLOHQFRFRHTHTDMCHCEGFHIELEIHIKLNHNJPJTHVNVPSPQNN",
	"UXV[WXXSXKWEVCUETJUMUQTTRSMRJQFOCOAQBOCMFLJKRKSMSQ"
	][l],i=>i.charCodeAt(w=0)-77);
  for (i=q=e.length/2;i--;)v.push([e[2*i+1],e[2*i], 30*Math.random()-15]);
  // Decorational small stars
  for (i=60;i--;)
    v.push([30*Math.random()-15,30*Math.random()-15,30*Math.random()-15]);
};
s = Math.min(a.width, a.height);
R = function(e) {
  if (w) {
    // We won, move automatically towards the goal and stay there
    x += Math.sign(m-x);
    y += Math.sign(n-y);
	if (w++>150) O(l+1);
  }
  // Background gradient
  e = c.createLinearGradient(0,0,0,a.height);
  e.addColorStop(.7,"#001");
  e.addColorStop(1,"#115");
  c.fillStyle = e;
  c.fillRect(0, 0, a.width, a.height);
  c.fillStyle = c.strokeStyle = "#fff";
  o=(w>80?(w/4 -19):1)*(1-f*f/900);
  c.globalAlpha = 1/o;
  if (f)f--;
  // Start with end vertex (careful with multiple levels!!)
  e = [l?l>1?v[12]:v[25]:v[0]];
  for(i in v) {
    // Apply 3D rotations
    k = v[i];
    u = Math.PI*(n-y)/(y<n?n:(a.height-n))/2;
    g = - k[2]*Math.sin(u)+Math.cos(u)*k[1];
    h = k[1]*Math.sin(u)+Math.cos(u)*k[2];
    u = -Math.PI*(m-x)/(x<m?m:(a.width-m))/2;
    j = h*Math.sin(u)+Math.cos(u)*k[0]; 
    k.x = j * o * s / 30 + a.width/2;
    k.y = g * o * s / 30 + a.height/2;
    // Paint star
    c.beginPath();
    c.arc(k.x, k.y, i<q?5/2:1, 0, 2*Math.PI);
    c.fill();
	// Store it for line rendering if necessary
    if (i < q-(l-1?0:2))
	  e.push(k,k);
  }
  // Line postprocessing
  if (l-2) {
    e.push(v[0]);
  } else {
	e.push(v[13],v[2],v[16]);
  }
  // The line intensity depends on the distance to the goal
  c.globalAlpha = Math.max(0,.8-Math.hypot(m-x, n-y)/(.8*s))/o;
  // Are we close enough to win?
  if(!f&&!w&&c.globalAlpha>.7)w=1;
  for (i=e.length/2;i--;) {
    // Draw line
    c.beginPath();
    c.moveTo(e[2*i].x, e[2*i].y);
    c.lineTo(e[2*i+1].x, e[2*i+1].y);
    c.stroke();
  }
  c.globalAlpha = 1;
  requestAnimationFrame(R);
}
onmousemove = function(e) {
  // If we won, ignore input
  if (!w){
    x = e.pageX;
    y = e.pageY;
  }
};
// Initialize game
O(x=y=0);
// Render
R();
// Change function to ES6 format
// Change 2.5 to 5/2
// Minified, ES6 and packed (with Math)

Final words

With this game I wanted to do something different, and I believe I achieved it. I was lucky to get an idea that actually required a simpler form of 3D rendering in order to work, and I really like the result. I’m already looking forward to next’s years compo!

Last year I didn’t have the time to participate in JS1K… but this one I could! I made two games, so this article describes the creation process of the first one: Memoji, a memory game.

Preface

Back in 2012, the theme for JS1K was “Love”. My first idea was to make a memory game, to be named “Loving memories”.

I thought that it would be trivial to implement rotating cards using trapezoids to simulate a 3D effect, but when implementing the prototype, I learned that, unfortunately, HTML5 Canvas lacks that sort of transformation, as it’s limited to scaling, translating, rotating, and skewing.

That didn’t stop me, and I found a way to achieve the same effect: rendering an image by painting it one column at a time at different heights, using the drawImage(image, sx, sy, sWidth, sHeight, dx, dy, dWidth, dHeight); method.

While this works, and it’s quick enough, the resulting function takes quite a bit of the available space. At that moment, I didn’t think it would be possible to implement the game the way I wanted, so I gave up and made a different one, which I’m still quite proud of.

Fast forward to 2017! I decided to revisit my concept and see if it was feasible. I could see very soon that it was! When I first investigated it, I didn’t know about Regpack, or canvas literals hashing, and this year’s rules also allow ES6, so it was quite clear that it would fit.

Hence, I decided to go for it, but I also set my goal to make it a polished game; many times, because of the space contraints, developers need to find shortcuts, like using an static size, or placing the game at the (0,0) coordinates to simplify the code, but since the game itself is quite simple, I wanted to provide a proper experience in both desktop and mobile.

Enablers

As I mentioned earlier, before being able to implement this game, some things had to be developed, and I had to learn a few tricks:

• Regpack: this is a very interesting tool, which is used by most JS1K demos. It has evolved quite a bit through the years, adding new features. Basically, it will take some code, analizes it, find repeated strings, and generates a code that will expand into the original version. The higher number of repeated strings, the better the compression will be, so the code can be fine tuned to take advantage of it. For instance, it’s a good idea to minimize the number of used variables as much as possible, and also try to reuse the same patterns over and over.
• Color emojis: During the past few months there has been quite an advancement in the adoption of color emojis by desktop browsers (as they have been available in cell phones for quite a bit). Firefox now has an embedded color emoji font in all platforms, and both Mac and Windows now come with beautiful, full color emojis. For a space-constrained competition like JS1K, that’s a treasure chest that’s difficult to ignore, so this year a large number of entries have decided to take advantage of that feature.
• Canvas literal hashing: one important handicap of using JavaScript in demos is that the JavaScript API literals are quite long; strings like globalCompositeOperation or requestAnimationFrame really fill up the space quickly! A technique that has been used to work around that is to “compress” all strings in the Canvas object using a function like this:

for(i in c)c[i[0]+[i[6]]]=i;

After this function is applied, we can access c.globalAlpha as c[c.gA], or c.createLinearGracient as c[c.cL]. The only issue with this approach is that the game may stop working if new functions are added to the Canvas that collide with the existing mappings… but it works today!

Tricks

In order to make everything fit in just 1024 bytes, it’s important to analyze the code and find alternatives that do a the same job (or as close as possible) while consuming less bytes (or reuse existing code so it can be compressed better). Here’s a few that went into this game:

• Emoji selection: From the Unicode code point U+1F400 (rat 🐀) to U+1F43F (chipmunk 🐿) we can find the animal emojis, which are rendered in color where available. Those characters are quite adequate for this sort of game, as they’re quite different from each other, and they look quite good! For the game we need to pick 8 random animals, so in order not to use the same animal twice, the following code is used:

figure+=1+Math.random()*7|0;

While it’s not uniformly distributed (low number characters will be used more often than high ones), it fully prevents duplicates without using many bytes.

• Card randomization: in order to randomly place the different cards on the board, I decided to use the following code snippet:

board.sort(()=>.5 - Math.random());

I really like this solution because we let the JS engine do the heavy lifting. Unfortunately, this is not purely random, and it’s specially inefficient on the edges… which was a problem with my default distribution:

There was a high chance that the first two cells and the last two weren’t altered, which was quite noticeable after playing for a bit, so with a few extra bytes I altered the default layout to the following:

It may not look like a big difference, but it works a lot better with the randomized sorting.

• Card shading: in order to make the 3D rotating effect look better, some shading was added to the resulting image. As explained before, each column is drawn individually, so a black rectangle is painted over it with an alpha channel value calculated from the rotation angle. This creates some artifacts around the cards’s rounded corners, so in order to make the problem less noticeable, the animation speed became “ease in out”, which also improves the 3D feeling of the cards.

Commented source code

// Hashing function
R = function(e,n,Z){
  for(Z in e)e[Z[0]+(Z[n||6])]=e[Z]&&e[Z].call?e[Z]:Z;
};
R(c);
R(a,3);
w = a[a.wt], h=a[a.hg];
// Calculate side
s = (((w<h)?w:h)>>2)-24;
// Pseudo-3D function
S = function(img, left, top, portviewWidth, n){
  q = n;
  if (portviewWidth-s) {
    c[c.fy] = "#000";
    for(n = portviewWidth; n--;) {
      c.da(img,
        n * s /portviewWidth,
        0, 
        s / portviewWidth, 
        s, 
        left + n + (s-portviewWidth>>1), 
        top - .5 * q * (s-portviewWidth) * (n - portviewWidth/2)/(3*portviewWidth), 
        1, 
        s + q * (s-portviewWidth) * (n - portviewWidth/2) / (3*portviewWidth));
      // Frame darkening
      c[c.gA]=.7*(1-portviewWidth/s);
      c.fc(
        left + n + (s-portviewWidth>>1), 
        top - .5 * q * (s-portviewWidth) * (n - portviewWidth/2)/(3*portviewWidth), 
        1,
        s + q * (s-portviewWidth) * (n - portviewWidth/2) / (3*portviewWidth));
      c[c.gA] = 1;
    }
  } else {
    // Efficient painting path
    c.da(img,left,top);
  }
}
g = [];
// Store canvas object
q = c;
f = -1;
// Initialize board
for(n=17;n--;){
  // New canvas
  a=a.cn()
  R(a,8);
  // Reuse canvas for better RegPack compression
  c=a.gx("2d");
  R(a,3);
  // Cell value
  a.f=f=(n<8)?g[n+8].f:(f+1+Math.random()*7|0);
  // Set size (if not set, it's very slow on mobile)
  a[a.wt]=a[a.hg]=s;
  // Canvas reduction
  R(c);
  // Pick colors depending of the card type: normal or back
  c[c.sS]=(n-16)?"#ddd":"#553";
  c[c.fy]=(n-16)?"#ddd":"#aa7"
  // Round box
  c[c.li]="round";
  c[c.ld]=16;
  // Stroke
  c.sR(8,8,s-16,s-16);
  // Fill Rect
  c.fc(8,8,s-16,s-16);
  if (n-16){
    c[c.fy]="#000"
    c.font=s/2 + "px d";
    c[c.ti]="center"
    c[c.ts]="middle"
    // emojis to use: 61 from 1F400 (128e3)
    c.fx(a.y=String.fromCodePoint(f+128e3),s/2,s/2)
  }
  // Store it as a board cell or the card back
  (n-16)?g[n]=a:B=a;
}
// Restore canvas object
c = q;
// Randomize
g.sort(function(){return.5 - Math.random()});
A=function(W,X,Y,Z,n){
  // Clean the canvas
  c[c.fy] = "#123"
  c.fc(0,0,w,h)
  // Paint all cells
  for (n=16;n--;) {
    S(((g[n].z>1&&g[n].x<13)||(g[n].z&1&&g[n].x>13)||g[n].z&4)?g[n]:B,
      w/2-s*2+(s+16)*(n%4)-16,
      h/2-s*2+(s+16)*(n/4|0)-16,
       (g[n].x&&--g[n].x&&g[n].z-4)?s*Math.abs((g[n].x-12)/12)|0:s,
       ((g[n].z&1?-1:1)*(g[n].x<13?-1:1)));
    if (!g[n].x&&g[n].z&4) {
      g[n].z = 1;
      g[n].x = 24;
    }
  }
  // Are we done animating?
  if (k>-1 && !g[k].x && !g[f].x) {
    // Do we have a pair?
    if (g[f].y == g[k].y) {
      g[f].z = g[k].z = 3;
    } else {
      g[f].z = g[k].z=4;
      g[f].x = g[k].x=24;
    }
    // Reset selections
    k = f = -1;
  }
  requestAnimationFrame(A);
};
// Initialize
A(k = f = -1);
// Mouse click listener
onclick = function(e,clickedX,clickedY){
  // Store clicked row & column
  clickedX = (e.pageX-w/2+s*2+16)/(s+16)|0;
  clickedY = (e.pageY-h/2+s*2+16)/(s+16)|0;
  if (clickedX > -1
    &&clickedX<4
    &&clickedY>-1
    &&clickedY<4
    &&g[e = clickedX+4*clickedY].z!=3
    &&e-f
    &&k<0) {
    (f>-1)?k = e:f = e;
    // Animation
    g[e].x = (g[e].z&4)?0:g[e].x||24;
    // 2 is opening animation
    g[e].z = 2;
  }
};
// Processing the release version:
// - Minify with Google Closure Compiler (simple optimizations)
// - Remove final semicolon
// - Change functions to arrow functions, reuse function signature
// - Change getContext to use backticks (ES6)
// - Fix loops to use same index variable
// - Pack with Regpack

Final words

While there’s nothing extraordinary going on with this memory game, I’m really happy with the end result, and most importantly, to have been able to achieve what I thought was impossible a few years ago. Plus, my daughters love to play with it in my cell phone 😄

Well, hasn’t it been a while? After all this time, I had to set up Octopress again, but I decided to migrate to Hugo instead.

I’m a big fan of static pages; they can be deployed anywhere, they’re fast, robust and most important secure. Also, they don’t need constant updates 😅 Of course, not everything can be done statically, but things like this little blog greatly benefit from it.

When I started the blog I decided to use Octopress. I really liked the concept, and I can tell that a great deal of effort and polish went into it. However, it’s not easy to configure (at least on Windows), and it’s usage could be more intuitive.

Since my last post I switched computers, so I needed to reconfigure everything again in order to make new posts… I heard about Hugo, so I decided to give it a try.

For the past couple of hours I’ve been setting up and migrating this blog, and I have to say it has been quite an easy transition. Of course, the fact that both platforms use Markdown helped enormously. Since Hugo is delivered as a single executable file, no setup was required, and the usage was simple enough. That said, their online documentation could be improved.

At first I got 404 error messages when trying to show the individual posts,although they were correctly listed in the main page. Turns out that I had to modify the configuration from each post, so I used regexp find & replace to change all posts at once with the appropiate changes.

Also, it was a bit difficult to pick a theme; they have a site dedicated to them, but each of them have different configuration and features… Quite many of them seem unsuitable for a blog site. In the end, I went for a extremely simple blog theme, but I had to check out a number of them.

So, after I was done, I checked the result using Hugo’s internal server, liked what I saw, and uploaded it. When I was using Octopress, I used s3cmd, but this time I decided to use AWS CLI, which seems quite complete and easy to use. I’m also using CloudFront, but at this point, I’m quite certain I’ll just host the blog on S3.

That’s all! Expect my JS1K writeup in the next few days. Thanks for reading 😄

So, what is it about shrinking some code to the point of unreadability that keeps people entering the same competition year after year?

The premise of JS1K is quite simple: fit something cool in 1024 bytes of JavaScript; so, why do I personally enjoy it? Doing a demo, animation or game without constraints is just a matter of time and patience, but when adding a highly strict, almost absurd limitation like fitting everything in 1Kb, it automatically becomes a lot more difficult, and therefore, challenging.

So, there’s a lot of advice online on tips & tricks to optimize code for JS1K (like this blog post), so I won’t repeat it; here’s a few things I learned this year that may be helpful to other people.

Automatic JS code reduction

What I used is Uglify 2 (online version here); make sure to uncheck the “Mangle” option, and check the options under “Compressor…"; other than great minification, it gives some cool options to avoid some automatic processing that may be undesirable, like evaluating constant expressions.

Then I used RegPack 3 (online version here); it’s like JS Crush on steroids, and I want to give kudos to the author for the amount of effort and thought that has gone into it.

It’s nice that it gives both JS CRUSH and RegPack outputs, and also it’s possible to change the “Tiebreaker”, which in my case reduced some bytes by using the non-default “most copies first” option.

8-bit sprite drawing

I stumbled onto a wall trying to efficiently animate some areas of my JS1K entry, and then I remembered a very cool entry from a previous year that actually ended in 8th place.

This is the key source code for the sprite drawing:

T=parseInt
// color palette
P='000fb6853345789593fffff6933ccc444555222f00'.match(/.../g)
// insane sprite drawing method
S=function(z,x,y,w,s){for(i=0,f='';i<z.length;i++)f+=new Array((o=P[z[i].charCodeAt(0)-97]||'',n=T(z[i+1]),(n?(i++,n):1)+1)).join('"'+o+'",');for(z=eval('['+f+']'),i=0,r=0,l=0;i<z.length;(r=(++r)>=w?0:r),i++,l=T(i/w))if((v=z[i]))a.fillStyle='#'+v,a.fillRect(x+(r*s),y+(l*s),s,s)}

Quite insane, if you ask me, but works wonderfully! What it does is to define a very efficient syntax to represent 8-bit graphics, which uses a form of run-length encoding.

So, let’s take a sample string: ab2c3b2a; first, it will “explode” this string, so each letter will be represented as many times as the number next to them (up to 9); hence, the sample string will become “abbcccbba” (when no number is present, “1” is assumed); the resulting data will be rendered sequentally as squares of the size specified by the s parameter, going into a new line each w squares; each letter is a color (‘a’ is the first color in the palette, ‘b’ is the second, etc), and squares will be rendered transparent when using undefined colors (‘x’, for instance). This method is great for representing sprites with low color variety, which was exactly my case.

In the original JS1K entry, this call:

S('j4x3b3j2x2b4jx2j2bj2x2j2e3x2je4x2e2d2e2xe2be3xe6xd7',520-p,230,7,10)

Renders this:

Central point

So, quite a lot of the code consists of rendering something at point x,y; the drawing area was 400 pixels wide and tall, so quite a lot of the coordinates (which, unfortunately, didn’t follow any pattern as I was trying to duplicate a hand-made graphic) had 3 digits; one optimization that worked quite well is to try to find the point that was the closest to all the other points.

In my case, that point was 146,150; then, I represented all the coordinates as operations related to that point; for instance, point 151,155 was represented by 5+146,150+5; because it was used many times, RegPack automatically compressed +146,150+ into a single byte, making a coordinate that took 7 bytes into one that takes 3, which is great when the same operation is being used many times over.

Conclusions

In this current age of modern computing, where computing is measured in Terabytes and Gigahertzs, it’s so easy to take the easy way and waste resources like there’s no tomorrow; computing power is relatively cheap compared to good software design and optimization.

So, what is JS1K good for? IMHO, the first and most important lesson to learn is not giving up; there’s always some additional optimization that can be done… sometimes it even requires to go back a few steps and redoing a lot of the work, but that’s the cost of reaching the objective; nobody said it was easy!

Now, from a more practical point of view, I believe that this competition is great for learning the finer points of JS; operator priority, when can brackets be skipped, different ways of achieving the same results…

Then there’s the identification of patterns; one of the most effective ways of reducing code, specially when using JS compressors like JS Crush and RegPack, is to try to identify all similar points and trying to “equalize” them, so they’ll be compressed further; also, reusing the same logic for different functions is a great way to learn abstraction.

… and of course there’s the improved code reading skills that come from working on minified code that relies on global variables :)

Another year, another JS1K! Last year I created a plasma effect, and this year I wanted to do something completely different.

Remember the Nyan Cat viral video? It’s based on a simple GIF animation, so I thought it had to fit in a single kilobyte of JavaScript.

The end result:

To my surprise, the GIF file weights in just over 30Kb (33,067 bytes, to be exact), which appears to be quite a lot, but after careful examination, I understood why.

Even though the animation is made using 8-bit retro style, the reality is that it’s quite more uneven than it looks; some squares are 6x6 pixels, other 5x5, other 6x5… also, some of the elements are displaced by 2 pixels.

So, first I went for the easy stuff, and did the rainbow and the body; that didn’t take long, and I could make them completely accurate to the original; unfortunately, by that time I already realized it would be impossible to make everything fit in just 1Kb; the tail and legs have a relatively complex animation, and the head has quite a lot of detail to it.

So, I recalled seeing a very cool demo that ended in 8th place in the JS1K 2012 competition; it had some cool 8-bit style sprites and even a bit of animation.

The core sprite drawing mechanism for it is really smart:

T=parseInt
// color palette
P='000fb6853345789593fffff6933ccc444555222f00'.match(/.../g)
// insane sprite drawing method
S=function(z,x,y,w,s){for(i=0,f='';i<z.length;i++)f+=new Array((o=P[z[i].charCodeAt(0)-97]||'',n=T(z[i+1]),(n?(i++,n):1)+1)).join('"'+o+'",');for(z=eval('['+f+']'),i=0,r=0,l=0;i<z.length;(r=(++r)>=w?0:r),i++,l=T(i/w))if((v=z[i]))a.fillStyle='#'+v,a.fillRect(x+(r*s),y+(l*s),s,s)}

It’s a bit difficult to understand at first, but it’s really cool; it defines a syntax to paint sprites that is quite optimal for low color counts, which is exactly what I was looking for; after asking for permission to use it, I adapted and optimized it a bit for the specific needs of this animation.

After all the core logic was in place, it was time for optimization; first I used Uglify 2 to minify the code (the options it has are very convenient to preserve hand-made optimizations), and then RegPack; one of the feature I like the most of it is the possibility to know what groups have been optimized, so then it’s possible to search the code for similar points that could be changed to take advantage of the tokens that are already used.

It still didn’t fit, so from there it was just a matter of spending hours looking at the code, and fighting for every byte.

The end result? It fits!! Well… kind of; I was disappointed that I couldn’t include the stars of the original animation, but I’m quite sure those I would have needed 200 to 400 additional bytes, quite far from my “byte budget”.

Apples to Oranges

So, this is how the animations look side-by-side:

Apples to Apples

So, let’s be fair! Now, let’s build a GIF and APNG animations that show exactly the same images as the JS version; it’s 12 frames per image, so here are the results:

Certainly it’s quite less than the original, but there’s still quite a gap.

Some time ago I wrote an article about using JS in the Code Jam competition; sometimes, the solution for its problems require need the processing of very large integer numbers, to the point where they exceed the maximum “real” integer length of JS.

UPDATE 08/09/2013: The Silent Matt library test code has been updated, as a reader pointed out in a comment that it could run quite faster with a simple change; also, I rerun all tests in Chrome 28, which shows improvements in most libraries.

While JS doesn’t have a real integer primitive (everything is “number”), using values over 9007199254740992 (equivalent to 2^53) may not return the exact answer, as precision is lost; also, bitwise operations (like » or |) are not allowed.

To work around this limitation, we can use “BigInteger”, a data structure that can hold integer numbers as big as we need them to be. In JS there are several libraries that offert his kind of structure. So, in order to find the best library for my usage, I investigated the different alternatives, and decided to write this post in order to share my findings.

In order to compare the performance of the different libraries, a brute force implementation of “Bullseye”, which is problem A of Round 1A 2013, was implemented, adjusting it for each library. The value used for the tests was “1 100000000000000”.

Tom Wu’s BigInteger (website)

It’s used by the Dojo toolkit as their BigInteger class, and was also used by Google as one of their V8 benchmarks.

While it’s quite well made for 2005 code, it defines many functions in the global namespace; on the bright side, it has a lot of functionality, and it’s quite easy to use even though the documentation is almost non-existant, as all the functions are listed at the bottom of the library.

The code:

var params = readStrings();
var currentPaint = new BigInteger(params[1], 10);
var currentRadius = new BigInteger(params[0], 10).add(BigInteger.ONE);
var numberCircles = 0;
var finished = false;
var TWO = BigInteger.ONE.add(BigInteger.ONE);
while (!finished) {
  var neededPaint = currentRadius.shiftLeft(1).subtract(BigInteger.ONE);
  if (neededPaint.compareTo(currentPaint) <= 0) {
    numberCircles++;
    currentPaint = currentPaint.subtract(neededPaint);
    currentRadius = currentRadius.add(TWO);
  } else {
    finished = true;
  }
}
return numberCircles;

It completes the test in 16.81 seconds.

JavaScript BigInteger Library by Silent Matt (website)

Well documented and easy to use library; the functions will take strings, regular numbers and BigInt objects, which is a big plus. On the down side, it didn’t include “bit shifting” functions, which should do operations like multiplying by a power of 2 a lot more efficient.

The code:

var params = readStrings();
var currentPaint = new BigInteger(params[1]);
var currentRadius = new BigInteger(params[0]).add(BigInteger.small[1]);
var numberCircles = 0;
var finished = false;
var TWO = BigInteger(2);
while (!finished) {
  var neededPaint = currentRadius.multiply(2).subtract(BigInteger.small[1]);
  if (neededPaint.compare(currentPaint) <= 0) {
    numberCircles++;
    currentPaint = currentPaint.subtract(neededPaint);
    currentRadius = currentRadius.add(BigInteger.small[2]);
  } else {
    finished = true;
  }
}
return numberCircles;

Completes the test in 14.71 seconds.

Big Integer Library by Leemon Baird (website)

Very powerful library, although can be a bit tricky to use. What I liked the most about it is the ability to do operations “in place”; while the other libraries will always create a new instance of BigInteger for each operation, this library provides the possibility to perform the operations directly on its values, which can make it a lot faster. On the down side, it can be tricky to use; for instance, when parsing a string into a bigInt, the minimum number of elements needs to be specified, and the in-place operations require manual control of the number size in order to provide a correct result.

The code:

var params = readStrings();
var currentPaint = str2bigInt(params[1], 10, 25);
var currentRadius = str2bigInt(params[0], 10, 25);
addInt_(currentRadius, 1);
var numberCircles = 0;
var finished = false;
while (!finished) {
  var neededPaint = dup(currentRadius);
  leftShift_(neededPaint, 1);
  addInt_(neededPaint, -1);
  if (equals(neededPaint, currentPaint)|| greater(currentPaint, neededPaint)) {
    numberCircles++;
    sub_(currentPaint, neededPaint);
    addInt_(currentRadius, 2);
  } else {
    finished = true;
  }
}
return numberCircles;

Completes the test in 8.24 seconds (best result among all libraries, quite impressive!).

BigInteger.js by Peter Olson (website)

This library has a nice documentation, and is simple and easy to use; for instance, the functions will take integer values, and it’s even possible to use regular integer operations as the “valueOf” function is overwritten; that said, it has limited functionality, and in some cases the function names are quite different than the other libraries, and, in my opinion, using a different style than what other languages tend to choose.

The code:

var params = readStrings();
var currentPaint = bigInt(params[1]);
var currentRadius = bigInt(params[0]).next();
var numberCircles = 0;
var finished = false;
var TWO = bigInt(2);
while (!finished) {
  var neededPaint = currentRadius.times(2).minus(1);
  if (neededPaint.compare(currentPaint) <= 0) {
    numberCircles++;
    currentPaint = currentPaint.minus(neededPaint);
    currentRadius = currentRadius.add(2);
  } else {
    finished = true;
  }
}
return numberCircles;

Completes the test in 5 minutes 57.32 seconds.

Conclusion

Ultimately, the choice of library depends on the project; some may require basic functionality, and others may need as much performance as possible. In the past I used Tom Wu’s library, but I’m quite impressed with the performance and design of Silent Matt’s solution, so that will be my choice for future developments that require very large integers.

Ever heard of Magic: The Gathering? Essentially, it’s a trading card game where players build their decks from a set of printed cards and then play each other; while strategy and skill play the biggest roles, luck is a determining factor as in any other card game.

This article assumes that the reader has some background knowledge about how the game works, so if you don’t but are curious, I recommend reading the Wikipedia article first.

One type of cards in this game allows players to attempt to locate other cards from their deck using different mechanisms; the differences can be subtle, so I decided to run a simulation to determine how useful are they at finding specific cards.

Decks that rely on the combination of 2-3 cards to win the game are the ones that tipically need these cards the most, so I decided to base my simulation on that; it divides the cards in two categories: wanted or not wanted, and then plays the different cards to see how early they’ll get one of the wanted cards.

The tested cards are:

• Ponder: the player will look a the first three cards of his deck; then he has the option to return them in any order, or shuffle the deck, and finally he’ll draw a card.
• Portent: similar to Ponder, but can also target the opponent’s deck; also, the card isn’t drawn in the same turn, but at the beginning of the next one.
• Preordain: look at the top 2 cards, and put each of them back either on the top or the bottom of the deck, and finally draw a card.
• Serum Visions: first draw a card, then look at the top 2 cards and finally return them like in Preordain.
• Mystic Speculation: look at the top 3 cards, and return them like Preordain or Serum Visions.
• Careful Study: draw two cards, then discard two cards.
• Index: look at the first 5 cards, then return them on the top of the deck in any order.
• Spy Network: like Index, but with the first 4 ones; also, the player can check his opponent’s hand and top deck card.
• Brainstorm: draw 3 cards, then return 2 cards to the top of the deck.
• Any cantrip: this refers to any spell or effect that makes the player draw a card.
• Nothing: this is the baseline, what happens if no spell is played.

The simulations were run 200,000 times following the Monte Carlo method, and taking in account a deck of 51 cards with several proportions between wanted and unwanted cards; the results are shown as the probability that the player got at least one wanted card by certain turn:

The cards that have flat probabilities for some turns (Index, Spy Network and Brainstorm) are the ones in which the player has ordered the cards on top of his deck, so he knows exactly what he’s going to draw next; while this can be avoided by playing cards or effects that shuffle the deck, it wasn’t taken in account in the simulator.

The cards that would show exactly the same probability line as another card were omitted; for instance, Opt and Sleight of Mind would have exactly the same line as Careful Study.

So, to answer the question this article began with, Ponder appears to be better than Preordain when searching for a specific card, even after a number of turns; also, it’s interesting to notice that Serum Visions is almost as good as Preordain for this purpose, as Preordain is banned in some formats.

While I was developing Nibbo I wanted to make the sidebar stay visible all the time; as I couldn’t find any existing library that I liked, I decided to develop my own.

The one I tried first was jQuery scroll follow, but I didn’t like that the sidebar actually moved to put itself on the right position; many websites implement this by keeping the CSS positioning as “absolute” (so it follows the scroll) and switching it to “fixed” when the sidebar would be partly hidden, so that it’s location would be static in the screen even if the user keeps scrolling down, so, no flickering or movement of any kind.

The problem with this approach comes when the sidebar is actually taller than the viewport; if it’s kept fixed on the screen, then a part of it will never be visible to the user. There’s a number of solutions for this, but the approach I liked the most was to scroll the sidebar together with the content, and when the bottom of the sidebar is reached, lock it at the bottom; if the user then scrolls up, then scroll the sidebar up together with the content until the top of the sidebar is reached, and then lock it at the top.

I was quite proud of the implementation I made, and I planned to make it available under an open source license, but never found the time… so, I finally took the code, cleaned it up, documented it, added a demo, and uploaded it to GitHub!

Check the demo here.

During the past few days I’ve been work on a new Android app; one thing I find very, very important is to make any software look native to the platform it’s running on, and doing that on Android needed some work.

Default theme

So, I installed the Android SDK and the Eclipse plugin, and after working on an initial prototype, I found out that both in a 2.3 real phone, and in the emulator (which runs version 4.0), the lists had bright text over white color, rendering the list almost unusable; the problem here was the default application definition in AndroidManifest.xml:

    <application
        android:icon="@drawable/ic_launcher"
        android:label="@string/app_name"
        android:theme="@style/AppTheme" >

What was wrong is the android:theme field; removing this field will make your application use the default… the problem is that the default changes depending on the android:targetSdkVersion on the same AndroidManifest.xml file:

    <uses-sdk
        android:minSdkVersion="7"
        android:targetSdkVersion="11" />

So, for Android 4.0+, the default theme will be selected depending on that field:

• For values less than 11, @android:style/Theme
• Between 11 and 13 @android:style/Theme.Holo
• For 14 and higher @android:style/Theme.DeviceDefault

Action bar

So, here the obvious choice would be to use a value of 14 or more to use the Theme.DeviceDefault value… but it’s not as easy; the problem here is the “action bar” that was introduced on Android 3.0 .

The “action bar” are the buttons that appear at the right side of the title bar; it uses the same elements as the activity menu, which can have an attribute android:showAsAction that determines wether or not they’re shown in the action bar.

So, if you want to provide compatibility with older Android version you have two options: incorporate your own action bar in older Android versions, or make sure that the important actions (like saving) are shown as buttons.

For the first option, you can implement it yourself (for instance, using the “ActionBarCompat” code sample), or use a third party library like ActionBarSherlock.

I opted for the second option, as the action bar is not a native component in Android versions that are still widely used, and I wanted it to feel as native as possible.

On the onCreate method I added the following:

        if (Build.VERSION.SDK_INT >= Build.VERSION_CODES.HONEYCOMB) {
        	setUpActionBar();
        	// Hide button panel
        	findViewById(R.id.buttonpanel).setVisibility(View.GONE);
        }

And created a new method:

    @TargetApi(11)
    private void setUpActionBar() {
    	getActionBar().setDisplayHomeAsUpEnabled(true);
    }

The @TargetApi(11) annotation is to avoid warnings; you only need to implement this method in the case you want to integrate better with the action bar; in this case, it offers an alternative way to go back to the previous dialog.

Icon colors

After defining your action bar menu items, you probably will want to use icons on them; these are defined by using the android:icon attribute in the menu item definitions.

Here we arrive to an ugly area; the icons are just bitmaps, and they follow certain style (details in the Action Bar Icons Design Guidelines).

So, if you happen to use the Theme.DeviceDefault option, there’s no way to assure that the icons will have the right color for the device at hand, so you’ll need to style the action bar yourself to make sure they’re presented properly.

This is not the case in case that you opt to use a specific theme, like Theme.Holo, which is the option I decided to go for.

An additional advantage of using the Holo theme is that the icons you use will look fine in the Android 2.3 menus; they don’t look completely native, as the system icons have a 3D effect, but they look nice IMHO; of course, if you would like to provide the perfect icons, just specify a different icon set for older versions by providing alternative resources.

Google, listen to me!

I was quite disappointed when I realized that it wasn’t possible to provide a real native experience with Android; if one vendor decided to put use a bright theme in their phone, my app will look black and pretty different, or, at best, with unique action bar colors.

The way I think this should have been implemented is having some way to define masks (maybe as a new type of drawable?); it would be a bitmap image that would be treated as grayscale, and would colorize them with the current text color when rendering them; that way, the action bar icon would have the same color everywhere, and not depend on the theme.

One of the biggest complaints about android is the fragmentation, and not having even the possibility to make an application feel completely native will just keep adding to this perception.

Today I participated in Code Jam’s second round; I didn’t do very well, but it was definitely an entertaining experience.

To compete in Code Jam, I use JavaScript; not a lot of people use it, and even less do well in the competition. Still, the statistics show a large increase of contestants using it compared to the last year.

As I mentioned in my previous post, multi-dimensional arrays are quite useful to solve algorithmic problems, but it’s not the only thing I’ve used; I also created a mini-development environment to code the solution, and I decided to release it as an open source project.

This is not the first project of this kind; I found some alternatives here and here, but my version has the following advantages:

• Helper functions to read the input with ease.
• Support for file drag & drop for the input, and also an automatic “big file mode” for files too large to be placed inside a text field.
• Integrated Big Integer library; it comes with Tom Wu’s BigInt library, which is really handy to solve problems with very large numbers, which aren’t infrequent in Code Jam.
• Includes a “runner” web page that contains a simplified version of the IDE in a single file, so it’s easy to send along with the coded solution.
• Uses web workers to run the code in a separate thread, and local storage to remember the last data.

It’s compatible with at least Firefox and Chrome (the runner page should run in almost any browser). This tool has helped me achieve better scores in Code Jam, so I hope it can help you too!

I use JavaScript when competing in Code Jam, and one of the things I noticed was that multidimensional arrays are a bit of a hassle, so I decided to create a helper class for that purpose.

Coming from a Java background, the Arrays class came to mind, so I decided to reuse most of the API in my implementation.

So, introducing Arrays.js!

It comes with unit tests for all its functionality, but if I missed something, feel free to open an issue. Also, it’s released under the permissive MIT license.

When I wanted to preview a sequence of large images, I decided to go for a lightbox plugin, but I also wanted a better way to see the fine details than having to open the full image.

ColorBox is my favorite lightbox plugin; it’s highly customizable, comes with multiple themes, and still manages to be quite small!

When it comes to large images, it has two options: either show a scaled down version, or use scrollbars; while I prefer the scaled down version, I find it annoying to open the full version and then scroll to the area of interest, so I decided to use the loupe plugin.

So, how to integrate them? First of all, I found out that hte loupe plugin was not setting the z-index CSS property (which ColorBox sets to “9999”), so the CSS needs a change in order to make the loupe stay on top:

/* loupe style - it's important to include the z-index:10000 to overlay over colorbox! */
.loupe { z-index: 10000; background-color:#555; background:rgba(0, 0, 0, 0.25); border:5px solid rgba(0, 0, 0, 0); cursor:url(blank.png), url(blank.cur), none; }

Then, the JavaScript call to ColorBox can be done as follows:

$(".group").colorbox({rel:'group', transition:"none",
    onComplete:function(){
      var image = $('#cboxLoadedContent .cboxPhoto').get(0);
      $("<img/>") // Make in memory copy of image to avoid css issues
          .attr("src", $(image).attr("src"))
          .load(function() {
              if ((this.width > image.width) || (this.height > image.height)) {
                $(image).loupe();
              }
          });
    },
    onCleanup:function(){ $('.loupe').remove(); } }
  );

Why the extra image creation? It’s the only crossbrowser way to retrieve the image’s original width and height (in Firefox the naturalWidth and naturalHeight properties can be used, but they aren’t standard); the good thing is that the image will be in cache, so it won’t be loaded twice.

See it in action here.

I was in need of a tiny web server for one of my projects, and I found out that Java 1.6 actually comes with one!

While I have no idea how well this server performs, it’s perfect for what I was looking for, as my intention is to use it just for one user. First I decided to implement a simple file server, and over it I want to define some custom URLs with special handling. So, now that this part is finished, I think it does make a good base for future projects… so in case you need it, here you’ve it:

import java.io.FileInputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.io.File;
import java.net.InetSocketAddress;
import java.net.FileNameMap;
import java.net.URLConnection;
import java.util.concurrent.Executors;

import com.sun.net.httpserver.Headers;
import com.sun.net.httpserver.HttpExchange;
import com.sun.net.httpserver.HttpHandler;
import com.sun.net.httpserver.HttpServer;

public class FileHandler implements HttpHandler {
	FileNameMap fileNameMap = URLConnection.getFileNameMap();
	
	public static void main(String[] args) throws IOException {
		int serverPort = 8080;
		InetSocketAddress addr = new InetSocketAddress(serverPort);
		HttpServer server = HttpServer.create(addr, 0);

		server.createContext("/", new FileHandler());
		server.setExecutor(Executors.newCachedThreadPool());
		server.start();
		System.out.println("Server is listening on port " + serverPort);
	}

	public void handle(HttpExchange exchange) throws IOException {
		String requestMethod = exchange.getRequestMethod();
		String targetPath = exchange.getRequestURI().getPath();
		if (requestMethod.equalsIgnoreCase("GET")) {
			
			// Here it's a good place to include custom path handling,
			// like calls to Java functions
			
			// Handle paths trying to open index.html
			// Instead of this, we could show a list of the files in the folder
			if (targetPath.endsWith("/")) {
				targetPath += "index.html";
			}
			
			// Check if file exists
			File fileFolder = new File(".", "htdocs");
			File targetFile = new File(fileFolder, targetPath.replace('/', File.separatorChar));
			
			if (targetFile.exists() && targetFile.isFile()) {
				// If it exists and it's a file, serve it
				int bufLen = 10000*1024;
				byte[] buf = new byte[bufLen];
				int len    = 0;
				Headers responseHeaders = exchange.getResponseHeaders();
				
				// Get mime type from the ones defined in [jre_home]/lib/content-types.properties 
				String mimeType = fileNameMap.getContentTypeFor(targetFile.toURI().toURL().toString());
				
				if (mimeType == null) {
					mimeType = "application/octet-stream";
				}
				
				responseHeaders.set("Content-Type", mimeType);
				
				exchange.sendResponseHeaders(200, targetFile.length());
				
				FileInputStream fileIn = new FileInputStream(targetFile);
				OutputStream out = exchange.getResponseBody();
				
				while ((len = fileIn.read(buf,0,bufLen)) != -1) {
					out.write(buf, 0, len);
				}
				
				out.close();
				fileIn.close();
			} else {
				// If it doesn't exist, send error
				String message = "404 Not Found " + exchange.getRequestURI();
				exchange.sendResponseHeaders(404, 0);
				OutputStream out = exchange.getResponseBody();
	            out.write(message.getBytes());
	            out.close();
			}
		}
	}
}

It’s very basic, but it has default index, 404 errors and MIME type autodetection.

So, once you’ve setup your Octopress blog, where do you host it? I decided to go for CloudFront/S3; again, there were some flaws, so here’s my experience!

I found this nice article about setting up Octopress to use CloudFront; it was quite straightforward, but I needed to call the “s3cmd” script with Python, and use “public/" instead of “public/*":

desc "Deploy website via s3cmd with CloudFront cache invalidation"
task :s3 do
  puts "## Deploying website via s3cmd"
  ok_failed system("python c:\\s3cmd\\s3cmd sync --acl-public --reduced-redundancy --cf-invalidate public/* s3://#{s3_bucket}/")
end

While this appeared to work properly, in reality I had some problems with the CloudFront invalidation, as some files weren’t invalidated properly; I found out that s3cmd is trying to invalidate the “index.html” files, but since it’s using the S3 static website with CloudFront Custom Origin, in reality it should invalidate the path, not the file; for instance, if we uploaded the file “test/index.html”, we need to invalidate “test/".

So, I forked s3cmd and modified it so it will get the default index file in S3, and modify the CloudFront invalidation query appropiately; I already sent a request to s3cmd’s author to include my modifications, which can be found in my github fork.

In conclusion, it was more difficult than I expected, but now that it’s set up, it should work smoothly; while S3 is nice, CloudFront should be faster for most visitors!

When I had to decide what blog publisher to use, I decided to go for Octopress, as it generates static files, making the blog faster and safer; however, installing it on Windows was not as straightforward as it could be, so this post details what I had to do.

In the Initial setup section of the Octopress documentation, the first thing they ask you to do is to install Ruby; unfortunately, both RVM and rbenv don’t seem to work on Windows. So, after searching around I found a very easy installer, which can be downloaded here.

I downloaded both “Ruby 1.9.2-p290” and “DevKit-tdm-32-4.5.2-20111229-1559-sfx.exe”; the second is required by Octopress, as Octopress installation will throw a “Error installing RedCloth” message if trying to install without the DevKit.

The Ruby installer is very straightforward to install; I recommend toggling the option to put Ruby in the PATH automatically; the DevKit file is trickier, but just follow the instructions.

The rest of steps are unchanged, so follow them and you’ll have it running in no time.

Now, my initial impressions about it.

• It’s easy to create new posts, but I need to get used to the syntax; it uses a language called Markdown.
• Be careful with Unicode characters it may give encoding errors; use HTML entities when possible.
• I really like the theme; it’s very elegant and comfortable to read.

So, here we go!

I’ve been planning to start a development blog for a while, but I always had excuses not to; that ends today!

The main purpose of this blog is to give back; I can’t count the times when I searched the solution for coding-related problems, and found helpful blog articles I could benefit from; so, now I want to do the same, share the things I learn for anybody who needs them.