Re: [pygame] Physics, collision detection etc?

["René Dudfield" <renesd@xxxxxxxxx>]

hi,

it'd be cool if we also had a good kdtree implementation for spatial
stuff too :)  For cases when we had say 1000 objects or so.

note, the wikipedia entry has a basic implementation in python
http://en.wikipedia.org/wiki/Kd-tree

There's also some quadtree python code lying around if you needed
it(see cookbook).  However, maybe even a simple grid will be better
for you.


cu,


On Fri, Oct 10, 2008 at 2:46 AM, Peter Gebauer
<peter.gebauer@xxxxxxxxxxxxxxxxxxxxx> wrote:
> Hello René.
>
> The thing is, in a large world spanning 16000x10000 pixels that will be a
> huge mask. Even if I reduce the resolution of the mask alone it will be
> either top inprecise or still too large.
>
> I don't want to write for OpenGL alone even though the plan is to use OpenGL
> as test output. My plan is to build a large world of 3 or 4-sided
> convex polygons that could be used to detect colliding with large shapes in
> that world.
>
> The best way to do this is probably to expose some of Zhang Fan's physics
> code, much of the math involved is already there, it just lacks
> non-rectangular shapes and a nice Python API to access it.
>
> /Peter
>
> On 2008-10-09 (Thu) 11:41, René Dudfield wrote:
>> hi,
>>
>> Note, that you can find contact normals with the mask module. See mask example.
>>
>> For some types of games, per pixel collision detection is fast enough.
>>  It uses rect bounding boxes as a first pass, so mostly it's not much
>> slower than rect collision detection.  Assuming you are working in 2d,
>> and you cache the mask(not regenerating it every frame) that is.
>> However the mask.from_surface routine is fairly fast, it could do with
>> some more optimization.
>>
>> For opengl, it'd be interesting to do it in a shader too... since then
>> you could just reuse your drawing routines to draw your
>> objects(sprites) into a buffer (each with a different color), then use
>> a shader to find all of the contact normals.  That way your collision
>> could be pixel perfect, even with different methods of
>> drawing(cartoon, glow, and other shaders) where the polygon
>> representation is not correct.
>>
>>
>> cheers,
>>
>>
>>
>>
>> On Wed, Oct 8, 2008 at 9:46 PM, Greg Ewing <greg.ewing@xxxxxxxxxxxxxxxx> wrote:
>> > Nirav Patel wrote:
>> >
>> >> If the polygons are Surfaces or can be turned into Surfaces, they can
>> >> be turned into Masks to do pixel collision.
>> >>
>> >> On Tue, Oct 7, 2008 at 11:21 AM, Peter Gebauer
>> >> <peter.gebauer@xxxxxxxxxxxxxxxxxxxxx> wrote:
>> >>
>> >> > Yep, but as I said, I need to find colliding polygons, not pixels.
>> >
>> > Pixel collision isn't suitable for all purposes,
>> > e.g. if you need to find contact normals for
>> > physics calculations.
>> >
>>
>