A small milestone

The millionth penstroke on Mandalagaba since the code rewrite last February

There’s more data I’d like to pull out of this. For example the average length of a stroke, average time, how many human lives where spent drawing mandalas, et cetera :).

An HTML5 canvas Flood Fill that doesn’t kill the browser

I took the longest time implementing the fill tool  on Mandalagaba. How hard could it be? Recurse through pixels looking for a color and update them to a new color.

While this method certainly works and is easy to implement, it is also extremely slow. Slow in a way that hangs the browser, yielding infamous messages from the browser.

Here we’ll take a look at various Javascript flood fill implementations along with their drawbacks. Jump to #4 if you are only interested in the best one.

In all cases, the code is available in the example iframe, look for the function flood_fill.

1. Simple Recursive

Not much to explain here, we simply recursively call the function on adjacent pixels when they match the color we are trying to fill over.

Click to change color / pop-out link

It’s reasonably fast but the problem with this one is that any fill area slightly large yields too much recursion which breaks subsequent JS. This Canvas box is 200x200px and at 300x300px, Firefox complained about:It’s easy to see how this implementation will not satisfy a reasonably featured paint program. Even if your browser let you stack more function on the heap, I would bet it would lead to slowness.

2. Iterative

We simply take the previous idea of looking at adjacent pixels and filling them, and make it iterative instead so the function calls don’t get stacked to a ceiling.

Click to change color / pop-out link

The problem with this is is that is is sloooow. So slow it stalls browser. Most of time is spent having to keep track of pixels_stack. Recursion doesn’t have that need but as we’ve seen, it has other issues.

3. Recursive-Iterative (AKA catch-your-breath iterative)

This is a twist on #2 which every so often, recurses on itself via a setTimeout to let the browser catch it breath a little. It also yields a cool visual effect.

Click to change color / pop-out link

I really like the visual effect, and it makes the slowness tolerable. But the issue is that Mandalagaba has a network engine and allows for re-rendering of one’s work. So synchronization is a big deal, and you know what makes synchronization easy? Not having to worry about it.

So as long as I can help it, my life is a lot easier if the operations the users can perform are atomic. Operations need to be able to be processed one after the other counting on the fact that the ones that came before have completed.

The first 2 solutions are atomic but suck; this 3rd one, however cool it may be, isn’t.

4. The Holy Grail

I’m not sure where this algorithm originated from, but I’ve gotten to know it on this web page which explains it very well (with GIFs!). It is iterative and goes about finding pixels to fill in a much smarter way.

Click to change color / pop-out link

That’s it, no drawback here 🙂 I’ve tested it on large canvasses and this is what is implemented on Mandalagaba. Now of course, in a real application there is a ton more complexity dealing with smoothing edges and blending alpha. I only wanted to expose boiled down versions of these algorithms so they are easier to wrap your mind around.

Feel free to ask questions in the comments.

Nosy Monster alive and well

The Nosy Monster has been sitting on my desk idle for a while now, I’ve always wanted to work on it a bit and make it more reactive to web input. Finally, I bit the bullet and it’s now a lot smoother to operate. Instead of clicking for pre-timed commands, the start of a key press actuates and the end stops. With a websocket communication layer and a socket python command server, the commands find their way from keyboard to motors super fast.

To account for wireless imperfections and AP hopping, I also wrote the logic such that there isn’t a “start” and a “stop” command. Instead there is only a “start” command which gets sent every 200ms and if it isn’t heard every 300ms, Nosy Monster stops. This ensures it won’t be locked in a state of actuation which could lead to perilous situations.

I intend on polishing the code & publish a tutorial that hopefully a 7 year old could handle.

The Nosy Monster was deployed at the Dartmouth Thayer School of Engineering’s open house. I didn’t know how robust it was going to be under sustained kid use.

It turned out to be a huge hit, I let the kids drive it around a bit and then I’d throw the Nosy Monster in another room where they would have to find their way around with no visibility other than the camera. It performed flawlessly through the evening.

It’s always an enormous point of satisfaction to see kids get into something you made. Once I sent the RC car “to Mars” (the other room), the kids were really focused.  All but one got stuck and never came home. I should have had a prize for the one, but what’s next, participation trophies?

With a much more usable and reliable toy, I decided to setup the same kind of maze in a house room under construction.

I moved the camera up on a stick for a better angle of vision, the next model will have a fisheye camera.

Without a reverse, it takes a few tries to get through the maze without getting stuck. He had to learn to be careful.

I’m bubbling up with ideas  of cool things to do with the concept and acquired techniques. From a solar powered exterior land rover, to battle bots.