Simple collision detection

Hi all,

I would like to know if anyone has some tips of making a basic collision
dectection function. Basically, I need a bounding box routine for my
Lunar Lander clone so that I can check to see if the lander has touched
a platform. Both the lander and the platform are surfaces in my game.

Any help in the form of code snippets or links to websites would be great.

Thanks,
Don

Hi all,

I would like to know if anyone has some tips of making a basic
collision dectection function. Basically, I need a bounding box
routine for my Lunar Lander clone so that I can check to see if the
lander has touched a platform. Both the lander and the platform are
surfaces in my game.

If you really want plain bounding box, it’s pretty much irrelevant how
stuff is rendered. All you need is to get the relative sizes and
positions right, and then do some math and checks based on that.

Keep in mind that just testing for intersection is not sufficient if
you want things to bounce and stuff like that. It works for simple
things like “ship blows up when hit”, but for more advanced stuff,
you need to calculate exactly when collisions occur (sub-frame
accuracy) and act accordingly. (Of course, you can “cheat” by using a
very high logic frame rate, so that objects don’t move too far
between frames, but that can become expensive if the game logic is
complex and/or driven by a scripting engine.)

Any help in the form of code snippets or links to websites would be
great.

Fixed Rate Pig is a more or less playable platform game engine that I
hacked some time ago. It’s not a minimal example though; it’s main
purpose is to demonstrate some rather advanced methods, but it does
contain a simple collision detection system that tests tile edges
against sprite bounding cicles. Measures are taken to avoid tunelling
when sprites move at high speeds, though that’s not really needed if
you run the logic engine at a sensible frame rate. (This one’s fixed
at 20 Hz or something, just to demonstrate the motion interpolation.)

http://olofson.net/examples.html

//David Olofson - Programmer, Composer, Open Source Advocate

.- Audiality -----------------------------------------------.
| Free/Open Source audio engine for games and multimedia. |
| MIDI, modular synthesis, real time effects, scripting,… |
`-----------------------------------> http://audiality.org -’
http://olofson.nethttp://www.reologica.se —On Monday 25 October 2004 14.59, Donald wrote:

Hey Don. I’ll get something for you later today. I promise to make it
readable.

-Steven “Grellin”> ----- Original Message -----

From: Donald [mailto:dcathcart@ns.sympatico.ca]
Sent: Monday, October 25, 2004 9:00 AM
To: sdl at libsdl.org
Subject: [SDL] simple collision detection

Hi all,

I would like to know if anyone has some tips of making a basic collision
dectection function. Basically, I need a bounding box routine for my
Lunar Lander clone so that I can check to see if the lander has touched
a platform. Both the lander and the platform are surfaces in my game.

Any help in the form of code snippets or links to websites would be great.

Thanks,
Don


SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl

here’s a ultra simple box intersection test:

GameObject consists of
x, y - top left position
w, h - width/heihgt

bool coldec_obj2obj(GameObject o1, GameObject o2){
int l1 = o1.x; //left
int r1 = o1.x+o1.w; //right
int t1 = o1.y; //top
int b1 = o1.y+o1.h; //bottom

int l2 = o2.x;
int r2 = o2.x+o2.w;
int t2 = o2.y;
int b2 = o2.y+o2.h;

	
//dr bobb's rect-rect collision detection
//http://www.ddj.com/documents/s=983/ddj9513a/
if (l1 > r2 || l2 > r1 ||
     t1 > b2 || t2 > b1) {
     return false;	//no intersectoin
 }
 else {
     return true;	//intersection
 }

}

have fun

Donald wrote:> Hi all,

I would like to know if anyone has some tips of making a basic collision
dectection function. Basically, I need a bounding box routine for my
Lunar Lander clone so that I can check to see if the lander has touched
a platform. Both the lander and the platform are surfaces in my game.

Any help in the form of code snippets or links to websites would be great.

Thanks,
Don


SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl

I highly recommend the bitmask collision library available
on the SDL website. I’ve been using it in my game and not
only is it extremely fast, it’s also got neat features like
per-pixel collision detection and such!

Cheers,

Paul LoweOn Monday 25 October 2004 05:59 am, Donald wrote:

Hi all,

I would like to know if anyone has some tips of making a
basic collision dectection function. Basically, I need a
bounding box routine for my Lunar Lander clone so that I
can check to see if the lander has touched a platform.
Both the lander and the platform are surfaces in my game.

Any help in the form of code snippets or links to
websites would be great.

Thanks,
Don


SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl

You mention sub-frame accuracy in your collision detection. I’m fairly
inexperienced in things like this, so I was wondering how this is
generally accomplished (don’t need source code, the theory behind how
it’s done should be fine). Also, what do you gain by doing things this
way over not?

Thanks,
–Scott

David Olofson wrote:> Keep in mind that just testing for intersection is not sufficient if

you want things to bounce and stuff like that. It works for simple
things like “ship blows up when hit”, but for more advanced stuff,
you need to calculate exactly when collisions occur (sub-frame
accuracy) and act accordingly.

If you’re running your game at 60fps, you may
want your physics engine to run twice as fast.
In other words, you get 2 physics updates for every
frame.

A bunch of physics engines (especialy if you’re working on
racing games and stuff) are designed to run at 120Hz (when
the actual game runs at 60Hz).

(At least I hope that’s what Dave means by sub-frame accuracy)
;-)> ----- Original Message -----

From: sdl-bounces+kos=climaxgroup.com@libsdl.org
[mailto:sdl-bounces+kos=climaxgroup.com at libsdl.org]On Behalf Of Scott
Harper
Sent: 26 October 2004 14:55
To: A list for developers using the SDL library. (includes SDL-announce)
Subject: Re: [SDL] collision detection – sub-frame accuracy?

You mention sub-frame accuracy in your collision detection. I’m fairly
inexperienced in things like this, so I was wondering how this is
generally accomplished (don’t need source code, the theory behind how
it’s done should be fine). Also, what do you gain by doing things this
way over not?

Thanks,
–Scott

David Olofson wrote:

Keep in mind that just testing for intersection is not sufficient if
you want things to bounce and stuff like that. It works for simple
things like “ship blows up when hit”, but for more advanced stuff,
you need to calculate exactly when collisions occur (sub-frame
accuracy) and act accordingly.


SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl

Here’s an example:
Assume you have 2 objects, O1 & O2, defined as follows:
at frame 0:
O1 is at <0,5> w/ velocity <10,0>
O2 is at <5,0> w/ velocity <0,10>
clearly they should intersect at <5,5> at time 0.5. But if our
calculations are done on a per frame basis only, at frame 1 we get:
O1 is at <10,5> w/ velocity <10,0>
O2 is at <5,10> w/ velocity <0,10>
Assuming objects are moving in straight line segments, a solution is:
at every frame, calculate the path of each object & perform a
collision detection on the paths (essentially line intersections).
Reality is of course more complicated as this only works on zero
volume objects - ie it will not register collisions of paths that pass
’near’ each other & would have overlapping objects. Also, it requires
curved paths to be approximated by straight line segments. As w/
anything, the more realism you want, the more complicated things
becomeOn Tue, 26 Oct 2004 07:54:38 -0600, Scott Harper wrote:

You mention sub-frame accuracy in your collision detection. I’m fairly
inexperienced in things like this, so I was wondering how this is
generally accomplished (don’t need source code, the theory behind how
it’s done should be fine). Also, what do you gain by doing things this
way over not?

Thanks,
–Scott

Yeah, that’s pretty much it; the game logic deals with time periods
shorter than the nominal frame period.

It doesn’t have to be restrictid by logic frame rates, though. Another
way to handle it is to deal with “exact” delta times instead, doing
away with the frame as a unit in the game logic. The problem with
this is that it quickly gets hairy and/or inaccurate, unless you put
a lot of effort into ensuring that rounding and approximation errors
do not make rendering frame rate, CPU speed, wall clock time (start
timestamp) and other factors affect the game logic.

//David Olofson - Programmer, Composer, Open Source Advocate

.- Audiality -----------------------------------------------.
| Free/Open Source audio engine for games and multimedia. |
| MIDI, modular synthesis, real time effects, scripting,… |
`-----------------------------------> http://audiality.org -’
http://olofson.nethttp://www.reologica.se —On Tuesday 26 October 2004 16.09, Kostas Kostiadis wrote:

If you’re running your game at 60fps, you may
want your physics engine to run twice as fast.
In other words, you get 2 physics updates for every
frame.

A bunch of physics engines (especialy if you’re working on
racing games and stuff) are designed to run at 120Hz (when
the actual game runs at 60Hz).

(At least I hope that’s what Dave means by sub-frame accuracy)
:wink:

Hello, I’ve been around the SDL community for a while now and have never
really liked any of the tutorials available so I decided to write my
own. I’ve attached the tutorial (12k) as well as the source code (2k)
and I would very much appreciate any feedback from the list.

Thanks in advance.
-------------- next part --------------
Getting Started:

First of all welcome, and thank you for downloading the first
installment of what will, hopefully, be a long running series
of tutorials.

In this tutorial we will explore SDL’s history, learn how to download
and install SDL and SDL_image from CVS, learn how to create a
very basic SDL application, and finally learn how to compile a SDL
program.

Now without further ado, let’s begin.

Short history on the SDL library:

SDL came about in 1997 when it’s author, Sam Lantinga, was working on a
Win32 port of the Macintosh emulator Executor. SDL’s first prototypes
ran on the Win32 and GNU/Linux Operating Systems, with BeOS and slew
of other Operating Systems to follow that.

Fast forward seven years later,SDL’s development is still going strong
and still being ported to various new and exotic platforms.

Installation from CVS:

Installing SDL is a breeze, assuming that the right tools are in place.
You will need automake and autoconf, which can be found at
http://www.gnu.org. The remaining process is pretty much automated.

Lets begin logging into SDL’s official CVS repository, by running the
following command in a terminal:

`cvs -d :pserver:guest at libSDL.org:/home/SDLweb/libSDL.org/cvs login’

Hit when prompted for a password, than proceed to check out
the sources with the following command:

`cvs -z3 -d :pserver:guest at libSDL.org:/home/SDLweb/libSDL.org/cvs checkout SDL12’

Once the source is checked out you should run the following command:

`cd SDL12; ./autogen.sh; ./configure; make; make install’

If all goes well you should now have the latest and greatest SDL
library installed. Don’t forget to periodically run:

`make distclean && cvs -z3 update -d’

Which will keep SDL’s source code up to date. If ever you feel the need
to recompile the SDL library, simply go through the third step off this
walk through.

First program:

All right enough foreplay let’s get right down to it. Our first program
will be very simple, just basic SDL initialization and small keyboard
manipulation.

Let’s begin by including some basic headers, SDL’s headers, and the std
namespace:

#include “SDL.h”
#include “SDL_image.h”
#include
#include

using namespace std;

I will not go into depth what these variables are here… Most of them are self
explanatory. For instance screenh/w, and bpp which are variables to set
our applications video attributes.

const int screenh = 360;
const int screenw = 640;
const int bpp = 16;

Video flags, I’ll go into what these do a little further in the tutorial.

const Uint32 vflags = SDL_HWSURFACE|SDL_HWPALETTE|SDL_DOUBLEBUF;

