Making Balls Bounce off of Walls in a Labyrinth

If you enjoy this post, I recommend reading the update: A slight update on encoding…

You can watch an example implementation in Flash of this algorithm at the following link: https://dl.dropboxusercontent.com/u/19633784/bouncing.html

In this post, I’ll detail an algorithm for making balls collide with walls in an arena, like the following image:

The problem here is determining when and how a ball is to bounce. Okay, so a ball has a position $(x, y)$ and a radius $r$. It also has a direction $\theta$ and a speed $v$. These are all the parameters required to uniquely specify a ball in the arena. So now we’ve modelled a ball, but how do we model the walls?

The wrong approach

I’ve actually tried doing this several times before, and it’s failed every single time so far. What I did wrong was trying to model a Wall-object and specifying it with a position $(x, y)$ and an orientation $\theta$. Why does this not work?

First of all, I personally find this much harder to do, and second of all it’s expensive. You need to check the distance to every single wall object every frame, and this is expensive. This approach would in pseudo-code work like this:

for every ball:
for every wall:
if(collides(ball, wall))
ball.bounce();

A quick analysis of this algorithm shows that it’s time complexity for collision detection of a single ball is $O(w)$, where $w$ is the amount of walls.

The correct approach

The encoding

There is an update to this encoding, which is much, much faster.

In the second model, which is the only model that has worked for me, we model the walls as tiles. A tile is an object in the arena which has a size $T_w$ (Tile width), a position $(x, y)$ and four slots for walls:

This is an example of a tile. A tile can have a left wall, it can have a right wall, an upper wall and a down wall – all independent of each other. We notice that each wall slot has two states – on or off. There either is or isn’t a wall in that slot. This makes it evident that there are a total of $2^4 = 16$ different tile types, each with a different configuration of walls. Actually, we can uniquely specify the wall configuration using a single integer, an ID. Now, all we have to do is make an encoding for the wall configurations:

The encoding doesn’t really matter, but I felt like sharing my way of encoding the walls. Okay, so now that we’ve modelled the tiles, how do we make the ball bounce off of the walls?

Here is the true strength of this approach. We only need to check a single tile, rather than check all of them (like we did in the last approach). This is because we know the position of the ball in question, and because the tiles are evenly distributed in a known order, it’s very easy to determine which tile the ball is currently under.

Okay, so now we’ve actually reduced this problem to the problem of determining when a ball hits the edge of a square. Thankfully, this problem is ridiculously easy. Consider the situation where a ball is inside a tile:

Each tile has a width $T_w$ and the walls of the tile also has a width $W_w$.

The ball has a relative position $(x, y)$, where $(0, 0)$ represents the top-left coordinate of the tile, and $(T_w, T_w)$ represents the bottom-right coordinate of the tile. The ball also has a velocity $v$, a direction $\theta$ and a radius $r$. It should be evident that the net change in position of the ball is equal to $(\cos(\theta) \cdot v, \sin(\theta) \cdot v)$. What we now need to do is to determine whether or not it has hit a wall between $(x, y)$ and $(x + \cos(\theta) \cdot v, y + \sin(\theta) \cdot v)$.

To loosen notation a bit, we define $P_ {old} = (x,y)$, $x_{new} = x + \cos(\theta) \cdot v$, $y_{new} = y + \cos(\theta) \cdot v$, and $P_{new} = (x_{new}, y_{new})$. To determine whether or not it hit a wall, we examine the four cases; each wall.

When do they hit the walls?

To determine whether or not the ball has hit the left wall, we need to figure out if the leftmost part of the ball is as far the the left as the rightmost part of the left wall or further. Obviously the new x-coordinate of the ball is $x_{new}$, and since the radius of the ball is $r$, the leftmost x-coordinate of the ball must be $x_{new} - r$. Since the walls are placed as far to the side as possible, the leftmost x-coordinate of the wall must be 0, but since it has a width of $W_w$, this means the rightmost x-coordinate is $W_w$. Aha! This means we must bounce from the left if $x_{new} - r \leq W_w$.

