Quote:Original post by Wyrframe
"per-object-per-frame"... while this will initially be simulated, a major goal is for it to be realizable as a distributed system of individual vehicles, each resolving and announcing their own projected paths. Picture like real cars, except instead of only gleaning information from looking at another vehicle's position, direction and velocity, and the status of its turn signals, we can analyze its position, direction, velocity, and what it plans to do over the next 10 seconds.

ten seconds isnt too much, i thought you were talking about much more.

Quote:
On iteratively seeking out closest-approach, that is a nice idea, but not feasable over the kinds of scales we're talking about. If iteration steps are over time-span, I might get collisions in the gaps in-between. If iteration steps are over distance, I might get an obscenely high number of points to test. An arc might be half a second and a quarter-meter long, or it might be a half-hour and fourty thousand meters long, depending on the environment, the vehicles being evaluated, and the time-spans involved.

if your rootfinding algorithm sucks, yes.

iterating trough all pieces of the path x seconds away from the vehicle is something you need to do anyway, right? and its of no speed consequence at all, assuming the pieces of your path are not .0001 second in length, were taking about a handfull of spline vs spline checks.

efficient and robust numerical rootfinding between two low-degree splines isnt very easy, but its very doable.

one way to do numerical rootfinding:

say your path is constructed out of quadratic pieces. the equation we need to solve is of the form |path1(distance(t)) - path2(distance(t))| = radius1 + radius2.

its not hard to see this equation can at most have 4 roots in case distance is a linear function of t. in case distance is quadratic with t (constant acceleration), path will evaluate to a 4th order, and the solution will have 8 roots at max. we are however talking here about HIGHLY hypothetical situations.

either way, evaluation the above formula at a couple of points, fit a polynomal trough them, and try and find its first root (a well documented subject). if you fit an 8th order polynomal, youre guaranteed to find all roots as long as your polynomal is a good approximation, but it most probably is. however, im quite sure fitting a quadratic and solving that with the ABC formula will work just fine unless you start pushing your algorithm into these unlikely scenarios.

well there are tons of methods to solve the above equation. another decent and simple method is to just sample the path at intervals < radius. its slow though for objects with small radius compared to their pathlength.

i think it would be wise to specify first how accurate it NEEDS to be precisely, and pick your method based on that, because one thing is for sure: youre not going to reach infinite precision without infinite processing power. everything is going to be an approximation, the question being: is it acceptable. i think the only way to find out is to try different methods. im certainly not able to give you a conclusive answer as to what is the best method.

one note btw: i dont think cars plan more than a few seconds ahead, and drivers certainly only take into account a very limited projection of other drivers.

anyway solving these equatios isnt going to be the hard part of this rather ambitious project youve undertaken. its going to be one massive headache, i can assure you that.