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.
Re: Some simple 2d gamerelated 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 * (BA). 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:
(BA) . (MC) = 0
or
(BA) . (M  A  x * (BA)) = 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 MA <= r or MB <= 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 (MC) after the bounce has to be negative of what it was before the bounce.  [reply] [d/l] [select] 
Re: Some simple 2d gamerelated maths questions
by JavaFan (Canon) on Aug 27, 2008 at 21:06 UTC

 [reply] 

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.
 [reply] 
Re: Some simple 2d gamerelated 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.  [reply] 
Re: Some simple 2d gamerelated maths questions
by GrandFather (Sage) 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
 [reply] 

To prevent such cases, I have generally taken the *previous* position value when deciding. "They're touching now, and it came from thataway."
 [reply] 

 [reply] 
Re: Some simple 2d gamerelated 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
 [reply] 
Re: Some simple 2d gamerelated 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 halfplane defined by the line, and, f(X,Y) < 0 for each point of the other halfplane.
Consequently, it is directly usable for testing if two points are on the same halfplane. 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 halfplane and h(X,Y) in negative halfplane 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 nonlinear expressions.
 [reply] [d/l] [select] 

