TIGSource Forums

I've tried to implement dirty rectangles in my game but there are so many of them that they actually slow the game down.
The thing is, there are rockets flying all over the screen and in each frame each rocket leave a 1x1px trace behind. There could be as many as a 1000 traces at the same time. The traces slowly fade out, which takes approximately 2 seconds, so I still need to update them pretty often.

So my question, is there a way to implement dirty rects in an elegant and efficient way in my case? Or is it just better to update the whole screen? The framerate was better and it ate less CPU without the dirty rects when there are lots of traces, but with not so many of them the dirty rects give a significant boost in performance.

One solution I have come up with is to disable the dirty rects once there are too many traces on the screen, is it the best I can do?

You could handle the rockets in groups, instead of one at a time.  For example, split the screen into larger squares, and if there are any rockets touching a square, consider the whole square 'dirty' and add just one rect for that square.

If you have that many things moving over that much of the screen, there's not a lot of benefit to using dirty rectangles;  better to just blit the whole screen.  The only time that dirty rectangle systems are really useful is if you have a mostly static screen with only a few dozen moving objects.

(With that said, though, are you merging dirty rectangles which partially overlap or border each other?  Are you padding the width of the dirty rectangles to multiples of 4 bytes?  If not, your dirty rectangle algorithm will run much slower than it could)

I'll try that, thanks.


The thing is those rectangles are 1x1 pixel and very rarely (if ever) overlap. About the padding, what exactly do you mean? Should the rectangles be 64x64?

EDIT:


I divided the screen (1024x768) in 192 64x64 rects. The list of those rects is called 'screen_rects'. Here is how the code checking if a trace obj is inside a certain rectangle looks like:


It's python + pygame. But the code is slow as hell. The game is completely unplayable when he does this every frame. Am I doing something terribly wrong?

That's len(screen_rects)*len(traces) checks per frame. If each moving bullet is in traces, that's a painfully large number of checks.

The problem here isn't dirty rectangles, the problem is that you're running what is roughly an O(N²) algorithm on a large dataset.

If your rectangles are spaced evenly across the screen, you could simply divide each object's position by the known size of the rectangles in order to select a given rectangle by index. At that point, it becomes O(N) instead of O(N²) because you can do a direct lookup (either in a dictionary, or in a jagged array).

The other points about dirty rectangles still stand, though. You're going to want either a very small number of rectangles per paint, or very large rectangles, before you actually see a benefit from using them.

I created a dictionary of the screen rectangles and the reduction of checks from N^2 to N helped, but it's still too slow. Thanks all for your help, I'll try to replace the traces with some kind of lines, if that won't look good I'm back to updating the whole screen every frame. It wasn't that bad after all.

People still use dirty rectangles in 2009?
Unless you're coding for a mobile phone or sthg, just refresh the whole screen.

Does Pygame have anything equivalent to a batch or group where you can draw all the sprites in one call? Or is that just OpenGL (and pyglet I might add ;) )

I'd like to know that too, here's what I did.

Then you can use this like;


Obviously it needs the variable names for things to be the same across classes so it's not fool proof or even very functional.

I’m not sure how much overhead there is but I think you could make it sort the dict for priority and skip the unimportant stuff if it takes too long without too much more effort.

 

Honestly, with that many traces, I think you are hitting the hard limit of Python in terms of speed. Python is slooooooooooooow, but Psyco could be of help to you (module that speeds up execution of Python code).

I'd say use dirty rectangles whenever they're worth it. Memory transfers are not free, even on today's hardware. I even use dirty rectangles on the PS3, which isn't exactly a mobile phone.

I guess this makes sense if you're writing a purely software 2D engine.  I'm not sure exactly why you'd want to do that on PS3 but I have no idea what type of game you're making.