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

In that situation, A* would find the shortest path among the paths that run along grid edges. In most situations, these paths are not optimal at all (far from it) and look unnatural.

You could run an A* algorithm, generating the visibility graph on-demand for units.

Quote: Original post by Eitsch
my first idea was to use a grid on the terrain but it does't look very good.

I don't see why a grid wouldn't look very good?

Do you have a pass that removes unnecessary nodes from the path? As long as you can find a straight unnoccupied line between 2 nodes of your path, you can remove the nodes in between.

Hope this helps

Eric

Quote: Original post by ToohrVyk
In that situation, A* would find the shortest path among the paths that run along grid edges. In most situations, these paths are not optimal at all (far from it) and look unnatural.

You could run an A* algorithm, generating the visibility graph on-demand for units.

Depending on the granularity of your grid, this can give pretty convincing results...

Another option would be to generate a surface from which the shape of the bounding boxes (or collisions) of your entities are removed, then run a delaunay triangulation over this surface, merge these triangles into convex polygons. This should give you great nav meshes, but requires more complex calculations at runtime for new buildings insertion than grids...

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

A simple change to A* gives much more pleasing results. Simply add a fraction of the cost of moving one square for each deviation from a straight line from start to end point. Keep the value small relative to the cost and it doesn't interfer with finding the optimal path. The result is a path that follows more of a straight line.