I've been given the task of implementing a pathfinding scheme (not my strongest part of game programming :P). I'm just doing a little research and experimenting with ideas. The basics of the enviroment is a simple 3D forest scene. All the trees use a cylindar for collision. I guess my question would be, if an agent has to go from point A, to a random point B, avoiding all the trees, which Pathfinding algorythm would suit the problem best? All the Pathfinding techniques that I have looked at, like A*, seem to tile based, or use predifined nodes to tranverse. But non of these seem to be able to adapt easily to this situation. Although the scene is rendered in 3D, it is essencially a 2D environment, with random circles scattered for collision. I give thanx for any help. (Any terms that I should google for?)

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?