path finding using splines and thier derivatives...

Dwiel · 2003-04-27T05:49:32

Hello, I have been thinking about all of the different pathfinding algorithms and was trying to think of a way to do it mathematcially by creating an equation f that would return the cost of a unique path through the map defined by a single variable x. The derivative of this function could then be tested for zeros. These zeros could then be tested until we found the one that was the absolute maximum of the function. One major problem with this method is the part "a unique path through the map defined by a single variable x". if this variable x is not continuous in the interval of inspection, then we can't take the derivate of the function that uses it, for the function will also be discontinuous in theis interval. The only solution is to have an infinate amount of possible x values inside the domain of the problem; which is not present in a grid system. (there are a finite number of paths in a grid system) The solution to this problem, in my opinion, is to use a spline to define the path that will be passed to the function f which calculates the cost of the path. The spline can hold an infinite number of paths inside our interval and can be limited to the number of curves allowed n, by using n - 1 control points. Now that we have a method for uniquely defining our path, we need to figure out how to find its cost. If we have a continuous surface, then we can find the total cost by finding the area between the spline path and a projection of that path on a plane underneathe the cost-surface. I am not sure mathematically how to do this, but with higher calculus this should be possible. I can take a stab at how to find this area... if we make a function f(x) where x is the distance travelled along the spline path that returns the height of the cost-surface at that point, we can easily take the interagal of this function to find the area. Now say we have this function costofpath(somepath), we can take its derivative, find the zeros and test each one to find the absolute max. This would result in the BEST path from point a to point b which n amount of curves. The derivative of the function costofpath(somepath) should be able to be simplified and reduced along with a function which returns zeros on this curve. It is fairly simple from there. I know for a fact that this all sound very intricate, but I am just wondering if it is feasible at all... I don't see anything wrong with it theoretically, although if I did, I wouldn't be postign this... I was planning on using Mathematica to do most of the calc/complex algebra for me so that it could be simplified down to a single function which would be converted to code and be very efficient. Hope someone out there at-least somewhat understands me Dwiel [edited by - Tazzel3d on April 17, 2003 7:13:29 PM]

Artificial Intelligence Programming

Started by Dwiel April 17, 2003 06:11 PM

10 comments, last by Dwiel 21 years, 4 months ago

Dwiel

Author

365

April 23, 2003 09:10 PM

Eelco: Thanx for the info... I am actually having a harder time figuring out how to come up with the splines given control points.... Would you be able to provide me with some equations? preferably in the polar coordinate system... I guess then differentiating would then be very easy because it would be reduced to constants, the control points, and t, the increment variable used for the polar function. If you are going to let me in on how to make the splines, I would also like to add that I would like them to at-least be differentiable at points where two meet. SO if I had 8 points which defined two splines, I''d like for them to be formed so that the point at which the two share a point have the same slope...

Thanx a lot!!!!!

Dwiel

[edited by - Anonymous Poster on Febtober 93, -4793 BC 56:69:80 MP]

Dwiel

Eelco

301

April 27, 2003 05:49 AM

>SO if I had 8 points which defined two splines, I''d like for
>them to be formed so that the point at which the two share a
>point have the same slope...

thats simply a matter of placing the endpoint of one spline on the startpoint of the other. besides the two controllpoints next to these equally positioned two points should both point away from eachother, ie their dotproduct should be -max. if you want the second dericative to be a smooth curve too, they should also be of equal length, but i think thats not an issue.

i wouldnt know what you need polar coords for btw... anyeway here are the formulas, you can convert the outcome of those to polar as you please. this is for cubic splines btw.

Pn are controlpoints 1-4

then the spline can be redefined as C3 * T^3 + C2 * T^2 + C1 * T^1 + C0 * T^0

where:
C3 = P1 - P2 + P3 - P4
C2 = P2 - 2P3 + 3P4
C1 = P3 - 3P4
C0 = P4

then you an easily get the derivative, by doing 3C3 * T^2 + 2C2 * T^1 + 1C1 * T^0, or the integral if you wanted to, but im not sure what could be an application of the integral. anyway i hope this gets you a little further

path finding using splines and thier derivatives...

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

path finding using splines and thier derivatives...

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines