Mike and The Hornet’s Nest – When to Ask for Help

Long ago, when I was still in school, I was studying on my bed (foolproof – I know) and I noticed something funny on my window. Upon further inspection it turned out that a hornet (we call them wasps in South Africa) was building a nest in the putty of the window. Now I’m usually quite friendly to new neighbours, but my bed was right next to the window and this guy looked like he was into some heavy Gangsta Rap.

My new neighour - Waspbert

Can I borrow some brown sugar?

This was pretty serious. I didn’t want to be swarmed by hornets, so I immediately started making a plan to solve the problem. All I needed was a cricket bat, a man-sized shield and a homemade beekeeper suit. I already had the cricket bat and the makeshift shield was optional, but I had no idea how to make the suit. I spent months thinking of different alternatives. I ran into deadends at every turn. The pool net was too wide and I could never drink that much tea. It went on and on, and all the while the hornet’s nest was getting bigger and bigger.

Here is a crap quick overview of my solution:

Some months later, I was walking with my younger brother Brian the Lion and we came across the window. I showed him the nest (which hadn’t grown as much as my mathematical model suggested) and was just about to start telling him about my designs for the Wasp-a-nator 3000 when he said something along the lines of “You should sort that out” and kicked the nest clean off the window.

Now I’m not going to say that kicking the hornet’s nest is a good idea, but in this case the nest was tiny. Once I looked at it, it was clear that it had been abandoned long ago (I’ve been told I snore).  It looked just like this:

Actually it wasn't even this big

Up until that point I hadn’t told anyone about the nest, but after telling Brian, the problem was solved in a matter of seconds. I should have asked him months ago. How did Brian solve it so quickly? Maybe he had done it before. Maybe he just saw it from a different perspective. Maybe he was living out some Slumdog Millionaire scenario. Maybe he’s just crazy that way.

I learnt a valuable lesson that day: Asking for help can make solving a problem infinitely easier. Since that day I have a hundred stories of people helping me solve problems that would have taken forever. My father-in-law fixed my lawnmower in a day after I spend 4 weekends on it. My first SQL database restore took me hours before a friend showed me what to click.

When its just your time that you’re wasting, then go ahead. But as developers, your pride can end up costing your company much, much more. After releasing our latest version of our application, we were flooded with calls about it taking over a minute to respond. The developer who worked on it, let’s call him Bert, spent the next two months trying to find the cause of the bug, day after day proclaiming that “he hadn’t changed anything” and the classic “it works on my machine”.

Eventually, the top execs decided that the bug was costing too much in terms of both money and reputation and they called in the previous developer, Ernie. Ernie had had almost the exact problem when he worked on it and solved the problem in less than 20 minutes.

If Bert had asked Ernie at the beginning, he would have solved the problem literally 4464 times quicker. Aside from the customers lost, Bert’s pride cost the company 4000 times what he should have.

Some things to remember:

Developers are paid to get problems solved. The quicker, the better. It’s not about who comes up with the solution. What would you rather say in your performance appraisal – that you got a problem solved in 20 minutes, or that it took two months to solve but it was your solution at the end of the day? As my friend Jarfish once told me: “A good developer knows when to ask for help”

Even if you have a solution, someone could still make it better. I mean, sure, my Wasp-a-nator solution probably would have worked. Eventually. A different perspective can make all the difference.

Ask the right people. Knowing who to ask or where to find an answer is probably one of the best skills you can have as a developer. Asking the wrong people can do more harm than good. There’s certain people I can think of that would have patented the Wasp-a-nator if I had told them about it.

If there’s no one you know who can solve the problem, post a question on a forum like Stack Overflow or Google Groups.

A wrong solution is still wrong no matter how quick. More importantly, it can be much, much more expensive. If the hornet’s nest had not been so small and abandoned it, kicking it would ensure a swift trip to Painville.

Do you have a story where not asking for help cost you or your company? Let me know. I’d love to hear it.

HTML5 Canvas: Using and Optimizing Context.getImageData

One of the new features in HTML5 is the Canvas element which allows custom drawing and even per pixel manipulation. This is supported through the context.getImageData() and context.putImageData() methods. This enables you to do some really fancy things that you couldn’t do before.

