our strategy game looks like this screen: how would you do the path finding around the palms and houses? my first idea was to use a grid on the terrain but it does't look very good. would you recommend a lib (opensteer)? any ideas. [Edited by - Eitsch on January 19, 2006 9:36:17 AM]

If your maps are going to stay that simple, then you don't need anything all that fancy at all. That house is convex, as are the trees, and both are fairly small.

Steering behaviours would probably be a good idea. Just having them steer towards the goal and away from nearby buildings and trees should get them to the goal just fine.

Of course, if you can build buildings really close to each other so that they end up creating mazes, then you might want something more complex.

just do normal grid based A* pathfinding. when an object is placed down you mark the grid-cells that it occupies as "obstructed". then A* will just find a happy optimal path. easy-peasy

-me

Along the same lines as xEricx's thoughts... Consider the palm trees. They're static and hence define a natural set of nodes for a triangulation of the landscape. Generate that tiling. Now permit pathfinding between geometric centres of the constructed triangles, with connectivity of triangles defined only where they share an edge. You can use whatever pathfinding algorithm you like. Since the domain is quite small in the number of triangles, I'd suggest using a Distance Transform algorithm rather than A*.

Whatever you choose, the generated paths will not intersect a tree except in the case where a path passes between two trees with insufficient spacing for a unit to pass (unlikely). Now smooth the path. My preference would be to do this at run time by having the agent track ahead by 1 waypoint (so it doesn't track the next waypoint in the sequence, but the one after that). If it finds an obstacle lying on the straight line path ahead of it, it chooses to steer back toward the path (i.e., toward the waypoint it is skipping). Make sense?

This method permits you to build coarse paths quickly and to refine them during movement in a dynamic fashion. This latter is desireable if multiple agents are pathing in the same area.

Now, as for your houses... just use the corners of the bounding box as nodes in the triangulation and remember to remove the resulting internal triangles generated.

Cheers,

Timkin

the user will be able to place objects in form of an U

[target]

___________
|..[pos]......|
|................|

a graph algorthm would work here right?

Quote:Original post by Eitsch
a graph algorthm would work here right?

A graph algorithm will work in any situation in which you can transform the pathing domain into a graph. Shapes such as the horseshoe (U-shape) are particularly troublesome for local search techniques and easily dealt with using graph-based search. The tradeoff is when do you do the computation... prior to moving if you use a global (graph-based) search or online (when you hit a snag) if using a local search.

For such wide open spaces as depicted by your image, a graph based search will be inefficient unless you use a heirarchical pathfinding approach. I would suggest combining coarse graph-based pathfinding with steering behaviours.

Cheers,

Timkin