Monday, January 2, 2012

The Wallpaper Algorithm Using HTML5 and JavaScript


There's a fun little book called The New Turing Omnibus - 66 Excursions in Computer Science from 1993. An omnibus is "a volume containing several novels or other items previously published separately". The first item in this book is the following algorithm:

WALLPAPER
1. input corna, cornb
2. input side
3. for i ← 1 to 100
     1. for j ← 1 to 100
       x ← corna + i x side/100
       y ← cornb + j x side/100
       c ← int (x² + y²)
       if c even
         then plot(i, j)

All that is needed to translate this algorithm to a running computer program is to have a Turing-complete programming language and a way to plot pixels on a display. So if you want to try it out for yourself first before seeing one solution, stop reading now and try it. I'm going to demonstrating how I implemented this algorithm by using JavaScript and HTML5's canvas element. The book only shows one implementation using Pascal so I thought I'd do something a little more modern.

We'll be creating two files. The first one will be the html5 content:
<!DOCTYPE HTML>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Wallpaper</title>
</head>

<body>
  <button id="myButton">Show Wallpaper</button>

  <canvas id="myCanvas">
  Your browser does not support the canvas element.
  </canvas>

  <script src="wallpaper-algorithm.js"></script>
</body>

</html>
Next create a file called wallpaper-algorithm.js with:
document.getElementById("myButton").onclick = function () { 
  this.style.display='none';
  wallpaper(); 
}

function wallpaper() {

  var browserWidth = window.innerWidth;
  var browserHeight = window.innerHeight;
  var canvas = document.getElementById("myCanvas");
  var ctx = canvas.getContext("2d");
  var corna = 0;
  var cornb = 0;
  var side = 345;
  var xmul;

  canvas.setAttribute('width', browserWidth);
  canvas.setAttribute('height', browserHeight);
  document.body.style.background = 'black';
  
  for (var i = 1; i <= browserWidth; i++) {
    x = corna + i * side / 100;
    xmul = x * x;

    for (var j = 1; j <= browserHeight; j++) {
      y = cornb + j * side / 100;

      if (i % 2 == 0) {
        ctx.fillStyle = 'white';
      } else if (j % 2 == 0) {
        ctx.fillStyle = 'lime';
      } else {
        ctx.fillStyle = 'purple';
      }

      if (Math.round(xmul + y * y) % 2 == 0) {
          ctx.fillRect(i, j, 1, 1);
      }

    }

  }

}
As an exercise, the book says to write the algorithm using three colors instead of two. That was easy enough so above I had it use four colors (black, white, lime and purple).

The book also says to make corna, cornb and side as user inputs, but for the sake of example, I hard-coded them. The variables corna and cornb represent the lower left-hand corner of the square of interest. The variable side is the length of the square's sides. Try side values of 5, 25, 33, 41, 45, 51 and 325 for some neat patterns.

Feel free to experiment with the algorithm and have fun with it. All-in-all it's a great example of what can be done with a simple algorithm and screen graphics. It's also a great demonstration of HTML5's canvas element coupled with JavaScript.

For exact details on how the algorithm works, buy the book. I think Google Books has a free version online as well.

Followers