🚀 go-pugleaf

In a previous article, kennehra@craft.camp.clarkson.edu (Rich"TheMan"Kennehan) says:

>
>
>Hi.  Could someone please give me some simple collison/detection
>routines?  the routines used for the games "Sopwith" and 
>"Robotron 2084" would be ideal.  Thanks in advance!
>

Well, in my tank game (ala Atari combat), I used color
to determine collisions.  A routine would scan the row of pixels
an object was about to run into.  If the any of the pixels was
not the background color, a collision was about to occur.  The
color also told me the type of object that was hit.  I used the
320 by 200  VGA mode, allowing easy video access.
 
 
Here is a summary of the collision-detection discussion from
10 months or so ago:
 
 
 
From: <kdorff@NMSU.Edu>
Just a quick idea to expand on YOUR idea:
 
I am using a VGA card, and with that card each pixel can have values
from 0-255 for the color.  So what you can do is check the color in
the map, but assign the colors in the map so that each "thing" in the
program is assigned a range, ie
 
    0-127  are used to make a colorful background, this way you can
           also quickly tell what is there by anding the value with
           128 and if you get a 0 you know you are only on a
           background.
   128-xx  thing 1
   xx-yy   thing 2
   etc
 
And that is one possibility, that way you can also make each "thing"
have as many colors as you see fit, like 16 a thing should be more
than enough.  THIS should also make design a little easier, possibly.
 
Kevin
 
From: schnitzi@eola.cs.ucf.edu (Mark Schnitzius)
 
You can get into a lot of trouble doing things that way.  The best
way to do it is with a distance formula, assuming you have the
coordinates for the objects which are being tested for collision.
Don't bother computing the square root in the formula; testing
whether sqrt((x1-x2)^2+(y1-y2)^2) < 1 is the same as testing whether
(x1-x2)^2+(y1-y2)^2 < 10.  This will save you a costly calculation.
This method assumes that you objects are roughly circular, and the
coordinates for the object are centered on the object.  For larger
misshapen objects, you can save several key points on the object
and test all of them.  Hope this helps.
Mark
mschnitzius@eola.cs.ucf.edu
 
From: schnitzi@eola.cs.ucf.edu (Mark Schnitzius)
 
Sorry.  Saying it only had to be less than 10 was a mistake.  What I
meant to say is that, when using the distance formula, you don't need
to take the square root, because you can just square both sides of the
inequality.  For instance, if you are looking for a distance of less
than one, then the distance _squared_ is less than one also.  If you
need a distance less than two, it is easier to look for a distance
squared less than four.  I don't know where I came up with "one
squared equals ten".
Mark
mschnitzius@eola.cs.ucf.edu
 
From: maddie@crash.cts.com
 
If you aren't TERRIBLY concerned about memory, one way to do collisions
is to reserve a buffer of memory the same size at the visible buffer.
Modifyyour drawing routine to do two more things, treating the "collision
buffer"as a seperate display buffer: 1, READ this buffer as you write each
pixel and
save the highest number. 2, write the objects "collision" number (an
arbitratynumber assigned to the object) to the "collision buffer."
 
Basicly, the way this ends up working is you eat up an extra chunk of
memoryas big as your display memory, but you also get a collision system
that can
be displayed on the screen (which is a REAL boon to debugging).


=============================================================================
Tom Schenck                                        | crash!maddie@nosc.mil
Knight Technologies                                | "I think, therefore,
uh,San Diego, CA                                        |

um..."
=============================================================================From:
mark@cantua.canterbury.ac.nz (Mark Botting)
 
I've been waiting a long time for someone to ask this!!!
 
First of all I like to detect collisions by comparing the coordinates and
sizes of objects. This means you can have any background you like
(especially for monochrome graphics - your way needs a 'blackground'). Also
it means that objects can be in front of other objects without colliding
for 3-D games (with appropriate tests).
 
Collision(A, B) = A.x1 <= B.x2 and
                  B.x1 <= A.x2 and
                  A.y1 <= B.y2 and
                  B.y1 <= A.y2;
 
     (x1,y1)
        +-----+        where A & B are two objects
        |     |        and (x1, y1) is top-left corner of an object
        |     |        and (x2,y2) is the bottom right corner.
        +-----+(x2,y2)
 
 
Once upon a time (in the last 2 yrs) the best general way I knew of
checking for collision was to compare each object against every other
object. This can be optimised a little by not comparing object[j] with
object[i] when you've already compared object[i] with object[j]. For
example the following pseudocode:
 
for i := 1 to n-1
        for j := i+1 to n
                if Collision(i, j) then
                        DoSomething
 
BUT this can mean a large number of comparisons for reasonable numbers of
objects (32 objects -> 496 collision checks -> 1984 comparisons). So I
thought & thought & thought.... DING I realised that searches (we are
searching for objects that overlap) can be speed up by sorting the objects
first.In most games, for each animation cycle, each object doesn't move
much (if at all) and so doesn't usually need resorting. If it does need
sorting it won't be much perhaps one or two positions away in the list.
To detect collisions, simply check whether an object collides with the
objects next to it in the sorted list. You don't need check each object
against all others only those close to it.
I usually sort on the x coordinate because my graphics resolution is larger
in the x direction and so the objects are more spaced out.
I know it works because I used it for a two player game which had lots of
floors, coins, flowers, monsters etc as objects. Unfortunately I don't have
the source code handy, but I remember using a doubly linked list using
pointers. Pointers make insertion, deletion and re-ordering easy. I also
remember having the floors stored as a separate list because that don't
change and I only needed to check the players against the floors.
What I really want to know is: Has someone already thought of this? Or am I
the first - in which case I name this the BOTTING ALGORITHM   ;-)
I'd apreciate comments posted on this thread, and from anyone who has used
the BOTTING ALGORITHM I would like to know what the application was?
 
Happy hacking,  Mark  :-)
 
 
From: jefftep@cs.utexas.edu (Jeffrey Grills)
 
In article <1991Aug19.181725.1827@csc.canterbury.ac.nz>
mark@cantua.canterbury.ac.nz (Mark Botting) writes:
>[...]
>Collision(A, B) = A.x1 <= B.x2 and
>                  B.x1 <= A.x2 and
>                  A.y1 <= B.y2 and
>                  B.y1 <= A.y2;
>
>     (x1,y1)
>        +-----+        where A & B are two objects
>        |     |        and (x1, y1) is top-left corner of an object
>        |     |        and (x2,y2) is the bottom right corner.
>        +-----+(x2,y2)
>Once upon a time (in the last 2 yrs) the best general way I knew of
checking for collision was to compare each object against every other
object. This can be optimised a little by not comparing object[j] with
object[i] when you've already compared object[i] with object[j]. For
example the following pseudocode:
>
>for i := 1 to n-1
>        for j := i+1 to n
>                if Collision(i, j) then
>                        DoSomething
>
>[...]
>Happy hacking,  Mark  :-)
 
Yeah, that's a really good way to do it.  So good, in fact, that I use
somethingvery similar in my windowing code that I've written to determine
if windows
overlap, and if they do, what the overlapped region is ( and what isn't as
a matter of fact! )  It was written in Turbo Pascal 5.5, object oriented.
 
The idea was to have a stack of windows (hence sorted like yours, only in
the'z' plane), and to refresh an area of the screen with a single (sorta)
procedurecall. The object's method takes a region to redraw, draws what it
knows of that
area, and pases the rest down to the next guy in the stack of windows.
You obviously pass the refresh command to the top guy in the stack, and he
handles passing down the regions left to be redrawn.
 
Presto - built in Z-buffering.  This is great if you just want to show what
isin from of what, but does not account for distance scaling.  That may not
beto hard to add, if the item in question simply changes it's coordinates
tobe smaller, but remains centered as previously.
 
Here's what I did, the best I can remember off the top of my head,
in pseudo-code:
 
procedure window.refresh ( a.x1, a.y1, a.x2, a.y2 )
 
  if ((a.x1 > b.x2) or (a.x2 < b.x2) or (a.y1 > b.y2) or (a.y2 < b.y1))
  then
 
    { no overlap, tell next window to refresh the entire region requested }
    next_window^.refresh ( a1, b1, a2, b2 )
 
  else begin
 
    { calculate overlap }
    o.x1 := max ( a.x1, b.x1)
    o.x2 := min ( a.x2, b.x2)
    o.y1 := max ( a.y1, b.y1)
    o.y2 := min ( a.y2, b.y2)
 
    { display the region from this window that is visible }
    display ( o.x1, o.y1, o.x2, o.y2, thiswindow )
 
    { draw the area NOT overlapped }
 
    {above}
    if ( a.y1 < b.y1 ) then next_window^.refresh ( a.x1, a.y1, a.x2,
o.y1-1) 
    {left}
    if ( a.x1 < b.x1 ) then next_window^.refresh ( a.x1, o.y1, o.x1-1, o.y2
) 
    {right}
    if ( a.x2 > b.x2 ) then next_window^.refresh ( o.x2+1, o.y1, a.x2, o.y2
) 
    {below}
    if ( a.y2 > b.y2 ) then next_window^.refresh ( a.x1, o.y2+1, a.x2, a.y2
) 
    end else;
 