Recently, I use the getImageData() method to read height values from a canvas that I was using as a height map. You can see it in action at www.starputt.com and read about creating the gravity height map in my previous post. I also used it to determine the colour of each pixel in www.butterflylogos.com. In this case, I first drew the source image to a hidden canvas and then read out each pixel when the page loaded, so I could get away with a slow read.

Determining the Slope from a Height Map

In the case of Star Putt however, I had to read much more often. Basically for every object I had to check the height map in 4 spots to determine the slope along the x and y axises.

Unfortunately, the call to getImageData() is extremely slow and varies browser to browser.

To demostrate this, I’ve put together a simple benchmark for reading an 800 x 600 canvas.

I did three different reads:

  • Reading the canvas as one 800 x 600 blog
context.getImageData(0, 0, 800, 600);
  • Reading 800 columns of 1 x 600 pixels
for (var x = 0; x < width; x++) {
   context.getImageData(x, 0, 1, 600);
}
  • Reading 480,000 reads of 1 x 1 pixels
for (var x = 0; x < width; x++) {
  for (var y = 0; y < height; y++) {
    context.getImageData(x, y, 1, 1);
  }
}

Here are the results:

Test 1: 1 read of 800x600 pixels

As you can see Chrome and Internet Explorer 9 beat Firefox by a factor of 3. This is sad, as the fox is my favourite browser.

Test 2: 800 reads of 600 pixels

Again, the fox disappoints, taking over a second to do a mere 800 reads. Internet Explorer starts lagging taking around 0.2 milliseconds per read.

Test 3: 800x600 reads of 1 pixel each

It actually took a couple of times to get the stats for Firefox, cause the browser completely froze. The usual “Stop this script” also popped up. IE also ground to a halt.

So in summary, you need to call getImageData as infrequently as possible. What I did for Star Putt was to read the whole canvas into memory once each game loop. I then would look up the pixel values using the x and y.

You might find the following function useful if you are digging up the values:

function translateTo1DArrayCoords(x, y) {
  return (y * width + x) * 4;
}

The ImageData object that is returned from the getImageData() call has one long array of colors. The above  function will translate the x and y into the one dimensional co-ordinate. The width here should be the width that is returned in ImageData.width. This value can change from browser to browser (see later).  Each color is stored sequentially in the long array as [r][g][b][a], hence the multiplication by 4.

It has also been noted that by Selim Arsever that detaching the ImageData object from the call can make a big difference if you are modifying the pixel values.

Different ImageData Sizes

As I alluded to earlier, the browsers can return different sizes of data. If you pass in integer values when calling getImageData() e.g.

imageData = context.getImageData(10, 10, 300, 200);

… then the result is the same: a block of 300×200 pixels.

But if you pass in floats, e.g.

context.getImageData(10.5, 0, 600, 1)

… then things start getting tricky. IE9 and Firefox both return 600 pixels, but Chrome returns 601.

 

context.getImageData(10.75, 0, 600.5, 1)

… IE9: 600 pixels, FF4: 600 pixels, Chrome: 602 pixels

context.getImageData(10.1, 0, 600.5, 1)

… IE9: 601 pixels, FF4: 600 pixels, Chrome: 601 pixels

This can throw your calculations WAY off if you are storing the width that you are expecting to get back because your array look-ups will be looking at the wrong pixels. So either only use width member of the ImageData object, or round your x and y before calling getImageData()

context.getImageData(Math.round(x), Math.round(y), width, height);

Negative Numbers and Outside Areas

The Canvas spec says that you can call getImageData() with areas that fall outside of the canvas, and the browser should return  black RGB(0,0,0) for those pixels. This works in Chrome and IE9, but Firefox 4 throws this error “An invalid or illegal string was specified” code: “12″ whenever you do this. (Firefox throws this error for a whole bunch of other reasons too, kind of like “Firefox says no”)

// Firefox says "no". *cough*
context.getImageData(-10, 0, 1000, 1)

Creating Star Putt: Building the Gravity Field

Recently, I entered starputt.com in the Dev Unplugged competition at http://contest.beautyoftheweb.com. The game depends on a quick calculation of all the gravitational forces acting on each object. Basically, a simple implementation for a single object would be:

for every other object in scene :

acceleration = acceleration + Calculate gravitational force between the two objects.

