Hi All, I've been reading up on pathfinding techniques for about the last month. Basically I want to create some sort of dynamic pathfinding for a 3d world, that allows flight capability as well, providing not just a navmesh walkable surface, but also a representation of the world at any given height. I'm really interested in the possibilities of potential fields, in a voxelised structure, to allow for obstacle avoidance and natural paths. Also potential fields seems to lend itself well to dynamic obstacles, it would be easy to add new weights to a given area and recalculate local potential. Right, disclaimer: This is my first attempt at anything like this, I want to research the topic for the next year and come up with a solution early for my dissertation, which starts next year, and goes on a further year. I have some experience with game programming, but it is basic compared to some of you guys. I'm also not really up on all the terminology yet, but I'm getting there :) Basically, I have an idea in my head, but I think I'm gonna need some way of depicting walkable areas, al a dynamic navmesh. I've a good algorithm in my Game Programming Wisdom 4 book. It occurs to me I'm also gonna need to represent obstacles as well, in the form of potential fields. My main concern is that I want the npc to naturally "hug" the ground, and if I use potential fields to depict walk height too (probably not the way forward), I'm gonna need an obscenely fine voxel grid, or it ain't gonna be right. I'm therefore thinking of a hybrid approach with navmesh for walkable level(s), and potential fields emitted by non walkable areas/obstacles. I need some viewpoints offa some of you more experienced guys, who could probably put me straight in five seconds flat :) Cheers, Will.

Good starting point here for A*

http://www.gamedev.net/reference/programming/features/astar/

To hug the ground you could increase the cost to move to a cell that was higher than the current one.

Also there's some further reading on making the paths more natural.

Mark

Hi mate, I think you've missed my point, maybe I wasn't very clear. I'm aware of A*, D* and variations. Potential fields can be used on their own to resolve paths, and that's what I want to experiment with for my dissertation. A*, from what I read, isn't the best for realtime calculations of the kind that would be needed for dynamic situations (obstacles etc), and a potential field system can be very near realtime as the path only needs to be computed to the next grid/cell position.

I've seen potential fields working with numbers, it's fast. Also there is no need to do additional smoothing and steering calculations, the path is balanced by the forces present in the world. Basically potential fields seem to me to have loads of "potential". Remember a goal is made up of an attractive potential field, and if presented right the agent can find it's way down the gradient to it. That's what interests me most, as a replacement to traditional pathfinding algorithms.

The reason I want a navmesh, is I'm going to need to describe some sort of height guide to the agent, to show walkable areas. Length and width movement calculations will hopefully handled by balancing the fields in the world, but it still needs a floor to stand on, and to depict impassable areas.

My perspective:

There is only one truth in pathfinding, and it is the Bellman Value Function -- also called the Cost to Go. Don't think about paths; think about this function.

- Potential fields are approximations to the Value function.
- Navmeshes give a way to discretize the value function.
- A* allows one to compute the value function over a small region containing (1) the start, (2) the goal, and (3) an integral curve of the gradient starting at the start (in simpler language, #3 is the shortest path).

You see the same ideas over and over again, and they are, at heart, all ways of getting a handle on the Value Function.

Both voxels and navmeshes are "just" finite-element schemes for discretizing the Value Function. In fact, they can both be viewed as basis expansions.