SDL_Surface is the graphic surface structure which represents areas of `graphical’ memory,
memory that can be drawn to.

SDL_Surface* screen;

SDL_Event is a union of all event structures used in SDL, using it is a simple matter of knowing
which union member relates to which event type.

SDL_Event event;

Self explanatory boolean variable that will be used later in a conditional statement.

bool done = false;

The InitSDL function is called to initialize SDL, and a screen surface.

bool InitSDL (char* icon) {

SDL_init(Uint32), initializes SDL and should be called before all other SDL functions.
Accepts Uint32 parameters specifying which SDL subsystems you’d like to initialize, the
acceptable flags are:

SDL_INIT_TIMER - Initialize the timer subsystem.
SDL_INIT_AUDIO - Initialize the audio subsystem.
SDL_INIT_VIDEO - Initialize the video subsystem, and events subsystem.
SDL_INIT_CDROM - Initialize the CD-Rom subsystem.
SDL_INIT_JOYSTICK - Initialize the JoyStick subsystem.
SDL_INIT_EVERYTHINg - Initialize all of the above.
SDL_INIT_NOPARACHUTE - Prevent SDL from catching fatal signals.

Our example does not require anything too fancy, which is why we will only initialize
the video and event subsystem. Should you need to initialize anything other than
what you’ve already initialized at start up you can call SDL_InitSubystem, and
SDL_QuitSubystem to shutdown a specified subsystem. SDL_Init returns a 1 upon
failure and a zero value upon successful execution.

if (SDL_Init(SDL_INIT_VIDEO)) {

SDL_GetError(void), returns a NULL terminated string containing the last internal SDL
error.
cerr<<"Unable to initialize SDL: "<<SDL_GetError()<<’.’<<endl;
exit(1);

SDL_Quit(void), shuts down all subsystems and frees the resources allocated to them. Be
sure you call this function before any of your SDL applications exit. In this instance we call
SDL_Quit whenever an exit() call is made. If ever you have a more complex piece of
software make SDL_Quit part of your clean up routine.

} atexit(SDL_Quit);

SDL_WM_SetIcon(SDL_Surface*, Uint8), is used to set our applications Window managers
icon. In this instance we are using SDL_image’s IMG_Load function to load exotic file
formats, since SDL only supports the BMP file format out of the box.

SDL_WM_SetIcon (IMG_Load(icon), NULL);

SDL_WM_SetCaption(const char*, const char*) is, as you may have guessed, used to set
our applications Window Managers caption. The captions are displayed on our applications
title bar, and window list entry.

SDL_WM_SetCaption ("Window caption goes here.", "Icon name goes here.");

SDL_ShowCursor(int), toggles whether or not the mouse cursor is shown within our
applications screen. In this instance it is disabled.

SDL_ShowCursor(SDL_DISABLE);

SDL_VIDEO_CENTERED, is part of SDL’s environment variables, should this env var is set
SDL will attempt to center it’s window when running in windowed mode.

putenv("SDL_VIDEO_CENTERED=1");

SDL_SetVideoMode(int, int, int, Uint32), is used to set a video mode with specified width, height,
bits per pixel, and video flags. The acceptable video flags are the same as flags field of the
SDL_Surface structure. OR’d combination of the following is acceptable:

SDL_SWSURFACE - Create the video surface in system memory

SDL_HWSURFACE - Create the video surface in video memory

SDL_ASYNCBLIT - Enables the use of asynchronous updates of the display surface. This will
usually slow down blitting on single CPU machines, but may provide a speed increase on SMP
systems.

SDL_ANYFORMAT - Normally, if a video surface of the requested bits-per-pixel (bpp) is not
available, SDL will emulate one with a shadow surface. Passing SDL_ANYFORMAT prevents this
and causes SDL to use the video surface, regardless of its pixel depth.

SDL_HWPALETTE - Give SDL exclusive palette access. Without this flag you may not always get
the the colors you request with SDL_SetColors or SDL_SetPalette.

SDL_DOUBLEBUF - Enable hardware double buffering; only valid with SDL_HWSURFACE. Calling
SDL_Flip will flip the buffers and update the screen. All drawing will take place on the surface that
is not displayed at the moment. If double buffering could not be enabled then SDL_Flip will just
perform a SDL_UpdateRect on the entire screen.

SDL_FULLSCREEN - SDL will attempt to use a fullscreen mode. If a hardware resolution change is
not possible (for whatever reason), the next higher resolution will be used and the display window
centered on a black background.

SDL_OPENGL - Create an OpenGL rendering context. You should have previously set OpenGL video
attributes with SDL_GL_SetAttribute.

SDL_OPENGLBLIT - Create an OpenGL rendering context, like above, but allow normal blitting
operations. The screen (2D) surface may have an alpha channel, and SDL_UpdateRects must be
used for updating changes to the screen surface. NOTE: This option is kept for compatibility only,
and is not recommended for new code.

SDL_RESIZABLE - Create a resizable window. When the window is resized by the user a

SDL_VIDEORESIZE - event is generated and SDL_SetVideoMode can be called again with the new
size.

SDL_NOFRAME - If possible, SDL_NOFRAME causes SDL to create a window with no title bar or
frame decoration. Fullscreen modes automatically have this flag set.

A bit per pixel value of 0 is treated as the current displays bits per pixel. SDL_SetVideoMode returns
a NULL value upon failure, and the framebuffer surface upon successful execution.

if (SDL_SetVideoMode(screenw, screenh, bpp, vflags) == NULL) {
	cerr<<"Unable to set video mode: "<<SDL_GetError()<<'.'<<endl;
	exit(1);
}

SDL_GetVideoSurface(void), returns a pointer to the current display surface, which was set just a few
lines before.

screen = SDL_GetVideoSurface();

We return a boolean true value if all went well, false if anything went wrong. However, we most likely
would have exited by now if anything went wrong prior to this return statement.
return true;
}

Next up is the event handling function, in this instance we will handle keyboard interaction.

void KeyBrd (void) {

The SDL_PollEvent function, polls for currently pending events, and returns 1 if there are any pending
events, or 0 if there are none available.

while (SDL_PollEvent(&event)) {

The event data structure consist of the following:

type - The type of event.
active - Activation event.
key - Keyboard event.
motion - Mouse motion event.
button - Mouse button event.
jaxis - Joystick axis motion event.
jball - Joystick trackball motion event.
jhat - Joystick hat motion event.
jbutton - Joystick button event.
resize - Application window resize event.
expose - Application window expose event, usually used if our application is altered by an outside source
for instance a WM.
quit - Application quit request event.
user - User defined event.
syswm - Undefined window manager event.

Here we will use event.type to gather any reports of key/button presses.

	switch (event.type) {

SDL_Keyboard Event reports SDL_KEYDOWN or SDL_PRESSED, which report the same information
only they use different values, whenever a key is pressed down.

		case SDL_KEYDOWN:

As we just read event.key reports keyboard events, and the keysym structure is used by reporting
key presses and releases…

			switch (event.key.keysym.sym) {

You can get a whole list of all the keysym definitions by visiting the SDL_documentation at the following,
URL (http://sdldoc.csn.ul.ie/sdlkey.php).

				case SDLK_ESCAPE:
					done = true;
				break;
				default:
				break;
			}
		break;

We can use the SDL_QUIT type, to catch any quit request and respond to them accordingly.

		case SDL_QUIT:
			cerr<<"Caught termination signal, now exiting."<<endl;
			SDL_Quit();
			exit(1);
		break;
		default:
		break;
	}
}

}

That pretty much does it for our input handling function, in this tutorial we only went into key presses but
we will go into key releases in our next tutorial. With all that done we need to put the whole program
together.

int main (int argc, char* argv[]) {

Before we do anything with SDL we will need to initialize it.

if (!InitSDL("icon.png")) {
	cerr<<"You should not be here. Now exiting."<<endl;
	exit(1);
}

Once SDL has bee initialized successfully, we can begin our program and since we don’t have much work
to do in this program we will only utilize our KeyBrd function which will away for user input to ask it to
exit.

while (!done) {
	KeyBrd();
}

Once our user presses escape we exit our while loop and move onto returning resources to our OS.

return EXIT_SUCCESS;

}

Compiling and linking:

To compile any SDL program we use the `sdl-config’ script, which generates all the appropriate flags for
us. sdl-config accepts the following flags, just pass any flag that you feel is necessary:

