• Advertisement
Sign in to follow this  

Path finding

This topic is 4404 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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]

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
the user will be able to place objects in form of an U

[target]

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

a graph algorthm would work here right?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by ID Merlin
Keep the value small relative to the cost and it doesn't interfer with finding the optimal path.


I find this quite amusing actually. The addition of a penalty redefines the cost function and hence the optimal path, so in one sense you're not interfering with it (because you're finding the optimum for that new cost function) but in the other, you are interfering with it (because you're finding not finding the original optimum)! ;)

Timkin

Share this post


Link to post
Share on other sites
Quote:
Original post by Timkin
Quote:
Original post by ID Merlin
Keep the value small relative to the cost and it doesn't interfer with finding the optimal path.


I find this quite amusing actually. The addition of a penalty redefines the cost function and hence the optimal path, so in one sense you're not interfering with it (because you're finding the optimum for that new cost function) but in the other, you are interfering with it (because you're finding not finding the original optimum)! ;)

Timkin


You are correct.

But in the real world, the path that a unit would choose would either be something that looks like a straight line, and not a diagonal move until you hit a wall. The point of path finding in a game is not to find any mathematically optimal path, but to find a path that makes sense to the human player watching the unit move.

Share this post


Link to post
Share on other sites
Quote:
Original post by ID Merlin
But in the real world, the path that a unit would choose would either be something that looks like a straight line, and not a diagonal move until you hit a wall.


Obviously path shapes should be considered during cost function design. I wasn't deriding your suggesting of penalising nonlinearity in the paths... I was merely pointing out your paradoxical comment and that I found it amusing.

Quote:
The point of path finding in a game is not to find any mathematically optimal path, but to find a path that makes sense to the human player watching the unit move.


I'd disagree on that point, since the human doesn't have all of the information, or might not be able to reasonably process nonlinear interactions within that observed data of the pathing domain. The path should reflect what the player expects, but should deviate from those expectations where necessary. A path that doesn't meet the players expectations indirectly alerts the player to something that they haven't perceived and so may be a useful design tool.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
There's nothing new in that article... such methods are functionally equivalent to finding a piecewise linear spline interpolant with gradient constraints (spatial and parametric).

I wasn't disagreeing with the merits of such techniques where they are applicable; only with your statement about the 'point of pathfinding in games'.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement