Sign in to follow this  
mattstyles

2D Map Representation as 1D array

Recommended Posts

Is representing a 2D map using an array of arrays `[][]` really that nasty?

My knee-jerk reaction is that it is pretty nasty and I tend to always represent maps as one-dimensional arrays, however, whilst there are some advantages there are also some disadvantages, mostly around access to the structure as to get an [x, y] location involves knowing the dimensions of the structure i.e.

var size = [2, 2]
var data = [1, 2, 3, 4]

var get = (x, y) => (y + size[0]) + x

This is fine, but any time I want to use the map I need to also know the intended dimensions, which is just another thing to carry and pass around.

So... what things are nasty using nested arrays, my requirements seem to suggest it would be fine:

* I am not converting the map i.e. I am not rotating, shearing or skewing the map in any way

* My map dimensions are known ahead-of-time and never change during the life of the map

* I am generating the data myself, so working with a pre-existing structure/representation is not a concern

Using nested arrays mean I can access via [x, y] trivially and dimensions of the map are easy to ascertain by querying on array.length. So, should I get over my disgust at using `[[],[]]` nested arrays and just get on with using the right tool for the job?

Share this post


Link to post
Share on other sites

I think there are two main issues:

- Maintainability: using multiple indices, as in map [x][y] will be much easier to comprehend if you come back to the program years later to correct or enhance it.

- Performance. There is no doubt that allocating a single large array is faster than allocating hundreds or perhaps thousands of smaller ones, which is what happens in the 2-index case*. Likewise the garbage collector has much more work to do in the latter case but if your arrays remain permanently through your program (do not go out of scope) that is not a consideration.

In drawing the scenes in my forest I do allocate and release a 2D array every time (up to 400 x 400 so it can comprise up to 401 1D arrays). The time taken to redraw the same scene in my program is very variable and think this is probably due to garbage collection. I have been aware from the outset that performance might be improved by redesigning this but it is not my highest priority.

* According to the JavaScript standard because there is no way to say new Array (m, n) to indicate 2D (instead you would get the 1D array [m, n] in this case).

 

Edited by grelf
Numerical error

Share this post


Link to post
Share on other sites

I hadn't considered the recreating of arrays, I will effectively be recreating the array each operation, although I may be able to optimise that if it becomes a problem.

For my current project, like yours, it isn't a top priority, but might be in subsequent ones.

Share this post


Link to post
Share on other sites

Yeh, I think the disgust is warranted :)  Sweep it under the carpet - I prefer Object Oriented for map data structures.

Adding the interface and hiding the 2D array adds value soon enough.  A simple example getCell(x,y) avoids that common gotcha of cells[y][x].  Another example might be something like getCellAbove(x,y) where all the range checking can be neatly concealed.  More elaborate examples might return a Cell object with such relationships prebaked, or allow partitioning or redimensioning of the data set.  And that's the upside, the interface can evolve with the requirements.  Whether the underlying data structure is a 2D array, vs a 1D array, vs a string, vs another structure can be changed or upgraded later based on performance tests (these could even be determined per device).

All this being said I prefer to save myself minutes of coding rather than a ms at runtime, so I favour patterns over performance for the majority of tasks - I understand that's not everyone's preference or appropriate for certain projects.

Share this post


Link to post
Share on other sites

Matt: you prompted me to reexamine my scene drawing code with a view to possibly improving its performance.

It is even more surprising that I get the performance that I do, because the following is the gist of what happens with an array called "about" which is created every time a scene is drawn. Its purpose is to hold information gathered about the ground immediately around the observer (object called "me") out to a distance which is a user-alterable range (up to 400 metres, 1 ground unit per metre).

  var mex = Math.round (me.x), mey = Math.round (me.y);
  // Fractional array indices would not work
 
  var xyLen = 2 * this.range_m + 1; // max 801
  this.around = new Array (xyLen);
  // "this" is the scene object, we are in its draw() method
 
  for (var xScan = mex - this.range_m; xScan <= mex + this.range_m; xScan++)
  {
    this.around [xScan] = new Array (xyLen);
    // ... start filling this.around by scanning both x & y around me
    
My point is that this.around [xScan][yScan] is being indexed by ground coordinates which can be huge. I recently discovered that the width and height of my map are each about 1.8E15 metres (it could not be a planet in our universe). The code fails beyond that range but performance does not fall off before that!

So I get away with it because of JavaScript's very flexible way of indexing arrays (and evidently very efficient in current browser implementations).

If I were instead to allocate (the largest possible version of) the array just once when the scene object is constructed I would have to calculate indices in my own code so that they range from 0 upwards. I expect performance could easily be worse then.

 

Share this post


Link to post
Share on other sites
On 3/13/2019 at 7:05 PM, b10b said:

I prefer Object Oriented for map data structures

Yeah, only issue I have with that is that I only pass data around, not classes, and I'll have to sacrifice quite a lot of good stuff to be able to do it in a different way. 

I kind-of end-up in a similar place though with utility functions, but they generally run to the signature of:

getCell(data, meta, position)

// Could be curried:
getCell(data, meta)(position)

// Data could include meta (height, width etc for example)
getCell(data, position)
getCell(data)(position)

The only difference is that I have to specifically pass in the data and meta for the map, rather than rely on `this` and grab it from the instance.

It's a good point though, and there are multiple advantages for the class-based approach. I _think_ a good half-way house for me would be to expand the `data` object shape to include any meta-data about the map structure (I currently end up passing the raw data array—or array of arrays, whatever—and also supply meta, which is, to be honest, a bit annoying).

On 3/14/2019 at 11:55 AM, grelf said:

My point is that this.around [xScan][yScan] is being indexed by ground coordinates which can be huge.

My current patch code is reliant on being a 2d array, but I could get rid of that with a few more helpers and passing more information in via the `data` variable:

/**
 * Gets a patch of tiles based on an initial [x, y] location
 * @param data <Array<Array[Tile]>> the 2d raw map
 * @param position <Array[Number, Number]> [x, y] position to center on
 * @param dim <Array[Number, Number]> patch size. Defaults to [-1, 1], can be
 * used to alter the center.
 * @returns <Array<Array[PositionTile]>>
 */
export const getPatch = (data, position, dim = [-1, 1]) => {
  const [w, h] = [data[0].length, data.length]
  const [x, y] = position
  const [min, max] = dim

  const patch = []
  for (let i = y + min; i <= y + max; i++) {
    for (let j = x + min; j <= x + max; j++) {
      const tile = getPatchTile(data, [j, i], [w, h])
      if (tile) {
        patch.push({
          ...tile,
          x: j,
          y: i
        })
      }
    }
  }

  return patch
}

So I think it works pretty similar to your method, albeit without classes and instances being involved.

There are a couple of improvements I can see immediately, I'm effectively passing too much to `getPatchTile`, which also does bounds checking, and I don't like imperatively using nested for loops (which litter the codebase) so they could be generalised in to a helper function also.

In any case, I'm happy with scrappy code as this is mostly a POC but it is interesting as it exposes that there are indeed many different ways to skin this cat, and many of those ways aren't clearly better or worse than the other ways. Trade-offs and decisions.

Share this post


Link to post
Share on other sites

@mattstyles thanks for explaining, is this because of stateless / functional reactive?  Interesting, to me it feels almost like turning the same problem inside out ... with data needing to become another function (to abstract away from array directly)?

Share this post


Link to post
Share on other sites

@b10b yep, thats it exactly. I have a central 'store', which is just a big object, technically you could pass class instances (or functions) through as well but I'm not sure the exact downsides of that (easy serialisation is one, but could be worked around easily enough).

Re-rendering is a side effect of changes to that central object and will only occur when changes are detected (standard React rendering, which is the same as many true FP languages).

You could have both systems side-by-side and have a more manual system to 'tell' certain UI elements to that they need to re-render, I've tried that too with varying success.

I think, in my case at least, I could get a lot of benefits from memoizing some transform functions as I'm effectively running the same thing several times each render tick.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.