But wait, how do we bounce from the left? Obviously we want the change in the x-coordinate $dx$ to change signum, but we don’t want to affect the change in the y-coordinate $dy$. What manipulation on $\theta$ to get $\theta '$, such that $\cos(\theta ') = -\cos(\theta)$, but $\sin(\theta ') = \sin(\theta)$. Introducing trigonometric identities. It just so happens that $\cos(\pi - \theta) = - \cos(\theta)$, but $\sin(\pi - \theta) = \sin(\theta)$.

It just so happens that the bouncing for when the ball collides with either the right wall or the left wall is the same – we need to set $\theta = \pi - \theta$ to bounce it. But when do we bounce from the right?

Let’s see, to bounce from the right, we use the same strategy as for bouncing from the left. The rightmost x-coordinate of the ball must be as far to the right or further than the leftmost x-coordinate of the right wall. The rightmost x-coordinate of the ball is $x_{new} + r$, and the leftmost x-coordinate of the right wall is $T_w - W_w$. Alright, excellent! So we bounce to the right if $x_{new} + r \geq T_w - W_w$.

But wait! The procedure when bouncing from the right or the left was the same. In other words, we can make a single statement:

$(x_{new} - r \leq W_w) \lor (x_{new} + r \geq T_w - W_w) \implies \theta = \pi - \theta$

I’m not going to go into details with up and down – it’s pretty much the same. But here is the logical statement for up and down:

$(y_{new} - r \leq W_w) \lor (y_{new} + r \geq T_w - W_w) \implies \theta = - \theta$

Using the encoding

You may have noticed that we haven’t yet used the encoding from above, yet. We will actually introduce this now, because so far we have had nothing telling us to not bounce if there isn’t a wall. If we only followed our above two logical statements, the balls would bounce around in the very tile they were born in without any hope of ever escaping it.

Okay, so how do we do this? We’re going to define four sets – one for each type of wall, $\mathcal{L}$$\mathcal{U}$$\mathcal{R}$, and $\mathcal{D}$. Now, the thing is that these sets will contain the ID’s of the wall configurations containing that type of wall. For instance, the set $\mathcal{L}$ will have to contain the number 1, because the wall configuration for ID = 1 contains a left wall. This allows us to define four sets:

$\mathcal{L} = \{1, 5, 6, 7, 11, 12, 14, 15\}$

$\mathcal{R} = \{3, 6, 8, 10, 11, 13, 14, 15\}$

$\mathcal{U} = \{2, 5, 8, 9, 11, 12, 13, 15\}$

$\mathcal{D} = \{4, 7, 9, 10, 12, 13, 14, 15\}$

When checking if we should bounce to the left, we should also check that the ID of the current tile is a member of the set $\mathcal{L}$. Let $ID$ be the ID of the current tile. Then the logical statements expand to:

$[(x_{new} - r \leq W_w) \land (ID \in \mathcal{L})] \lor [(x_{new} + r \geq T_w - W_w) \land (ID \in \mathcal{R})] \implies \theta = \pi - \theta$.

$[(y_{new} - r \leq W_w) \land (ID \in \mathcal{U})] \lor [(y_{new} + r \geq T_w - W_w) \land (ID \in \mathcal{D})] \implies \theta = - \theta$.

Excellent! So now the balls can bounce around correctly inside 16 different tiles! Everything works now, right? Right?

The problem

When I first ran this I expected it to work perfectly. After all, it’s hard to spot any major errors in this system, right? But alas, your code never runs perfect first time. Never.

However, it’s not due to an error with the bouncing, it’s an error with the implementation of the tiles. My original idea was just to make a grid of $w \cdot h$ tiles and give each of them a random ID. This has a huge caveat, though. Take a look at this flash animation: https://dl.dropboxusercontent.com/u/19633784/bad_bouncing.html

As you can see, the walls are thinner in some places than in others, and you’ll notice that the balls sometimes fly right through the walls without actually colliding with them. This is a huge problem. Why does it occur, and how can we prevent it?

Take a look at this diagram I made:

Basically, the ball moves too fast for the new tile to discover that it actually was to the left of its leftmost wall. How do we fix this?

The solution

Quite simply, we don’t want to change our algorithm, we wan’t to change how we make the levels. We enforce a rule. Whenever a tile has a wall, the tile adjacent to that wall should also have a wall in the same place. Put visually:

In practice, we’ll first generate the map and then add the remaining walls – clean it, to make sure no errors will occur. This is done through a map, which maps the ID of a wall configuration and an orientation to another wall configuration. If we let $S$ be the set of all ID’s, and $O = \{\mathcal{L}, \mathcal{R}, \mathcal{U}, \mathcal{D}\}$ be the set of all orientations, then the map $\delta : S \times O \implies S$.

But what does this map actually do? Well, it adds another wall. If we for instance have a wall of ID 0 (no walls) then $\delta(0, \mathcal{L}) = 1$. This is because the wall configuration with ID = 1 is the same as the wall configuration with ID = 0, only it has an extra added left wall. See the idea?

If we add this to our simulation, we get one that runs much smoother, and far more reliably. Whew, glad we’re done with this one!

More problems

As any experienced programmer knows, there is no end to the rabbit hole of bugs. It only goes down further. And of course there are more bugs. Let’s consider the situation where a ball comes from a tile right into the side of a wall. In other words, what happens in this situation?

Obviously what we’d like to happen is that the ball bounces back again, but this is sadly not what happens. Actually what happens is that the balls preserves its horizontal momentum, but rapidly changes its vertical momentum every frame. This is because it just barely fits into one of the tiles before it discovers that it’s lowest point is lower than the topmost point of the bottom wall, making it bounce vertically. The same thing happens yet again as it enters the other tile. This is not a good thing, and it needs to be fixed.

Yet another solution

To fix this, we’re going to look at the corners of the adjacent tiles. We need to ask the question, does it collide with the corners of the adjacent tiles? More specifically, is the shortest distance between the line segment between $P_{old}$ and $P_{new}$ closer to the corners of the adjecent tiles than the radius of the ball? If yes, reverse direction.

This may sound like a mouthful, but it makes excellent sense. Take a look at this diagram:

Implementing this step as well is not hard, and in doing so we get the animation at the top of this link: https://dl.dropboxusercontent.com/u/19633784/bouncing.html

Algorithm Analysis

It’s clear that we only need a constant amount of operations per ball. We need to check the current tile only, and the adjacent tiles. So, per ball it has algorithmic time-complexity $O(1)$, and the overall time-complexity is $O(b)$, where $b$ is the amount of balls in the arena. This is better than the previous algorithm (Which was also harder to implement, IMO).

There still some few tweaks to work out, they still get stuck in the corner at times, and I’d like the balls to actually look like they hit the walls instead of looking like they’re hitting from a few pixels away, but all in all I’m happy with how this engine turned out.

Shout out the game Tank Trouble, which inspired me to make this blog post.

11 thoughts on “Making Balls Bounce off of Walls in a Labyrinth”

1. Matt says:

Excellent post! I like that you took the time to explain all the special cases you had to deal with.

2. SC says:

You should look into binary space partitioning trees which are able to achieve efficient collision search with arbitrary geometry (and arbitrary dimensions), provided that such geometry is static.

Also, if you have arbitrary environmental geometry (which prevents you from just adding radius to x or radius to y to get the boundary of your object), one way to deal with colliding an object that is bigger than a point is to offset the walls by a certain distance. In the case of a circle, you would offset the walls outward along their normal vector by the radius before you check for collision. Note that this will cause some issues at corners, especially with acute angles, and to get good behavior you will want to bevel the corners.

Another thing to note is that if your simulation step is too large compared to the velocity, your algorithm will probably not detect collisions if there are more than one in a step. Maybe it would never happen due to the way your simulation runs, but it’s something to consider if the system is less constrained. In fact, you may be glossing over this issue when it comes to corners: you should find the intersection nearest to the start point, calculate the new vector due to that collision, and then do the same thing recursively for the resulting vector until you find no collision.

Here are some materials I used when researching this:
http://sha.nnoncarey.com/physics/melaxbsp.pdf
http://sha.nnoncarey.com/physics/SamuelRanta-Eskola_BSPTrees.pdf

1. Thanks for the insightful comment 🙂 and it’s true, if the velocity of the ball is larger than the width of the tiles, the algorithm might behave in an unexpected way, and I haven’t included this case in it.

3. Anonymous says:

You have reinvented the octree 🙂

1. Could you elaborate? How is this an octree? 🙂

4. i still see balls go through walls, when they hit in a very flat angle (maybe if they hit a corner) – lets call it a “corner” case. and once i have seen it going in a zig-zag like it was clamped between invisible walls. still very nice post!

1. It’s not perfect, no 🙂 there are still some bugs to work out.

5. Anonymous says:

The first time I opened up the example I had a ball stuck in the top, going side to side along the top line, inside the wall.

1. Yeah, sometimes they spawn inside the walls. This has nothing to do with the algorithm