Re: [pygame] Line collision detection?

[Silver <rockachu2@xxxxxxxxx>]

On 2/20/2012 1:50 PM, Julian Marchant wrote:
> Hi, I tried searching the internet for an answer, but didn't find anything, so I'll ask here.
> 
> One problem with normal collision detection I'm sure we're all aware of is the problem that objects moving too fast can pass through other objects without a collision happening. I'm experiencing this problem with a scrolling shooter I'm working on because both bullets and enemies move pretty fast, one enemy is very small, and the frame rate is usually somewhat low (maybe 30 FPS) on the machine I'm targeting.
> 
> Now, obviously, I intend to make other changes which will help, e.g. making these tiny enemies bigger, but I'd like to tackle the problem directly. There are two ways I can think of: The first way, which I easily could implement and would be most effective, is to move the bullets in steps and do collision detection each step. I have done something like this in a previous game and it worked well, but it seems like overkill in this game (the bullet subrect is only 5x5 pixels) and it isn't perfect anyway.
> 
> The second way, which I would prefer, is to detect collision with a line from the bullet's new position to the bullet's previous position. I've seen this discussed on the Game Maker Community. The problem with this is I have no idea of how this could be done in a remotely efficient manner. The only method I can think of is to check every individual pixel one at a time, which is obviously not a good idea. Bullets can move diagonally, so just checking the x or y position won't work.
> 
> So, in a nutshell, my question is: how could I do "line collision" detection like this in a relatively efficient way?


Personally a way to combine the idea in the last reply (four corner
lines) would be to use a kind of inequality.

To do this in pygame you could extend the collision rectangle so that it
fills the whole area that the bullet travels in. Then you could do the
collision detection per-pixel or with whatever accuracy you wish.



So, if I have a rectangle (25, 25, 10, 10), moving at an x speed of 8, I
could do this:

speed = 8

if (25,25,10+speed, 10).collide(your target rect):
then ## you r pixel perfect collision algorithms, an example:

for stepoffset in range(speed):
    if (25+stepoffset,25,10,10).collide(your target rect)
        collide.


this could easily be expanded to support two moving projectiles.


it might not be as efficient as line-collision, but it seems easier to
understand to me.

I hope this helps.