3
\$\begingroup\$

perhaps the title isn't clear so here is an explanation with a picture to better express my question

Consider the following breakout clone game

enter image description here

where the game is rigged to change the ricochet angle according to some parameters

Suppose the ball was to hit one of these blue bricks, finding the angle at which the ball should ricochet to go toward any point below the bricks using trigonometry should be trivial and easy.

My question however, is if we have the following setup

enter image description here

How would I got about finding the optimal angle to ricochet from the collision point (circled in red) to get to a certain location (green dot for example)

The path should ricochet off of multiple points to get there, obviously, I'm just not sure how to go about it.

Any math guru who can help me out? Thanks!

\$\endgroup\$
  • \$\begingroup\$ This is very similar to the problem of determining the angle to hit a billiard ball to get a certain result, but harder since your 'billiard table' breaks when you hit it and is not convex. All the research I can find is for convex billiard tables. \$\endgroup\$ – Jemmy Dec 19 '13 at 21:40
  • \$\begingroup\$ Why are you trying to figure this out? It's an interesting math question but it's not immediately apparent to me why one would need to calculate this. \$\endgroup\$ – jhocking Dec 19 '13 at 21:45
  • 1
    \$\begingroup\$ What do you mean by optimal? The angle that minimises distance to the target location? \$\endgroup\$ – dsilva.vinicius Dec 19 '13 at 21:47
  • 1
    \$\begingroup\$ The angle that would get my ball to a certain point on the field as fast as possible \$\endgroup\$ – oxysoft Dec 19 '13 at 21:49
  • 2
    \$\begingroup\$ You could do Raytracing. Just send a number of rays in all directions and choose the ray that reaches your target. All rays can be computed in parallel. Modelling this problem mathematically is a very difficult challenge, since the restrictions of the problem change in every bounce. \$\endgroup\$ – dsilva.vinicius Dec 19 '13 at 21:56
4
\$\begingroup\$

Depending on how often you can have a "rigged" bounce, an incremental solution might be possible.

For this example, I'll assume that:

  • Collisions with the playing field boundary are always normal (angle in = angle out)
  • Collisions with blocks can be 100% rigged whenever needed (angle out = arbitrary)

Then each time you collide with a block, check whether you have an unimpeded path to the target point without touching another block (but collisions with the boundaries are permitted). If such a path exists, bounce that way.

A fast way to check this is to mirror your playing field and look for a straight-line path to any of the target point's reflections:

Finding bounces off the boundaries

In the example you've given, there's no such path - even the best option hits the green row.

So, as a fallback, we just aim for a block that gets us a better view and let the simulation proceed. When we hit that block, this code runs again, and hopefully finds a path directly to the target. If not, it gets incrementally closer each time.

This way you don't need to account for the erosion of the playing field in your algorithm, since you're only ever looking one block impact ahead.

There are a lot of metrics you could use to select this fallback target. You could...

  • ...use the mirroring trick above to identify all blocks reachable from both the source point and the target point, and pick a block from the intersection of those two sets. (Guaranteed to reach your target after hitting this block, if the intersection is non-empty)
  • ...select the block visible from the current one that is closest to the target point.
  • ...continue bouncing normally (angle in = angle out) waiting for one that permits a boundary-bounce-only path. (Makes rigged bouncing less obvious, but not guaranteed to succeed)
  • ...always just bounce toward the reflection of the target point that's closest to lying on the normal bounce vector (angle in = angle out), whether it gets you there or not. This applies a mild bias to all block bounces so it's consistent, and should usually prevent the ball from doing something obviously rigged like reversing course. ;)
\$\endgroup\$
1
\$\begingroup\$

You could do Raytracing. Just send a number of rays in all directions and choose the ray that reaches your target. As parameters, you should think of the reasonable number of rays to shoot, the maximum distance that a ray should travel before discarded as not adequate and the addition of some little randomness to the starting angles of the rays, so you can restart if no ray reaches the target location. To get the best numbers you should profile and test your application. It is important to note that all rays can be computed in parallel.

The path of modelling this problem mathematically is harsh, since the restrictions of the problem change depending on the bounces that are imposed to the ray.

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

Just do it backwards.

Assuming you don't care about "realistic bounces" (you said rigged), do the following:

  • Pick # bounces to use. (Here I've used 6 bounces and 7 line segments)
  • pick wall hit order (here i picked BLTRLT(Goal))

Then:

For each wall hit in the hit order:
    pick a random spot on the wall
    find the line segment from current ball pos to that goal pos
    travel along that line segment

If you construct a travel path based on this, you can reach any final destination point.

The game will be really wonky if the bouncing doesn't happen in some logical order, but hey.

enter image description here

\$\endgroup\$

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.