Re: Space Wars

        Are you doing trivial rejection of the two ships (e.g. checking for
intersection of the bounding boxes of the ships before you bother going through
the individual line segments)? It still might suck because you'll get slow when
the ships get right next to each other, but that's typically how it's done.
After that, you should do trivial rejection of each line segment individually,
so you can skip those multiplies except in the most extreme situations.

        For example, if you have a line segment X1,Y1 to X2,Y2 and another
line segment x1,y1 to x2,y2, then if X1 and X2 are both less than x1 and x2
(or greater than x1 and x2) then you know you don't have a collision, and this
can be done with just a couple compares (no multiplies). Ditto for Y1 and Y2
vs y1 and y2.

        So, when you are checking for a collision of a shot with a ship line
segment each time through the movement loop, which ship line segment position
are you using? The current one (before its position has been updated) or the
new one (after the position has been updated by the ship velocity)? Either way,
you can get a situation where ships and shots pass right through eachother,
because the ship velocity is large enough to cause the ship to skip over the
shot line segment. In a PC game I wrote for fun a few years back, I hacked
around this by just making sure that the velocity (position offsets added each
time through the movement loop) could not exceed the size of the ship itself.
I don't know if it would really have a gameplay impact if you didn't do it.

                        Drew

   From: jeff hendrix <jhendrix@quark.com>
   Date: Thu, 25 Nov 1999 11:20:08 -0700
   Content-Type: text/plain;
           charset="iso-8859-1"
   Reply-To: vectorlist@lists.cc.utexas.edu
   Sender: owner-vectorlist@lists.cc.utexas.edu
   X-Listprocessor-Version: 8.2.07 -- ListProc(tm) by CREN
   X-UIDL: 347cbc941deffcd0286ad2dd9ac2030e

           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.

   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 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?

   -jeff
Received on Fri Nov 26 10:42:26 1999