NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/sys/amiga/programmer/6884

Internet Message Format | 1996-08-05 | 6.7 KB

Subject: Re: Collision Detects !!!!
References: <[e-mail]>
Distribution: world
X-Newsreader: TIN [version 1.2 PL2]
Path: imada.ou.dk!breese
From: [e-mail] (Bjorn Reese)
Message-ID: <[e-mail]>
Sender: [e-mail]
Nntp-Posting-Host: salieri.imada.ou.dk
Organization: Dept. of Math. & Computer Science, Odense University, Denmark
Date: Thu, 4 Apr 1996 11:52:56 GMT
Newsgroups: comp.sys.amiga.programmer

[ Sorry if this appears twice. My newsreader died on me when I
  tried to post it the first time. ]

John Girvin ([e-mail]) wrote:

> px2 = player->x + player->width        // PreCalc player BRHC coords.
> py2 = player->y + player->height
>
> for (i=1; i<num_bullets; i++)
> {
>     if ( (bullet[i]->x - px2) < (bullet[i]->width + player->width) &&
>          (bullet[i]->y - py2) < (bullet[i]->height + player->height) )

I might be missing something, but it seems to me that this only works
under the assumption that the bullets are to the right and above the
player (ie. bullet[i]->x < player->x and similar for y.) Furthermore,
as player->width is present on both sides of the inequality it can be
omitted.

> A not-so-obvious optimisation depends on the shape of your playing
> area. If its tall and thin (eg: vertical scroller) then it is more
> likely that the Y-coords will be "out of range" than the X coords,
> so you should shift the Y comparison to be first in order to be more
> likely to discard non-collisions on the first comparison. Vice-versa
> if your playing area is wider than it is tall.

Yes, this is a nice optimisation technique which also may be applied
to programming in general. For instance if you have to do different
things if a value is positive, negative, or zero, it may be a good
idea to check for the positive case first if that is most likely to
happen.

Optimizing collision detection is strongly dependent on the
environment in which it takes place and the number of entities to
check.

The simple "check all ordered pair of entities" approach will
always win over more sophisticated approaches if the number of
entities are small (without specifying how small "small" is.)

With specific knowledge of the environment in which to do the
collision detection must take place, there are specific tricks
that you can utilize. One that immediately springs to mind is if
you have a horizontal scrolling game (same applies to vertical
scrolling) you can keep all entities in a list sorted by the
x-coordinate. Instead of checking for collision with all other
entities, it is sufficient to check with those within range.

> Also, look for references on "sector based collision detection",
> especially around rec.games.programmer archives (HINT!). It might
> help you more if you have lots of objects to check.

I never really liked this idea of subsections for two reasons.

  (1) Problems with boundaries. To solve this you have to check
      the neighbouring subsections as well.

  (2) Static segmentation. Choosing many small subsections may
      require too much management of their lists (or arrays) as
      the entities moves around. Choosing fewer bigger subsection
      will gain nothing if most entities are clustered in the
      adjacent subsection (which they often are.)

Subsections (static partitioning) can be sketched by this

  for previous, current & next y-subsection
    for previous, current & next x-subsection
      CheckCollision

Add to this the cost of maintaining the entities in the subsections.


I personally prefer a dynamic partitioning. This is an extension of
the horizontal scrolling trick mentioned earlier in this letter.

What you do is maintain two linked lists; one with all entities sorted
by their x-coordinate, and one by their y-coordinate. It isn't necessary
to sort the entire lists each frame. As the entities only move relatively
short distances you can just "bobble" the entities into their correct
position (ie. let them switch position in the linked list if their
keys - the x and y coordinates respectively - demands this.)

Okay, now that we've got the two ordered lists, it is sufficient to check
for collision with the entities that are within range by transversing
through the lists. Once we get to an entity that is out of range we can
discard the rest of the list (in one direction as we have to check each
list in both directions from the current entity.)

This, however, can be further "cooked down" if the collision handling
is expensive in itself. Currently we check a "band" on both the x and
y axis (the x's, y's and the O in the figure below) although we only
need to check the intersection of these two bands (the O.) To do this
we just mark entities as potential check when we run through the x
list, and do the collision handling when we run through the y list
if they were mark in the previous run.

    +------+-+----+
    |      |y|    |
    |      |y|    |
    +------+-+----+
    |xxxxxx|O|xxxx|
    +------+-+----+
    |      |y|    |
    +------+-+----+


So what you need to do is the following

  while (|dx| > dx0) do
    mark agent
  while (|dy| > dy0) do
    if (agent is marked) then HandleCollision

Furthermore there is the cost of maintaining the two ordered list, plus
the set used for marking.

The (untested) code below works under the assumption that there is a
known maximum number of entities (SETSIZE), and that each entities has
a unique ID number (from [0,SETSIZE-1].) Furthermore, the maximum width
and height of the entities must be known (XSIZEMAX and YSIZEMAX.) An
entity is called an agent.


typedef struct Agent {
  /* ... whatever ... */
  int xpos, ypos;
  int xsize, ysize;
  int id;
  struct Agent *xnext;
  struct Agent *xprev;
  struct Agent *ynext;
  struct Agent *yprev;
} agent;


/* for each agent call Collide() */

void Collide(agent *p)
{
  static unsigned int scnt = 0;
  static unsigned int set[SETSIZE];
  agent *s;
  int t;

  if (scnt++ == 0) memset(&set, '\0', SETSIZE);

  t = p->xpos + p->xsize + XSIZEMAX;
  for (s = p->xnext; s && (s->xpos < t); s = s->xnext)
    /* --- Mark s->id as member of set --- */
    set[s->id] = scnt;
  t = p->xpos - (p->xsize + XSIZEMAX);
  for (s = p->xprev; s && (s->xpos > t); s = s->xprev)
    set[s->id] = scnt;

  t = p->ypos + p->ysize + YSIZEMAX;
  for (s = p->ynext; s && (s->ypos < t); s = s->ynext)
    /* --- Is s->id member of set? --- */
    if (set[s->id] == scnt) HandleCollision(p, s);
  t = p->ypos - (p->ysize + YSIZEMAX);
  for (s = p->yprev; s && (s->ypos > t); s = s->yprev)
    if (set[s->id] == scnt) HandleCollision(p, s);
}


Sorry 'bout the long posting. I sorta got carried away ;)

--
Bjorn Reese                      Email: [e-mail]
Odense University, Denmark       URL:   http://www.imada.ou.dk/~breese

"It's getting late in the game to show any pride or shame" - Marillion