Collision detection quandry

robobunny has asked for the wisdom of the Perl Monks concerning the following question:

I'm attempting to add collision detection to Term::Animation, so that it can be used for simple games. Unfortunately, I've never done any real game programming, so I'm a bit lost and I'm probably going about this completely wrong. My dilemma is how to add it to the current process in a way that makes sense. Here's how the module works now (sans collisions and pseudo-fied):


add_objects();

while(!$done) {
    run_callback_routines();
    update_display();
}
[download]

Each object has a callback routine that determines how it behaves, that is called each time through the loop. Among other things, the callback determines how the object moves. My first attempt to add collision detection was something like this:


while(!$done) {
    check_for_collisions();
    run_callback_routines();
    update_display();
}
[download]

The callback routines would have access to a list of all the objects they collided with. The problem with this is that the display is updated immediately after everything is moved, so collisions get drawn on the screen that have not been dealt with. With fast moving objects, it wouldn't be an issue, but when stuff is moving slower it is obvious something is screwy. So my next thought was something like:


while(!$done) {
    run_callback_routines();
    check_for_collisions();
    update_display();
}
[download]

The difference here being that instead of handling collisions in the regular callback, there would be an additional callback routine that is called only for objects that have collided with something. But then, what do you do when the action taken by one of these causes an additional collision that you haven't detected?

So now I'm considering doing collision detection each time an object moves, instead of after they have all moved. Since the order the objects move isn't significant, I don't know if this is any better. I'd appreciate any advice you can offer.

Comment on Collision detection quandry Select or Download Code

Replies are listed 'Best First'.
Re: Collision detection quandry by Abigail-II (Bishop) on Feb 06, 2004 at 00:58 UTC
Personally, I'd check for a potential collision just before an object is about to move - and if a collision is about to happen, either not move, or do whatever you do if objects collide. That way, you don't have to move an object, cascade any triggered actions, and then roll-back if the collision detection routine afterwards determines the move shouldn't have happened. But then, that's just me. I also think your question has nothing to do with Perl. You'd face the same problems if you would program your game in C, Java or Python. You'd better off asking in a forum that's about game programming. There you have a much better chance of meeting someone who has tackled this problem before. Abigail	[reply]
Re: Collision detection quandry by shotgunefx (Parson) on Feb 06, 2004 at 12:14 UTC
It's a bit of a chicken and egg problem. I think one of the big problems you have is that there is no "controller" role here. Most games have specific object types and reactions. I don't see how you can get away without some cascading if you have abitrary objects and rules. Let's say you have two objects ($foo and $bar). You want them to bounce off each other if they collide, how can you do it? If you check $foo before moving and finds it will collide with $bar, it's easy enough to change $foo's movement, but $bar won't be aware of the interaction. You could come up with a way for $foo to tell $bar they collided, but that still leaves other issues. You also have a problem with the order of movements. Let's say $foo is at 0,0 and $bar is at 1,0. Both of them are traveling right 1 column per frame. $foo will always hit $bar even though they shouldn't. You can't just check to see if a cell is occupied after a movement to detect collisions either as an object might move 5 cells at a time. (So $bar could go right through $foo with a large enough movement) Perhaps the best way is to do the movements ( keeping track of the last positions in the object as well) flagging objects that have collided and returning them. (Detecting the collisions could be a little hairy) Then the programmer can decide what to do (such as handling the interaction, moving the objects and run_callback_routines() again (taking care to avoid infinite loops of course) -Lee "To be civilized is to deny one's nature."	[reply]
Re: Re: Collision detection quandry by robobunny (Friar) on Feb 06, 2004 at 19:30 UTC
Yeah, the root of the problem is that it wasn't originally designed for this purpose. I've been thinking through the same problems that you mention, and I don't think there's any way to avoid them without radically changing the way the module works. I think I'll probably do something like what you suggest and not worry about it too much, since it's not the primary purpose of the module anyway. Thanks for the suggestions.	[reply]
Re: (3): Collision detection quandry by shotgunefx (Parson) on Feb 06, 2004 at 21:21 UTC
No problem. Seeing that your using console graphics, I'm assuming you are going to want to detect collisions on the character level. If that's the way you go, once you get things working to your liking you could make it speedy and less memory hungry by creating bitmasks of the sprites and judicious use of bitwise &, and bit shifts. Let's say you limit sprites to 32 x 32 (pretty big for ascii characters), You could make a bit mask for the characters with something like so... (untested) Then by comparing the appropriate rows, collision checking can be done with a bitwise & (After you've shifted the mask appropriately ) my $transparent_color = ' '; my $chardata = [ ' \|x x\|', ' \| \|', ' = ', ]; my $map = make_collision_map($chardata); # This gives you a map like so #00000000000000000000000000110110 #00000000000000000000000000100010 #00000000000000000000000000001000 # Assuming the character animations is an array ref of one or more hor +izontal lines sub make_collision_map { my $sprite = shift; my @mask; foreach my $row (@$sprite){ warn "Sprite length exceeds limit:[$row]" and return if length($ +row) > 32; (my $bits = $row)=~s/[^$transparent_char]/1/g; $bits=~s/$transparent_char/0/g; push @mask, unpack("N", pack("B32", substr("0" x 32 . reverse ( +$bits), -32))) ; } return [@mask]; } [download] I don't have time to finish this right now, but hope it helps. -Lee "To be civilized is to deny one's nature."	[reply] [d/l]
Re: Re: (3): Collision detection quandry by robobunny (Friar) on Feb 06, 2004 at 22:04 UTC


Come for the quick hacks, stay for the epiphanies.
	PerlMonks