[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [pygame] sprite engine and help for algorithme



Kamilche schrieb:
DR0ID wrote:
Brian Fisher schrieb:

For example, what happens when the ghost moves behind the tree? In
that case, the ghost didn't dirty any part of the tree
Huh? When the Gohst moves or changes layer (!)....


I think I see what's going on here. Some people appear to be confusing a 'dirty sprite' (one that needs repainting) with a 'dirty screen rectangle)' (an area of the screen that needs to be redrawn.) Internally, I don't call the sprite flag 'dirty' - i call it 'paint.' If a graphic needs to be recreated because of size, appearance, or text changes, the 'paint' flag is turned on.

Maybe the following pseudocode will make the order of events clear.

For each dirty rectangle
   For each sprite
      If the sprite needs painting (paint flag is on)
         paint it (will add another rect to the dirty rects list)
         clear the paint flag
      If the sprite intersects the dirty rectangle
         draw it

Note that the dirty rectangle list is potentially modified as you iterate over it. Because of it, you shouldn't just 'clear the dirtyrects' at the end because you'll eat your newly-added rects! You should do a loop something like:

while len(dirtyrects) > 0:
   do proper stuff with dirtyrect[0]
   del dirtyrects[0]

This will repaint the existing dirty rectangles, and any new ones that got added during the iteration. And going through it this way is a good sanity check - if your program is looping endlessly, it's a sign you've put in an extra 'SetRect' where you don't need it, and the list never gets clear.


--Kamilche

Hi

why so complicated? Iterating over lists that are modified at same time?
Here my basic steps for my code:

First I collect and clear with background all dirty areas on screen by doing:

#-------------- 1. ------------------------------------------------------------
for each sprite:
if sprite.dirty>0:
clear sprite.oldrect area with background (oldpoistion)
add sprite.oldrect to update_rect_list
add sprite.rect to update_rect_list (new position)
sprite.dirty=0


#------------------------------------------------------------

For the second part it is not important how the update_rect_list is builded. Optimization like union colliding areas should be done until here.
Then I only have to iterate over the sprites:


#-------------- 2. ------------------------------------------------------------

for each sprite:
   if sprite.rect collides with any rect of update_rect_list:
      blit sprite to screen
      sprite.oldrect = sprite.rect

pygame.display.update(update_rect_list)
update_rect_list[:] = [ ]
#------------------------------------------------------------

So basycly I iterate 2 time over all sprites and one time over alls update_rect_list and I can use the fast pygame colliding functions. The question is which list is longer: the sprite list or the update_rect_list? Probably the update_rect_list because of the sprite.oldrect that can not be optimized to one update_rect_list rectangle for every sprite.

(comment to section 2 of code: if first iterating over the updat_rect_list then one has to find out which sprite collides what means that a sprite can be redrawen many times if it collides with different update_rect_list rectangles)


#help me###########help me###########help me###########help me###########help me###########please


One step I want to do to optimize the update_rect_list is that:

I found a algorithme to optimize the update_rect_list. It minimizes the number of rects and the area used. But had no time until now to test it for speed, so if someone want to help me take a look. I'm open to any suggestion.

#-------------- 3. ------------------------------------------------------------
_optimized = [ ]
for sprite in sprites: # a series of potential dirty screen areas producers
if sprite.dirty: #only add it if it is flaged dirty
newr = sprite.rect # or any rect that has to be added to the screen update areas list
if -1!=newr.collidelist: # if it collides with an existing dirty screen area then try to optimize
idxlist = newr.collidelistall(_optimized) # find all colliding dirty screen areas
toremove = [] # help list to not have to modifie list which it iterates over
for idx in idxlist: # iterates over found dirty screen areas
r = _optimized[idx] # get rect
u = r.union(newr) # precalculate the union
if u.width*u.height< newr.width*newr.height+r.width*r.height: # optimization condition
toremove.append(r) # this rect has to be removed from dirty screen area list
newr = u # rect has growen
_optimized.append(newr) # and after it has check it with all dirty screen area one could append it to the list
for r in toremove: #now it is time to remove the no longer needed ones
_optimized.remove(r) else: #this is for the rects that do not overlap with any existing dirty screen area
_optimized.append(newr)


#--------------------------------------------------------------------------

(comment to section 3: perhaps simpler tho only take the collision as condition but this area calculations are more precise (because I think any pixel which is not updated make things faster))

So that the code. I hope you understand it. It will wipe out all heavy overlaping sprite areas and only make one rect instead. Try it. The only I do not know if it is worth it to implement it because if the calculation is to time comsuming it is faster to blit a area three times. If it can be done better, pleas tell me.

Sorry for my long email, I hope your not tired to read such long email (I will try to make it shorter in future).

~DR0ID