Collision test

Hello
I just wonder what is the best way to make a test collision in a game
including objects such as monster.
I thought about a binary buffer 0=nothing 1=Collision I could use this
buffer as a layer on my screen_buffer,the matter is that it seem to be
very large (if i scroll a 1000x1000 image on a 640x480 screen for example
i ll need another buffer of 1000x1000 !!)
Could you help me ?

Alot of game collisions can be done with bounding boxes using the
sizes of the sprites. You just have to see if any of the corners of
the boxes enter the box and if it does you have a collision. There
should be plenty of reference material on the net for that.

Phoenix Kokido
members.xoom.com/kokido
@Wes_Poole

Franck Nouyriga wrote:> Hello

I just wonder what is the best way to make a test collision in a game
including objects such as monster.
I thought about a binary buffer 0=nothing 1=Collision I could use this
buffer as a layer on my screen_buffer,the matter is that it seem to be
very large (if i scroll a 1000x1000 image on a 640x480 screen for example
i ll need another buffer of 1000x1000 !!)
Could you help me ?

Hello
I just wonder what is the best way to make a test collision in a game
including objects such as monster.
I thought about a binary buffer 0=nothing 1=Collision I could use this
buffer as a layer on my screen_buffer,the matter is that it seem to be
very large (if i scroll a 1000x1000 image on a 640x480 screen for example
i ll need another buffer of 1000x1000 !!)
Could you help me ?

The lame way to do it would be to simply say:

if (monster.x + monster.w >= player.x &&
monster.x <= player.x + player.w &&

``````  monster.y + monster.h >= player.h &&
monster.y <= player.y + player.h)
{
/* Monster is touching player! */
}
``````

This is what I typically do. I adjust sensitivity in favor of the player,
usually. (For example, a playerâs bullet doesnât have to be exactly
hitting the enemy, but the enemyâs bullet has to be a little closer to the
center of the enemy.)

Of course, if youâre looking for more exact collision detection (a la
hardware sprites from things like the Atari 2600), it gets a bit complicated.
Youâll need to somehow keep track of when particular pixels overlap.

For example, consider these really low-resolution characters in a game:

#X#X# %%%

##X## % %

% %

(enemy) (player)

An example of where theyâre screen locations are overlapping (the "if"
expression above would be true), but where the pixels are NOT overlapping,
might be:###
#X#X#

##X##
###%
%%%
%
% %
% %

Close, but no cigar, so to speak.

To speed your code up, I suggest you do the rectangle collision test above.
Then, if itâs true, you then need to see if any of the charactersâ pixels
are colliding for your final test.

How do you do this? Well crap, I didnât think that far. IMO, most of
the games Iâll be writing will be going by so fast that collision
inaccuracies will make no difference. Itâs not like Iâm making a lunar
landar game. (Yet) My objects move sometimes 32 pixels a frame, and
at 20- 30-fps!

Off the top of my head, I think one way would be to have some âmaskâ data
for your important sprites, or if theyâre really large, for the exterior
portions of them. Then do some bitwise AND operations and if thereâs any
"1"s left in the result, youâve got a collision.

Out of curiosity, how do most SDL users here create transparencies in their
sprites? I use R,G,B=255,255,255. The âaliensâ demo program uses whatever
color the topleft corner is. Does anyone here use TIF or GIF format files

â Becoming the âMaster of ASCIIâ on this mailing list, it seems.

Itâs an interesting problem. I guess SDL doesnât have a blit that ANDs the
buffers. Itâd be an interesting function that could hide the implementation from
the user. Iâve never heard of a hardware version of this sort of operation.

-Lea.

The Amiga blitter could do mask collision in hardware. But I donât know
if it was a standard blitter or something different to current gfx card
blitters.

ttfn,
JohnOn Wed, Dec 08, 1999 at 09:29:29AM +0000, Lea Anthony wrote:

Itâs an interesting problem. I guess SDL doesnât have a blit that ANDs the
buffers. Itâd be an interesting function that could hide the implementation from
the user. Iâve never heard of a hardware version of this sort of operation.

Itâs an interesting problem. I guess SDL doesnât have a blit that ANDs the
buffers. Itâd be an interesting function that could hide the implementation from
the user. Iâve never heard of a hardware version of this sort of operation.

Well, back in MY day, the olâ Atari 'puters did JUST that, by golly!
<cough, spit>

Unfortunately, the thing had only 8 sprites. Four 8 pixel by 128-or-256 pixel
"players," and four 2 pixel by 128-or-256 pixel âmissiles.â Each sprite
was two colors. Some color, and clear.

So if you wanted a two color âsprite,â you just ate two players or a player
and some missiles.

But hey, it worked damned well on the old Atari 2600. Thatâs literally
ALL they had. No actual âplayfieldâ bitmaps. It was ALL SPRITES!
(No go fire up your 2600 and contemplate that while playing some of the
better Activision and I-Magic games! )

It was actually kind of interesting how it worked on the Atari. (Iâm sure
the Commodore 64 had a similar hardware-based collision detection system.
I donât know much about sprites on the C=64, except they werenât wacky
bar shapes like P/Mâs on the Atari.)

