2D collisions between 2 arrays

Question

I'm trying to do collision detection between bullets and enemies in my game. But it's very unpredictable and sometimes it works, sometimes it doesn't (bullet goes straight through without doing anything) and sometimes it kills the script returning "Uncaught TypeError: Cannot read property 'x' of undefined".

The collision detection is just a trivial for loop like this:

if (enemies.length > 0 && bullets.length > 0) {
    for (a = 0; a < bullets.length; a++) {
        for (b = 0; b < bullets.length; b++) {
            if (bullets[a].x + 36 >= enemies[b].x && bullets[a].x <= enemies[b].x + 56 && bullets[a].y >= enemies[b].y && bullets[a].y + 6 <= enemies[b].y + 69) {
                bullets[a].Delete();
                enemies[b].Delete();
            }
        }
    }
}

The .Delete() function is just a reference to arr.splice(index, 1) in the objects. Of course I didn't expect this to be perfect, but I'm surprised by the random behaviour of it. What could cause this and how can I improve the collision detection?

Answer 1

If I understand correctly, you have a bullet "object" of size 36x6 colliding with an enemy of size 56x69.

Let's take a look at each step of the collision:

bullets[a].x + 36 >= enemies[b].x

This will test if the bullet right side is to the right of the enemy's left side. Right after, you have this:

bullets[a].x <= enemy[b].x + 56

Here, you test that the left side of the bullet is to the left of the right side of the player. So far, the bullet must be fully contained horizontally.

Next, vertical collisions:

bullets[a].y >= enemies[b].y

This tests that the upper bound of the bullet is below or equal to the upper bound of the enemy. And then , you have:

bullets[a].y + 6 <= enemies[b].y + 69

Which does the same for the lower bound.

From what I can read, the bullet must be totally contained within the enemy for the collision to occur. So you will sometimes see the bullet "touch" the enemy, but not being totally inside, and the collision will not occur.

Worst than that, if on one update tick the bullet is off on the left, and on the other is off on the right, the bullet will have passed through the enemy without killing it.

Little ASCII arts to illustrate:

The bullet starts by being off on the left side:

  --------- // Tick 1 - Does not trigger collision
  |       |
-----     |
  |       |
  ---------

Then you increment the bullet's position:

  --------- // Tick 2 - Does not trigger collision
  |       |
  |     -----
  |       |
  ---------

The bullet will never have triggered the collision. But this, on the other hand, will:

  --------- // This triggers collision
  |       |
  | ----- |
  |       |
  ---------

If you want to have better collision management that does not require the bullet to be fully contained, but only to touch the enemy, have a look at AABB collisions:

• http://en.wikipedia.org/wiki/Axis-aligned_bounding_box#Axis-aligned_minimum_bounding_box
• https://stackoverflow.com/questions/22512319/what-is-aabb-collision-detection

For the crash side of things, Evan already found the problem, so refer to it's answer.

Answer 2

At first glance, I would say you're going to have a problem with splicing during the loop. Say you're at index 1 and you have a collision. You then remove that spot, and now everything moves up a space. But your loop counter still increments. So what used to be in the second index is in the first one, and you went from the first to the second, skipping it entirely. This explains why some collisions are never checked, and it would mean that if it happens in the last spot, you would go out of bounds.

Answer 3

You problem is in speed of checking for collisions.
there are two possible solutions:

1. Check several (n) times each frame (=move 1/n speed n times)
2. Instead of point-rectangle intersection perform line segment - rectangle intersection

the first solution is fast and easily implemented, on the other hand it doesnt really solve anything, if your bullets are too fast, they will still miss.
At cost of more difficult to implement collision detection(and some performance) you can get perfect results even for rectangles with lim size -> 0.
At the end the decision is up to you.