[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [pygame] sprite engine and help for algorithme
On 4/29/06, DR0ID <dr0id@xxxxxxxxxx> wrote:
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.
it's proportional to the size of the sprite because the more zones it
covers the more zones you need to update. Also, you don't need to
iterate over the zones, provided you have fixed size zones. You can
figure out what zones a rect will cover directly from the points of
the rect itself.
Lets say that you divide your 800x600 screen horizontally 16 times and
8 times vertically. then each zone is 50x75. so then for a rect
[x1,y1,x2,y2], then you check & update only the zones whose index is
in the rect [floor(x1/50), floor(y1/75),floor(x2/50),floor(y2/75)] No
need to check all 128 zones.
And what if you have very small sprites (4 pixels)? Suppose following
case (ok, its a worst case):
[picture]
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).
Well while you could certainly let each zone simply have a flag that
says whether it's dirty or not, I believe it's more effective to let
each zone contain a single rect to represent what portion of that zone
is dirty, but to add a new rect in the zone, you just do a simple
min-max thing to have the one rect cover the entire area in the zone
that's dirty.
So in the case that you had a small rect dirtying the corner of 4
zones, you can still get the min cover because each zone just has it's
little corner filled. The time where you would have the largest extra
area marked dirty is if you had a tiny little sprite mark the opposite
corners of a zone dirty, in which case the rect for the zone would
expand to cover the whole area.
... also, you can combine splitting up the screen into zones with any
dirty rect aggregating you like - you could even do the algorithm you
posted in each zone in order to combine the dirty rects within it.
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)
My experience with using the zones approach is with a 2d engine that
uses quite a lot of particles with a software-only rendering engine. I
would agree with your assessment, that with a particle system (on the
order of 100's of lots of small rects) is when it really makes sense
as an approach - because that's exactly when a system that just uses a
single dirty rect would have a lot of wasted dirty area, and an
approach that tracks multiple dirty rects would either spend a
moderate amount of time comparing new rects against the other 100's of
rects or would have a lot of overlapping rects, which might cause
other performance problems.