Path: chuka.playstation.co.uk!toby
From: toby@angst.forefront.com.au (Toby Sargeant)
Newsgroups: scee.yaroze.freetalk.english
Subject: Re: Collision Detection Shortcut Update
Date: 27 Feb 1998 00:51:20 GMT
Organization: PlayStation Net Yaroze (SCEE)
Lines: 62
Message-ID: <slrn6fc3pn.q20.toby@ns.forefront.com.au>
References: <6caa8e$5bj12@scea> <34F3BA79.6168@bc.sympatico.ca> <34F55175.2793@mdx.ac.uk>
NNTP-Posting-Host: ns.forefront.com.au
X-Newsreader: slrn (0.9.4.6 UNIX)

On Thu, 26 Feb 1998 11:26:45 +0000, Robert Swan <rs108@mdx.ac.uk> wrote:
>Some comments about collision detection, now that I'm implementing it
>into a game, but first I'll describe my game (ROTATE.ZIP from my
>website) to show you the
>context, and I'm hoping someone can come up with something faster.
>
>In my game an enemy ship is stored as a (world_x,world_y) coordinate and
>as an
>angle depicting it's orientation (rotation). What I need to do is to
>determine
>whether the ship should turn clockwise or anti-clockwise in order to
>turn towards the player's ship.

here's another suggestion:

Given ship at (x,y), a direction theta, and a target at (x2,y2)

calculate the cross product of the vector formed by theta with the
vector to the target:

Ax = sin(theta)
Ay = cos(theta)     -- lookup tables

Bx = x2-x
By = y2-y

C = Ax.By - AyBx

then:

C = mag(A).mag(B).sin(aplha)

because A is a unit vector, we can drop it from the equation, giving:

C = mag(A).sin(aplha)

mag(A) is just the distance to the target.

from this, you can get the angle between the two vectors, at the cost of a
square root and an inverse sine. sin^-1 can be computed as a lookup table,
and there is a very fast algorithm for integer square roots, which a web search
will no doubt drag up.

there are, as you've pointed out, varoius approximations to the magnitude
function, and you don't need to do it anyway; all you need to know is the
sign of C, and a function related to the magnitude of C which determines the
rate of turn.

because sin(theta)==sin(pi-theta), you can't tell whether the target is behind
or in front of you.

To determine whether the target is behind or in front of you, compute the
dot product of the two vectors:

D = AxBx + AyBy

if the sign of the dot product is negative, the target is behind you.

the dot product is also equal to mag(A)mag(B)cos(alpha), which might be handy,
but probably won't be.

Toby.