Collision detection in Arkanoid-like game at intersections

Question

I'm creating an Arkanoid-like game from scratch. I have no (formal or informal) education of any kind in game-development, so I kinda made up things as I went regarding collision detection based on personal ideas of "how it probably works".

I approximate the ball as a point and ignore its thickness, which is small anyway. I compensate for this visually by very slightly making all objects smaller than they are.

I don't "detect" collision, but anticipate it and change the outcome of the next frame. For example:

The ball is currently in position A, and it "wants" to go to E (red line). But I calculate all intersections with all segments which make up the bricks: B, C, D. The closest one to starting point (A) is B, so I choose B as the "real" intersection. I destroy the brick this segment belongs to.

Now I check how would the ball proceed if it would start at B, with its vector flipped horizontally (because I determine that the segment it hit was horizontal). This is the blue line. Again, from F and G, I pick F. I destroy the brick this segment belongs to.

Lastly, the orange line doesn't intersect, so I determine that the bottom of the orange line is where I should place the ball in the next frame.

---

This worked fine and I was satisfied with it, until I started nailing the edge case of the ball hitting the T intersection, where it all goes bananas.

What should happen here is that the ball bounces to the left and destroys either of the bricks. But what can happen is that my algorithms decides to choose the middle vertical segment (connecting boxes 1 and 2) as the collision point, either belonging to the 1st or 2nd box.

I thought of ignoring the edges of the segments, but then the ball would pass right through the T-intersection in this scenario, because it would also ignore what it's supposed to hit.

You can see it in action here (around after 00:07 mark): https://www.mp4upload.com/p6966u6kuzad

What are common techniques for handling this case? Even if I introduce the width to the ball, it could still hit the exact T-intersection at the tangent, so the problem would remain.

---

Requested to post code. Here's the main bit. Please note that I'm not expecting you to (or looking for) debugging the application. I'm more asking about how are these things even handled in general.

export function bounceBall(
  ball: Point,
  vx: number,
  vy: number,
  obstacles: Obstacle[],
) {
  const projectedNextPoint = ball.clone().translate(vx, vy)
  const movement = new Segment(ball, projectedNextPoint)

  const touchedObstacles: Obstacle[] = []

  let loop = 10


  let hasCollision = false
  do {
    hasCollision = false

    if (loop-- < 0) {
      throw new Error('oops')
    }

    // If in the previous loop the ball just grazed the surface
    if (movement.isZeroLength()) break

    const collisions: Collision[] = []
    for (const obstacle of obstacles) {
      const collision = getIntersectionOfSegmentAndObstacle_ClosestToStartExcludingStart(movement, obstacle)
      if (collision != null) collisions.push(collision)
    }

    const collision = getClosestCollisionExcludingSelf(movement.start, collisions)

    // We don't count a collision if it's the starting point.
    // If we did, grazing a surface would turn into an infinite loop.
    if (collision == null || Point.AreEqual(collision.point, movement.start)) {
      hasCollision = false
    } else {
      hasCollision = true
      touchedObstacles.push(collision.obstacle)
    }

    if (hasCollision) {
      movement.setStart(collision!.point)
      if (collision!.segment.isVertical()) {
        movement.mirrorVerticallyWrtStart()
        vx = -vx
      }
      if (collision!.segment.isHorizontal()) {
        movement.mirrorHorizontallyWrtStart()
        vy = -vy
      }
    }

  } while (hasCollision)

  return {
    touchedObstacles,
    vx,
    vy,
    newBall: movement.end,
  }
}

Answer 1

Solution 1 is to set your game in a universe of discrete pixels.

Solution 2 is to include the decimals of the right and underneath the blocks in the blocks area.

Let's say this is one block:

It is 6 units wide and 4 units high.

Instead of limiting the collision area to what is inside block make it 6.9999999999999999999... wide and 4.999999999999999999... high like this:

So here is 4 of these block in the way your animation makes it look:

And here is 4 blocks when you include what is "outside" of the block to be inside the blocks collision area:

When your ball hit the area between the blocks it would in this case count are hitting the upper right block.

Because 0.99999999999999999999999999999... != 1 a ball will not hit two blocks at once. And to prevent graphical glitches then you must also make each block one pixel wider and higher for the human eye,.

