A* and perculiar behavior
Author
Hi, so i've written a pathfinding algorithm. From what I can see it works, but it's a bit strange, i've attatched images to help me explain this.
http://img108.imageshack.us/my.php?image=pathnp0.jpg
basically my pathfinding guy walks along an axis until he 'has' to start moving diagonally accross nodes. in an open field this is a bit silly.
maybe A* is just too complicated for open fields. is a heuristic usually employed here where it's checked if the object can walk directly to it's target first before attempts to pathfind around obsticles are employed?
(Edited by mod to make link clicky)
[Edited by - Timkin on March 22, 2007 10:11:23 PM]
If I understand you correctly a lot of your issues will be down to the fact that you ai creatures can only walk down an edge.
One way of getting rid of this problem is to give nodes a radius to fill a large area and using anti nodes to steer around objects that are in the area. Then you can allow them to walk anywhere in a nodes radius or between two points with nodes of increased radius...
That probably doesnt give you the best explanation of what I mean but basically you need to consider making you path system more complex I believe.
One way of getting rid of this problem is to give nodes a radius to fill a large area and using anti nodes to steer around objects that are in the area. Then you can allow them to walk anywhere in a nodes radius or between two points with nodes of increased radius...
That probably doesnt give you the best explanation of what I mean but basically you need to consider making you path system more complex I believe.
Quote:Original post by Winegums
Hi, so i've written a pathfinding algorithm. From what I can see it works, but it's a bit strange, i've attatched images to help me explain this.
basically my pathfinding guy walks along an axis until he 'has' to start moving diagonally accross nodes. in an open field this is a bit silly.
maybe A* is just too complicated for open fields. is a heuristic usually employed here where it's checked if the object can walk directly to it's target first before attempts to pathfind around obsticles are employed?
You can use a line-drawing algorithm to plot a direct path from start to end, and if that doesn't collide with anything along the way, use that. Generally that just involves taking the line equation and using it to work out which blocks you need to pass through on a direct route.
More generally, you can create a path like you have done there, then loop through it, looking at pairs of nodes separated by an intermediate node. If you can plot an uninterrupted line between the 1st and the 3rd, you can remove the 2nd from the list. If you can't plot a line, move on to compare the 2nd in the path to the 4th, and so on. (This is probably most efficiently done as a binary search, but the linear approach is easiest to understand.)
You only expose a discreet world to your pathfinder, so it will only return a discreet path!
Easiest way is to smooth the path afterward like Kylotan explained. To be more efficient, you might want to use something better than a simple grid, maybe just a quadtree, or a navigation mesh, depending on what your world looks like. Either way, path smoothing in a form on another is usually a good idea in continuous worlds.
If you determine that this situation is often true, then that could be a good idea. On the other hand, when this situation arise, finding a path will be very fast and straightforward, so the gain will be minimal if your pathfinding algorithm is well optimized.
Easiest way is to smooth the path afterward like Kylotan explained. To be more efficient, you might want to use something better than a simple grid, maybe just a quadtree, or a navigation mesh, depending on what your world looks like. Either way, path smoothing in a form on another is usually a good idea in continuous worlds.
Quote:is a heuristic usually employed here where it's checked if the object can walk directly to it's target first before attempts to pathfind around obsticles are employed?
If you determine that this situation is often true, then that could be a good idea. On the other hand, when this situation arise, finding a path will be very fast and straightforward, so the gain will be minimal if your pathfinding algorithm is well optimized.
Or perhaps you are trying to solve an unnecessary problem. How does the algorithm act when you actually have a lot of grids? With such a small space, there is very little difference between the paths. It is quite likely that A* has many paths that are equal in their final cost and it just chose the one on the top of the list. A* views them as equal because of the mathematics of it. We view it is unequal because we see beyond the grids. If you were to be dealing with 30x60 instead of 3x6, the resolution would be a lot better. It's the same principle as to why fonts look jagged when you enlarge them. The granularity is the culprit.
A side comment on why the shown movement pattern might be optimal:
If turning to a new heading costs some unit of time or energy then the above solution is better than one might obtain with a 'straight' line.
If turning to a new heading costs some unit of time or energy then the above solution is better than one might obtain with a 'straight' line.
True, although I don't believe that is the case here.
Also, your point is NOT relevant if we are supposed to be representing a line as close as possible to the direct route - irrespective of grid (about 110 degrees here?).
Also, your point is NOT relevant if we are supposed to be representing a line as close as possible to the direct route - irrespective of grid (about 110 degrees here?).
Look up the Bresenham algorithm, which is the line-drawing that Kylotan was alluding to. If you're trying to determine paths in open regions of discrete grids, this is the easiest way to do it and gives you something that will translate visually onto the screen nicely.
Other than that, InnocuousFox has highlighted the relevant issue here. For the problem you've posed the pathfinder, there are indeed several solutions that are equally optimal. Why did you expect a solution other than the one you got? Why are you not satisfied with the solution you did get? Answer these questions and then consider how to rank the set of optimal paths the pathfinder can generate based on what you want. You'll need to change your pathfinder though, since A* returns only one path, being the first it finds. The member of the optimal set it returns depends on the order in which it inserts successor nodes into the open list, which is obviously dependent on the order in which you generate them.
Cheers,
Timkin
Other than that, InnocuousFox has highlighted the relevant issue here. For the problem you've posed the pathfinder, there are indeed several solutions that are equally optimal. Why did you expect a solution other than the one you got? Why are you not satisfied with the solution you did get? Answer these questions and then consider how to rank the set of optimal paths the pathfinder can generate based on what you want. You'll need to change your pathfinder though, since A* returns only one path, being the first it finds. The member of the optimal set it returns depends on the order in which it inserts successor nodes into the open list, which is obviously dependent on the order in which you generate them.
Cheers,
Timkin
If you were to end up with a number of paths of equal value, you could then pass them through a filter searching for the one that "looks" the best given certain parameters. Those can be defined with a brief fitness test such as the ones mentioned here. In this case, for example, we want the box(es) at the geometric center of the straight line to be "lit".
Quote:Original post by InnocuousFox
If you were to end up with a number of paths of equal value, you could then pass them through a filter searching for the one that "looks" the best given certain parameters.
The problem though is that pathfinding algorithms aren't typically designed to return the set of optimal paths, only the first optimal path found. Obviously customisation is required to achieve this outcome.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
