Project: Nonograms

What is a nonogram?

A nonogram is a logic puzzle taking the form of a grid for which each cell has to be either filled of left blank, depending on numbers describing the grid's contents. For each row and each column, there is an ordered list of numbers corresponding to the number of consecutive filled cells. For instance, consider the following (solved) nonogram:

The numbers of the second row, 2 and 1, mean that there are two consecutive filled cells, followed by a single filled cell. The number of the first column, 3, means that are three consecutive filled cells in that column. There can be blanks cells before the first number and after the last number, and there is always at least one blank cell between two numbers.

This puzzle was made popular in the 1990s by a video game involving a mustached Italian plumber on a portable console.

For more information, you can consult the Wikipedia page about nonograms which includes, among other things, solving techniques.

The project itself

This project is an individual one. You are encouraged to start working on it as soon as possible. You will have to make a short presentation by the end of the semester. It is divided in three parts:

1. Loading the nonogram from a BMP file – 2 points;
2. Computing and displaying the numbers – 1 point;
3. Implementing the actual game – 7 points.

Your will be in competition with the others on the 3^rd part of the project, for which you will be provided with a minimal set of expectations and a lot of freedom.

You are free to use and extend the code provided with the project or to start from scratch. You are encouraged to comment your JavaScript code, for both the reviewers' comprehension and your own (you can sometimes forget very quickly about your own code).

You can ask all your questions about the project (and about your code) during the lab sessions.

Part 1 – Loading the nonogram from a BMP file

The BMP file format

The BMP file format is a lossless picture encoding format. Because of a simplistic compression algorithm (not even available for pictures with a large number of colours), the resulting files are typically very large and not suitable for use on the Internet. However, since the nonograms are small in size and only need a two-colours palette, and since the encoding is very straightforward in that case, you will use BMP files to import the data in the project.

A complete description of the BMP file format is available on its dedicated Wikipedia page. In order to avoid unnecessary complex code, the data you are provided only contains the image data, as well as the width and height of the image. This means that you will have to decode the following structure:

where one cell stores the colour of one pixel. Note that the rows are stored from bottom to top, which is opposite of the usual convention for screens where the rows are numbered from top to bottom. Since the palette used is composed of only two colours, the information needed to store the colour of one cell is one bit. By convention, all the samples images provided with the project use 0 for the white colour and 1 for the black colour. In order to save space, the BMP standard defines that bits of each row are packed together into bytes. For instance:

Nonogram line:  ███ █████ █  
Bits:          0111011111010000
Byte values:     119     208   

Because the nonogram is only 14 bits wide, we need 2 more bits to fill the second byte. The act of padding consists in filling the blanks with bits set to zero. Remember that we know beforehand the width of the picture, so we know that the padding starts from the 15^th bit and we cannot get confused between the colour 0 of the palette and the value 0 of the padding. Furthermore, BMP requires that the size of each row must be a multiple of 4 bytes (32 bits). This means that we must further expand our padding:

Nonogram line:  ███ █████ █  
Bits:          01110111110100000000000000000000
Byte values:     119     208       0       0   

The complete image data of Example 1 is then (once again, rows are stored from bottom to top):

Nonogram   Bits   (Padding)                        Byte values
   ███     01110000000000000000000000000000    112   0    0    0  
  ██       11000000000000000000000000000000    192   0    0    0  
  ████     11110000000000000000000000000000    240   0    0    0  
  ██  █    11001000000000000000000000000000    200   0    0    0  
   ███     01110000000000000000000000000000    112   0    0    0  

The Byte values represent the contents of the binary file as you will see it in your code. Let's assume that you have the contents in a variable, you can see its contents by using the following snippet of code:

// we assume that the variable binary_contents contains the binary file
var i;
for(i = 0; i < binary_contents.length; ++i)
{
    Document.write(binary_contents.charCodeAt(i));
    if(i < binary_contents.length - 1)
        Document.write(", ");
    else
        Document.write("<br/>");
}

If you use this function on the binary file of the first example, you'll obtain:

112, 0, 0, 0, 192, 0, 0, 0, 240, 0, 0, 0, 200, 0, 0, 0, 112, 0, 0, 0

These are the values that you'll also see if you open the file with an hexadecimal editor.

The Base64 encoding

Because loading an external file from JavaScript is restricted, this HTML file directly contains a few default BMP files in the JavaScript code. And because binary files contain non-printable characters, their contents have been converted to the Base64 encoding. You might not know about this format, but it is the encoding used for all attachments in your emails, for instance. It allows to send binary content using only printable characters, at the expense of a slightly bigger file. You do not need to understand Base64 in order to accomplish this project. All you have to do is use the window.atob() function in order to convert back from Base64 to a binary format. The previous code snippet can now be completed:

var base64_contents = "cAAAAMAAAADwAAAAyAAAAHAAAAA=";
var binary_contents = window.atob(base64_contents);

var i;
for(i = 0; i < binary_contents.length; ++i)
{
    Document.write(binary_contents.charCodeAt(i));
    if(i < binary_contents.length - 1)
        Document.write(", ");
    else
        Document.write("<br/>");
}

Your task

You must write the necessary function(s) to decode the raw image data that you are provided with in the project. Each row must be stored in an array, with each cell of the array containing 0 for a white pixel and 1 for a black pixel. The first cell and last cell of the array must respectively represent the left-most and the right-most pixel of the row (i.e. don't put the padding bits). These arrays must be stored in another array that will be returned by the main function. The rows in that other array must be sorted from top to bottom.

You can consult this page for a short list of base64 encoded images, together with the resulting picture. You can test that your code is correct by using the Canvas element (explained in the following part).

Part 2 – Computing and displaying the numbers

HTML, CSS and JavaScript

HTML5, whose standardisation started many years ago, is still a work in progress as of January 2013. However, many features are already available in current web browsers. For instance, you can ask Youtube to switch to HTML5 and have your videos embedded into a <video> element, suppressing the need to use the Flash player. You can also display mathematical formulas by embedding MathML in a web page. There is also a File API which you might want to use later on.

At the beginning, HTML documents would contain both the contents and the presentation style of the web page. Since then, a lot of efforts have been produced to separate these two information. While HTML retains the contents (as a hierarchy of objects), CSS takes charge of describing the presentation style of the web page.

For a striking example of CSS, you can visit the CSS Zen Garden. While the contents of the page remain the same, you can apply hundreds of different CSS themes, each with its unique presentation style. CSS basically works by modifying properties stored in the HTML elements' style attribute.

Your JavaScript code has access to all the HTML elements on the web page. You can add, move or delete HTML elements, as well as read and modify their attributes. You can do it not only at creation time, while the page is being loaded by the web browser, but also happen later on, when processing an event. More on that in Part 3.

The HTML5 Canvas element

The Canvas element is, as its name implies, a surface on the HTML page on which you can draw whatever you want. You can draw shapes, create custom brushes, write text in a fanciful manner and do many other things with it. It is a raster-based drawing device, which means it handles a grid of pixels (unlike vector-based which stores coordinates of geometric objects in a plane). The nonogram of Example 1 is rendered on a canvas.

You can find a lot of online resources about the Canvas element, one of which is from Dive Into HTML5. A very interesting part of that page is the example of the Halma game near the bottom. You can see the code for handling the Canvas element of this page in the canvas_nonogram.js file. What you need to know is that:

• The size of the Canvas element is defined in pixels by its width and height attributes;
• The coordinates system uses the typical screen conventions: the abscissa increases from left to right and the ordinate from top to bottom. This means that for a canvas of width x and height y, the top-left corner has coordinates (0,0) and the bottom-right corner has coordinates (x,y);
• The background colour of the Canvas element (which is used by the clearing functions) is the value of the style property background-color;
• You can draw a black rectangle like this:

  my_canvas.getContext("2d").strokeStyle = "black";
  my_canvas.getContext("2d").fillRect(x, y, w, h);
  

• You can clear a rectangle like this:

  my_canvas.getContext("2d").clearRect(x, y, w, h);
  

• You can write text like this:

  my_canvas.getContext("2d").font = "bold 24px sans-serif";
  my_canvas.getContext("2d").textAlign = "left"
  my_canvas.getContext("2d").textBaseline = "top";
  my_canvas.getContext("2d").fillText("my text", x, y);
  

Your task

You have to compute the numbers describing the number of consecutive black cells for each row and each column, by processing the array that you created in Part 1. You must also display these numbers next to the nonogram. At this stage of the project, it is up to you to reuse and modify the existing code which is provided to you, or start from scratch your own way of handling a Canvas element.

Part 3 – Implementing the actual game

Events in JavaScript

In order to provide an interactive experience on your web page, you have to associate event handlers to some of your HTML elements. For instance, you can react to mouse clicks on the following Canvas (by the way, nonograms aren't necessarily squares):

When you click on the Canvas, the coordinates of the pixel on which you clicked appear in a window. If you open the source of this page, you will see that the Canvas element created is called "example_2_nonogrid". The code associates a JavaScript function to this Canvas' "click" event which is triggered whenever you left click on it with your mouse:

function showPosition(event)
{
    …
}

nono2.GetCanvas().addEventListener("click", showPosition, false);

When you add an event listener, you first precise to which event for function will be listening to. Among the other possible events, you might later be interested in "mousedown", "mouseup", "mousemove". The second argument is the name of the listening function. In order to avoid entering into intricate Javascript concepts, you are only shown the minimal working example. Note that there are no parenthesis after the name of the function. The third argument can be safely kept to false.

The listening function automatically receives an Event object as parameter when it is called. This object contains contextual information that you can use; in this case you compute the position of the mouse relative to the Canvas element:

function showPosition(event)
{
    var rect = this.getBoundingClientRect();
    var xpad = window.getComputedStyle(this,null).getPropertyValue("padding-left").slice(0,-2);
    var ypad = window.getComputedStyle(this,null).getPropertyValue("padding-top").slice(0,-2);

    var x = event.clientX - rect.left - xpad;
    var y = event.clientY - rect.top - ypad;

    alert("x:" + x + " y:" + y);
}

When the function is called, the keyword this represents the element which was clicked, i.e. the Canvas element in that case. The x and y variables contain the coordinates of the Canvas pixel on which you clicked.

This code is more complicated than it should because the Event object's vague specifications led to discrepancies between the web browsers. Firefox is particularly annoying with regards to that issue, so you are given working code in order to focus more on the parts which matter to your project. The Canvas element on this page has a CSS padding, which has to be taken into account when computing the coordinates. You can consult the CSS Box model page if you want more details about padding, borders and margins of HTML elements. The getComputedStyle() function is used to interrogate the browser about the final size in pixels that was given to the padding of the Canvas element.

Your task

The final task of your project is to implement a working nonogram game. The minimum working scenario which is expected of you is the following:

• The HTML page loads and displays the Canvas element;
• The Canvas element contains a grid;
• The Javascript code decodes a BMP file, computes and displays the numbers in the Canvas element;
• The player can click on a cell to fill it;
• The player can click on a cell to blank it;
• The player can click on a cell to flag it as blank;
• Once the player has drawn the nonogram correctly, he receives a congratulations message.

Many aspects of the game are left to your own discretion. The first video game has optional hints, a mode with penalties when you fill the wrong cell, limited time, etc. There are online versions with different features that you can try to reimplement. You can add mechanisms to use any BMP file, restart the game, use the keyboard rather than the mouse, etc. You can of course make the game look beautiful.

Reminder of resources:

• Base64-encoded pictures;
• canvas_nonogram.js (commented code to create and handle a Canvas element).