Programming exercises

I had an idea. Why not pose programming problems and then see what discussion ensues, perhaps with a reveal of my solution. Yes, you can tell I am still a teacher (perhaps much to the chagrin of some). So I will give it a go.

I remember when I told someone in their early twenties “I have been making games since I was 12”. To which the challenged me with “So did I” as if they were my equal. Do the math. I am 20 years older than you matey.

Maths is important. And that is going to be the subject of the problem I am presenting here.

One of the game prototypes I am working on (I am usually working on a personal prototype of some kind in unity these days) requires that I test to see if the player passes through a gate, rather than around it. Something like the gates of skiing. So, how can this be elegantly done?

You have the position of the player, the position of the sides of the gate. You must have a piece of code that is called at the right time to detect if the gate is properly taken or not. When this is detected, the game will switch to the next gate. The solution needs to work in 3D, but you can assume that the gates themselves are vertical.

What is the best solution you can come up with , in terms of size of code, clarity and robustness?

In a later post I’ll discuss my solution and we can compare notes.


5 Responses to “Programming exercises”

  1. Marios Karagiannis (@marioskar) Says:

    Form a line segment in 3D space with the previous and current position of the player as vertices. Check if this line intersects with the plane formed by the two gate sides.
    For 2D, it’s much simpler, since the gate will form another line segment and the problem is to find if the player previous-current position line segment intersects the gate line segment.
    This solution requires the storage of the previous position of the player but works even if the gates are not vertical but rather have arbitrary rotations.
    For efficiency, and if we do know that the gates are vertical, we can only run the check if the player position has moved over the line of the gate (if we assume the gate lies on a specific Y1 value, like the Kick Off goals for example :), we need only do the check when the previous position’s Y was Y1 or the previous was >Y and the current <Y1. I hope that makes sense.

    • Dino Dini Says:

      Thanks for taking part! I am going to cover this in the a course this block so I held off from giving the answer just yet.

      You approach will work, I think. Incidentally, the particular solution I used was different and did not require knowing the previous position.

      I will give more information soonish.

  2. Jimb0h (@jameswhitwell) Says:

    Hi Dino,

    I’m also looking forward to seeing you how went about this.

    You mentioned that you do your prototyping in Unity so in Unity I would have cheated and put a plane collider over my gate entrance and detected collisions between the collider and the player. To know if the player missed the gate you could just work out if the player is in front of the gate by doing the following:

    Vector3 playerVect = player.transform.position – collisionPlane.transform.position;
    float angle = Vector3.Angle(collisionPlane.transform.up, playerVect);
    bool isInFront = angle < 90;

    If they end up behind the gate without colliding with the plane covering the entrance then you can mark that gate as missed and then move on with the next one.

    Probably not the answer you were looking for but thought I'd post to let you know I'm waiting for your solution (which will no doubt be a tad more mathematical 😉

  3. Ruud Says:

    Let p be the position of the player, g_1 the position of the left pole, g_2 the position of the right pole, and u the up vector.

    First of all, to check whether the player is between the poles:
    ((p – g_2) · (g_1 – g_2) > 0) and ((p – g_1) · (g_2 – g_1) > 0)
    This checks whether the player is on the right side of the plane through g_1 with its normal pointing to g_2, and whether the player is on the right side of the plane through g_2, with its normal pointing to g_1.

    Define a = ((g_2 – g_1) × (p – g_1)) · u. When the condition above is satisfied, monitor the value a. It is negative when the player has not yet passed the gate, and positive when (s)he has (assuming a right-handed coordinate system). The reason that this works, is that the cross product is related to the sine of the angle between the vector from g_1 to p, and the vector from g_1 to g_2. When the player is on the line through g_1 and g_2, this angle is zero, and a is zero as well.

    We do need the up vector, because the two vectors g_1 and g_2 can only define a line, through wich the gate passes. An extra vector is required to define the plane.

    When you choose a nice basis, the up vector should have only one nonzero component. In that case, only one component of the cross product needs to be computed to determine a. Also, g_2 – g_1 and g_1 – g_2 can be pre-computed.

    An implementation of this should require no more than a few lines of code. There are no corner cases, so this method is extremely robust. However, it will be very hard to see what the code does, by looking at the mathematics of the problem only.

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: