Monday, February 13, 2012

Troubling Bridges

A long time ago, my father taught me a simple drawing game over which I would obsess for quite a while. It went like this: you first draw a certain shape (preferably with an ink pen), and you then try to cross through all the line segments at once, with a single stroke (i.e. without raising what is preferably a pencil) and without visiting a given segment twice.

I tried to recreate the spirit of this game (in memory of my father perhaps) as an experiment to learn the Processing.js platform. To test the game mechanics, you can try an easy puzzle first (click anywhere on the grid to place the cursor, and drag any of its ends through the segments, with the goal of turning them all green; you can press "r" to reset, "b" or right-click to move back, or use the yellow and blue buttons at the top):

This was of course trivially easy.. but what about this slight modification, for which I once filled entire notebooks of trials? (I'm not kidding!):

You can try it for yourself:

A few attempts will probably convince you that it's much harder.. but can you see why? In a next post, I'd like to say more about it. I also plan to describe the code and algorithms I have devised, as I greatly enjoyed my first contact with Processing, and I have many good things to say about it. I'm also thinking that this simple pixel grid world engine could be reused to build some other childhood-inspired games..

Don't miss the following conclusion!

4 comments:

  1. Cool, well made application. Indeed, the first one is trivial, the second one much harder (I haven't solved it (only 3 or 5 attempts!)).

    ReplyDelete
    Replies
    1. Thanks for the comment! In fact, I would advise against trying too hard to solve the puzzle.. for reasons that I'll explain soon, in a next post.

      Delete
  2. Could you post an answer to the "trivially easy" one? It seems impossible to me.

    ReplyDelete
    Replies
    1. I know it's not particularly easy to read, but a solution to this one (there are many) is actually the path found by following the red dashed arrows (starting at the top node) in the second graph of my latest post (http://cjauvin.blogspot.com/2012/02/eulerian-hoax.html).

      Delete