Re: [pygame] Python and Speed

["FT" <chester_lab@xxxxxxxx>]

Hi!

    I am just making an observation on this and objects, maybe I am missing
the point, but when checking collisions, if you know your objects size, the
vertex, or point depending on direction, could you not not solve this by
just the direct line between the 2 objects and not the surface?

    What I mean, you are in control of your game, you know your objects,
thus, you also know the point that will be hit depending on the direction
you are traveling in, so why not just check that point or small collection
of points?

    That is what I would do when running this kind of game. For my Star Trek
game does not use the actual pixel, but the area in which it is in and that
is a larger area. But when using pixel points, then only the points that
fall in-line with the direction you are traveling in. That seems to me to a
much faster check, little to almost 1 single point is what seems to be the
result in this...

    In other words you know your objects and where they are, then just draw
a straight line between them and calculate the edge at that line drawn. I am
not saying draw a line, just calculate to the edge of the object from
both...

        Bruce



On Apr 17, 2008, at 12:26 PM, Ian Mallett wrote:
> On Thu, Apr 17, 2008 at 12:15 PM, Casey Duncan <casey@xxxxxxxxxxx>
> wrote:Note this is not the most efficient way to do this, using a
> partitioned space you may be able to avoid comparing most points
> with one another most of the time. To do this in 2D you could use
> quad-trees, in 3D you could use oct-trees. See:
http://en.wikipedia.org/wiki/Octree
> Yes, I've tried this, but there are issues with points being in two
> separate places.  For example, if the collision radius is 5, and it
> is 3 away from the edge, then all the points in the neighboring
> trees must be tested.

Partitioned space is certainly a more complex algorithm, but so long
as all of your "points" (spheres?) are not close together, it is
usually vastly more efficient. If the partition size is optimal, than
the vast majority of particles will not be hitting the edge of a
partition, that will be an edge-case (pun intended). Even for those
that are it's usually still faster than the naive O(N^2) method that
compares every point with every other.

This algorithm is only effective if the space is large relative to the
collision geometries and they tend not to be clumped very close
together.

-Casey