–version Which returns our libraries version.
–cflags Returns include flags that can be used by gcc and any of the autotools such as make.
–libs Returns linker flags that can be used by gcc and any of the autotools.
–static-libs Returns linker flags to statically link our program, used by gcc and any of the autotools.

We can compile our program like so:

c++ sdl-config --cflags -Wall -O9 -pipe tut00.cc -o tut00 sdl-config --libs -lSDL_image

We run sdl-config twice, notice the opening character it is a opening quote which is the generated character
when you press the tilda key without the shift button, first with --cflags to give gcc the include path to SDL
headers and the last call --libs which tells gcc to search certain directories for the sdl library.

Closing words:

This tutorial turned out to be alot longer than I originally planned, but I think that it provides alot more then
other of the tutorials currently available. I hope that you enjoyed reading this tutorial, and I promise that
the next tutorial won’t be as long. :wink:

About the author:

The author is an aspiring game programmer, from the California. If you have any recommendations or
grammatical corrections, you can contact him via E-Mail (@Juan_D_Espinoza).

Resources:

http://www.libsdl.org
http://www.gnu.org


http://www-106.ibm.com/developerworks/library/l-making-linux-fun/
-------------- next part --------------
A non-text attachment was scrubbed…
Name: tut00.cc
Type: text/x-c++src
Size: 2222 bytes
Desc: not available
URL: http://lists.libsdl.org/pipermail/sdl-libsdl.org/attachments/20041109/b2646f60/attachment.cc

