Optimizing Update Rectangles

i’ve written some code that takes a list of rectangles and
resizes them and breaks them (only when needed) so that there
are no overlapping areas.

thinking this could be a clever tool, i plugged it into the
aliens demo. sadly, it ends up running noticeably slower than
without it.

the aliens demo should make a pretty good testbed too, since
it is creating two very overlapping update rectangles for every
sprite (one for the clear, one for the draw)

i believe the flaw comes from the painful method of searching
through all the rectangles comparing to all the other rectangles.
this gives me exponential slowdown for each rectangle in the list.

perhaps there is a better way to do this? i suppose the best method
would be to adjust the game’s logic to not create overlapping rects.

ohwell, unless someone can think of some shining improvement on
something like this it’s going to the scrapper. file it under the
"now i know" cabinet.

not really needing any help, but just thought i’d throw this out
the to pool of many brains before i really do can it. if anyone
wants the code i’ll post it.

Pete Shinners wrote:

i’ve written some code that takes a list of rectangles and
resizes them and breaks them (only when needed) so that there
are no overlapping areas.

I did something similar once, but I only combined rects that are
completely inside each other. Sort of a trade off of processing
versus overdraw.

It’s probably best to do it as you add them into the list, so
that the list won’t grow to as large a size when you do your
searching…

Pete Shinners wrote:

i’ve written some code that takes a list of rectangles and
resizes them and breaks them (only when needed) so that there
are no overlapping areas.

I did something similar once, but I only combined rects that are
completely inside each other. Sort of a trade off of processing
versus overdraw.

It’s probably best to do it as you add them into the list, so
that the list won’t grow to as large a size when you do your
searching…

Take a look at Maelstrom for one way to do it.

See ya!
-Sam Lantinga, Lead Programmer, Loki Entertainment Software