Re: Space Wars-Collision detection...

----- Original Message -----
From: jeff hendrix <jhendrix@quark.com>
To: <vectorlist@lists.cc.utexas.edu>
Sent: Thursday, November 25, 1999 10:20 AM
Subject: Space Wars

> My progress on space wars has come a long way, in other words, it's
> getting close to being finished.
>
> I've run into a small snag. I was working on the ship to ship
> collision routine and when I got it close to being finished I tested it
out
> and it slows MAME down to a crawl when it gets called. I'm checking every
> segment against every segment in the opposite ship. I'm checking 11 on
ship
> 1 and 9 on ship 2 for a total of 99 checks.
<very complex calcs skipped>
> This works find for shot collision detection (I'm using the old shot
> position and the new shot position for the line endpoints), but it's way
too
> slow for ship to ship.
> What I'm wondering is, does anybody have a simpler way to check for the
> intersection of 2 lines?

This may work for you.
I use a mutal collision det system. It works like this:
(this assumes the routine has already ran like 10+ times...)
You have two objects, A and B. A is in the process of being drawn,
sequentially around the outside (say it's an asteroid) "A" aready knows what
its
closest point to "B" was from last cycle. (Explained below)
It uses this as a base point to detect collisions with "B".
"A" tests only 3 points on itself; (no matter how many there are in the
object-
this routine DOES assume a vector draw, not bit-mapped) the closest point on
"B" to
object "A" last cycle, the one previous on "A"(say CCW), and the one after
on "A" (CW).
If one of the 2 outside points is closer, then it becomes the new target
point for "B" for its own
calculations next time. I Use distance (SQR(X*X+Y*Y) measurement, to
reference
(and this is the cool part!!) the point that "B" found
closest to "A" on itself while IT was being drawn!! Collisions are then
just a matter of proximity,
(If distance<40 then goto blowup) or detecting X/Y axis crosses within a few
steps!

Now-there are problems...if the object is spinning or moving too fast, the
system can lag...
having a wrap-around screen means that the object that just wrapped will be
screwed up-
for a few cycles-the "closest point" is on the wrong side! Also, when an
object is "born"
it takes a few cycles for the other objects to "align" themselves
initally...
Also, depending on draw seqence, the values used for the test may be 1 cycle
old(if the the object
has not been re-drawn yet) this could lead to some weird results!

Good stuff:pretty accurate, but only if the object is nearly circular.
+Every object "knows" how far away all other objects are, all the time!

Only 3 tests and some simple math for collision det-say 10 objects:
"1" tests "2" through "10" 9X3=27 tests (objects don't test themselves)
BUT this is done for EVERY object as it is drawn,
so 10X27 =270! Not too bad!
For your 2 ships: 1X3=3, 2X3=6!!! (only 6 tests?!?!)
Dream screen:100 objects 99X3=297 100X297=297000 tests (URP!-worse than
log(x)!!!)

I'm putting this idea in a game I'm working on... Asteroids 20,000 :*)
Don't get me wrong-it's a bit more complex than this, but it seems to work
ok for my game,
and the basic idea is sound-you don't need to test every point! (Or every
object either!)

> I'm implementing the following formula for each segment check (re-written
in
> assembly, of course, for a total of about 300 lines of code)
>
> x1,y1 - shot initial position
> x2,y2 - shot new position
> x3,y3 - last point from ship used to check collision
> x4,y4 - new point from ship used to check collision
> a1=y2-y1
> b1=x1-x2
> c1=x2*y1-x1*y2
> r1=a1*x3+b1*y3+c1
> r2=a1*x4+b1*y4+c1
> if r1 & r2 !=0 & have same sign, they don't intersect
> a2=y4-y3
> b2=x3-x4
> c2=x4*y3-x3*y4
> r1=a2*x1+b2*y1+c2
> r2=a2*x2+b2*y2+c2
> if r1 & r2 have same sign, they don't intersect
>
This is impressive, but I am a little lost here!
Using all integers can help, store positions/data in large numbers then
scale down
to draw-it adds speed!

Aaron Howald-soon author of "Asteroids 20,000"
ahowald@w-link.net
>
> -jeff
>
>
Received on Sat Nov 27 02:39:52 1999