The lexicographical (or row-major) order of a map

By on

Storing a tile-based map in a JavaScript array efficiently

Take this 2-dimensional tile-based map:

Tile-based map

As you can see according to these (x,y) coördinates

  • (0,0) = grass
  • (0,1) = water
  • (0,2) = grass
  • ...

Storing this map in memory can happen in two ways, for example you can store every Y-position in an X-row, like this:

map[X][Y] = tile;


  • map[0][0] = grass
  • map[0][1] = water
  • map[0][2] = grass
  • ...

But there's a little problem in Javascript to look this up. For example, if you want to look up a certain value you would do something like this:

if (map[0][1] !== undefined){
    tile = map[0][1];

But what if the X isn't defined, and you're directly searching for a Y value in it? It would throw an error in this case. So you actually have to do:

if (map[0] !== undefined){
    if (map[0][1] !== undefined){
        tile = map[0][1];

So 2 lookups for 1 coördinate.

A better way to do it would be to store it lexicographically.

Basically, you calculate the ID of the tile, what total number it is on the map, following this formula:

lexicograph = y * width + x

And that gives you this order:

Lexicographically ordered array



Woah! I'm really loving the template/theme of this site. It's simple, yet effective. A lot of times it's tough to get that "perfect balance" between superb usability and visual appeal. I must say you've done a amazing job with this. In addition, the blog loads very quick for me on Opera. Superb Blog!

Jelle De Loecker