An Optimal Scoring Algorithm for Avoiding Balls


A simulation is available at: https://dl.dropboxusercontent.com/u/19633784/score_test.html (check the bottom of the article for more info)

In my last posts the main topic at hand has been how to get balls to bounce around in a labyrinth of right-angled walls. However, there hasn’t been much playability as of yet, only an animation of the balls bouncing. So I’ve introduced a player entity now, which has a position (x, y) and a radius r – a player is also sphere as of yet. Now, in the game the point is to avoid the balls. You get points for doing dangerous manoeuvres, i.e. being close to the balls. We’re going to make some assumptions:

  • Being close to the ball is harder than being further away from the ball.
  • It’s harder when the ball is heading towards the player, rather than heading away from it.
  • It’s harder to avoid the ball when it has a huge velocity than when it’s going slow.
  • Let S be the score, and \textrm{Diff} the difficulty. Then \frac{d}{dt} S \propto \textrm{Diff}.

We’re going to break this down into three parts. In particular, we have a scoring function \sigma. In practice however, we’ll look at the derivative of this function, because we want to know how much to increase the score with each game tick. This can also be stylized as \frac{d}{dt} \sigma(d,a,b,v) = D(d) \cdot \theta(a,b) \cdot V(v), where D is the distance function, \theta is the direction function, and V is the velocity function. We’re going to look at the distance function D(d) first.

The distance function has a maximum value D_{max} when the player is as close to the ball as possible without dying. If we let w_b be the width of the ball, and w_p be the width of the player, then obviously the closest possible distance is \frac{w_b + w_p}{2}. We call the shortest possible distance for d=0, and therefore D(0) = D_{max}. We want the distance function to decay exponentially, so going further away by constant distance decays the score by a constant factor. In other words, we can express the distance function as D(d) = D_{max} \cdot e^{-k \cdot d}, where k is some constant.

Next up is the direction function \theta(a,b). The range of the function is [0, 1], where 1 corresponds to the situation where the ball is going exactly towards the player, and 0 is the situation where the ball is going in the exact opposite direction from the player. How do we calculate \theta?

Well, notice that we have two angles as the arguments to the function. This is because we only need two pieces of information for this – two vectors a and b. The vector a is the vector between the ball and the player. The horizontal constituent is the difference between the x-coordinates of the ball and the player, and likewise for the vertical constituent. And the vector b is the movement vector for the ball.

Okay, so now we need to calculate the dot product of a and b, because it just so happens that a \cdot b = 0 if the two vectors are orthogonal, it also so happens that a \cdot b = -1 when the vectors are pointing to each other, and a \cdot b = 1 if the vectors are pointing away from each other. Notice that the range of the dot product is [-1, 1], and we need to map this unto [0, 1], so we define the \theta-function as \theta(a,b) = \frac{(1 - a \cdot b)}{2}. This function will give 1 if the ball is going towards the player and 0 if its going away from the player.

And finally, we’ll go through the velocity function V(v). We’re going to assume it’s twice as hard to avoid a ball that’s travelling twice as fast as another ball. In other words, there is a linear correlation between the velocity and the score you should receive. In other words V(v) = C \cdot v, where C is any constant.

We can now assemble the scoring function \sigma. We see that \frac{d}{dt} \sigma(d,a,b,v) = D(d) \cdot \theta(a,b) \cdot V(v) =D_{max}\cdot e^{-k \cdot d} \cdot \frac{(1 - a \cdot b)}{2} \cdot C \cdot v.

In practive, we choose constants D_{max} = 100, k = -\log(0.75), and C = 1. So, here is the final scoring function:

\frac{d}{dt} \sigma(d,a,b,v) =100 \cdot e^{-(-\log(0.75)) \cdot d} \cdot \frac{(1 - a \cdot b)}{2} \cdot v

If you want to, you can test it out at the following link: https://dl.dropboxusercontent.com/u/19633784/score_test.html

You are the red ball, and the game freezes when you get hit by a ball. Refresh the window to try again (sorry about this solution).

Advertisements

Comment on this article

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s