Rectangle problem

[stuartbrockman]

Hi,
I am currently writing a simple 2D game in C++ and I need an algorithm
to help me decide which areas of the screen need redrawing. Each of
the entities on screen that have updated in a particular frame add
themselves to a vector maintained by a "ScreenManager" class and I
have their bounding rectangles. Unfortunately, many of these entities
are overlapping and performance is an issue, so I am looking for an
algorithm to simplify the job to be done.

To simplify the problem, say I have a struct:

struct Rect{
Rect(int x, int y, int width, int height);
int x, y, width, height;
};

I would like to have a function that takes a std::vector<Rect> and
returns another std::vector<Rect>, except that in the new vector, none
of the Rect's are overlapping, but they still cover the same screen
area.

e.g Say I have a Rect(1,1,10,10) and a Rect(5,5,10,10), the function
would return {Rect(1,1,10,10), Rect(5,11,10,4), Rect(11,5,4,4)} or
something equivalent.

Note that in the actual game, there would be more than two Rect's. And
they may be overlapping (or not) in any way.

Does anybody have any idea where I could start on this? The algorithm
is easy to do in my head with a pen and paper, but I can't seem to
work out how to do it in code.

 

[Juha Nieminen]

I am currently writing a simple 2D game in C++ and I need an algorithm
to help me decide which areas of the screen need redrawing.

Not an answer to your question, but if you are using some kind of
graphics library which takes advantage of hardware acceleration (which
is more the rule than the exception in current computers), the need to
refresh only the changed parts of the screen is mostly a thing of the
past. Refreshing the entire screen (or application window) every time
anything changes is usually so light with hardware acceleration
(especially for 2D games) that it's a non-issue.
From experience I can say that you can draw eg. 10 screen-sized
alpha-channeled bitmaps on the screen, each over the previous ones, plus
a couple dozens of smaller images, 50 times per second, and even a
low-end (but modern) CPU won't even hit 30% of usage.

Of course if you are drawing purely in software mode, without any
hardware acceleration, that's a completely different issue.