Sign in to follow this  

Using the book Numerical Analysis

Recommended Posts

lucky6969b    1330
Hello all, [cross-posted on other site, sorry :)] I am a noob in math so please bear with me. Currently, I get hold of a book called "Numerical Analysis" by Richard L. Burden and J. Douglas Faires There is a compact disc that comes with the book. Inside the CD, there are a couple of directories, one to use C and the others like matlab and maple to solve mathematical problems The problem now is that I want to generate a geometrical function to encompass all the computations on pathfinding that involve path smoothing. The map is about 300x300 points wide, with quite dense of obstacles. If I throw 90000 points with accompanying booleans at matlab or the c program, will it or will it not generate a function that fits in and solve all smooth turning problems (x,y) that I want to calculate. I was originally looking for a catmull-rom curve generation function with less than 3 control points, but I thought that was impossible. The original algorithm also worths a mention, I am using incremental pathfinding method which I call it "do-and-forget" the points are calculated at real time on the fly. I also use brushfire algorithm (HAA*) and an annotated map for clearance on the map... Any chance matlab will do that for me without extra labour? Thanks Jack

Share this post

Link to post
Share on other sites
grhodes_at_work    1385
I'm afraid that what you wrote isn't very clear at all. It sounds like you have a grid of 300 x 300 points (a heightfield?), and you want to cut holes in it to represent obstacles, then do pathfinding on the remaining set of points, using path smoothing to make a smooth path. And it sounds like with respect to the book, what you really want to know is if you give it a bunch of points can it find a smooth curve that fits through all the points. Is that approximately correct?

So, I don't know that book, don't know what it might have in it. I doubt you'll find anyone here who knows that book. But, many books on numerical analysis do talk about function interpolation, e.g., regression, splines, quadrature, etc. That said, it is not a good idea to try to find a high order curve that fits an arbitrarily large bunch of points. That would be expensive to evaluate, and would likely have undesirable artifacts...due to the need to have all the derivatives be continuous also. There can even be numerical instabilities. So, what you want to do is something like:

- Find the points you need, and sort them in the order you want them to be visited
- Build a curve that is piecewise, fitting through 3 or 4 points at a time, with tangent constraints at the ends so the transition from one segment to the other is smooth.
- You could just decide not to require all the points be hit. Just do a piecewise approximating spline, such as cubic Bezier curves between sets of 4 points.

There actually is a lot of good discussion about smoothing paths out there, for example the "Postprocessing for High-Quality Turns" chapter in the book AI Game Programming Wisdom 4.

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