Bounding Rectangle Collision Test
Collision testing is fast for your average, reasonable game. But what if you have several hundred or a thousand or more sprites on the screen at once, and each one needs to be included in collision testing? The number of collision tests that must be performed is equal to the square of the number of sprites. So, if there are 100 sprites, there will be 10,000 collision tests. A quick and fairly easy optimization of the collision testing system is possible here. Rather than testing every sprite with every other sprite, twice through the loop, it would be better to run two loops and compare every even sprite with every odd sprite in the list. This is something to keep in mind if you create a game that will require a lot of collision tests (which is not the norm).
The CollisionDemo (bounding rectangle version) is really fascinating to watch because it draws translucent boxes over the sprites when collisions occur. Figure 9.1 shows the program running, while Figure 9.2 shows some stats. The program does not run very well with a large number of sprites, mainly due to the boxes being rendered each time. If you have 1,000 sprites—with a corresponding 1,000,000 collision tests—then there could be upwards of 20,000 or so collision events per frame. The boxes are automatically removed after a few milliseconds, but they still slow down the program. But, it does run nicely with 100 or so sprites (which is far more than what you will usually find in a game during a single frame).
Figure 9.1. The CollisionDemo program demonstrates bounding rectangle collision detection using translucent collision boxes.
Figure 9.2. The stats of the CollisionDemo program show that the translucent boxes really hurt performance!
Let’s see the source code for the CollisionDemo_BR program (which focuses on the bounding rectangle method). We’re getting a bit ahead of ourselves here by using the unknown Console class, but I wanted you to see the results of the collision test without interrupting the subject at hand. The source code for Console is provided in the next chapter.
#include "..EngineAdvanced2D.h"
using namespace Advanced2D;
#define SCREENW 1024
#define SCREENH 768
#define OBJECT_BACKGROUND 1
#define OBJECT_SPRITE 100
#define MAX 40
Texture *asteroid_image;
Font *font;
Console *console;
std::ostringstream ostr;
Texture *collisionBox;
int collisions;
bool game_preload()
{
g_engine->setAppTitle("COLLISION DEMO");
g_engine->setFullscreen(false);
g_engine->setScreenWidth(SCREENW);
g_engine->setScreenHeight(SCREENH);
g_engine->setColorDepth(32);
return 1;
}
bool game_init(HWND)
{
//load background image
Sprite *background = new Sprite();
if (!background->loadImage("orion.bmp")) {
g_engine->message("Error loading orion.bmp");
return false;
}
background->setObjectType(OBJECT_BACKGROUND);
background->setCollidable(false);
g_engine->addEntity(background);
//create the console
console = new Console();
if (!console->init()) {
g_engine->message("Error initializing console");
return false;
}
//load asteroid image
asteroid_image = new Texture();
if (!asteroid_image->Load("asteroid.tga")) {
g_engine->message("Error loading asteroid.tga");
return false;
}
//create asteroid sprites
Sprite *asteroid;
for (int n=0; n < MAX; n++)
{
//create a new asteroid sprite
asteroid = new Sprite();
asteroid->setObjectType(OBJECT_SPRITE);
ostr.str(""); ostr << "ASTEROID" << n;
asteroid->setName(ostr.str());
asteroid->setImage(asteroid_image);
asteroid->setScale( (float)(rand() % 150 + 50) / 100.0f );
//set animation properties
asteroid->setTotalFrames(64);
asteroid->setColumns(8);
asteroid->setSize(60,60);
asteroid->setPosition( rand() % SCREENW, rand() % SCREENH );
asteroid->setFrameTimer( rand() % 90 + 10 );
asteroid->setCurrentFrame( rand() % 64 );
if (rand()%2= =0) asteroid->setAnimationDirection(-1);
//set movement properties
float vx = (float)(rand()%10 - 5)/10.0f;
float vy = (float)(rand()%10 - 5)/10.0f;
asteroid->setVelocity( vx, vy );
//collision toggle
asteroid->setCollidable(true);
//movement timer keeps sprite consistent at any framerate
asteroid->setMoveTimer( 16 );
//add asteroid to the entity manager
g_engine->addEntity(asteroid);
}
//load the Verdana10 font
font = new Font();
if (!font->loadImage("verdana10.tga")) {
g_engine->message("Error loading verdana10.tga");
return false;
}
font->setColumns(16);
font->setCharSize(20,16);
if (!font->loadWidthData("verdana10.dat")) {
g_engine->message("Error loading verdana10.dat");
return false;
}
//load highlight image used to show collisions
collisionBox = new Texture();
if (!collisionBox->Load("highlight.tga")) {
g_engine->message("Error loading highlight.tga");
return false;
}
return true;
}
void updateConsole()
{
int y = 0;
console->print(g_engine->getVersionText(), y++);
y++;
ostr.str("");
ostr << "SCREEN : " << (float)(1000.0f/g_engine->getFrameRate_real())
<< " ms (" << g_engine->getFrameRate_real() << " fps)";
console->print(ostr.str(), y++);
y++;
ostr.str("");
ostr << "CORE : " << (float)(1000.0f/g_engine->getFrameRate_core())
<< " ms (" << g_engine->getFrameRate_core() << " fps)";
console->print(ostr.str(), y++);
ostr.str("");
ostr << "Processor throttling: " << g_engine->getMaximizeProcessor();
console->print(ostr.str(), y++);
y++;
ostr.str("");
ostr << "Screen: " << g_engine->getScreenWidth() << ","
<< g_engine->getScreenHeight() << "," << g_engine->getColorDepth();
console->print(ostr.str(), y++);
y++;
ostr.str("");
ostr << "Entities: " << g_engine->getEntityCount();
console->print(ostr.str(), y++);
ostr.str("");
ostr << "Collisions: " << collisions;
console->print(ostr.str(), y++);
y++;
ostr.str("");
ostr << "Press F2 to toggle Processor Throttling";
console->print(ostr.str(), 27);
}
void game_update()
{
updateConsole();
collisions = 0;
}
void game_render3d()
{
g_engine->ClearScene(D3DCOLOR_XRGB(0,0,80));
g_engine->SetIdentity();
}
void game_render2d()
{
font->Print(1,SCREENH-20,"Press ~ or F12 to toggle the Console");
//draw console
if (console->isShowing()) console->draw();
}
void game_keyRelease(int key)
{
switch (key) {
case DIK_ESCAPE:
g_engine->Close();
break;
case DIK_F12:
case DIK_GRAVE:
console->setShowing( !console->isShowing() );
break;
case DIK_F2:
g_engine->setMaximizeProcessor(!g_engine->getMaximizeProcessor());
break;
}
}
void game_end()
{
delete console;
delete asteroid_image;
delete font;
}
void game_entityUpdate(Advanced2D::Entity* entity)
{
switch(entity->getObjectType())
{
case OBJECT_SPRITE:
Sprite* spr = (Sprite*)entity;
if (spr->getX() < -60) spr->setX(SCREENW);
if (spr->getX() > SCREENW) spr->setX(-60);
if (spr->getY() < -60) spr->setY(SCREENH);
if (spr->getY() > SCREENH) spr->setY(-60);
break;
}
}
void game_entityCollision(Advanced2D::Entity* entity1,Advanced2D::Entity* entity2)
{
Sprite *box;
Sprite *a = (Sprite*)entity1;
Sprite *b = (Sprite*)entity2;
if (a->getObjectType() == OBJECT_SPRITE && b->getObjectType() == OBJECT_SPRITE)
{
collisions++;
//add first collision box
box = new Sprite();
box->setColor(0x33DD4444);
box->setImage(collisionBox);
box->setPosition( a->getPosition() );
box->setScale( a->getWidth() * a->getScale() / 100.0f );
box->setLifetime(100);
g_engine->addEntity( box );
//add second collision box
box = new Sprite();
box->setColor(0x33DD4444);
box->setImage(collisionBox);
box->setPosition( b->getPosition() );
box->setScale( b->getWidth() * b->getScale() / 100.0f );
box->setLifetime(100);
g_engine->addEntity( box );
}
}
void game_keyPress(int key) { }
void game_mouseButton(int button) { }
void game_mouseMotion(int x,int y) { }
void game_mouseMove(int x,int y) { }
void game_mouseWheel(int wheel) { }
void game_entityRender(Advanced2D::Entity* entity) { }One of the most obvious performance improvements that can be made to a 2D game is in the collision detection department. Figure 9.3 shows the same CollisionDemo program running, but this time there are 1,000 sprites with bounding rectangle collision detection turned on. This demo performs 1,000,000 collision tests, each of which requires a call to the isInside function—so, one conditional and four function calls, times 1,000,000, every frame. The framerate has dropped to 2 fps, which is slideshow rate.
Although one may argue that 1,000 sprites is a gross exaggeration of what will ever be found in a real game, the exaggeration helps to identify bottlenecks that slow down the engine. Here’s a good question: What if you just want to draw a thousand or so sprites, without concern for collisions? That’s a good point. The Sprite class has a property called collidable (with support methods isCollidable and setCollidable). Turning off collision testing for the asteroid sprites results in a very healthy improvement, as shown in Figure 9.4.
Figure 9.4. The engine supports sprite rendering without collision detection.
What this illustrates is a need for optimization. Before attempting to speed up the code, let’s start with the compiler. If you’re using Visual C++, change the configuration in both the Engine and CollisionDemo projects from Debug to Release build (and perform a Rebuild All), which will automatically optimize the project. If you’re using Dev-C++, open the Project Options and choose Compiler, Optimization, and Best Optimization.
AdviceDev-C++ supports multiple compiler configurations too, but not by default. Open the Tools menu and choose Compiler Options, and you can create new configurations using the dialog that appears (including Debug and Release) and set each configuration using the Settings tab. |
With compiler optimizations turned on for a Release build, the new non-collision results are shown in Figure 9.5. As you can see, the framerate nearly doubled!
But how will the Release build improve the framerate with collisions turned back on? Let’s go back into the game_init function and turn collision back on for all asteroid sprites. When run, the output results in 3 fps, as shown in Figure 9.6. The same 90-percent improvement is seen here, but the small framerate is rounded down (and is really closer to 4 fps).
Figure 9.6. With collisions turned back on, the framerate improved by the same amount (percentage-wise).
Still not satisfied with the result? Sixty million collision tests per second (one million per frame) is some very heavy processing—a heavy load for a game. There is a simpler improvement that can be made here—reducing the number of times collision testing is performed. In a perfect world, where everyone owns a quantum computer that’s capable of performing nearly instantaneous calculations, we could just throw as many collision tests as we want at the engine, and it would handle them with ease.
We would not want to drop the rate to once per second because that would result in noticeable artifacts (such as clear hits going undetected in a high-speed arcade game). In your typical arcade-style shooter, bullets are the fastest sprites, capable of crossing the screen in about one second. That’s a velocity of about 1,000 pixels per second, or one pixel per millisecond—which is extremely fast. Taking that into account and considering that the average sprite is 64 pixels wide, we come up with a figure of 60 fps (~16 ms)—the screen refresh rate. That’s the ideal rate in order to catch all collisions immediately when they occur. But it is simply overkill for a sprite-based game and is an inefficient use of cycles.
A cleaner number is more like 10 to 20 times per second. If we sample collisions at 10 Hz, we can catch fast-moving sprites at a granularity of 100 pixels (at most). Sampling at 20 Hz cuts it down to 50-pixel granularity—that is, the position of the sprite every 50 ms, based on the assumption that the screen contains at least 1,000 pixels in one direction (for instance, horizontally). But remember, these are extremes! We’re just estimating based on the extreme cases, and it’s rare for a sprite to move that fast in practice. At any rate, we should reduce the collision testing to 20 Hz. (Note: This was done retroactively in Engine::Update earlier in the chapter.)
So, what solution can we come up with to improve collision processing to an acceptable level? In addition to the even/odd optimization mentioned earlier, another way to optimize the sprite collision system is by dividing the screen up into partitions or squares and only testing sprites that exist in the same area of the screen (like a 2D version of binary space partitioning, an optimization used to improve 3D games).