Project: Ecua Cines

EcuaCines.com

Features:

  • Displays up-to-date movie descriptions, trailers, and showtimes for all major movie theaters in Quito, Ecuador
  • Allows users to quickly compare movie times instead of loading each theater's web page
  • Works on mobile devices
  • Loads faster than any of the corresponding movie theaters' websites
  • Has at least one Easter egg

Technologies:

  • Zurb Foundation, jQuery, Font Awesome, and Box2DWeb for the front-end
  • PHP with Simple HTML DOM and MySQL for the back-end, with cron jobs and Google Page Speed optimizations
  • Photoshop for the logo design

Discussion:

The website automatically obtains all movie showtime information from each cinema's official website, and then it has to be able to show these showtimes grouped by movie or by cinema. While this may seem like a trivial task, it turned out to be an interesting algorithmic challenge.

Human Steps:

  1. Open each movie theater's website
  2. Recognize that "Superman: El hombre de acero", " EL HOMBRE DE ACERO", and "Hombre de Acero" all refer to the same movie.
  3. Copy and paste the movie title (pick one of the three variations) and description along with the showtimes for each theater into Ecua Cines's database

Robot Steps:

  1. Open each movie theater's website
  2.  Find a piece of text that represents the movie's title by traversing each website's html tags according to hard-coded directions.
  3. Recognize that "Superman: El hombre de acero", " EL HOMBRE DE ACERO", and "Hombre de Acero" all refer to the same movie.
  4. Traverse cinema website according to hard-coded rules to find the movie summary text. (we only need to do this once for each movie)
  5. Traverse  cinema website according to hard-coded rules to find the movie times. Get each of the times by matching pieces of text with one or two digits followed by a ":" or an "h" and followed by two more digits. Assume a 24-hour time format.
  6. Save the title, description, and showtimes for each movie as obtained in steps 3, 4, and 5 into Ecua Cines's database

How can we teach a robot to ignore the differences between the three strings of characters from step 3, but still differentiate these from other movie titles? This is what I ended up making the program do, and that has worked in practice:

  • Trim whitespace from the start and end of movie titles
  • Remove all accents from letters, e.g. turn all 'á's into 'a's (this accounts for the fact that many people prefer to capitalize "áéíóú" as "AEIOU" instead of "ÁÉÍÓÚ")
  • TURN THE MOVIE TITLES INTO ALL CAPS (this accounts for variations in capitalization)
  • Remove commonplace Spanish words like "EL," "LA," and "Y" (only keep 'important' words)
  • Match each movie title with the title from another theater with the shortest Levenshtein distance to this title, but requiring a maximum threshold to avoid false positives when there actually is no valid match. (this accounts for small misspellings and singular-plural variation e.g. "MONSTERS UNIVERSITY" vs. "MONSTER UNIVERSITY")
  • If the thresholded Levenshtein method finds no matches, match together movie titles that have a 8-or-more-letter common substring (there's a really cool dynamic programming algorithm for efficiently finding the greatest common substring of two strings)
  • If everything else fails, conclude that this movie is unique to this theater

Sprite Sheets

Even assuming a constant bandwidth speed, total image size isn't the only factor that determines how fast a website loads its images. It turns out that for each image that the page needs to load, it makes a request to the web server, so loading ten 42KB images individually will be slower than loading the same ten images put together into one larger, ~420KB image. Here's where sprite sheets come into play: by combining several images snugly into one image file and then cutting/masking the compound image into the original small images on the client side, we manage to make less requests to the server, obtaining a lower server load and allowing for faster download speeds.

Popcorn Spritesheet

I made this sprite sheet today for a project I'm working on (hint: it involves a physics engine).

Tutorial: Curve Bounce in HTML5

In this tutorial we'll program a simulation of a red rubber ball that bounces off of a sine wave in a frictionless, gravity-less environment (a very typical scenario). We'll be using Javascript, the HTML5 Canvas element, and the easeljs library.

This tutorial is different from others I have found in that it internally stores the hitting surface as a mathematical function rather than a collection of lines, and it uses the derivative of the function to calculate the response of each collision.
Curve Bounce

    You'll need:

  • Some programming experience in Javascript or Actionscript
  • High School Physics (vectors, velocity)
  • A web browser that supports HTML5 (If the demo linked below works, you're all set)
  • A text editor such as TextWrangler (Free, Mac), Notepad++ (Free, Windows), or VIM (Free, Mac, Windows, and Linux). VIM has a steeper learning curve than the other two since it's intended for use without mouse input, but learning it can help you edit your code faster.

Step 1: Set up

You'll find four starter files in the above download

  • index.html - contains the 600-by-400 canvas element we'll be drawing on (you can change these dimensions, of course!) and imports the other three files. Open index.html in a modern internet browser (or reload the page if already open) anytime you'd like to test your program
  • normalize.css - a normalization stylesheet that helps make website styles more consistent across browsers
  • style.css - any other css styling goes here. Edit this file to change the canvas's background color
  • main.js - we'll write the main code for our program in this file

For this tutorial, everything's set up so that we'll only need to modify main.js. Inside main.js you'll find the following code:

/*
 * runs when index.html is fully loaded
 */
window.onload=function() {

}

Since our onload function is empty, when you open index.html on your favorite browser, you'll see a website reminiscent of Kazimir Malevich's painting Black Square. Pretty cool, but not exactly what we're looking for.

Step 2: You're on the ball

Let's add a ball to our canvas. Modify main.js so that it looks like this:

// initialize stage and ball globally
var stage, ball;

/*
 * runs when index.html is fully loaded
 */
window.onload=function() {
    //initialize stage object, where "canvas" references the id of our canvas
    stage = new createjs.Stage("canvas");

    // initialize ball object
    ball = new createjs.Shape();
    // select ball color to be red.
    ball.graphics.beginFill("#ff3333");
    // draw circle of radius 5 at position (0, 0) relative to the ball's
    //   coordinates
    ball.graphics.drawCircle(0, 0, 5);
    // set ball object's coordinates
    ball.x = 120;
    ball.y = 50;
    // add our ball to stage so that it actually gets drawn.
    // (this needs to be done only once per object)
    stage.addChild(ball);

    // draw all shapes to canvas
    stage.update();
}

Note that we initialized stage and ball outside of the onload function so that we'll be able to reference them later when we add animation to our program. If you now open index.html, you should see a red ball on a black canvas.

Step 3: Adding motion

It's time to get the ball rolling. Lets add the following declarations at the beginning of the file:

var vx=10, vy=10;

vx will represent the ball's velocity in the x direction (negative: left, positive: right) measured in pixels per frame. vy will be the velocity in the y direction (negative: up, positive: down). We're initializing both to +10.
Now add the following code right before the the onload function's ending curly bracket:

    createjs.Ticker.setFPS(60);
    createjs.Ticker.addEventListener("tick", tick);

This tells the program to call the function tick() (which we'll define momentarily) on every "tick" event, that is, every 1/60th of a second.

Add the following function at the end of the file, after the onload function:

/*
 * called every frame (60 times per second)
 */
function tick() {
    // if ball would be out of bounds on the next frame,
    //   make it bounce away from the wall
    if(ball.x+vx<0) {
        vx = Math.abs(vx);     }
    if(ball.x+vx>stage.canvas.width) {
        vx = -1*Math.abs(vx);
    }
    if(ball.y+vy<0) {
         vy = Math.abs(vy);
    }
    if(ball.y+vy>stage.canvas.height) {
        vy = -1*Math.abs(vy);
    }
    // update the ball's position according to the current velocity
    ball.x += vx;
    ball.y += vy;

    // draw all shapes to canvas
    stage.update();
}

and now the ball bounces off the walls.

Step 4: Drawing the curve

As promised, we will make the ball bounce off of a fancy, mathematically defined curve. First, however, we'll need to define our mathematical curve and draw it on the canvas. Add the following function after the tick() function, that is, at the very bottom of main.js:

/*
 * defines the the shape of curve the ball will be bouncing off of.
 * Try playing around with the values inside this function!
 */
function f(x) {
    return 100*Math.sin((2*x)*3.14/180)+300;
}

This is a function in the sense you learned in math class: we give it an input number, and it gives us an output number. In this case, it gives us the sine curve you've seen in the end result. Note that the origin (0, 0) of our canvas is the upper-left corner, and that the y-axis increases as we go down the canvas. The x-axis works as usual.

Now, to actually draw the curve to the canvas, we'll approximate it as a series of line segments. Edit the onload function so that it looks as follows (where we've highlighted the new code):

// initialize stage and ball globally
var stage, ball;
// set ball velocity
var vx=10, vy=10;

/*
 * runs when index.html is fully loaded
 */
window.onload=function() {
    //initialize stage object, where "canvas" references the id of our canvas
    stage = new createjs.Stage("canvas");

    // initialize ball object
    ball = new createjs.Shape();
    // select ball color to be light blue.
    ball.graphics.beginFill("#3399CC");
    // draw circle of radius 5 at position (0, 0) relative to the ball's
    //   coordinates
    ball.graphics.drawCircle(0, 0, 5);
    // set ball object's coordinates
    ball.x = 120;
    ball.y = 50;
    // add our ball to stage so that it actually gets drawn.
    // (this needs to be done only once per object)
    stage.addChild(ball);

    // initialize curve object
    curve = new createjs.Shape();
    // set line width to 2px
    curve.graphics.setStrokeStyle(2);
    // select a random color for the line
    curve.graphics.beginStroke(createjs.Graphics.getRGB(Math.floor(Math.random()*256),
                                  Math.floor(Math.random()*256), Math.floor(Math.random()*256)));
    // start first line segment at position (0, f(0))
    curve.graphics.moveTo(0, f(0));
    // keep on drawing line segments to (i, f(i)) as i moves across the width of the canvas
    for(var i=0; i<stage.canvas.width; i++) {
        curve.graphics.lineTo(i, f(i));
    }
    // add our curve object to stage so that it actually gets drawn.
    stage.addChild(curve);

    // draw all shapes to canvas
    stage.update();

    // set framerate to 60FPS
    createjs.Ticker.setFPS(60);
    // call tick(event) on every "tick"
    createjs.Ticker.addEventListener("tick", tick);
}

Where the Math.floor() function rounds down and Math.random() generates a number in the interval [0, 1), so Math.floor(Math.random()*256) generates a random number between 0 and 255, inclusive.

At this point you'll see the curve on the screen, but the ball ignores it completely(!)

Step 5: Detecting curve crossing

When is the right time to bounce? How do we detect if the ball is about to cross the curve? Since our curve is a function in the mathematical sense, we know that there will only be one 'y' value for the curve for each 'x', and assuming our function will be continuous, we can simply check if the ball will be below the curve on the next frame, i.e. if its 'y' value will be greater than the curve's 'y' value.

Add the following code at the very beginning of the tick() function, right after its first opening curly brace:

    // check if a crossing is about to happen.
    if((ball.y+vy) >= f(ball.x+vx)) {
        // if ball would cross the curve on next frame, log the message "crossed" to console
        console.log("crossed");
    }

At this point a new "crossed" message will be printed to the javascript console every time the ball crosses the curve. (This link explains how to access the javascript console in different browsers). In some browsers, printing to the javascript console makes the program crash if the console isn't open, so comment out the console.log line after you're done testing.

Let's bounce.

Step 6: Bouncing off the curve

Our program now knows where the ball hits the curve, but we'll need more information about the direction the curve faces at the collision point to know how the ball will bounce.

Right after the end of the f(x) function, define the following function:

/*
 * returns the derivative of f(x) evaluated at x
 */
function dfdx(x) {
    return (f(x+0.00001)-f(x))/0.00001;
}

If you've taken Calculus, you'll recognize that dfdx(x) is an approximation to the derivative of the curve f(x) we drew earlier. If you haven't taken Calculus, all you need to know is that dfdx(x) measures the slope of the curve f(x) at point x.

When dealing with the four walls, we simply had to change the sign of one of the components of the velocity to make the ball bounce. How do we bounce at an angle?

Once we've defined dfdx(x), we can make the ball bounce by adding the following code right after the commented-out console.log command:

        var J = dfdx(ball.x);
        var K = 1+J*J;
        var tangentComponent = {x:(vx+vy*J)/K, y:J*(vx+vy*J)/K};
        var normalComponent = {x:J*(vx*J-vy)/K, y:-1*(vx*J-vy)/K};
        vx = tangentComponent.x - normalComponent.x;
        vy = tangentComponent.y - normalComponent.y;

This code separates the velocity vector into two component vectors—one tangent to the curve at the collision point and one normal (perpendicular) to it—and then puts the components back together with the perpendicular component flipped.

Now open index.html. If everything worked well, the ball should now bounce off the curve. Nice!

Conclusion

Here concludes this tutorial. For larger projects, remember to minify your Javascript files before uploading them to make your program load faster. Some Ideas of how to expand this project:  try adding sound, visual effects, gravity, and friction to the scene.