Re: [pygame] sprite engine and help for algorithme

["Brian Fisher" <brian@xxxxxxxxxxxxxxxxxxx>]

On 4/29/06, DR0ID <dr0id@xxxxxxxxxx> wrote:
> 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.
One simple approach to optimizing dirty rects is to split the screen
area up into a bunch of smaller fixed integer size rectanglular zones,
then for each zone, you only maintain a single dirty rect. Then to add
a rectangle to the dirty area, you split the rect up for each zone it
overlaps, and then expand the dirty rect for each overlapped zone to
fully cover the dirty area in the zone. The idea behind that approach
is that the cost of work to add a dirty rect is proportional to the
size of the added rect, and doesn't increase at all when you have a
whole lot of dirty rects.

To describe it another way, it's like you only have one single dirty
rect that covers the whole screen, except that your screen is made up
of a grid of other smaller screens....