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

Re: [pygame] sprite engine and help for algorithme

Brian Fisher schrieb:
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....

Hello

thank you for your idea. If I understand it right you split the screen into smaller zones like that:

+----------+----------+----------+----------+----------+----------+----------+

| Zone1 | Zone2 | ... | | | | |
| | | | | | | |
+----------+----------+----------+----------+----------+----------+----------+

| | | | | | | |
| | | | | | | |
+----------+----------+----------+----------+----------+----------+----------+

| | | | | | | |
| | | | | | | |
+----------+----------+----------+----------+----------+----------+----------+

| | | | | | | |
| | | | | | | |
+----------+----------+----------+----------+----------+----------+----------+

| | | | | | | |
| | | | | | | |
+----------+----------+----------+----------+----------+----------+----------+ 

(Sorry for my terrible ASCII art)

And now you only check with which zones a dirty sprite collides and mark these zones dirty. So with each sprite (changing number) you have to go through all zones (fixed number) to find out the dirty zones.

I do not understand why the cost to add a dirty rect is proportional to the size of the sprite ( unless you mean marking a zone dirty (wich is setting a flag) but you have to iterate over all zones anyway). That the cost does not increase if there are a lots of dirty rects is true because of the fixed number of zones.

And what if you have very small sprites (4 pixels)? Suppose following case (ok, its a worst case):


+----------+----------+----------+----------+----------+----------+----------+

| | X | X | | | | |
| | +-- |--+ | | | | |
+----------+-------|--+---|-------+----------+----------+----------+----------+

| | +-- |--+ | | | | |
| | X | X | | | | |
+----------+----------+----------+----------+----------+----------+----------+


for that case you have to update the four zones with a X, which is a much bigger area then only the sprite (unless you make a zone == 1 pixel which probably is inefficient).

Perhaps its a good approach if you have, for example, a particle system. Then you only have to dirty the bounding rectangle (if the paritcles a not spread over the entire screen) instead of a big number of tiny rects (I do not know which cost is higher, to update many dirty tiny rect or to update more pixels with lesser number of rects)

Anyway I attached an image (sorry for the bad resolution but I can not send bigger sized images) of what my algorithme would produce. The white rectangles are the result of my code ( the red ones are from my old optimiziation code (not the filled with red, only the ones with red border, zoom in to see it better). As you can see there are still overlappings of white bordered rects, but at least, it make only one rect at areas with heavy overlapings of sprites. Thats ok because the area of the union of these two rect would have been bigger as the two rects together (and to calculate the the minimal area in terms of rectangles would be very complicated because you have to cut rectangles and I do not know how to do that and in which way to obtain the minimal number of rects). And your right, the cost to add a dirty rect increases with the number of dirty areas but the number of dirty areas is keep at a minimum.

~DR0ID

GIF image