I''ve implemented pathfinding in a game as such: The land is carved up into convex subspaces ahead of time, and high level pathfinding is just an a* search using the subspaces as nodes. Finding a high level path isn''t a problem, ie. unit wants to get from one area to another, high level path guides him around the mountain, etc... What I need now is a low level pathfinding, or at the very least, something that can get the units to walk somewhat intelligently around obstacles The land isn''t split up into any sort of grid, ie. the space units can occupy is continuous, but I''m willing to take any suggestions on how to implement this. I''ve looked at some gamasutra articles, and of course boids stuff. Are these the best sources, or are there others?

Do you use path/waypoints in it or not?

There are several ways to discretise the continuous motion across finite size areas. Have units enter and exit areas at the midpoints of polygon edges. Then paths through the area are straight lines from one midpoint to another. If there is a static object within the area that blocks such paths, then you can define fixed alternate (nonlinear) paths across the area. In the situation where you have a dynamic object blocking a path, perform a small search within the area to find the shortest path around the object and back onto the midpoint-midpoint line.

That''s one idea. The other is to use potential fields. Define a line through the area that is the preferred path. Define a potential field that increases away from the preferred path. Dynamic objects also create small potential fields with highest potential at the object. During each frame, move the unit in the direction of lowest potential gradient.

As a last suggestion, discretise each polygon and perform search for a path through the polygon once the unit enters the prior polygon in the list of polygons returned by the high-level pathfinder. That way there should be a path ready by the time the unit gets into the next polygon.

These are just ideas. Feel free to use them or not.

Cheers,

Timkin