Archived

This topic is now archived and is closed to further replies.

How do professional games handle collision detection?

This topic is 5619 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

How do professional games handle collision detection? I am refering to 2D games such as Diablo II, Fallout, Age of Empires...etc. Anything you can think of. I just want to know how they are checking for collisions, what their methods are for not checking every single thing on the map. Just basically how it all works. -- Tis Me! --

Share this post


Link to post
Share on other sites
What sort of collision detection were you thinking of? Since the games you listed are tile-based, there isn''t much need for conventional collision detection; units just won''t move onto a tile that isn''t passable.



Don''t listen to me. I''ve had too much coffee.

Share this post


Link to post
Share on other sites
How I am working this out is this, and I learnt the method from searches on this board. I forgit who posted it but here goes..


1) load .bmp or whatever

2) build a BOOL *hitmap for each sprite. basically, go thru each pixel during PRE-initialization of the game and if there is any pixel at all, hit=TRUE else hit=FALSE.

3) you want to grab the rectangular region between the two under test, the overlapping region that is when you do your actual collision detection.

4) if ((hitmap(sprite1,i,j) & hitmap(sprite2,x,y)) return 1;
where 1 = collision occured. You could make it int *hitmap and return the specific sprite you collided with.

You first test if your sprite is anywhere near a tile. If not, it is called trivial rejection. If it is, then you mathematically go thru hitmaps of both sprites (or tiles) of interest and if you get a pixel hit then return the hit otherwise return zero.


One of my functions are:

hSprite terrain;
terrain.LoadSpriteBank("tiles.bmp", 4,2, 32,32, RGB(0,0,0),TRUE);

the tiles are 4 rows and 2 columns
tile resolution is 32x32
RGB(0,0,0) is the colorkey I am passing for transparency
and TRUE means to go ahead and build a hitmap for collision purposes.

Then my collision detection is:

col = (CollisionBank(terrain, 5, terrain, 1));

terrain is a class object, from hSprite.


My functions are not yet perfected but I am getting there.. this is my basic collide which works with two different hSprite objects: If anyone sees what I am doing wrong or where I could clean this up at, please let me know. Thanks.


  int Collision(hSprite spr1, hSprite spr2) {
int i, j, nx, ny; // intense debrugging

int col=0, ncx=0, ncy=0, rmax=0;
int dx=spr1.xs;
int dy=spr1.ys;
int sx=spr2.xs;
int sy=spr2.ys;
if ((dx==0) && (dy==0) && (sx==0) && (sy==0)) return(0);
nx = abs(dx-sx); // nx = x offset from border of tile2 into tile1

ny = abs(dy-sy); // ny = y offset from border of tile2 into tile1

rmax = MAX(spr1.xwid, spr2.xwid);

if ((nx > rmax) && (ny > rmax)) return(0); // trivial rejection

ncx=0; ncy=0;

for (j=ny; j < rmax; j++) {
for (i=nx; i < rmax; i++) {
if ((dx <= sx) && (dy <= sy)) {
if (spr1.HitMap[(j*rmax)+i] & spr2.HitMap[(ncy*rmax)+ncx])
return 1;
}
if ((dx > sx) && (dy <= sy)) {
if (spr1.HitMap[(j*rmax)+ncx] & spr2.HitMap[(ncy*rmax)+i])
return 1;
}
if ((dx <= sx) && (dy > sy)) {
if (spr1.HitMap[(ncy*rmax)+i] & spr2.HitMap[(j*rmax)+ncx])
return 1;
}
if ((dx > sx) && (dy > sy)) {
if (spr1.HitMap[(ncy*rmax)+ncx] & spr2.HitMap[(j*rmax)+i])
return 1;
}
ncx++;
}
ncx=0;
ncy++;
}
return col;
}







I fseek, therefore I fam.

Share this post


Link to post
Share on other sites
Thanks for the replies all. And for the code drarem

I was in fact refering to pixel perfect collision detection (sorry, should have been more precise.)
Marking tiles as walkable/nonwalkable is easy but just doesn''t quite cut the cake. I don''t want the character or npcs for that matter to be restricted to the tiles. Plus, there''s always collision with moving objects to worry about...

-- Tis Me! --

Share this post


Link to post
Share on other sites
You don't necessarily have to depend on the graphical tile (the tile block used to represent a visual tile in the world) for collision. what you can do is split each tile into smaller tiles for collision detection alone. The character (taking into consideration of the small area it will occupy) can be placed in one of these smaller tiles and check for collision using this tile. Also you don't need to precalculate these smaller tiles, you can nail down the big_tile in which the character is standing and split this tile further for more accurate collision at runtime.

I really don't think doing pixel perfect collision detection in an isometric game (like AOE) is of any use, and probably won't give any appreciable result. The fact that the characters have a pseudo 3D representation and the bounding rectangle of the character sprite is not really the actual bounding rectangle/box seen through the pseudo 3D world; limits one from using pixel perfect collision detection using the sprite bitmap.






There is no problem so complicated that it cannot be complicated further.

[edited by - aanand_420 on July 23, 2002 3:09:32 PM]

Share this post


Link to post
Share on other sites
Yeah, pixel perfect collision, when you think about it, is really nothing more than passable/nonpassable subtiles like aanand_420 described, but with a tile size of 1 pixel. Ask yourself: do you really need this? Will it justify the significant extra processing cost to be able to move the characters a couple of pixels closer to a wall?



Don''t listen to me. I''ve had too much coffee.

Share this post


Link to post
Share on other sites