end

This becomes problematic with a large number of objects and I was set on having thousands of objects flying around. I especially wanted the tails of the comets to be affected as well. Each tail could have around 50 – 90 particles at a time. Looking up for some solutions on the net, I found out that the n-body problem actually is not easily solvable. Great.

So I came up with the plan of pre-rendering the gravitational field as a height-map and moving that around the plane. It wouldn’t be 100% accurate, but it would be much faster because:

  • The calculation would be done once and cached. This is done before the game starts and remains the same throughout the game.
  • The object only has to do one check instead of n checks.

The actual gravitational computation was done using an ASP.net MVC action that renders the image to disk and returns a FileResult.

        public ActionResult Map(int mass)
        {
            if (mass == 0)
            {
                return new EmptyResult();
            }

            // 1000 = 1 Solar mass
            // Scaling:
            float solarMass = mass / 1000.0f;

            // Create the bitmap.
            string filePath = Server.MapPath(String.Format("/Content/img/Generated/massMap_{0}.png", mass));

            var diameter = (int)Math.Ceiling(Math.Sqrt(GravitionalConstantInSolarMasses * solarMass / 0.01) * PixelsInParsec * 2);

            using (var destinationBitmap = new Bitmap(Math.Min(1000, diameter), Math.Min(1000, diameter)))
            {
               var centerPoint = new PointF(destinationBitmap.Width / 2.0f, destinationBitmap.Height / 2.0f);

                for (int y = 0; y < destinationBitmap.Height; y++)
                {
                    for (int x = 0; x < destinationBitmap.Width; x++)
                    {
                          destinationBitmap.SetPixel(x, y, DetermineHeightBySolarMass(x, y, solarMass, centerPoint));
                    }
                }

                destinationBitmap.Save(filePath);
            }

            return new FilePathResult(filePath, "image/png");
        }

Calling on that would return an image like this:

Gravity Height Map for mass 1000

Gravity Height Map for mass 1000

Next was to overlay them together. This was done with context.drawImage() using a context.globalCompositionMethod = “lighter”. This offloaded all the work to the graphics card as these operations are implemented in hardware in the newer browsers.

So a couple of objects near each other would look something like this:

Many objects close together

The rings occur because I’m encoding a height in the colours from blue to red. So height = 255 would be RGB(0,0,255) and height =256 would be RGB(0,1,0) which is the black ring.

The only thing left to do was determine the direction of the slope. This was done by sample the heights at 1 pixel left (x -1, y) and 1 pixel right  (x+1, y) of the current location. I did the same to get the vertical slope using 1 pixel above and below. (I actually ended up using the points 5 pixels away from the location, because Internet Explorer did a bit more anti-aliasing when drawing the image).

You could probably do a more accurate calculation of the gravity using some collision detection against the height map. I basically just used the direction and some small factor to keep the calculations down.

Here’s the javascript:

function setSlope(sprite) {
    if (sprite.x < 0
            || sprite.y < 0
            || sprite.x > width 
            || sprite.y > height) {
        return;
    }

    var x = Math.round(sprite.x);
    var y = Math.round(sprite.y);

     var cx1 = translateTo1DArrayCoords(x - 5, y);
    var cx2 = translateTo1DArrayCoords(x + 5, y);
    var cy1 = translateTo1DArrayCoords(x, y - 5);
    var cy2 = translateTo1DArrayCoords(x, y + 5);

    directionVector.x = getHeightFromColorArray(colorBlock, cx2) - getHeightFromColorArray(colorBlock, cx1)
    directionVector.y = getHeightFromColorArray(colorBlock, cy2) - getHeightFromColorArray(colorBlock, cy1)
    directionVector.z = 0;

    if (distanceSquared(directionVector) == 0) {
        sprite.aX = 0;
        sprite.aY = 0;
        return;
    }

    // Normalize, but without the intensive sqrt. Not accurate, but fast.
     var d = distanceSquared(directionVector);

    normalized.x = directionVector.x / d;
    normalized.y = directionVector.y / d;

    // Some fudge factors to convert from space measurements to screen.
    var a = Math.min(3, 0.8 + distanceSquared(directionVector) / 10.0);

    sprite.aX = normalized.x * a;
    sprite.aY = normalized.y * a;

}