How to avoid copying the level Surface every frame in worms-like game?

Question

I am working on a game that has destructible terrain (like in the game Worms, or Scorched Earth) and uses pixel perfect collision detection via masks.

The level is a single surface and how it works now is that I create a copy every frame, draw all sprites that need drawing on it, then blit the visible area to the display surface.

Is there any way to avoid copying the whole level surface every frame and still be able to use the pixel perfect collision tools found in pygame?

I tried blitting the level surface first, then blitting every sprite on the screen (with their blit coordinates adjusted by the camera, except for the player character whose coordinates are static), but in that case the collision detection system falls apart and I can't seem to be able to fix it.

UPDATE

I have managed to make it work the following way: When drawing the sprites, I convert their game world coordinates (which are basically coordinates relative to the origin of the level bitmap) to screen coordinates (coordinates relative to the camera, which is the currently visible area of the level).

During the collision detection phase I use the coordinates and bounding boxes that are positioned relative to the level surface; so just like above. The thing is that the camera's position is bound to the player's position which is not and should not have been a static value (I am really not sure how I managed to not realize that for so long).

While this fixes my problem, the answer below is a much more comprehensive look on how to improve performance in a situation like this. I am also open to suggestions to use other libraries that would make the ordeal easier, or faster. I have thought about pyglet and rabbyt, but it looks like the same problem exists there.

Answer 1

This is an issue that used to come up a lot in the days before graphics accelerators, when computers were slow. You basically want to minimize the work required to refresh the screen. You are on the right track, but I recommend the following:

1. Keep a copy of the background available offscreen, as you are doing now.

2. Allocate a working bitmap that is the same size as the screen.

3. For each sprite, compute the bounding rectangle (bounding box) for its new and old positions.

4. If the new and old bounding boxes overlap, combine them into one larger box. If they do not overlap, treat them separately.

5. Group all the bounding boxes into sets that overlap. They might all end up in one set (when the sprites are close to each other), or each bounding box might be in a set by itself (when the sprites are far apart).

6. Copy the background to regions of the working bitmap corresponding to each bounding box set.

7. Copy the sprites for each set to the working bitmap in their new positions (in the correct z-order, of course!).

8. Finally, copy the finished offscreen bitmap to the display surface, set bounding box by set bounding box.

This approach minimizes the amount of copying that you have to do, both of background and sprite. If the sprites are small relative to the display area, the savings should be significant. The worst case is where the sprites are all arranged on a diagonal line, just barely overlapping each other. In this case, you might want to switch to a more generalized bounding shape than a box. Take a look at QuickDraw Regions for an example: Wikipedia Discussion Patent Source.

Now, you may be thinking that the work to group the bounding boxes into sets is a O(n^2) operation, and you would be right. But it grows only with the square of the number of sprites. 16 sprites implies 256 comparisons. That's probably less work than a single sprite blit.

I focused on minimizing the pixel copying work. I must admin I am not familiar with the particulars of your collision detection library, but I get the idea. Hopefully that is compatible with the algorithm I have proposed.

Good luck. If you finish the game and post it online, put a link to it in your question or a comment.