3
\$\begingroup\$

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:

enter image description here

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.

enter image description here

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,
  }
}
\$\endgroup\$
  • \$\begingroup\$ Can you show us your code for detecting these collisions? \$\endgroup\$ – DMGregory Mar 16 at 13:30
  • \$\begingroup\$ @DMGregory Edited the question. \$\endgroup\$ – Lazar Ljubenović Mar 16 at 13:38
  • \$\begingroup\$ Hey, I'm learning collision detection myself, could you post the rest of the code in? Thanks \$\endgroup\$ – Aurimas Mar 16 at 17:27
1
\$\begingroup\$

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:

enter image description here

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:

enter image description here

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

enter image description here

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

enter image description here

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,.

\$\endgroup\$
  • \$\begingroup\$ But 0.999999999... does == 1, mathematically. Did you mean that the greatest 32-bit floating point number less than 1, 0.99999994 != 1? If so, I recommend using the actual value there, rather than the ellipsis to indicate an infinite continuation of 9s. \$\endgroup\$ – DMGregory Mar 17 at 12:40
  • \$\begingroup\$ Mathematically, yes it does, but in the code you can fix that with a if-statement. \$\endgroup\$ – Lord Wolfenstein Mar 17 at 12:58
  • \$\begingroup\$ And here is the kicker. If you reach to many decimals of 0.99999999999999999... that it equals to 1 for the computer then it will only hit the lower block in my image. \$\endgroup\$ – Lord Wolfenstein Mar 17 at 13:04
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Are the videos available online? I find it weird experience that it seems like the ball bounces off a brick but doesn't destroy anything. \$\endgroup\$ – Lazar Ljubenović Mar 16 at 17:31
  • \$\begingroup\$ Can't find it no longer, anyway, the other option is to destroy all the bricks, which would mean up to 3 at the time \$\endgroup\$ – Aurimas Mar 16 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.