Non A* Pathfinding

Good old steering behaviors would fit the bill:

Craig Reynold's page
Open Steer

Open Steer has all you need to do such a thing.

Good luck!

Thanx xEricx for the great links. I now have a pretty firm grasp on the theory of what I need.

I guess what I'm looking for is a mix of _Seek_and_Flee_ and _Obstacle_Avoidance_.

However, I'm in need of more information about the Obstacle Avoidance demo. I've searched google, but it's hard to find anything that comes anywhere close to a programming aspect.

I just need some info on the techniques involved in the Obstacle Avoidance demo, like (what appears to be) Box->Circle Collision Detection and Response.

I believe seek, flee, and obstacle avoidance behaviors are often implemented using a potential field method. Each object has a field associated with it, and the agent tries to go in the direction along which the positive value increases most quickly.

The code really is incredibly trivial - if you're having to look elsewhere to find it, you're probably overestimating the problem!

To be honest I never heard of anybody using potential fields for seek, flee, or obstacle avoidance. They're typically just implemented as simple vector arithmetic based on the target in question.

With obstacle avoidance, you can check to see if you're on a collision course with the obstacle (project velocity forward by a certain amount, check for intersection with object), and if so, add a steering vector to move away from the obstacle. Find a vector to the obstacle that's perpendicular to the direction of travel, and you need to steer in the opposite direction, with a magnitude inversely proportional to the distance to the obstacle.

Just to clarify, A*, and Dijkstra's algorithm (wich is practically a particular form of A* where the heuristic is 0) are not "tile-based", they are algorithms for finding a path in a graph - i.e. a set of nodes interconnected by edges, with costs associated with each edge. They are usually used for tile-based games because the graph is implicit in the tile structure - each tile is a node unless you can't walk over it. How you get a graph from your 3D data is up to you. Laying out some nodes manually and leaving the engine to find out wich nodes are directly accessible from each node, is the simplest way to do it.

Although, it doesn't sound to me that a forest with isolated cillindrical trees needs much of a pathfinding algoritm, so steering behaviours is indeed the best choice in this case. But don't you have buildings, stairs, rooms, briges, rivers you can't walk over etc?