JavaScript Challenge #3 (Cows all the way down)

Written By Christopher Pitt, on Wednesday, August 8th 2012, 2:51am

This week we get graphical! Many people are exposed to some form of turtle drawing program when they first learn programming (or just basic computer usage and analytical thinking). It’s also a good way to develop the parts of your brain that deal with forward planning.

The challenge for this week is to design a turtle drawing program that accepts any form of user input in order to move, rotate and style a “pen” across a canvas. It should resemble the functionality demonstrated in the following diagram…

The important things we are looking for are the ability to change direction and then to move forward in a straight line. You can do this with HTML elements (and some interesting CSS) but we encourage the use of SVG or canvas in your solutions as they are more suited to the task.

Hint: you don’t have to have the labels on the left and you can use text fields (or even keyboard navigation) instead of links. What is important is how you maintain and modify direction and position of the “pen” (the point at the “front” of the line).

You can make your solutions as intricate or as basic as you wish!

As before; post your solutions in the form of links to jsfiddle, tinker or jsbin (in the comment section) and we’ll update this post with a link to a review post detailing solutions that we think tackle the problem in ways worthy of mention.

Good luck!

EDIT [2012/08/15]: We are closing comments and reviewing submissions. We will follow this post up with a review of our favourites and what they teach us about the task and JavaScript development in general.

EDIT [2012/08/22]: We have posted the review post to for these submissions.

