Sign in to follow this  
deffer

Searching for equation using GAs or NNs, or (?)

Recommended Posts

deffer    754
Good day... So... I'm searching for an algorithm to create smooth paths (in 2D), that my units could be following. --BACKGROUND-- I'm having waypoints (chewn out from A*) and I want to plot a nice spline to connect them. Nice, as in C2 continous. That's child's play - I got a 5th degree poly between each consective pair of waypoints. I'm building it given: entry velocity, entry acceleration, exit velocity and distance vector. There are two polys: Px(t) Py(t) where t varies from 0 to T, where T is the exact time to travel between given pair of consective waypoints. Now, what I want: I have an upper limit to velocity, and a similar to acceleration. I don't know T. I've also noticed that it's better not to use fixed exit velocity, so I got only a general direction of exit velocity, but I don't know the magnitude of exit velocity (let's call it k). And I want to minimize T (not minimize, as, finding the minimum, but I want my units to travel resonably fast). --PROBLEM-- I'm searching for a set of equations, that given: vel0, acc0, dist, velexit - 2D floats (8 floats) velmax, accmax - floats (that makes it 10 floats overall) would give me: T, k - floats I know that there is no way on earth I would come up with it [grin]. But I can afford to search for it in an organized way. I don't know, maybe some 10x2 matrix would suffice. I don't know too much about GAs or NNs, hehe, so could someone lend me a hand here?

Share this post


Link to post
Share on other sites
Palidine    1315
Perhaps not the answer you're looking for.

It wasn't my area of expertise but I did dip into the locomotor code of the last project I worked on. The fine tuned steering was decoupled from the path planning. That is, the A* was only optimized, not smoothed into a curve. The locotomor was responsible for steering the unit along the path within the bounds of it's turn-rate and such. The end result is a smooth walk-through of the A* without actually having to solve the smooth path ahead of time.

Basically, the locotomor tries to steer from node to node within it's bounds. There's inevitably some logic in there about whether it's better to keep going for the "next" node or whether to just skip that one and go on to the next. I remember orbiting bugs from this solution as well that we had to fix (unit gets into a perfect orbit of the "next" node).

The advantage this system had over a completely pre-planned path was that you could do entity avoidance without re-pathing. So if me and my buddy cross paths, we can happily bump & steer around eachother and then resume following our path.

-me

Share this post


Link to post
Share on other sites
deffer    754
That's the kind of behaviour that lets your character move around.
And that's how I plan to do it. In the end, my entities will be moving step by step, just as you described. I don't plan to use this ideal path per se. Only as a general reference.

But somehow I got to find out ahead the stats of the path (mainly duration), so I can pass them to AI. And I want those stats to be quite accurate.

Share this post


Link to post
Share on other sites
Timkin    864
So you're basically looking for an algorithm to fit a b-spline (with 5th order bases) to a given set of control points, subject to constraints on the parametric velocity of the curve. I would not be looking toward a GA or ANN for this task, but rather a deterministic constraint satisfaction optimisation technique. There is a huge amount of literature in Operations Research on solving such problems. I'm not an expert in this area, so I wont presume to suggest the best OR-based algorithm for you to use. Try [Google] or check out your local college or state library though; you're sure to find what you need there.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
deffer    754
Thanks for the info.
I looked into OR a bit, and it seems like a branch of programming used to solve some general optimisation problems. Mine is much, much simpler, I think..

Let me rephrase:
I'm not searching for an algorithm that will be calculating the spline (that would be too complex for me right now).
I'm searching for an algorithm that will calculate coefficients of an equation. Equation of fixed size and complexity. With that equation in my hands, I could be calculating splines over and over again, without any AI support.

I don't know if it makes any difference.
Is this a more common problem, with a known approach?

Sorry if I'm taking nonsense, I have almost no experience it this field, hehe.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this