# A* and perculiar behavior

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

## Recommended Posts

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]

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by WinegumsHi, 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.)

##### Share on other sites
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.

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.

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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?).

##### Share on other sites
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

##### Share on other sites
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".

##### Share on other sites
Quote:
 Original post by InnocuousFoxIf 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.

##### Share on other sites
Can't you just change your heuristic? I assume you're using Manhattan Distance now. That's nice in that it's optimal for a square grid topology, but it gives no preference for straight-line paths. If you use, say, a Euclidian-distance heuristic instead, then on an open plane A* will reduce to a line-drawing algorithm.

If I'm right, that's the easy solution.

##### Share on other sites
It won't reduce to a line drawing algorithm, because the amount spent moving one discrete tile horizontally is roughly 2/3rds of the cost of moving diagonally, while the improvement to the estimated distance in each case is almost identical, until the angle between the current point and the target becomes steep enough.

##### Share on other sites
What about giving the heuristic a tiny preference (so that it only matters when considering otherwise equivalent-cost paths) for selecting paths that stray the least from a straight line (as measured by a dot product, for instance)?

##### Share on other sites
The problem is that they won't be 'otherwise equivalent'. In a path from (0,0) to (100,1), once you get to about (50,0) it's adding about 0.4 onto the current path length by moving diagonally (as desired) rather than continuing on straight, whereas the amount cut off the estimated remaining path by being at (50,1) rather than (50,0) is about 0.01. So the amount of bias you'd have to apply would presumably be quite high, and that might create inoptimal paths at other times.

##### Share on other sites
Hmm...

Looking at your illustration again I realize my comment about Manhattan Distance was silly, as if you'd been doing that then your character would have walked an L-shaped path.

I'm playing with this on paper. I still suspect that breadth-first search with a heuristic can reduce to line-drawing.

Let's number squares so we know what we're talking about: The top-left square is (1, 1), its neighbor to the right is (2, 1), and the neighbor below it is (1, 2) -- etc, so that the bottom right cell is (6, 3).

We probably agree that the 'ideal' path is,
(1,1)->(2,1)->(3,2)->(4,2)->(5,3)->(6,3)

We start at (1, 1). We add (2, 1), (2, 2), and (1, 2) to the OPEN list, and move (1, 1) to the CLOSED list. For these, the costs are,

C=P+T+H

where

P is the cost from the start to the parent cell,
T is the cost of the transition from the parent cell to this cell
H is the heuristic cost to get from the child cell to the goal.

(As you can see, I've split up the "parent cost" of A* (called G) into seperate P and T terms; I think that's clearer).

So, for these children, the costs are as follows:

(2,1):
P = 0
T = 1
H = 4.47
=> C = 5.47

(2,2):
P = 0
T = sqrt(2) = 1.414
H = 4.123
=> C = 5.54

(1, 2):
P = 0
T = 1
H = 5.10
=> C = 6.10

The lowest-cost one is (2, 1), so that's the one we look at.

Next, consider the children of (2, 1) not already in the OPEN list, and their costs. They are,

(3, 1)
P = 5.47
T = 1
H = 3.61
=> C = 10.08

(3,2)
P = 5.47
T = 1.414
H = 3.162
=> C = 10.05

Ah hah! (3, 2) has a lower cost than (3, 1)! So we go there!

Now we have in the OPEN and CLOSED lists (in no particular order, except that (3,2) is on top of the OPEN list -- I won't bother to keep things sorted as we won't hit that part of the OPEN list in this example):

OPEN: (3,2), (3, 1)
CLOSED: (2, 1)

Now consider the children of (3, 2) (not already in the OPEN or CLOSED lists). They are: (4, 1), (4, 2), (4, 3), (3, 3), (2, 3)