22 Responses to “JavaScript Challenge #3 (Cows all the way down)”

  1. Wijnand says:

    My basic function. Is this what you guys/girls had in mind?

    Good luck!

  2. Arian says:

    My attempt with Canvas including some animations:

  3. chrisp says:

    Wijnand: yes, that is the kind of thing we are going for! :)

    Arian: your code, dear sir, is beautiful as ever.

  4. Mickele Moriconi says:

    Mine: Move using arrow “up”, change directions with “left” or “right” and colors are the keys.

  5. Kevin says:

    Awesome! I have no experience with canvas so this will be a great exercise.

  6. Pete says:

    • Vanilla JS (sorry kids, no jQuery this time!)
    • OO-style interface
    • Animation
    • Nyan

    I must say, this turned out to be easier (and less code) than I expected. But it was fun! Can’t wait for next week!

  7. Pete says:

    Necessary fork:

    (Had to make just a couple updates to my original code so drawing didn’t take a million years)

  8. Brian Nickel says:

    This is reminiscent of a Turtle program my dad wrote when I was a kid as an introduction to programming. All components are broken into loosely coupled units which report changes via events. The application itself listens to events and renders the result.

    One feature of this design is that the turtle caret is not part of the rendering itself meaning the drawing doesn’t need to be replayed after every step. All changes to the canvas are permanent and performance won’t degrade as the drawing gets bigger. (That said, performance issues probably won’t surface for renderings of this size.)

  9. Pete says:

    Some thoughts on animation performance (and an annoyingly absent feature from Canvas):

    Animation in Canvas is actually pretty tough (as others might be figuring out). Essentially, you have to draw your entire screen many times per second, and if (like us) you’re “constructing” the canvas from historical data, the obvious (and typical) solution is to keep a history of all that data and “replay” it every frame to generate the current view, then add on whatever should have changed.

    So, for instance, in my original code, if you wanted to draw a line 10 pixels long, it would add 10 entries to its “(animation) queue” array, each drawing one pixel of the line. Each frame, the front of the queue would be pushed to the back of the “history” array and the entire history array would be drawn. Obviously, this means that after only short sessions, this history array would grow quite long. I’ve updated the code to allow you to easily view the length of your history (see the “History Length (debug)” button:

    After running the Nyan macro (see the “NYAN!” button), the history length would be about 2000. And each of those 2000 steps must be re-performed up to 60 times per second. This resulted in noticeable performance degradation when running on my iPhone 4S.

    So how to improve this? Well, I had a couple ideas.

    The easiest to implement had to do with trimming the number of entries in the history queue. Arian’s implementation does something similar to this. Essentially, it takes into account that drawing 10 1-pixel lines takes more processing power than drawing 1 10-pixel line, and has the same effect. In Arian’s case, he refrains from pushing “uncompleted animations” to the history queue (or rather, replaces the tail of the queue with each subsequent “animation step”). My solution is similar, but slightly more efficient. I keep track of the type of action (a color change, rotation, or push forward) and if the type of action performed by the tail of my history queue matches the head of my animation queue, it will merge them and combine their values (or, in the case of a color change, replace the value) to produce a single step that will perform both actions. Here’s the result:

    Now the NYAN macro only adds 281 entries to the history queue, which is much better, but still not ideal. The performance of each frame render still clocks in at O(n), so your algorithms professor would tell you that there’s no actual improvement here. And she’d be right.

    So how to improve this more?

    Well, the obvious solution is to retain the complete rendered screen and only perform the differences between the current frame and the next frame. This problem is actually ideal for such a solution because each subsequent frame will contain ALL the contents of the previous frame (assuming you don’t reset the board and can exclude your cursor). Additionally, Canvas offers most of the tools (note the “most”) to carry this out in a simple fashion (see: context.getImageData and context.putImageData). So the frame render algorithm would look something like this:

    Restore the previously recorded frame (if any) Draw new data Record the frame Draw the cursor

    It’s that simple. Except the trick is that in order to save a hundred lines of code or so, my solution to this puzzle made use of Canvas’s built-in transformation utility. And while this makes it very easy to perform all the drawing, there’s no way to export your transform matrix in order to redraw your cursor in the correct position. This means that you still need to retain and re-perform all your historical transforms. And as noted before, this continues to lock us into linear (O(n)) complexity for each frame draw! How frustrating!

    The good news is that the good folks at the W3C seem to have also noticed this issue and the Canvas spec has been updated to include context.currentTransform in order to retrieve (and save) the current transform. But no browsers aside from Mozilla have implemented this feature yet. So it’s very unsafe to use. People have written their own transform classes to “solve” this problem, but that’s still an awkward solution.

    So what other solution might we have? Well, even though it seems like a big hack (and it is), the best solution I’ve come up with is to simply place the cursor on a second (overlapping) canvas element. That way, we can clear and re-draw the cursor without popping the transform, and also draw all new data to the other canvas without actually having to refresh it. This results in huge increase in performance. In fact, it reduces the complexity of each frame draw to a big, fat, constant O(1). I’m working on implementing that, it’s a bit tricky, but in the end, it’s probably the most efficient solution to handle animation without a per-frame overhead that increases with each action.


  10. Brian Nickel says:

    @pete Your final solution is the best approach although you can take it one step further. You can actually have one offscreen canvas for your lines, one for your cat, and then a third visible one that you composite them onto using drawImage.

    Here’s my tweak to your solution:

    I like your context transform approach. It’s very clean.

  11. Pete says:

    I like Brian’s take on my proposed idea. I don’t like having to have 3 canvases, but as Brian notes, the solution is actually much cleaner (because you don’t have to go through the trouble of trying to stack two canvases). That being said, I’d already completed my implementation of the proposed idea and was working on benchmarks by the time I read Brian’s follow-up.

    The benchmarks show exactly what I expected, by removing the O(n) build complexity for each frame, the performance goes WAY up. I added a benchmark utility to each of my previous solutions to clock and demonstrate the advantage.

    Keep in mind that my code puts a 1/60th second delay between each frame draw. Since the Nyan draw takes 2092 frames, there’s a baseline of 35 seconds to complete the Nyan. I performed the benchmarks on my iPhone 4S because it accentuates the performance gains and it’s a common platform you can test with yourself (if you have one). So without further ado, here’s the results (complete with updated code to include benchmark tool):

    Interesting note: On the last version, my iPhone actually out-performs my desktop by about a second. Also, remember that these numbers INCLUDE the 35 seconds of delay. So really we should talk in terms of processing time (time taken in addition to the 35 seconds of delay), and if we look at that, the performance gains are staggering:

    • No optimization: 36 seconds of processing time
    • Reduced history size: 16 seconds of processing time
    • Removal of history queue: 2 seconds of processing time

    So yeah, the performance gains from eliminating the per-frame re-draw are astounding.

  12. Christopher Pitt says:

    Pete: beautiful code and thorough explanation. Good job sir! :)

  13. Rocka84 says:

    Here’s mine, quite simple but with keyboard control, variable move- and turn-speed, line-color and -width. Only tested in FF and no graphics or animations though.

  14. Brian Nickel says:

    Repeat solution using the transform approach:

    In this design, I simplified Turtle into a StatelessTurtle and leveraged the existing Animator to perform the drawing with a somewhat different role. (Loose coupling FTW!)

    I added two more helpers. UnifiedCaller takes an object (in our case a context) as a template and builds a new object with the same method that can call its functions on a variable number of other objects. This allows you to call transforms once and have them apply to both the turtle and the drawing context.

    The other helper, OffscreenRenderer, takes a canvas and lets you generate any number of contexts to composite onto it. Compositing is triggered with the render method.

  15. Brian Nickel says:
  16. Dimcho says:

    Hi, JavaScript enthusiasts :)

    Here is my relatively simple solution:

    • vanilla JavaScript :)
    • code ‘packed’ in an object
    • no reloading canvas
    • additional image with CSS absolute positioning
    • no animation (at least for now)

    Best regards

  17. Pete says:

    Alright, now I’ve gone just a bit too far.

    Maybe. Or at least I’ve been too ambitious for a Friday afternoon.

  18. Pete says:

    Or how’s this for META?!?!

    Okay, I promise. I’m done now. Have a great weekend, all!

  19. kentaromiura says:

    @Pete you basically wrote a printer, now, connect that to a old lpt device through arduino, make a film of it printing the nyan ??? PROFIT!

  20. Brian Nickel says:
  21. corto says:

    here’s what I got : Coffee + jQuery

  22. Peter C says:

    It turns out I wrote a small library to do Logo-style drawing on a canvas a while back. Well, actually I wrote that library to demonstrate injecting local variables into functions, but it draws too. :P

    I don’t really have much experience with canvas, and I wish I had the time to learn enough to do something freaky like Pete, but I don’t, so excuse the primitive-ness. At least it has undo, which is something I didn’t see in any of the other ones.