i noticed you set bpp to 16 but then you are dealing with the pallette too,
whys that? I thought only 8 bit had palletes (or am i mistaken?).

The author is an aspiring game programmer, from the California. If you have
any recommendations or
grammatical corrections, you can contact him via E-Mail (socomm at gmail.com).

THE california? might wanna fix that

looks very cool though otherwise to me though (:> ----- Original Message -----

From: socomm@myrealbox.com (Juan D. Espinoza)
To: "A list for developers using the SDL library. (includes SDL-announce)"

Sent: Tuesday, November 09, 2004 4:30 PM
Subject: [SDL] SDL_tut00, feedback request.

Hello, I’ve been around the SDL community for a while now and have never
really liked any of the tutorials available so I decided to write my
own. I’ve attached the tutorial (12k) as well as the source code (2k)
and I would very much appreciate any feedback from the list.

Thanks in advance.




SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl

i noticed you set bpp to 16 but then you are dealing with the pallette
too,
whys that? I thought only 8 bit had palletes (or am i mistaken?).

I don’t know about SDL’s support for this, and I don’t even know which
modes are supported anymore on modern hardware since I only ever work
with 24+ bit color now - but there have been paletted 16-bit color
modes and real color 16-bit color modes in the past.On Nov 9, 2004, at 7:41 PM, Alan Wolfe wrote:

i noticed you set bpp to 16 but then you are dealing with the pallette
too,
whys that? I thought only 8 bit had palletes (or am i mistaken?).

I don’t know about SDL’s support for this, and I don’t even know which
modes are supported anymore on modern hardware since I only ever work
with 24+ bit color now - but there have been paletted 16-bit color
modes and real color 16-bit color modes in the past.

Yeah, I remember that too. Didn’t SGI do that on some of their hardware
about 20 years ago? 'twas cool, you could use it to build all sorts of
handy pallets. But, SDL only uses the pallet for 8 bit modes.

	Bob PendletonOn Wed, 2004-11-10 at 05:17, Donny Viszneki wrote:

On Nov 9, 2004, at 7:41 PM, Alan Wolfe wrote:


SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl

±-------------------------------------+

i noticed you set bpp to 16 but then you are dealing with the pallette too,
whys that? I thought only 8 bit had palletes (or am i mistaken?).

Thank you, I must have overlooked that.

THE california? might wanna fix that

Yeah I was thinking from the Los Angeles region' but instead decided to go with California, just forgot to removethe’. Thanks for correction.

looks very cool though otherwise to me though (:

Thanks, and anyone interested in downloading the whole thing you can
find it at the following location:

http://samesoft.sourceforge.net/juan

I’ll also add a link to it on http://www.libsdl.org, if I can later
today. Thank you all for the feed back, and I’ll post back if I get
around to creating a SDL_tut01 :^).On Tue, 2004-11-09 at 16:41 -0800, Alan Wolfe wrote: