# Re: [pygame] Line collision detection?

Or if you like spoilers maybe somebuddy has some Python code you can rip, like this guy:

Specifically, functions line_intersects_line and point_in_poly.

Gumm

On Mon, Feb 20, 2012 at 3:33 PM, Miriam English wrote:
You could use the point of intersection between two lines.

One line is the bullet trajectory.
The other line is the target trajectory.
You have to take into account the time of the intersection too.
If the intersection falls inside the target at the right time for both projectile and target then it is a hit.

Paul Bourke gives a simple explanation with C code examples at:
http://paulbourke.net/geometry/lineline2d/
That's for 2D. The 3D solution would be more complex, but not too much.

It could be simplified by making bullets travel instantaneously if distance is negligible. In fact if that's the case there may be an even simpler way of solving whether a line intersects a volume.

Cheers,

- Miriam

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?

--
If you don't have any failures then you're not trying hard enough.
- Dr. Charles Elachi, director of NASA's Jet Propulsion Laboratory
-----
Website: http://miriam-english.org
Blogs:   http://miriam-e.dreamwidth.org
http://miriam-e.livejournal.com