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]

Interesting. I love Calculus (though I''m only in my second year), but I''ve never tried applying it to pathfinding. Ultimately, since game worlds tend to be very discrete and calculus relies on continuity, I don''t know how successful the approach will be, but it sounds really interesting, so I''ll give it a shot.

I can''t think of a solution now, but I can see an immediate problem. You''re trying to find the lowest cost spline by minimizeing its cost/length function - but, though there are infinitely many paths definable by that spline, it still can''t define ALL paths. That depends on the number of control points - which brings us into piecewise functions, and away from calculus.

I''m going to think about this, and post back.

I am only in my 1st year calculus, but have done some reading in a 1st/2nd/3rd year book for fun ... I''m prety sure that if you have n control points, you will be taking the derivative of a function with n variables (at least), which I don''t know how to do right now... I''m only on single variable though from what I have read in my book, It isn''t much different. I believe you would need to decide on a maximum number of control points before you start the algo... I''m going to talk to a friend at school who is currently in what ever comes aftr year 2 calc, and knows a lot about math in general anyway, and see if he knows how to find the area under the spline...

Good to hear that it doesn''t sound completly ridiculus...

BTW, I think that the surface would also have to be a spline surface so that it would be continuous and therefor differentiable...

Dwiel

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

TerranFury, just wait a year and you''ll see how calculus handles piecwise functions.

I am pretty sure that if we have some functions defined as:

x(t, p1, p2, ... , pn)="x coord of spline which passes through each of the n control points"x(t, p1, p2, ... , pn)="y coord of spline which passes through each of the n control points"C(x, y)="cost of passing over this area of the map at this presise point {x, y}" 

then we can find the area under the curve formed by the projection of the spline projected onto the surface created by C(x, y) by using the following equation:

Integrate[C[x[t, p1, p2, ... , pn], y[t, p1, p2, ... , pn]], {t, 0, 1}] 

My next step will be to figure out how to make the parameteric spline functions x(t), y(t) and surface spline function C(x, y)...

I am having a hadr time finding how to do this.. I have found code and detailed math papers on it, but nothing which says something similar to given control point p1, p2, p3, ... ,pn, we can derive a parametric function:.....

If anyone here can do this for me, that would be wonerful!!! maybe just some steps on how they are derived so that Ican derive my own for however many number of control points I will want and then later when I do it for the surface... BTW, I was leaning toward harmonic cubic splines...

Dwiel

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

While this is a thread about pathfinding - and hence AI - it is also one about maths and thus, you might get more discussion from taking this to the Maths & Physics forum, where, I can assure you, splines are discussed quite often.

However, since we''re here...

If you can describe your path in a piecewise fashion in the form described by Tazzle3D, i.e.:

x1(s) = f1(s;p1,p2,...,pn)x2(s) = f2(s;p1,p2,...,pn)...xm(s) = fm(s;p1,p2,...,pn) 

where (p1,p2,...,pn) are free parameters and presuming you can describe a cost function of the form

C = g(x  (s)) 

where x is the vector described above, then you can integrate C along the spline parameterised by s by integrating the differential quantity dC/ds. If x is a vector quantity though (i.e., of 2 or more dimensions) then this is not necessarily a trivial excercise.

The alternative to this (and the one I would recommend) is to reparameterise the functions x (s) to a new set of functions, x (u), such that the differentials du represent unit cost changes for movement along x . That is, the derivatives dx /du can be integrated to give the cost of movement along the path defined by x (u).

To perform numeric integration you can try the following integrators (in order of increasing complexity and accuracy): Euler, Simpsons, Runge-Kutta. Code for these is easily found online via google.

Cheers,

Timkin

Timkin: thanx for the input, I have been busy with relatives all weekend and have just now been able to check the forums again, but would you mind moving the thread to the math/physics forum for me? or any mod could do it... thanx.

For those who are reading:
I am currently tring to come up with the equation that I will be able to use for the path.. the spline.. if anyone here knows how to make these based on control points, the fewer the better, PLEASE thanx a lot!

Dwiel

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

quote: Original post by capn_midnight
TerranFury, just wait a year and you''ll see how calculus handles piecwise functions.

I know how to integrate and differentiate piecewise functions; that''s pretty common-sense-ical (New word! ). Yeah, you can differentiate or integrate the paths themselves, but I don''t think it''ll get you too far. I was talking about the cost function, which, in order to find minima on, you need to differentiate and look for zeroes (and test, of course, that they aren''t maxima, and then compare all the minima). I could see how to use that approach to find the best path with some fixed number of control points, but when the number of control points itself is also a variable, I just get hopelessly confused.

...or was that what you were telling me to just wait for?

I figured that you would set a number of control points that each path would have, and never let a path surpass that limit. This does somewhat limit the paths that can be chosen, but I believe that for my use, it should suffice to have a path nearing maybe 10 control points... Remember that a path using n points can always be recreated using n+1 points...

Dwiel

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

differentiating and integrating splines is quite simple: eliminate (1-t) and write the function in the form v1 * t + v2 * t ^ 2 + v(n) * t ^ n. the formulas for v are found when eliminating (1-t) for a given spline.
finding integrals or derivatives is a piece of cake then. i could give an example of this for a cubic spline if anyone is interested?