end window.refresh
 
Since I wrote this from my head, be nice if there are a few little
glitches.I'm not perfect - that's what testing is for.
 
This code is nice and fast to detect no overlaps, especially if the
compiler handles short-circuit boolean expressions.  Notice that the side
( right and left ) refreshed only draw the area on the right and left
excluding what is included by the top and bottom.  In the lng run, this
will save lots of time, and considering you already have the values
handy, it may as well be done.
 
Oh, and remember where you say this incase you decideto use it, make
lots of money from it, and have a guilty concious you would like to
purge. :-)  Or better yet, remember it so that some *sshole can't
patent it and force me to pay him royalties..
 
--
---------------------------+-------------------------------
jefftep@cs.utexas.edu      |  "my moral standing ...
Computer Science Dept      |    ... is lying down."
Painter Computer Lab       |       -Nine Inch Nails
 
 
From: mark@cantua.canterbury.ac.nz (Mark Botting)
 
I recieved this a while ago and pass onto you folks to peruse/pick over.
 
>From ELIOT@cs.umass.EDU Tue Aug 20 06:30:15 1991
 
 >(Feel free to redistribute this message.  I can't post it myself.)
 >
 >There are a couple of tricks that can help speed up calculations of this
sort. >The first trick is to pre-compute the smallest enclosing cirlce (or
sphere) >for each object.  Detecting collisions of spheres or cirlces is
very fast,
 >just measure the distance between their centers and determine if this
 >is smaller than the sum of their radii.  Assuming that most objects
*don't* >collide you can quickly check most objects.  Then use a more
detailed >analysis for the few objects with colliding enclosing spheres.
 >
 >Another trick is to use a corse bitmap describing individual objects or
 >the whole scene.  w3{{Again, this works best when collisions are rare.
 >If you have a 64X64 o r32X32 bitmap with a one in every occupid
 >position then it is easy to tell if an object is in the clear.
 >The computer strategy in Empire Master uses this technique.  There is
 >a bitmap showing which sectors have known enemy units in them.  A machine
 >unit that can't reach a sector with known enemy units does not need to
 >call the expensive parts of the strategy code so it runs much faster.
 >
 >Chris Eliot
 
 
IMHO using smallest enclosing rectangles has many advantages over circles,
unless you are specifically dealing with round objects - such as
pool/snooker,        - Easier to precompute, simply find width and height.
Circles need centres can be hard for complicated shapes.
        - Size of shape is easy to change (can't think of a good use for
this).        - Distance between centres can involve squares (ie r^2 = x^2
+ y^2) which means multiplication ('*' is generally a relatively slow
operation). Less accurately the distance between centres can be determined
by adding the horizontal and vertical difference - which is basically using
rectangles.        - Complicated or concave outlines can be achieved by
using more than one rectangle for an object. This is possible with circles
too, but circles are less flexible - they must overlap, either with large
radii or more circles.
 
Advantages of circles
        - I like curves ;-)
        - Only need one comparison - rectangles use four.
 
 
For rectangles where
 A, B are two (rectangular) objects
 (x, y) is top left corner
 w is width
 h is height.
   if A.x <= (B.x + B.w) and
      B.x <= (A.x + A.w) and
      A.y <= (B.y + B.h) and
      B.y <= (A.y + A.h) then...
Analysis
 4 comparisons
 4 additions
 4 test-and-branches (assuming short circuit evaluation)
 => total of 12 (similar speed) operations
 
For circles where
 A, B are two (circular) objects
 (x, y) is the centre
 r2 is the square of the radius
   dx := A.x - B.x;
   dy := A.y - B.y;
   r := A.r + B.r;
   if ((dx * dx) + (dy * dy)) <= (r * r) then...
Analysis
 2 subtractions
 1 comparison
 2 additions
 1 test-and-branch
 3 multiplications (equivalent of approx 8 arithmetic ops in terms of
execution time on machines I know of)
 => total of 6 + 3*8 => 30 operations
 
So rectangular detections are generally faster. (Any flaws in my logic?)
 
Apologies for verbosity,  Mark  :-)




-- 
=======================================================================
Kevin Dahlhausen                      "Hopfen und Malz, Gott Erhalts"
ap096@po.cwru.edu