8bitrocket.com
3May/090

Tutorial: Clearing a blit canvas by erasing only the portions that have changed (using damage maps or a dirty rect).

Tutorial: Clearing a blit canvas by erasing only the portions that have
changed. This is commonly called damage mapping or  dirty rect processing.

(Squize called this a Damage Map. I have heard that before but didn't know that it was basically what I was doing here).

That's a mouthful, but I had trouble coming up with a shorter, more
informative title...

DAMAGE MAPPING!

I am currently working on a mini-retro remake of the game Star Castle
called Solar
Fortress
. I am at the point in my code design where I need
to figure out how I am going to render my particle and special effects
to the screen. Most of the current game objects are standard sprites
with BitmapData making up their look (an embedded Bitmap Object with a
BitmapData attached). For the the special effects and particles, I am
planning to blit to a layer on top of the main screen. I was about to
start writing this code as I would any standard set of blit operations
when I was side tracked by an old book on game programming my Andre
LaMothe.

In this classic book on DOS games, Andre
spills the beans on a number of classic game programming secrets such
as blitting, sprites, image compression (RLE), transparency, and much
more.
While waiting for Steve to finish up a conference call, I sat at his
desk perusing this classic gem. In his chapter on sprites and
blitting, Andre wrote about a method for refreshing the a blit screen
that I had never tried. Usually, I refresh the entire viewable blit
canvas with the background layer before I start to blit the individual
sprites to the canvas. Andre's method was quite different.

Inside the loop where he updates and blits each object, he first copies
the background under object and replaces the foreground screen location
of the object with the background, effectively erasing the object only.
Then, he copies the object to its new location on the screen. Thus, he
only  updates the screen portions that have changed.

I decided to test this method in AS3 against my normal copyPixels
screen erase and against a method of simply
clearing the background with a solid color using the
fillRect()
of the BitmapData object.

Below is a swf with the results of the tests. This swf blits 6,000
moving 10x10 squares to the screen
using my (and Chris Cutler's)  optimized
sleep based active timer
. It runs though each of the
three
methods for 100 frames. Before and after each frame it uses a
getTimer()
operation to count the milliseconds passed and adds that to a total.
After 100 frames it divides that total number by 100 to get the average
number of milliseconds. It does this separately  for each of
the three different methods.

This
was written as a very quick and dirty test. The results in the
browsers and players I have seen generally show that the new method
(erase just the
portion that has changed)  to run faster than the other 2
methods.
They are all very close though.  This is a little surprising
to me because with 6,000 objects I would have thought the extra 5,999
blit
operations (although small) would take more more time than the one full
screen erase operation. If you run the test multiple times you will get
slightly varying results. Generally though, they methods rank like this:

Fastest: to Slowest:

1. Just erase screen parts that have changed

2. FillRect() with a solid color - unusable though if you background is
NOT a solid color or is a transparent layer on top of the game player
(like mine will be).

3. Use copyPiixels to re-draw the entire back ground each frame.

Here is an explanation of the three methods. If you need some basics
on my blitting code, try
this tutorial
. After these explanations, the
swf has been embedded for you to try. The entire main class follows
that so you can test out the code if you desire.

Method 1: CopyPixels
Entire Background

In this method (my normal method), at the start of each render cycle, I
erase the blit canvas by copying the entire background BitmapData to
it. I then blit each object into its new position.   With 6000
objects, this equals 6001 blit operations per frame cycle.

[cc lang="javascript" width="550"]canvasBD.copyPixels(backgroundBD, backgroundBD.rect,backgroundPoint);[/cc]
Then update each object and blit it to to the canvasBD
 

(loop through objects for run this code for
each)

[cc lang="javascript" width="550"]
blitPoint.x = tempObject.x;
blitPoint.y = tempObject.y;
canvasBD.copyPixels(objectBD, objectBD.rect, blitPoint);[/cc]

Method 2: fillRect()

This method is only possible because I have a solid back background. I
would not be able to use the BitmapData.fillRect() method with a
detailed
background. There is a way to use the Sprite.beginBitmapFill() method,
but that was out of the scope of this test. It also would have been
invalid because it would have required a different canvas for the
Background (a separate Sprite). In my version of  this method,
at the start of the render cycle I simply fill the background canvas
with black and then do the 6000 blit operations.
 

[cc lang="javascript" width="550"]canvasBD.fillRect(canvasBD.rect, 0xFF000000);[/cc]
Then update each object and blit it to to the canvasBD:
 

(loop through objects for run this code for
each)

[cc lang="javascript" width="550"]
blitPoint.x = tempObject.x;
blitPoint.y = tempObject.y;[/cc]
canvasBD.copyPixels(objectBD, objectBD.rect, blitPoint);[/cc]

Method 3: Erase Updated
Background Only

In this method, I do NOT erase or fill the background canvas before I
begin the 6000 blit operations. I actually do 12,000 blit operations.
For each object I first blit the the background under it to its current
position as an eraser, then update the object's position and then blit
back into its new location.
 

Before Objects are updated

(loop through objects for run this code for
each)

[cc lang="javascript" width="550"]
blitPoint.x = tempObject.x;
blitPoint.y = tempObject.y;
canvasBD.copyPixels(backgroundBD, objectBD.rect, blitPoint);
 [/cc]

Then update the  object positions, animation frame, etc and
then run this code:

[cc lang="javascript" width="550"]
blitPoint.x = tempObject.x;
blitPoint.y = tempObject.y;
canvasBD.copyPixels(objectBD, objectBD.rect, blitPoint);
[/cc]

What is it doing:  
While looping though all of the objects in the array (of particles for instance), it first blits from the background (backgroundBD) to the viewable canvas (canvasBD)

Next, it assumes that your code updates the position and or animation frame of the object and then it blits the bitmapData containing the object (objectBD in this example) to the canvas (canvasBD).


Results

Generally, I have found a 2 or 3 millisecond average speed increase per
frame tick by just erasing the portion of the screen for each object
that has changed. Also, the fillRect() operations seems to be a
little faster (generally) than the copyPixels operation.  This
is the result for 6000 objects, using my optimized timer for 100
frames.
I have provided the code so you can test it out (if you desire) with
more or less objects and more or less frames. I have found that the
results are a little different with fewer objects. With just 1-50
objects on the screen, Method 3 seems to be much faster, but as you add
objects (under 1000), the results are mixed. When you get up to 5000,
clearly the Erase Only the Updated Portion (Method 3) comes out on top
more often.

Still, I don't see using any of these methods as a problem. I
am going to use the new method for my current game though just because
it is new and I can.

Test it for your self and let me know if you see similar results.

 

[cc lang="javascript" width="550"]
package
{
import flash.display.*;
import flash.text.*;
import flash.geom.*;
import flash.events.*;
import flash.events.TimerEvent;
import flash.utils.Timer;
import flash.utils.getTimer;
/**
* ...
* @author Jeff Fulton
*/
public class Main extends Sprite
{
 

private var mode:Function;
//gameTimer
public static const FRAME_RATE:int = 40;
public var _period:Number = 1000 / FRAME_RATE;
public var _beforeTime:int = 0;
public var _afterTime:int = 0;
public var _timeDiff:int = 0;
public var _sleepTime:int = 0;
public var _overSleepTime:int = 0;
public var _excess:int = 0;
public var gameTimer:Timer;
private var rformat:TextFormat = new TextFormat("_sans","12","0xffffff","true");
private var messagetext:TextField = new TextField();
private var aKeyPress:Array=[];

private var backgroundBD:BitmapData = new BitmapData(400, 400, false, 0x000000);
private var canvasBD:BitmapData = new BitmapData(400, 400, true, 0xFF000000);
private var canvasBitmap:Bitmap = new Bitmap(canvasBD);

private var objectBD:BitmapData = new BitmapData(5, 5, false, 0xff0000);
private var aObject:Array = [];
private var tempObject:Object;
private var blitPoint:Point = new Point();
private var backgroundPoint:Point = new Point(0, 0);

private var startTime:Number;
private var endTime:Number;
private var totalTime:Number;

private var resultCopypixels:Number;
private var resultBitmapfill:Number;
private var resultBliterase:Number;

private var numObjects:int = 6000;
private var numFrames:int = 100;
private var frameCtr:int = 0;

public function Main()
{

for (var ctr:int = 0; ctr < numObjects; ctr++) {
//trace("creating object: " + ctr);
var tempObjectCreate:Object = new Object();
tempObjectCreate.x = 0;
tempObjectCreate.y = 0;
tempObjectCreate.dx = 0;
tempObjectCreate.dy = 0;
tempObjectCreate.bitmapData = objectBD;
aObject.push(tempObjectCreate);
}

addChild(canvasBitmap);
mode = modeMenuSetup;
//gameTimer=new Timer(_period,0);
gameTimer=new Timer(_period,1);
gameTimer.addEventListener(TimerEvent.TIMER, runGame);
gameTimer.start();
}

public function runGame1(e:TimerEvent):void {
mode(0);
e.updateAfterEvent();
}

public function runGame(e:TimerEvent):void {
//trace("run game");
_beforeTime = getTimer();
_overSleepTime = (_beforeTime - _afterTime) - _sleepTime;

//****run the current system function
mode(0);
//***********************************

_afterTime = getTimer();
_timeDiff = _afterTime - _beforeTime;
_sleepTime = (_period - _timeDiff) - _overSleepTime;
if (_sleepTime <= 0) {
_excess -= _sleepTime
_sleepTime = 2;
}
gameTimer.reset();
gameTimer.delay = _sleepTime;
gameTimer.start();
while (_excess > _period) {
//****run the current system function
mode(1);
//***********************************

_excess -= _period;
}

e.updateAfterEvent();
}
private function modeMenuSetup(updatetype:int):void {
stage.addEventListener(KeyboardEvent.KEY_DOWN,keyDownListener);
stage.addEventListener(KeyboardEvent.KEY_UP, keyUpListener);
messagetext.width = 250;
messagetext.height = 200;
messagetext.x = 60;
messagetext.y = 100;
messagetext.text = "This will test 3 different methods of
nrefreshing the backgroundn
after a set of blit operationsnnPress Space to Start Test";
rformat.align = "center";
messagetext.setTextFormat(rformat);
addChild(messagetext);

mode = modeMenuRun;

}

private function modeMenuRun(updatetype:int):void {
if (aKeyPress[32]) {
trace("space pressed");
mode = modeSetupCopypixels;
}
}

private function modeSetupCopypixels(updatetype:int):void {

for (var ctr:int = 0; ctr < numObjects;ctr++ ) {
tempObject = aObject[ctr];
tempObject.x = (Math.random() * 399);
tempObject.y = (Math.random() * 399);
var randInt:int=int(Math.random()*36);
tempObject.dx=Math.cos(2.0*Math.PI*((randInt*10)-90)/360.0);
tempObject.dy = Math.sin(2.0 * Math.PI * ((randInt * 10) - 90) / 360.0);
}
//trace("all object reset");
//trace("object 1 x=" + aObject[1].x);
messagetext.text="Running copyPixels test"
messagetext.setTextFormat(rformat);
frameCtr = 0;
resultCopypixels = 0;
totalTime = 0;
mode = modeRunCopypixels;
}

private function modeRunCopypixels(updateType:int):void {
startTime = getTimer();
switch (updateType) {

case 0:
backgroundBD.lock();
drawCopypixelsBackground();
updateAndDrawCopypixelsObjects();
backgroundBD.unlock();
break;
case 1:
updateAndDrawCopypixelsObjects();
break;

}
endTime = getTimer();
totalTime += (endTime-startTime);
frameCtr++;
//trace("frameCtr="+frameCtr);
if (frameCtr == numFrames) {

resultCopypixels = (totalTime/numFrames);
trace("copypixels result=" + resultCopypixels);
mode = modeSetupBitmapfill;
}
}

private function updateAndDrawCopypixelsObjects():void {

//trace("object 1 again x=" + aObject[1].x);
for (var ctr:int = 0; ctr < numObjects;ctr++ ) {
tempObject = aObject[ctr];
tempObject.x += tempObject.dx;
tempObject.y += tempObject.dy;
if (tempObject.x > 399) {
tempObject.x = 0;
}else if (tempObject.x<0) {
tempObject.x = 399;
}

if (tempObject.y > 399) {
tempObject.y = 0;
}else if (tempObject.y<0) {
tempObject.y = 399;
}

blitPoint.x = tempObject.x;
blitPoint.y = tempObject.y;
//trace("blitPoint=" + blitPoint.toString());
canvasBD.copyPixels(objectBD, objectBD.rect, blitPoint);

}

}

private function drawCopypixelsBackground():void {
canvasBD.copyPixels(backgroundBD, backgroundBD.rect,backgroundPoint);
}

private function modeSetupBitmapfill(updatetype:int):void {
for (var ctr:int = 0; ctr < numObjects;ctr++ ) {
tempObject = aObject[ctr];
tempObject.x = (Math.random() * 399);
tempObject.y = (Math.random() * 399);
var randInt:int=int(Math.random()*36);
tempObject.dx=Math.cos(2.0*Math.PI*((randInt*10)-90)/360.0);
tempObject.dy = Math.sin(2.0 * Math.PI * ((randInt * 10) - 90) / 360.0);
}
messagetext.text = "Running fillRect test";
messagetext.setTextFormat(rformat);
frameCtr = 0;
resultBitmapfill = 0;
totalTime = 0;
mode = modeRunBitmapfill;
}

private function modeRunBitmapfill(updateType:int):void {
startTime = getTimer();
switch (updateType) {

case 0:
backgroundBD.lock();
drawBitmapfillBackground();
updateAndDrawBitmapfillObjects();
backgroundBD.unlock();
break;
case 1:
updateAndDrawBitmapfillObjects();
break;

}
endTime = getTimer();
totalTime += (endTime-startTime);
frameCtr++;
//trace("frameCtr="+frameCtr);
if (frameCtr == numFrames) {
resultBitmapfill =(totalTime/numFrames);
trace("bitmapfill result=" + resultBitmapfill);
mode = modeSetupBliterase;
}
}

private function updateAndDrawBitmapfillObjects():void {

//trace("object 1 again x=" + aObject[1].x);
for (var ctr:int = 0; ctr < numObjects;ctr++ ) {
tempObject = aObject[ctr];
tempObject.x += tempObject.dx;
tempObject.y += tempObject.dy;
if (tempObject.x > 399) {
tempObject.x = 0;
}else if (tempObject.x<0) {
tempObject.x = 399;
}
if (tempObject.y > 399) {
tempObject.y = 0;
}else if (tempObject.y<0) {
tempObject.y = 399;
}

blitPoint.x = tempObject.x;
blitPoint.y = tempObject.y;
//trace("blitPoint=" + blitPoint.toString());
canvasBD.copyPixels(objectBD, objectBD.rect, blitPoint);

}

}

private function drawBitmapfillBackground():void {
canvasBD.fillRect(canvasBD.rect, 0xFF000000);
}

private function modeSetupBliterase(updatetype:int):void {
for (var ctr:int = 0; ctr < numObjects;ctr++ ) {
tempObject = aObject[ctr];
tempObject.x = (Math.random() * 399);
tempObject.y = (Math.random() * 399);
var randInt:int=int(Math.random()*36);
tempObject.dx=Math.cos(2.0*Math.PI*((randInt*10)-90)/360.0);
tempObject.dy = Math.sin(2.0 * Math.PI * ((randInt * 10) - 90) / 360.0);
}
messagetext.text = "Running bliterase test";
messagetext.setTextFormat(rformat);
frameCtr = 0;
resultBliterase = 0;
totalTime = 0;
startTime = getTimer();
mode = modeRunBliterase;
}
private function modeRunBliterase(updateType:int):void {
startTime = getTimer();
switch (updateType) {

case 0:
backgroundBD.lock();
drawBitmapfillBackground();
updateAndDrawBitmapfillObjects();
backgroundBD.unlock();
break;
case 1:
updateAndDrawBitmapfillObjects();
break;

}
endTime = getTimer();
totalTime += (endTime-startTime);
frameCtr++;
//trace("frameCtr="+frameCtr);
if (frameCtr == numFrames) {

endTime = getTimer();
resultBliterase =(totalTime/numFrames);
trace("bliterase result=" + resultBliterase);
mode = modeResultsSetup;
}
}

private function updateAndDrawBliteraseObjects():void {

//trace("object 1 again x=" + aObject[1].x);
for (var ctr:int = 0; ctr < numObjects; ctr++ ) {
blitPoint.x = tempObject.x;
blitPoint.y = tempObject.y;
canvasBD.copyPixels(backgroundBD, objectBD.rect, blitPoint);
tempObject = aObject[ctr];
tempObject.x += tempObject.dx;
tempObject.y += tempObject.dy;
if (tempObject.x > 399) {
tempObject.x = 0;
}else if (tempObject.x<0) {
tempObject.x = 399;
}

if (tempObject.y > 399) {
tempObject.y = 0;
}else if (tempObject.y<0) {
tempObject.y = 399;
}

blitPoint.x = tempObject.x;
blitPoint.y = tempObject.y;
canvasBD.copyPixels(objectBD, objectBD.rect, blitPoint);

}

}

private function modeResultsSetup(updateType:int):void {
canvasBD.copyPixels(backgroundBD, backgroundBD.rect,backgroundPoint);

messagetext.text = "Results (avg milliseconds):nCopypixels: " + resultCopypixels +
" millisecondsnBitmapfill: " + resultBitmapfill + " millisecondsnBliterase: " +
resultBliterase + " milliseconds"+"nn[R] to run again.";
messagetext.setTextFormat(rformat);
mode = modeResultsrun;
}

private function modeResultsrun(updateType:int):void {
if (aKeyPress[82]) {
for (var ctr:int = 0; ctr < numObjects;ctr++ ) {
tempObject = aObject[ctr];
tempObject = null;
}
mode = modeMenuSetup;
}

}

private function keyDownListener(e:KeyboardEvent):void {
trace(e.keyCode);
aKeyPress[e.keyCode]=true;

}

private function keyUpListener(e:KeyboardEvent):void {
aKeyPress[e.keyCode]=false;
}
}

}
[/cc]

That's all of the code. You can use it as the Main class in a Flex
project or as the document class in a Flash project. It will work
either way.

Beyond:

There are other optimizations that can be used in conjunction with this
code to further control when the screen is updated. One thing I would
add is the ability to not update an object if it hasn't changes. If an
object is simply stationary (x+dx=x and y+dy=y) on a frame, then do
NOTHING to it. Don't erase it, don't re-blit it, just leave it alone.
Another would be to further optimized the animation render by not
updating an object if the same frame of object animation is being
displayed  on this timer tick as was displayed in the previous
timer tick.

If you enjoyed this post, please consider leaving a comment or subscribing to the RSS feed to have future articles delivered to your feed reader.
Comments (0) Trackbacks (0)

No comments yet.


Leave a comment

No trackbacks yet.

This site is protected by Comment SPAM Wiper.