Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Some simple 2d game-related maths questions

by skx (Parson)
on Aug 27, 2008 at 20:43 UTC ( #707298=perlquestion: print w/ replies, xml ) Need Help??
skx has asked for the wisdom of the Perl Monks concerning the following question:

I've written a simple game using the SDL bindings for perl.

The game itself was a a lot of fun to write, and wasn't too difficult. But I'm having a couple problem with it, and whilst they are not entirely Perl problems I suspect there is a module which could help me. I've searched CPAN for collision detection and gaming modules and come up short.

My problem is soley related to maths. My main (circular) sprite has an X,Y position, and each "tick" of the game this is updated:

$ball->{'x'} += dx $ball->{'y'} += dy

Here dx and dy are integer values which control the speed/angle of movement.

Now for my problem:

  • How can I tell whether the circular sprit intersects with an arbitrary line.
  • If it does how should I make it "bounce" away.

Currently my line structure is represented by a pair of coordinates "startx,starty" + "endx,endy". So my collision detection comes down to testng:

  • Does any part of the circle, radius N, intersect with the line X1,Y1,X2,Y2

This should be easy, but my code is brittle and seems to fail at times.

Similarly for the bounce I know that I need to take into account the angle of the line, but right now I just invert the dx + dy components and hope for the best.

Steve
--

Comment on Some simple 2d game-related maths questions
Download Code
Re: Some simple 2d game-related maths questions
by JavaFan (Canon) on Aug 27, 2008 at 21:06 UTC

      There's a fair amount of arithmetic to do to get the final result.

      You might save cycles by doing an initial check whether the bounding box around the ball intersects the bounding box around the line -- depending on the length of the line and its angle.

      The other approach may be to avoid performing a calculation on every (dx, dy) step. In particular, if the ball is moving in a straight line (or any other path that you have a polynomial for), you can calculate where the centre will be if it meets the line, then after each step you can check if the centre has gone past that point (the bounding box (x, y, x+dx, y+dy) encloses the impact point). Until, of course, the ball changes direction.

Re: Some simple 2d game-related maths questions
by moritz (Cardinal) on Aug 27, 2008 at 21:29 UTC
    First of all the game is quite nice, but there's a simple method with which you can win every level pretty fast, which kind of kills the fun as it is now.
    How can I tell whether the circular sprit intersects with an arbitrary line.

    I don't know how familiar you are with linear algebra, it really helps ;-)

    (Update: When I talk about "points", I really mean "position vectors to points". Thanks FunkyMonk)

    I'll call the end points of your line A and B, the center of your sprite M, the point on the line which is the closest to M is called C (all those are vectors), the radius of the sprite is r (a scalar value).

    Since C is on the line between A and B, it must be expressible in the form A + x * (B-A). Since it's the closest point to M, the connection line from C to M is perpendicular to the original line, or as a formula:

    (B-A) . (M-C) = 0 or (B-A) . (M - A - x * (B-A)) = 0 # (that's a scalar product)

    The only unknown part in this equation is x, which you can calculate from that equation, but to which I'm too tired at the moment.

    If 0 <= x <= 1 and |M - C| < r, then it circle touches or intersects the line.

    Likewise if |M-A| <= r or |M-B| <= r it also touches or intersects. In all other case it doesn't.

    To get a realistic bouncing behaviour, the angle between (dx, dy) and (M-C) after the bounce has to be negative of what it was before the bounce.

Re: Some simple 2d game-related maths questions
by GrandFather (Cardinal) on Aug 27, 2008 at 23:00 UTC

    Are you sure dx, dy aren't so big that the ball teleports right past the line? It may be that all the ball needs to do is quantum tunnel far enough that the center of the ball is on the other side of the line? Maybe you could post a little code showing your calculation and indicate the range dx, dy are likely to take?


    Perl reduces RSI - it saves typing
      To prevent such cases, I have generally taken the *previous* position value when deciding. "They're touching now, and it came from thataway."

        So in fact you need to perform a complicated area intersection with the area traced out by the moving object and the boundary line unless you can guarantee that the object won't move twice it's "diameter" or more in a single update.


        Perl reduces RSI - it saves typing
Re: Some simple 2d game-related maths questions
by swampyankee (Parson) on Aug 27, 2008 at 23:56 UTC

    It's a very common problem in the CAD community; you could try poking around one of their boards. Or you could look at someplace like here, here or here.


    Information about American English usage here and here. Floating point issues? Please read this before posting. — emc

Re: Some simple 2d game-related maths questions
by tod222 (Pilgrim) on Aug 28, 2008 at 00:13 UTC
    I'm not sure if this SDL_Collide library will do what you need, and it doesn't seem to have a perl wrapper, but it seemed worth a mention in any case.

    Update: SDL_Collide appears to have been created as a result of this thread of discussion on gamedev.net.

Re: Some simple 2d game-related maths questions
by pajout (Curate) on Aug 28, 2008 at 13:03 UTC
    It is funny to reinvent the wheel sometimes :>)

    I suppose that position of the line is constant and the radius of moving circle is constant too. In that case you can define that line by formula

    [1] aX + bY + c = 0
    (Note: vector (a,b) is perpendicular to the line.)

    If you consider left side of [1] as function,

    [2] f(X,Y) = aX + bY + c
    you can easily see that f(X,Y) = 0 only if point X,Y is on the line, and, f(X,Y) > 0 for each points of one half-plane defined by the line, and, f(X,Y) < 0 for each point of the other half-plane.

    Consequently, it is directly usable for testing if two points are on the same half-plane. But you want to test something different a bit. Let you construct two helper lines parallel to the [1] line, both in the distance equal to circle radius, g(X,Y) in positive half-plane and h(X,Y) in negative half-plane of the [1], with the same "orientation" of positivity/negativity. You can construct these functions just once when program starts, regardless on the position of the circle.

    Let (X1,Y1) is position of the circle center before movement and (X2, Y2) is position after movement. Exploring signs of f(X1,Y1), f(X2,Y2), g(X1,Y1), g(X2,Y2), h(X1,Y1), h(X2,Y2) will give you, what do you need.

    I think it is more suitable than some non-linear expressions.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://707298]
Approved by moritz
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (6)
As of 2014-12-27 13:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (177 votes), past polls