[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[pygame] PROPOSAL: Faster Collision Checking: Ordering Sprites to Boost spritecollide Speed (Please Comment!)

Hello,

I have a proposal regarding the spritecollide function. I have written
it down, comments would be very much appreciated. I hope you can check
it for errors, but if it's fined out enough it may be worthy to be
incorporated into the pygame distribution.

THE PROBLEM
===========

The current spritecollide function is slow. The current spritecollide
function checks *all* sprites in a group. In some situations, this can
be unacceptable. In my situation, I have approx. 200 walls, 200 bonuses,
100 monsters and 1 player in a 3000x2000 playing field. Every frame, each
monster moves. On every move, each monster checks whether it collides with
a wall; *any* wall. 100*200 = 20.000 collision are checkd per frame!
The following profile is the result:

         241616 function calls (241610 primitive calls) in 56.350 CPU seconds

   Ordered by: internal time
   List reduced from 173 to 10 due to restriction <10>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     8538   12.800    0.001   13.580    0.002 sprite.py:551(spritecollide)
     5504   10.890    0.002   11.030    0.002 level.py:65(spritesinrect)
      294    5.120    0.017    5.150    0.018 screen.py:103(drawsprites)
     7437    4.870    0.001    5.220    0.001 basesprites.py:253(shouldfall)
    22801    3.660    0.000   38.840    0.002 basesprites.py:421(update)
     1238    3.490    0.003    3.490    0.003 screen.py:29(tiled_blit)
     7437    1.880    0.000   33.220    0.004 basesprites.py:347(move)
      238    1.430    0.006   42.130    0.177 groups.py:52(update)
    22801    1.360    0.000    1.360    0.000 basesprites.py:413(distance)
     7437    1.340    0.000   11.880    0.002 basesprites.py:268(adjustmove)

Here, drawsprites and tiled_blit are graphical; those functions respectively
draw sprites and background. Usually, those are the slowest, but because of
the spritecollide (and, in my case, spritesinrect, which does almost the same),
the game runs at at approx. 4 fps with profile and 7 without.

POSSIBLE SOLUTION
=================

A possible solution could be to order the sprites inside a group. If it
can be guaranteed that all sprites in a group a sprite collides with
are next to each other, a significant boost to speed can be given,
especially if the sprite is inside the group itself. But it is not trivial
how to do this.

When ordering sprites based on distance to point X, they are not ordered
based on distance to point Y. However, then ordered based on vectored
horizontal distance to point X, they _are_ ordered based on vectored
horizontal distance to point Y. In this example, the rectangles are
sorted based on vectored horizontal distance:

  3 >>> r1=r(0,0,50,50)
  4 >>> r2=r(10,40,30,30)
  5 >>> r3=r(20,3,25,50)
  6 >>> r4=r(40,30,20,10)
 14 >>> r5=r(1,2,3,4)
 15 >>> r6=r(30,80,40,0)
 22 >>> [re.centerx for re in (r5,r1,r2,r3,r4,r6)]
[2, 25, 25, 32, 50, 50]
 23 >>> (r5,r1,r2,r3,r4,r6)
(<rect(1, 2, 3, 4)>, <rect(0, 0, 50, 50)>, <rect(10, 40, 30, 30)>, <rect(20, 3, 25, 50)>, <rect(40, 30, 20, 10)>, <rect(30, 80, 40, 0)>)

Now, we can guarantee, that if a rect in indexed x in this sequence, that
every rect indexed (x-n-1) is horizontally further away that (x-n). Thus,
if a rect (x-n) is horizontally to far away to possibly collide, we do
not need to check any further rects/sprites. When possibly checking
thousands of rects, this is a signifacant boost already.

INVOLVED PROBLEM
================

However, it becomes difficult whet checking both horizontally and vertically.
I have been brainstorming a bit with myself here: using a 2-d array wouldn't
be possible, because it isn't shaped uniformly and adding sprites wouldn't be
possible.

POSSIBLE WORKAROUND?
====================
Maybe having two lists is possible: one vertically, and one horizontally.
First, spritecollide would check which segment in the h-list consists of
sprites which possibly collide. We name the lowest index hl and the highest
index hh. We do the same for the v-list we have as group attribute: the
lowest index we call vl and the highest index we call vh. Now, we construct
the two lists: hp = h[hl:hh]; vp = v[vl:vh]. hp contains all sprites with
which rect we have a common x coordinate, and vp contains all sprites with
which we have a common y coordinate.

Sprite collides with every sprite which is in both lists. I am sure that,
at least for large amounts of sprites, this algorithm is faster than the
current 'raw' algorithm.

DISADVANTAGE
============

To keep a h-list and a v-list current, we need to do two things. Every time
a sprite is added, we need to add a reference in the two lists at the right
place. This is not a huge problem. However, every time a sprite _moves_, we
also need to update the list. This is undoable, so we need to think of a
different solution. Making h-list and v-list properties (or pseude-attributes)
is a possiblity: every time h-list or v-list is asked for, it is sorted before
it is returned. Sorting a sorted list is virtually no overhead in Python:

 43 >>> l=range(1000000)
 44 >>> random.shuffle(l)
 45 >>> profile.run("l.sort()")
         2 function calls in 7.510 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    7.500    7.500    7.500    7.500 <string>:1(?)
        1    0.010    0.010    7.510    7.510 profile:0(l.sort())
        0    0.000             0.000          profile:0(profiler)


 46 >>> profile.run("l.sort()")
         2 function calls in 0.350 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.350    0.350    0.350    0.350 <string>:1(?)
        1    0.000    0.000    0.350    0.350 profile:0(l.sort())
        0    0.000             0.000          profile:0(profiler)

But well, one million elements is a lot ;). With 10.000, there still is
a problem:

 47 >>> l=range(10000)
 48 >>> profile.run("l.sort()")
         2 function calls in 0.000 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(?)
        1    0.000    0.000    0.000    0.000 profile:0(l.sort())
        0    0.000             0.000          profile:0(profiler)


 49 >>> profile.run("[l.sort() for _ in xrange(100)]")
         2 function calls in 0.280 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.280    0.280    0.280    0.280 <string>:1(?)
        1    0.000    0.000    0.280    0.280 profile:0([l.sort() for _ in xrange(100)])
        0    0.000             0.000          profile:0(profiler)

...so this isn't great either.

POSSIBLE WORKAROUND
===================

Maybe we need higher level sprites to solve this problem: sprites
which know about their location, and which .rect shouldn't be
.move_ip()'ed by hand. Such a sprites' .move() method would call
.rect.move_ip and notify the group about this movement; the group
can then shift the sprite according to the position change. I am
not sure you about how to solve this.



Comments would be very much appreciated.

yours,
Gerrit Holl.

-- 
Asperger Syndroom - een persoonlijke benadering:
	http://people.nl.linux.org/~gerrit/
Het zijn tijden om je zelf met politiek te bemoeien:
	http://www.sp.nl/
____________________________________
pygame mailing list
pygame-users@seul.org
http://pygame.seul.org