Fastest algorithm to draw a crossword grid in <canvas>?

Question

I'm rendering a grid of cells, very much like the grid you find in a crossword puzzle, but using four different colors to fill each cell (not only black or white).

The grid size is about 160x120, and I need to render it as fast as possible, as it will be used to display a Cellular automaton animation.

I have tried two different approaches to render the grid:

• Render each cell using something like:

  var w = x + step;
  var h = y + step;
  canvasContext.fillStyle=cell.color;
  canvasContext.fillRect(x+1,y+1,w-1,h-1);
  canvasContext.strokeRect(x,y,w,h);
  

• Render the all of cells without the border, and then render the grid lines using:

  var XSteps = Math.floor(width/step);
  canvasContext.fillStyle = gridColor;
  for (var i = 0, len=XSteps; i<len; i++) {
      canvasContext.fillRect(i*step, 0, 1, height);
  }
  //Similar thing for Y coord
  

Both algorithms perform poorly: it is slower to draw the grid than the cells in both cases. Am I missing something? How can I optimize those algorithms? Is there another way I should try?

Note: the grid moves, as the user can displace it or zoom the view.

The general question will be: what is the fastest algorithm to draw a grid of cells on a element?

Answer 1

The fastest way to do something is to not do it at all.

Draw your unchanging grid once on one canvas, and draw (and clear and redraw) your cellular automata on another canvas layered above (or below) that. Let the browser (in all it's native compiled optimized glory) handle dirtying and redrawing and compositing for you.

Or (better) if you are not going to change your grid size, just create a tiny image and let CSS fill it as the background.

Demo of CSS Background image to Canvas: http://jsfiddle.net/LdmFw/3/

Based on this excellent demo, here's a background image grid created entirely through CSS; with this you could change the size as desired (in whole-pixels increments).

Demo of CSS3 Grid to Canvas: http://jsfiddle.net/LdmFw/5/

If you must draw a grid, the fastest will be to just draw lines:

function drawGrid(ctx,size){
  var w = ctx.canvas.width,
      h = ctx.canvas.height;
  ctx.beginPath();
  for (var x=0;x<=w;x+=size){
    ctx.moveTo(x-0.5,0);      // 0.5 offset so that 1px lines are crisp
    ctx.lineTo(x-0.5,h);
  }
  for (var y=0;y<=h;y+=size){
    ctx.moveTo(0,y-0.5);
    ctx.lineTo(w,y-0.5);
  }
  ctx.stroke();               // Only do this once, not inside the loops
}

Demo of grid drawing: http://jsfiddle.net/QScAk/4/

For m rows and n columns this requires m+n line draws in a single pass. Contrast this with drawing m×n individual rects and you can see that the performance difference can be quite significant.

For example, a 512×512 grid of 8×8 cells would take 4,096 fillRect() calls in the naive case, but only 128 lines need to be stroked in a single stroke() call using the code above.

Answer 2

It's really hard to help without seeing all the code to know where the performance is going, but just off the bat:

• Instead of drawing a background grid using stroke, can you draw it using one call to drawImage? That will be much faster. If its truly static then you can just set a css background-image on the canvas to an image of the grid you want.
• You're using fillRect and strokeRect a lot and these can probably be replaced with several calls to rect() (the path command) and only a single call to fill at the very end. So all the filled cells are rendered at once with a single filling (or stroking or both) command.
• Set the fillStyle/strokeStyle as little as possible (not inside loops if you can avoid it)

Answer 3

You are using fill to draw the lines; it would be faster, I think, to define a path and stroke it:

canvasContext.beginPath();
var XSteps = Math.floor(width / step);
canvasContext.fillStyle = gridColor;
var x = 0;
for (var i = 0, len = XSteps; i < len; i++) {
   canvasContext.moveTo(x, 0);
   canvasContext.lineTo(x, height);
   x += step;
}
// similar for y
canvasContext.stroke();