Answer 2

I'd recommend thinking of your blocks as a regular grid, with a fixed spacing horizontally & vertically. We'll use componentwise division to divide these spacing parameters out of both our starting position & velocity, so from here on in we can pretend our grid has a spacing of 1 unit in each direction to keep the math simple.

Now we can think of this collision detection problem as though we were rasterizing a line to a grid of pixels.

Our travelling ball is a ray that we can raymarch through this space, along the line:

positionAtTimeT = initialPosition + velocity * t

Where initialPosition is the position of our ball at the start of this check, and positionAtTimeT is its position t seconds later, travelling with constant velocity.

We can find the integer coordinates of the current cell we're occupying by flooring the initial position:

int2 cell = (floor(initalPosition.x), floor(initialPosition.y))

Next we're going to see which cell borders we cross as we continue to march across the grid. I'm going to elide checks for a zero velocity along either axis in what follows, but if your ball can move purely horizontally or purely vertically you'll want to ignore the zero'd axis to avoid division-by-zero errors.

The direction we're travelling across the grid horizontally & vertically is the sign of our velocity:

int2 cellIncrement = (sign(velocity.x), sign(velocity.y))

And, after we reach the first border along each axis, we continue striking a new border along that axis regularly, with interval:

float2 crossingInterval = (cellIncrement.x / velocity.x, cellIncrement.y / velocity.y)

So the next (vertical) cell border we'd reach by travelling horizontally is:

int nextBorder = cell.x + cellIncrement.x + (cellIncrement.x < 0 ? 1 : 0)

And we'd reach it at time tX seconds:

float tX = abs(nextBorder - initialPosition.x) * crossingInterval;

We can do the same to find the time to hit a horizontal border by travelling vertically, tY.

Now we take turns, choosing whichever is smaller, tX, tY, or tMax, the duration of our frame.

• If tX is smaller:

  • we add cellIncrement.x to cell.x

  • we check if that cell is occupied. If so, break it, and reflect our ray horizontally:

    positionAtTimeT = initialPosition.x + velocity.x * tX
velocity.x *= -1
initialPosition.x = positionAtTimeT - velocity.x * tX
    

    cell.x -= cellIncrement.x
cellIncrement.x *= -1
    

  • we add crossingInterval.x to tX to get the time of the next crossing.

• if tY is smaller: we do all of the above, but for y instead.

• it tMax is smaller:

  we stop iterating, and position our ball where it's ended up at the end of the frame,

  positionAtTMax = initialPosition + velocity * tMax

We loop this until we reach the tMax exit case (or hit some maximum number of bounces if you want to account for pathological cases)

The advantage of this style is that the crossing of each border segment is well-ordered, and can never result in the ball tunneling into the edge between two blocks when it should have hit their outside faces first.

Even in the case where it hits a corner first (like the example in the question), we get sensible results:

1. tX & tY are equal, let's say we arbitrarily choose tY to process first.

2. We increment our current cell vertically, and check if for the presence of a block.

3. Since the block is empty, (we haven't crossed the vertical line into the next column of blocks to our right yet), we do no breaking / reflection, so we increment tY and carry on.

   (So we don't get an erroneous vertical reflection when hitting two stacked blocks side-on)

4. Now tX is smaller, since they were equal and we just incremented tY.

5. We increment our current cell horizontally, and check for the presence of a block.

6. We find one (the upper of the two stacked blocks), so we break it & reflect off of it to the left (into a cell we already checked above & know is free), then increment tX.

7. We've now correctly bounced past the corner, destroying one of the blocks (the top one).

   If we'd handled tX before tY in the event of equality, we would have destroyed the bottom block, but our trajectory would be the same.

   If you really wanted to, you could add a special case for tX == tY to flip a coin or destroy all adjacent blocks, to ensure there's no bias at exact corner hits.

Answer 3

I watched a few vidoes of Arkanoid and it seems that usually the gaps between bricks is filled with material which when touched doesn't destroy any bricks but instead acts only as material that the ball bounces off.

So in your second picture the ball would bounce with -45 degrees.

You asked not to debug anything, so there it isn't.