Tuesday, June 26, 2012

Javascript Golfing



 +

  
What is Javascript Golfing?
Well, Javascript golfing is the process of writing the smallest amount of javascript code to do something awesome. It tests your ability to reduce, reuse, and recycle for the purpose of achieving the tiniest footprint possible. Also, it's fun!
Note: All of these games and more can be found here: Games.Zolmeister.com

First attempt, Snake:
My first attempt at golfing was inspired by MXSnake (back when I didn't even know it was called golfing). Here is my version: tinySnake (686 bytes). Kind of large, not too pretty and nothing really special, except my key events which I think are quite unique.

 onkeydown=function(a){  
 q=a.which-38;  
 q%2?n=0:n=q-1;  
 q%2?e=q:e=0  
 }  

I realized that the key presses should be directly tied to the movement variables of the snake, so I used the keyCode itself to set the movement (I think it could be done even more elegantly, but it's a start).

Second attempt, Pong:
My second attempt at golfing was inspired by an article on hacker-news I read about, where someone made tron in 219 bytes(!). Instead of trying to best them though, I made Pong (451 bytes) instead. (Screen is blank until you hit a key, W and A for p1 movement and UP and DOWN for p2 movement) Sadly I don't have the original non-compressed code, but my technique for compression mimicked the tron game.

Third Attempt, Two Towers:


After feeling good about my pong implementation, I decided I wanted to make something new and original. I settled on a game where the player spawns objects to attack an enemy base. Another constraint I wanted to have was to keep it below 1KB (it's 1008 bytes currently), so that it could be compared to the applications at http://js1k.com (definitely check this out, there are some truly amazing apps people created). This time I did not lose the original non-compressed source:

 //chrome auto-generates accessors for objects with ids  
 <body><canvas id=c width=700></canvas>Buy:  
 <script>  
 C=c.getContext('2d')  
 money=time=level=1//multiple assignments in one statement reduces the use of semicolons  
 upgrade=.99  
 R=Math.random;//assign common functions to variables  
 enemies=[{size:50, x:650, speed:-1/1e99}]//use e for large values (1e3=1000) - saved 1 byte  
 friendlies=[{size:50, x:70, speed:0}]//use unique variable names for easy hand-minification  
 C.fillRect(0,0,c.width,c.height);  
 part1="<button onclick='";  
 part2="</button>"  
 doc=document  
 for(i=3;i<10;i++)  
      doc.write(part1+"buy("+i+")'>$"+i*10+part2);  
 //using ~~ instead of parseInt helps a lot  
 doc.write(" Upgrade: "+part1+"upgradeValue=~~(200/upgrade-200)*10+100;money-upgradeValue<0?i:(upgrade-=.05,money-=upgradeValue);this.innerHTML=upgradeValue'>"+upgrade*100+part2);  
 //keep functions to a minimum (the word function is expensive)  
 //the function below gets removed and the whole thing inserted in an onclick event  
 function buy(n){  
      n=n/upgrade*10  
      money-=n*upgrade;  
      money<0?money+=n:friendlies.push({size:~~(Math.pow(n,2)/250)+5,x:100,speed:60/n});  
 }  
 function animation(){  
      if(R()<.03)//AI code (random is your friend)  
           enemies.push({size:~~(R()*level)+7, x:650, speed:-(level-R())})  
   C.clearRect(0,0,700,300);  
   C.fillText("$"+~~money,9,9)  
   //concat both friendlies and enemies for updating the objects (drawing and moving)  
      g=[].concat(enemies,friendlies)  
      for (i in enemies){  
       for (j in friendlies){  
            //during minification, && and || can usually be replaced by & and | respectively  
        if(friendlies[j].x+friendlies[j].size>=enemies[i].x-enemies[i].size && enemies[i].size>0 && friendlies[j].size>0){  
         --friendlies[j].size<0?friendlies[j].size++:i;  
         enemies[i].size==1?money+=enemies[i].size:i;  
         --enemies[i].size<0?enemies[i].size++:i;  
         enemies[i].x-=enemies[i].speed;  
         friendlies[j].x-=friendlies[j].speed;  
         }  
       }}  
      for (i in g){  
                g[i].x+=g[i].speed  
                //I used negative speed values to differenciate between enemies and friendlies  
                C.fillStyle=g[i].speed<0?'#F10':'#10F';  
                C.save()  
                time+=.01  
                C.translate(g[i].x,150-g[i].size)  
                C.rotate(time*(g[i].speed<0?-1:1))  
                C.font=g[i].size+'pt txt';  
                //thanks http://js1k.com/2010-first/demo/750 for the inspiration to use unicode  
                C.fillText(String.fromCharCode(1161),g[i].size/2,g[i].size/2)  
                C.restore()  
           }  
      //inline if statements are better if doing one action  
      //friendlies[0].size==0?history.go():i;  
      //function are special  
      friendlies[0].size==0&&history.go();  
      //regular ifs are more eficient for more than 1 call  
      if(enemies[0].size==0)friendlies=[friendlies[0]],enemies[0].size=50,level++,money+=500;  
       money+=.25;  
       time+=.1  
 }  
 //put the function inside of quotes in the interval call later to save space  
 setInterval(animation,50)  
 </script>  

Finally, here are some tips for golfing:

Look at other peoples code. They come up with interesting tricks like this one (to remap the canvas calls to have shorter names):
 for($ in C=c.getContext('2d'))C[$[0]+$[6]]=C[$];  
-Source: Bouncing Beholder (This game is crazy-good, worth reading through the source)
Check out this tutorial on stackexchange.
Use a tool like jscrush after you hand-minify your code (and check that closure compiler won't help).
Good Luck!

Saturday, April 14, 2012

Zoggle

Welcome to my guide to Zoggle. Zoggle is not affiliated with Boggle.
Zoggle is available...
On my website Zoggle. (Works on iOS - add to home screen)
On Google+.

How to play:
The objective of the game is to score as many points as possible. Points are scored based on the length of the words.
Length : Points
3,4      = 1
5         = 2
6         = 3
7         = 5
8+       = 11

Words are made by connecting letters Horizontally, Vertically, or Diagonally (illustrated below).


Zoggle is a webapp that takes this game to a whole new level by having all players play at the the same time in the same game in real-time. This creates a whole host of tough problems to solve.

Problem #1, Real-Time Gaming Data In The Browser:
This wasn't actually a problem I had because I already had a solution in mind. The key to solving this problem is to use Node.js (with the Express.js web framework) and Websockets (socket.io), hosted on Amazon EC2.
Problem #2, The Board Solving Algorithm:
The computer generates a random board of letters in a 2-dimensional grid. The next step is to figure out all of the words possible for that given grid. For reference I looked at this page. My solution ended up being slower than the python implementation (200ms vs 80ms), but it was still fast enough to be production worthy.
The basic steps to my algorithm:
1. Reduce the size of the dictionary to only contain words possibly made by the grid. This basically consisted of removing all words that contained a letter not on the board. This took my dictionary from 100k, to ~2k.
2. Flood fill the board grid starting at the the first letter of the dictionary words to see if they can be made. Flood fill works by recursively "filling" adjacent grid cells. All this means is that I make sure that for example the 2nd filled grid cell contains the 2nd letter of the dictionary word, otherwise return.
Flood Fill Graphic:


Here is the code for checking to see if a word can fit on the grid:
function fitWord(x, y, cboard, tarWord, cword) {
  if (x >= boardWidth || x < 0 || y >= boardHeight || y < 0)// out of bounds
    return;
  if (cboard[x][y] == "")// visited space
    return;
  if (tarWord.indexOf(cword) == -1)
    return;
  var board = copyTwoDimentionalArray(cboard);
  var let = board[x][y];
  cword += let;
  if (cword == tarWord) {
    wordFit = true;
    return;
  }
  board[x][y] = "";
  fitWord(x + 1, y + 1, board, tarWord, cword);
  fitWord(x + 1, y - 1, board, tarWord, cword);
  fitWord(x - 1, y + 1, board, tarWord, cword);
  fitWord(x - 1, y - 1, board, tarWord, cword);
  fitWord(x, y + 1, board, tarWord, cword);
  fitWord(x, y - 1, board, tarWord, cword);
  fitWord(x + 1, y, board, tarWord, cword);
  fitWord(x - 1, y, board, tarWord, cword);
  return;
}

Problem #3, Cross-Platform CSS:
Since this is a custom webapp, and did not want to re-code (port) the game to iOS and Android, I had to change CSS to accommodate them. There are ways to do this with CSS only, however I found those ways to be inconsistent and unreliable. Instead I opted to detect via JavaScript.
navigator.userAgent.indexOf("Android") != -1
And then add the required CSS
var mobileCss=document.createElement("link");
  mobileCss.setAttribute("rel","stylesheet");
  mobileCss.setAttribute("href","/stylesheets/mobile.css");
  document.body.appendChild(mobileCss);
So far this has worked reliably for me. I did however achieve separate CSS for portrait mode vs landscape mode via CSS.
@media screen and (orientation:portrait)
@media screen and (orientation:landscape)
Problem #4, Touch detection on Android & iPhone:
Turns out that window.onmousemove doesn't work on mobile devices. Instead I had to use window.ontouchmove and re-write my board highlight detection to use elementFromPoint.
document.addEventListener("touchmove",function(e){
  e.preventDefault();
  var j = document.elementFromPoint(e.touches[0].pageX, e.touches[0].pageY);
    currentWord += j.innerText;
    currentWordUsed.push(j);
    j.parentNode.parentNode.setAttribute("class",
        "tileHighlight");
}, false);

Problem #5, CSS3 on Android:
Android, while it claims to support CSS3 in reality does not. It only supports animation of one property at a time. This can be seen at the end of a Zoggle game, where the game will fade out before it gets moved to the side. This is because it would get all choppy otherwise.
Special Notes:
Socket.io Configuration
io.configure('production', function() {
  io.enable('browser client minification'); // send minified client
  io.enable('browser client etag'); // apply etag caching logic based on version
  io.set('connect timeout',2000);//if connection fails, fall back in 2 seconds
  io.enable('browser client gzip'); // gzip the file
  io.set('log level', 1); // reduce logging
  io.set('transports', [ // enable all transports (optional if you want
              // flashsocket)
  'websocket', 'flashsocket', 'htmlfile', 'xhr-polling', 'jsonp-polling' ]);
});
app.js Caching
var cacheTime = 1000 * 60 * 60 * 1 * 1;// 1 hour
  app.use(express.static(__dirname + '/public', {
    maxAge : cacheTime
  }));

Custom 404
myapp/node_modules/express/node_modules/connect/lib/http.js
It specifies what express is doing with the 404 cases:

res.setHeader('Content-Type', 'text/plain');
res.end('Cannot ' + req.method + ' ' + req.url);
I changed this code to something like this:

res.setHeader('Content-Type', 'text/html');
res.render('errors/404', { title: 'Page not found'});