JavaScript Collision with Tile Map

[pdiddles03]

Given the following code:

  var player = {
    x:0,
    y:0,
    height:16,
    width:16
  }

  var map = [
    [0,0,0,0,0,0],
    [0,0,0,0,0,0],
    [0,0,0,1,0,0],
    [0,0,0,0,0,0],
    [0,0,0,0,0,1],
    [1,1,1,1,1,1]
  ];
  var tiles = [];
  var x = 0;
  var y = 0;
  map.map(function(row, i){
    row.map(function(cell, j){
      switch(cell){
        case 1:
          tiles.push(/*some kind of information to store here*/);
        break;
      }
      x+=16;
    })
    x = 0;
    y+=16;
  })

How would you write the collision detection for this? What information would you store into the tiles array?  How i would normally do it is just loop through the array and determine the tile position and the player position. But if you have a large array that may not be good for performance.  

[pdiddles03]

Hard question?

[mattstyles]

What does the tile array represent? if 0's are spaces and 1's are blocked then surely it's a simple case of:

function updatePosition () {
  // Calculate next position for player
  // e.g.
  var desiredX = player.x + 1
  var desiredY = player.y

  // Query table for cell data
  var cell = map[desiredY, desiredX)

  // Run collision detection code
  if (cell === 1) {
    return
  }

  // If we get here then no collision so move away
  player.x = desiredX
  player.y = desiredY
}

If your tile structure gets more complex then that is still fine, just use table lookup again to get the cell you're want and you'd need to check against something in that structure that denotes it blocks movement, e.g.

// This returns a cell object, used when creating your map
function createCell (isBlocker) {
  return {
    textureID: 10,
    isBlocker: isBlocker
  }
}

// A representative map
var map = [
  createCell(false),
  createCell(true)
]

// Some time later, lets assume player is moving from map[0] to map[1]
function isCollision (index) {
  return map[index].isBlocker
}

// Invoke it
isCollision(1)

// This will return true, so the cell is blocked so do not update player movement

Note here that even though we've changed your cell definition from a number to an object the logic is the same.

7 hours ago, pdiddles03 said:

But if you have a large array that may not be good for performance.

Spot on, this might be a problem and 2d arrays as you've specified in your post are usually worse for lookups than a 1d array with a helper function to convert [x, y] into [index].

However, there is a case that changing your map structure from the 2d one you're currently using is premature optimisation, try it out for your use-case, for example the following array structure with 1e12 total entries (that's a pretty bloody big map) takes less than a ms and half in node (which is v8, so, Chrome perf should be comparable) on my machine (which is beefy, granted, but its a ruddy big map!), 60 fps gives you ~16ms, 1.35ms of that just for a lookup is a lot, but, its a big map and if you can afford it then its no problem, again, test your use-case and find your optimum map size, create automatic perf tests and optimise the structures when it becomes  a problem.

console.time('make')
var map = new Array(1000000).fill(new Array(1000000).fill(0))
console.timeEnd('make')

console.time('lookup')
console.log(map[90000][90000])
console.timeEnd('lookup')

// make: 33.392ms
// 0
// lookup: 1.357ms

Note that my highly unrepresentative set of random numbers (90k x 90k here but I tried a few other combos, ~20 each) found no difference in where you do the lookup, its not like it has to search through all the items in your array to find the one you want when you do a lookup (note that depending on how you change your structure it could make a difference but, largely, just indexing an array doesn't really matter where you index). Note also that there could be a crafty v8 optimisation as all the array entries are identical, I doubt it but its not unfeasible.

Some things you might want to consider if your map gets prohibitively large:

* use a 1d array and a helper to convert [x, y] into [index]. Creating the helper function is remarkably easy, but I'll leave that to you

* consider some sort of space partitioning, a tree of some sort (i.e. look for how octrees or binary space trees work) might help. Might be worth also searching for 'chunking' i.e. subdividing maps into chunks (this is exactly what space partitioning is, but with the prevalence of minecraft you might find some info in google under chunk rather than partitioning).

* if your structures get really complex (they shouldn't) then maybe you'd hold multiple maps, one that just contained 'blocking' or collision data? maybe the lookups will be faster and there shouldn't really be much in the way of memory overhead/waste/redundancy unless you kept the same info in multiple arrays.

Some other things to consider for collision detection:

* your map is currently a static entity when you check against it, what if it also moved? who moves first?

* how to check against a list of entities? again, if they move, who moves first? or maybe they all move simultaneously and you check for collisions against where all these entities want to move to? although in that case who has preference when a collision occurs? what happens when entities collide?

* if your entities or map is moving how would you stop entities from going through each other? i.e. if player moves 3 spaces in one movement just checking the destination isn't going to work, you're going to have to check all intermediate locations too.

[pdiddles03]

Awesome!!! Thank you!!!!