Tiled based pathfinding in a 1- or 2-dimensional array

Question

As far as I know all tile based map editors export a JSON object containing one dimensional arrays. While most pathfinding libraries/tutorials are only provided for two dimensional arrays.

Also if for example I would like to do pathfinding in this one dimensional array and this array is huge i'm geussing this would cause performance issues.

So why is it that most tile based map editors output a one dimensional and how should I handle those regarding pathfinding?

example tile editor

Just google pathfinding to find all the two dimensional patfhfinding tutorials

Answer 1

Depending on the orientation by which it is converted to the 1-D array;

function convert(x, y, height, width) {
    return x + y * width;  // rows
    /* return y + x * height; // cols */
}

function reverse(i, height, width) {
    var x, y;
    // rows
    x = i % width
    y = (i - x) / width
    /* // cols
    y = i % height;
    x = (i - y) % height; */
    return [x, y];
}

Now, say we have a 6 wide by 3 high map

         1-D             |                   2-D
 0   1   2   3   4   5   |   x0y0  x1y0  x2y0  x3y0  x4y0  x5y0
 6   7   8   9  10  11   |   x0y1  x1y1  x2y1  x3y1  x4y1  x5y1
12  13  14  15  16  17   |   x0y2  x1y2  x2y2  x3y2  x4y2  x5y2

Pick an index in the 1-D Array, e.g. i = 8, to convert it to it's 2-D co-ordinates we can use reverse

reverse(8, 3, 6); // [2, 1]
//      i, h, w   =  [x, y]

Or say we picked co-ordinates x = 2, y = 1 in our 2-D Array, we can convert it to the index in the 1-D Array with convert

convert(2, 1, 3, 6); // 8
//      x, y, h, w   =  i

Once you can convert between the two systems you can do your path finding as normal. You can name these functions however you like, I wrote them more so you can see how to switch between the two systems.

Depending on how it is made, the y axis may have 0 at the bottom, not the top, or the entire thing could be mirrored across a diagonal (which I called cols in the above functions). It really depends on how it was done, but as long as you are consistent with the conversion and have the correct height and width (read maximum y and maximum x respectively), it should not matter.

Answer 2

One approach might be to retrieve an offset into the 1D array, based on the 2D vector coords of the tile:

int MaxX = 100; // assumes a max row of 100;
int offset = Y * MaxX + X;
tile[offset] = ....

No need to convert, just reference the tile directly in the 1D array. I used this approach for A* in a recent game project, and works for me.