Of these, (4,1) and (2,3) increase the heuristic, so since I'm being lazy I'll say we can ignore (even though in an actual implementation you'd churn through and compute their costs, of course). I'll look at those remaining:

(4,2)
P = 1+sqrt(2) = 2.414
T = 1
H = 2.236
=> C = 5.65

(4,3)
P = 2.414 (as before)
T = 1.414
H = 2
=> C = 5.83

(3,3)
P = 2.414
T = 1
H = 3
=> C = 6.41

Of these, (4, 2) is the best. We do not continue on the diagonal when we better-approximate a straight line by moving along the axis!

Now, we have,
OPEN: (4,2), followed by (4,1), (4,3), (3,3), (2,3), (3,1), (2,2), (1,2) in no particular order.
CLOSED: (1,1), (2,1), (3,2)

Now consider the neighbors of (4,2): (5,1) is clearly going the wrong way. That just leaves (5,2) and (5,3).

(5,2)
P = 2+sqrt(2)
T = 1
H = sqrt(2)
=> C = 3+2*sqrt(2)

(5,3)
P = 2+sqrt(2)
T = sqrt(2)
H = 1
=> C = 3+2*sqrt(2)

We have a tie! But notice that if you only consider the part of the path that is remaining, either option leads to an equally-good approximation to the line: It's the difference between these two paths:
 __   \  vs.  \__

I have an intuition that this only happens for these very short paths.

I figure that little anomaly isn't too aesthetically annoying -- but if it bothers you, it can definitely be solved by adjusting your heuristic for paths of length <= 3, by choosing the path which results in the best r^2 fit of the last 4 points to a line.

With that exception, it does seem to reduce to line-drawing!

What about my understanding differs from yours, Kylotan?

##### Share on other sites
Emergent
Using only knowledge of the current position and the goal position you won't be able to do a line-drawing heuristic, since it does matter what the starting position was!

Your heuristic does make the path more line-like, but for cases where distance w << h or w >> h it won't make a straight line.

You heuristic will trigger a diagonal step when:
sqrt((x-1)^2 + y^2) - sqrt((x-1)^2 + (y-1)^2) > sqrt(2) - 1

But what if, in the given example, the goal was placed in (100,3)?

Well still the heuristic wouldn't trigger a diagonal step until it is (4,2) fields away from the goal, since generally for:
sqrt(x^2 + y^2) and
sqrt(x^2 + (y-1)^2)
an large x will only decrease the difference between these two.

It would therefore move from (1,1) to (96,1) and only then it would begin to move diagonally.

Hope that made any sense, else feel free to ask for clarification.

##### Share on other sites
Quote:
 Original post by ZrednaEmergentUsing only knowledge of the current position and the goal position you won't be able to do a line-drawing heuristic, since it does matter what the starting position was![...]Hope that made any sense, else feel free to ask for clarification.

Yes, that makes sense.

Summarizing: You take a diagonal step when doing so improves your heuristic (vs. the lower-cost axial move) more than it costs extra.

Now if I'd only thought of things in those terms from the beginning!

You might still be able to pose line-drawing in terms of A*, though , with a heuristic that takes the global knowledge into account: Perhaps a linear combination of the perpendicular distance from the point in consideration to the ideal line, with the pythagorean distance to the goal (weighted so the first dominates, and the second serves only to keep things going in the "right direction.") The problem with this is that it would not particularly useful, as it assumed a straight-line path exists -- and if one did you'd just use something like Bresenham instead of bothering with A*.

I recall, vaguely, that you can do pathfinding in a world defined by convex polygons by pathing among obstacle vertices, and drawing straight lines in-between. It seems you could do that here -- in which case you'd be doing A* on a graph somewhat different from a grid.

##### Share on other sites
Quote:
 Original post by EmergentSummarizing: You take a diagonal step when doing so improves your heuristic (vs. the lower-cost axial move) more than it costs extra.

This is driven by the basic principles of heuristic search. We require that the cost function is monotonic and that the heuristic never over-estimates the true cost, which means that any two nodes will have a traversal cost between them greater than or equal to the difference between their respective heuristic costs to the goal. If the traversal cost equals the heuristic difference, the heuristic is an optimal assessor of cost.

In addition to this, if using the SLD heuristic, there is very little discriminatory power far from the goal for two neighbouring nodes on a grid. Hence the heuristic lends little weight to the ordering process of the nodes on the open list. This means you'll tend to favour taking the action with the lower local path cost, until such time as the heuristic dictates a different solution.