# Algorithm for calculating a bullet path to a target with max. 2 ricochets

Sorry for the poor title but I didn't have a better way to phrase it...

So there's this amazing game by Nintendo (yes!) on Wii called WiiPlay. There're 9 minigames in it, and my favorite one is called Tanks!. It's about destroying COM enemy tanks without getting yourself destroyed. Here's a screenshot of a level: One way to destroy tanks is by firing bullets. There's this lime green enemy tank which fires high-speed bullets that ricochet (against the walls and blocks) twice. You can see how the player tank can get instantly destroyed if it stays at where it is now, as that lime tank in the center can fire a bullet that follows the green path I drew on the image.

As an amateur programmer myself I have been wondering how can the lime tank determine at which direction it should fire at to smite the player tank.

I thought about it myself but didn't came up with any possible algorithm. I'll explain my conclusions in case they inspire someone. Just for simplicity during my explanation, I assume a wall to be any surface against which a bullet can ricochet. An isolated rectangle of blocks thusly form four walls.

I concluded that the 2 points at which the bullet ricochets always either lie on one side of a parallelogram or become opposite vertices of a parallelogram. The firing enemy tank and the player tank it aims are not necessarily the other 2 vertices but definitely lie on the lines colinear to either of the four sides of the parallelogram. Here is an illustration of the 4 possible ways a parallelogram can be formed: HOR-VER means the bullet first hits a horizontal wall, then it hits a vertical wall.

And then I'm stuck. I thought about moving around a line that connects the enemy tank and the player tank around the map to see if it forms a parallelogram with any two hits with any wall, but this does not always work because the enemy tank and the player tank are not necessarily coincidental with the vertices of the parallelogram.

Also, I'm not sure of the general flow of the algorithm. Does the algorithm take any of the following 2 structures, or maybe I am wrong with both of these?

• Keep figuring out possible paths and always mark one as the best (can be the shortest, the most obscure, the most inescapable, or a combined and weighted assessment based on multiple criteria) and forget about the rest. The one left after all calculation is the best one to take.
• First determine all walls first reachable with the bullet (the bullet needs not ricochet against any other wall in order to reach each of these walls), then determine all reachable ranges on each of these walls (it is sometimes impossible to reach a faraway point on a wall without ricochet if another wall stands near you), then again determine all reachable walls with a ricochet, and all ranges reachable on these walls. These 4 processes can be done by a way similar to ray-tracing. During each process, if the player tank is hit by any ray, figure out the bullet path according to that ray.

In my opinion, this algorithm is hard to figure out because:

• a bullet can be fired in any direction; and
• there are infinitely many points on any wall, as in mathematics, where there are infinitely many points on a line.

But Nintendo people made it anyway, so... anybody with an idea?

• Just to check, you are asking for how this could be done, not how Nintendo chose to actually do it, right? Jul 23 '15 at 18:00
• @lxrec you're right, just interested in a possible way to do it, not the way they did it. Jul 23 '15 at 18:02
• The game doesn't need to find a solution. When you press the button to fire, the game already know your position and direction you are facing then it only uses that information. It will trace the trajectory and if it finds the enemy tank in the path you will hit it otherwise no. Jul 23 '15 at 18:14
• While there are “infinitely” many angles, you can easily reduce them to a few equivalence classes. Nicky Case's Sight and Light is a cool demo of rendering shadows between polygons – which is exactly your problem, except that you are using bullet paths rather than light rays, and that your rays may be reflected two times. Note that the reflection does not matter to the AI – the reflection merely extends the line of sight, though this does mean the same object may be visible from multiple angles.
– amon
Jul 23 '15 at 18:15
• @Mandrill I'm afraid you didn't quite get my question. I was asking how the enemy tank can devise a bullet path that hits the player tank. Jul 23 '15 at 18:22

Given a direct line of sight, the problem is obviously trivial. However, we are dealing with reflection. Properly finding out which parts of the scene can be seen is challenging when implementing reflection as part of a ray tracer, since this might miss some openings. A “binary search” between two promising angles is also not viable: due to the reflections, the actually visible space is not continuous, so the heuristic “if it's to the right of A and to the left of B, there must be a target solution between A and B” is not permissible, and will miss “creative” solutions. I would instead recommend implementing reflection by re-running the tracer from a virtual position – the position where our firing tank seems to be when seen in the mirror:

``````target |obstacle
X   |
\  |  X real position
\   /
\ /
----------- mirror surface
\
\
X virtual position
``````

The advantage is that the mirrored ray is now a straight line originating from the virtual position. I tried to illustrate the technique in the following sketch: X marks the firing position, (X) the target. The coloured areas are visible.

1. Direct line of sight: the target is not visible. However, we can hit surfaces (1) and (2).

2. One reflection. There are two virtual firing positions within the obstacles. The lower position has direct LOS to the target, so we have our first firing solution: the bullet path is the part of the ray between the target and the lower mirror surface, and between the ray–mirror collision point and the real firing position.

3. Two reflections: The upper virtual position from the first reflection can see part of the lower obstacle through its mirror surface. Since two reflections are allowed, we can mirror this position into the lower obstacle. The positions are marked as (I) the real position, (II) the virtual position from the first reflection, and (III) the virtual position from the second reflection.

From (III), we have direct LOS to the target (X), so we have found another firing solution. The bullet path is along the line X–III until the second mirror collision point, then along the line III–II between the mirror collision points, and finally along the line II–I from the first mirror collision point to the real position I.

