If you're working in the 2D canvas context, and you'd like to fill your canvas with objects on both
y axes, you might not need to reach for nested
for loops! It's possible to get
y coordinates from a single, one-dimensional array.
This is a little math-y, and not as easy as just using nested loops, but it (might? could? possibly?) lead to performance benefits, depending on your use case.
Whereas nested loops can lead to exponential complexity (
O(n^i)and therefore, possibly, degraded performance), a single
for loop (or multiple loops side-by-side) scales in a linear way (
i * O(n), if I'm not mistaken), which can lead to better performance. More on Big O notation at ye olde Wikipedia.
That said, browsers are pretty heckin' fast at drawing to the canvas, so if your canvas program is performing well with nested loops, no reason to change. Also if you're using the GPU to draw to canvas, this is almost certainly unnecessary.
I just liked the challenge.
Anywhey, here's how to do it.
Say you have an array that represents ten blocks in your drawing. You know you want the drawing to be five blocks wide (that is, you want it to have five columns of blocks), and each block will be 5 pixels wide. You can use the following formula to derive each individual item's
// i = the index of the block whose coordinates you'd like to calculate // columns = the total width of your drawing, divided by its pixel scale // scale = the width of one of your drawing's blocks in canvas pixels x = Math.floor(i % columns) * scale y = Math.floor(i / columns) * scale
Doing the math manually bears this out. Our original array looks like this:
var arr = [a, b, c, d, e, f, g, h, i, j]
If our scale is 5 and our number of columns is 5 (which means the total area of the canvas is 250px, or
(columns * scale) * (rows * scale)), let's get the X and Y position on the canvas of item 7 in the array (which has a value of
var i = 7, columns = 5 // In our imaginary coordinate system based on the width of our blocks, X = 2: var x = Math.floor(i % columns) // 2 // Now we can convert that to our real, pixel-based coordinate system // that exists in the canvas x = x * scale // 10
var y = Math.floor(i / columns) // 1 // ...and our actual canvas pixels: y = y * scale // 5
So if we were to split our array onto two lines, item 7 would be at position
2, 1, which means in our actual pixel-based canvas coordinates, the item's position is
It helps to imagine the array broken onto multiple lines, like a matrix:
a b c d e f g h i j
There you can see that item 7 is
2 items over,
1 item down (remember to start at 0, though).
What about going the other way around? What if you have X and Y coordinates (in real pixels), but you want to know what block exists at that position (for instance, to react to user input)?
We just reverse the formula. Y is the easiest one to reverse, so let's start there. First, let's take our Y coordinate and convert it back to the imaginary coordinate system:
// The user clicked at position 13, 8. Here's what we know var x = 13, y = 8, columns = 5, scale = 5, i // i = undefined // First we should convert our pixel coordinates back to our drawing's scale x = Math.floor(x / scale) // 2 y = Math.floor(y / scale) // 1 // Now we can solve for Y. If i / columns == y... // i = columns / y i = columns / y // 5 // And we can just add the X value (in our imaginary coordinates) // to our Y value to get the real `i`: i = i + x // 7 arr[i] // h! Just what we expected.
If you can get away with only doing that calculation once, you might see a nice performance bump, compared to nested arrays!
I used this technique on a couple of demos, most recently on a Conway's Game of Life demo. Click and drag around---no loss in framerate, even on my iPhone 6 Plus!
So, there you have it. It's definitely easier to reach for nested arrays when you need to work in two dimensions, and it might not hurt your app's performance in the slightest. The only way to know for sure is to test. But with a little algebra, you can keep your arrays one-dimensional and possibly save some cycles!