You would clear a byte in memory called âHITCLR.â Then, after the next frame
had occurred (1/60th of a second laterâŚ), if any players and/or missiles
were touching each other or certain playfield pixels (like part of the
solid part of the letter âXâ on the screen somewhere, for example), certain
bits would be set.

In the PC world, I always thought hardware sprites would have been PERFECT
for mouse pointers and text-insertion cursors. Of course, PCâs are so
fast now that blitting and unblitting a mouse pointer happens WAY quicker
than 60 or 80 times per second, so you never notice any drawingâs going on
at all.

Iâve actually contemplated writing a front-end library for SDL which would
manage sprites and do collision detection. Kind of like a widget set, but
for sprites. NoteâŚ I havenât SERIOUSLY contemplated it, so donât
expect anything any time soon, or even ever.

-bill!

Amiga, being designed by a bunch of the same people who designed the Atari
8-bit computers, probably did have funky super-cool hardware blitting and
collision detection.

Blame Jay Miner (rest in peace) for most of the awesomeness of both systems.

Itâs a shame he never actually stuck around to see what either system could
really do. (Some of the most amazing graphical stuff on the Atari was
done in the early and mid 1990âs by teenage demo coders from Europe.
They must have some helluva and education system, when it comes to math,
over there!)

-bill!> On Wed, Dec 08, 1999 at 09:29:29AM +0000, Lea Anthony wrote:

The Amiga blitter could do mask collision in hardware. But I donât know
if it was a standard blitter or something different to current gfx card
blitters.

Franck Nouyriga wrote:

Hello
I just wonder what is the best way to make a test collision in a game
including objects such as monster.
I thought about a binary buffer 0=nothing 1=Collision I could use this
buffer as a layer on my screen_buffer,the matter is that it seem to be
very large (if i scroll a 1000x1000 image on a 640x480 screen for example
i ll need another buffer of 1000x1000 !!)
Could you help me ?

HmmâŚyour memory calculations seem to be wrong! A 1000x1000x1 buffer
is only 1 million / 8 bytes, or ~122K. I donât think thatâs a lot of
memory, especially since your image buffer can be 16 or even 32 times
this size (depending on your color depth).

Collision detection is effectively a comparison between the overlaps of all of your objects and against every other object (in the extreme case). A lot of heuristics have been developed for speeding up such comparisons. One of the simpler ones is to compute a bounding box for all of your objects to eliminate the objects that obviously donât overlap and canât collide. The tests for overlap of bounding boxes are trivial and should not be too difficult to implement. The 1-bit buffer is very useful for actually detecting collisions if the bounding boxes do overlap, and if even 122K seems excessive to you, then you can just generate a 1-bit buffer of the appropriate size based on the (overlapping) bounding boxes and do it the same way. But IMHO, 122K is a pathetically small amount of memory by todayâs standards and it would be a lot simpler to use the bounding boxes and then check the big buffer.â

| Rafael R. Sevilla @Rafael_R_Sevilla |
| Instrumentation, Robotics, and Control Laboratory |

College of Engineering, University of the Philippines, Diliman

Hello,On Tue, 7 Dec 1999, Franck Nouyriga wrote:

I just wonder what is the best way to make a test collision in a game
including objects such as monster.
I have no programming experience on this subject, but I have seen some
routines for collision detection in the last version of the project
Xgame ( a general graphics library for writing games and Demos)

Xgame - An X11 game programming library

It includes sample code of the library with amazing games and demos.
hope this helps,
bye.
-Hermang

John Marshall wrote:

Itâs an interesting problem. I guess SDL doesnât have a blit that ANDs the
buffers. Itâd be an interesting function that could hide the implementation from
the user. Iâve never heard of a hardware version of this sort of operation.

The Amiga blitter could do mask collision in hardware. But I donât know
if it was a standard blitter or something different to current gfx card
blitters.

It was the first Blitter and it was (and it is, in many ways) more
powerful to current blitters
on current gfx boards.
THat âoldâ blitter can fetch datas from 3 channels (A,B and C) and
perform 256 kind of
logic operations on input channels to produce a single output channel (D
channel).
CUrrent blitters often have 1 input channel and can perform few logic
ops, like XOR,
and thatâs not enough to do collision test.

ciao,
Marco> On Wed, Dec 08, 1999 at 09:29:29AM +0000, Lea Anthony wrote:

Hello!
About your idea of a front-end library for SDL that implements sprites âŚOn Wed, 8 Dec 1999, William Kendrick wrote:

Itâs an interesting problem. I guess SDL doesnât have a blit that ANDs the
buffers. Itâd be an interesting function that could hide the implementation from
the user. Iâve never heard of a hardware version of this sort of operation.

Iâve actually contemplated writing a front-end library for SDL which would
manage sprites and do collision detection. Kind of like a widget set, but
for sprites. NoteâŚ I havenât SERIOUSLY contemplated it, so donât
expect anything any time soon, or even ever.
-bill!
I suggest that you check the source code of a project called Xgame.
It has all these features and double buffering, sprites animation,
collision detect routines, keeps separate buffers for background pixmaps
and foreground pixmaps, routines for precise timing useful for making a
program keeps the rate of fps, etc.
It includes some amazing games samples and graphic demos.

Xgame - An X11 game programming library

I am considering porting some of its functions to SDL âŚ
Check it out and tell me what you think.
bye,