Actually, the lower virtual position from the first reflection could also be reflected into the upper obstacle, but this will not lead to any direct solutions.

Once you can figure out which parts of the obstacles are visible (and can therefore be used to reflect the bullet), implementing mirroring via a depth-first search would seem straightforward. To find suitable mirror surfaces, the techniques outlined in Nicky Case's Sight & Light might be used: rather than trying out 360 vectors – which might miss openings, and also is wasteful – we launch rays only to the edges of obstacles.

• I don't understand how "launching rays only to the edges of obstacles" work. Do you mean to start launching rays towards the end of the walls, and gradually inwards until we find a solution? If so, I understand that with this rule the solution can be found faster. Jul 24 '15 at 3:32
• After some consideration, I think this is the best answer because obviously, with the mathematical answer I marked as best before, cannot directly deal with one-bounce and bounce-free solutions. Aug 8 '15 at 8:26
• This is brilliant! Any advice on how to create a mirrored representation of your level without being too demanding on your game? Jul 25 '18 at 16:27

Just extending Karl Bielefeldt idea for a 2 walls reflections: A and B are given (the tanks). You first must list all walls that A can see and a list of all walls B can see. Then you make pairs where the first wall is in the fist list and the second wall is different from the first wall and is in the second list. You need to make this test for all possible pairs of walls (unless you find a way to eliminate candidates). Once you find R and S for a given pair of walls you check

1) if A has direct vision of R

2) if R belongs to the wall1 (the wall is just a segment, no the whole line)

4) if S belongs to wall2 (the wall is just a segment, no the whole line)

To find R and S: Since you know wall1 you can determine the line equation tangent to wall1, since R belongs to the line tangent to wall 1, you have a relation between the 2 coordinates of R (ending up with one degree of freedom for R) Similarly to S (you have a relation between S coordinates since this point belongs to the line tanget to wall2). So now you have 2 degrees of freedom and you must have 2 additional independent equations to determine a solution. One equation is:

``````(AA')/(RA')=(SS')/(RS')
``````

the other equation is:

``````(BB')/(SB')=(RR')/(SR')
``````

notice that in the above equations A,A',B,B' are know or can be calculated directly. R' and S' are function of the coordinates of R and S and the wall equations. I didn't finish the math so I don't know how the equations will look like.

• This is a great mathematical approach. But the algorithm requires a lot of computation time for solving the simultaneous equations, I guess? There are a lot of square roots and exponentiation involved with distances. Jul 24 '15 at 3:35

You can take advantage of the fact that the angle leaving the ricochet must be the same as the angle entering it. For a given horizontal wall with y-coordinate `c` and two fixed tanks with coordinates `(a,b)` and `(d,e)`, there is only one angle which satisfies the equation below. Just solve for `x` to get the distance along the wall at which you must aim. Two walls works the same. You just have two equations and two unknowns.

You have neat diagrams showing how to direct rays, so I'll leave the details on how to determine a pair of reflecting surfaces.

Let's call the surface that must be hit first surface A, and the second, B.

Try to hit the (visible) edges of B by shooting at A. In other words, determine the points where one would see reflections of the ends of B if looking at the mirror-finished A. This must be easy to do, you have only one reflection point to handle.

Now you know two rays that hit the (visible) edges of B. Let's call them edge rays Compute their reflections off B; they must go somewhere past your target. You can determine if the target lies between them, that is, to the left of one ray but to the right of the other, or vice versa. This is trivial to do using the general equation of the straight line.

If the target is not between the edge rays, you obviously cannot hit it with any intermediate ray; pick another pair of surfaces.

If the target is between the rays, look for the intermediate hitting ray using binary search. You have two firing angles corresponding to the edge rays, your hitting angle lies between them. Provided that your target's angular diameter, as seen from the firing point, is not excessively small, you will need few iterations until you find a direction of a hitting ray.

Here's a picture: Here the two edge rays are shown in red and blue. Apparently you can find a ray emitted at a smaller angle than the red one but greater that the red one so that that ray will hit the green target.

• No, not necessarily! Think about your diagram if there was an extra obstacle lying anywhere right between the red and blue bullet paths. If you fire a bullet at an angle right between the red and blue angles, you might get a closer hit to the player tank, but you might also miss completely because some the bullet could ricochet off some random obstacle lying in between. Please see @amon's answer where he discusses about this possibility. Jul 24 '15 at 3:38
• Upvoted @amon's answer; I like the idea of straight-line mirroring. Also I suppose that the algorithm should check that the hitting path is actually passable after finding it in this simplified way. Even more interesting is a possibility where the target is only partially occluded (possibly even separated into two visible regions). Amon's method is more amenable to handling it.
– 9000
Jul 24 '15 at 4:40

First off, remember in physics class when you talked about refraction of light? Well your problem can be solved using those principles. The angle of incidence is equal to the angle of reflection. so the enemy tank needs to run through every possible angle for the first bounce so that the second bounce may hit the player. Keep going with the ray tracing idea too. Now, this gets complicated when the player is moving but it should be a good enough idea for you to get started on an algorithm

• I understand the principles of reflection. You can see my reply to @amon's comment. You're right that player movement must be taken into consideration, but I think it can be left as one criterion for choosing one optimal among multiple possible paths based on assessment. However, this can be ignored because this is correlative with distance of bullet path, i.e., the longer the path, the more the player can move before the bullet reaches destination. Jul 23 '15 at 18:45