in reply to Collision detection quandry

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."

Replies are listed 'Best First'.
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]
      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]
        Thanks, I may be adding character level collision detection, but initially it will just use bounding boxes. When/if I do, it will certainly be using the technique you describe.
[reply]

In Section Seekers of Perl Wisdom