Development:AI Navigation

From VsWiki
Jump to: navigation, search

At present the navigation routines are quite limited.

The files involved are flybywire.* and navigation.*

Problems with the current routines are: They are unable to navigate (efficiently) in a ship that has 90% of its thrust only available in the forwards direction.

A solution I am pursuing is a general system of implementing states...

moveTo(position, velocity, heading, angular_velocity, time) where a valid argument set would involve between one and all of the vector arguments, and optionally time.

At present, a valid trajectory for a ship is limited only by the absolute acceleration, that is, the acceleration in any direction. A fairly reasonable trajectory to interpolate between two points, each with an associated velocity can be calculated using a cubic bezier, where the length of the control points is relative to the velocity at the point.

[ézier_curve It may help to read this page on wikipedia for more information on beziers]

A cubic bezier, for the purpose of this, can be defined as a function with four static parameters (the four control points), and one parameter that varies from 0 to 1 (i'll refer to this as x). Bezier(p0, p1, p2, p3)(t), to use a python like syntax. Or bez = Bezier(p0, p1, p2, p3), bez(0) == p0, bez(1) == p3

A bezier can be of any order, cubic, quadratic, linear and I suppose, a single point.

The derivative of a cubic bezier (with respect to the parameter x) turns out to be a quadratic bezier. What's more is that the control points that define this bezier, are simply (p3 - p2, p2 - p1, p1 - p0), the second derivative of a cubic bezier turn out to be a linear bezier, where the control points are given by (p3 -2p2 +p1, p2 -2p1 + p0) (I'm sure you can see a pattern forming here, I think I'm missing out some constants here, don't care)

If we set dx/dt = k . velocity (the change of the parameter with respect to time is directly proportional to the velocity of the ship), with a cubic bezier, the acceleration of the ship will be a linear value between p3 -2p2 +p1 and p2 -2p1 + p0, so, by forcing these values to be within the circle defined by the ship's maximum acceleration, it constrains the trajectory to the set of all possible trajectories. yay!.

More to come, I'm not a writer :)

cracken 20:38, 19 December 2006 (PST)