From: deadman@garnet.berkeley.edu (Ben Haller)
Newsgroups: comp.sys.mac.games,comp.sys.mac.programmer
Subject: Re: NON-QUICKDRAW GAMES
Date: 11 Sep 1992 18:15:52 GMT
Organization: Stick Software
NNTP-Posting-Host: garnet.berkeley.edu

  Boy, this is a fun thread.

In article <timm.716178957@void> timm@void.ncsa.uiuc.edu (Tim McClarren) writes:
>deadman@garnet.berkeley.edu (Ben Haller) writes:
>>> - efficient collision detection algorithms
>>  My current favorite is, keep a sorted list of sprites (keeping it
>>sorted, assuming your sprites don't constantly teleport, is O(n)) and
>>compare nearby elements in the sorted list (again, O(n) for normal cases).
>>If you get a bounding box intersection, do a mask compare.  This is
>>pretty efficient, I think.  I hope...
>
>This seems to be the de-facto way of doing it.  I'd love to hear
>from someone who hasn't used this method.  Is there another method?
>What about geometric approaches?  Break the list in two, break those
>lists in two, etc.  But now you've got to keep track of when it's
>time for objects to jump lists.  I think the boundaries become
>problematic in those cases, no?  Or how about breaking the universe
>into radial areas?  Or does that involve too much expensive trigonometry?
>And the center gets really nasty.  Also, what about "walls" or other
>non-moving obstacles?  For the case of walls, does one simply break them
>up into rectangles?  Is that the best?
  Hmm.  Most of these ideas are not so hot, I think.  Why would you
*want* to break the list into parts?  Why would you *want* to use
radial areas (assuming your game isn't radially-based, like Tempest or
something)?
  Walls are generally a separate issue.  Depending on what kind of walls
you have, you might have an array representing where the walls are in
your world so you can do an array look-up to see if a particular area
contains a wall, or you might treat them as sprites and keep them in the
collision list (this would usually not be appropriate, however), or maybe
some other way...
  I think the sorted list approach makes a hell of a lot of sense, as
does your hash table idea.  I would also be interesting in hearing
alternatives.
  Of course, once you get a bounding box intersection (or a hash table
collision, as the case may be) you don't need to do a *mask* compare, you
could do a polygon-polygon intersection, or a circle-intersection test,
or various things like that...

>What about hashing?  Can that be done?  Hash on some absolute location
>every time through the loop for each object, and just compare those
>objects that hash to the same place.  It seems like this could be
>really fast (O(n)) and easy to implement.  And you don't have to worry
>about those damned sorted lists :o).
  Well, when I was typing up there it seemed like a good idea.  But now
it doesn't.  Why not?  Well imagine starting at x=10.  That hashes to a
particular value.  Now presumably you want nearby coordinates to hash to
the same value (so you do, in fact, detect a collision), so x=11 would
probably hash to the same value.  Continue upwards until your hash function
produces a different value, at say x=20.  Now.  Suppose you have a sprite
at x=19 and one at x=20.  Clearly they should collide, but they hash to
different values.  So how do you detect the collision?
  Also: what exactly are you hashing on?  The center of the sprite?  The
left edge?  What about sprites that are very wide, such that they collide
with objects that hash several places away?  Etc.

-Ben Haller (deadman@garnet.berkeley.edu)