#### Archived

This topic is now archived and is closed to further replies.

# Pathfinding heuristic question....

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

## Recommended Posts

well... i am now building a basic and simple RTS game. i have used the a* path finding algorithm.... the path (even if there is no obsticale what so ever) is usually NOT in a straight line.... i read somwhere that inorder to make the path go in a straight line, i need to give a bonus, or to substruct a certain percentage from the cost calculation in the huristic function... and well, i have been having a hard time implementing it. plz plz plz help me cyberia_2ooo@linuxmail.org icq - 76671658

##### Share on other sites
Assuming you are using something like manhattan distance as your heuristic your problem may lie in the tie breaking of nodes of the same value. Assume you have a map like this and you can only move north, south, east or west:

GOO
OOO G = goal S = start
OOS

What may be happening is:

XOO
XOO X = path traveled
XXX

which is one of the shortest paths

assuming you want something like this:
XOO
XXO
OXX

which is also the shortest path but a bit more of a straight line (as best as you could do on a grid)

The problem comes from nodes like this one:

GOO
OOO P = problem node
OPX

The A* algorithm has two choices here, either to go west or north
It sounds like yours is going west when you want it to go north.
What you can do is add a simple routine to break ties by moving to the node that makes the difference between the X and Y distance to the goal closest to 0.

If that is in fact the problem, I hope this helps.

Grunhund

##### Share on other sites
Could you please draw a map with your problem so we can know exactly the behaviour you don''t want. I have coded a A* as well and had this problem (not real problem although)

ooXooo
oXoXoo
SoooXG
oooooo

Because it costed the same moving in any of the tiles surroind your tile. If you make that your costs to your 4-neighbours is less than to your 8-neighbours you will avoid that. Is this what was happening to you?

##### Share on other sites
You can forget additional heuristics and just solve the problem easily just with a little randomization.

Normally, most A* implementations expand the current nodes'' children in a preset order. However, that order doesn''t matter, and it doesn''t need to remain constant. So if you recurse on a nodes'' children in a random order, you''ll avoid annoying right-angle patterns, and the algorithm will still work exactly as it did before.

##### Share on other sites
quote:
Original post by TerranFury
You can forget additional heuristics and just solve the problem easily just with a little randomization.

But this is not as efficient. You''ll expand more nodes unnecessarily with this approach. Altering the heuristic a tiny amount is more deterministic.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]

##### Share on other sites
For all monotonic domains you can get away with using straight line distance from the node to the goal as the heuristic estimate. For most game scenarios this will be sufficient. Anything else is just unnecessary complication.

Cheers,

Timkin

##### Share on other sites
Timkin:

I agree that straight-line distance is a good heuristic, as it is an admissable heuristic, and it will also lead to straight rather than right-angle paths.

However, I don''t understand how the random order I proposed is inefficient. Of course, part of the problem may be a simple error (on my part) of communication, since I was thinking more of depth-first searches than I was of A*. My mistake. Anyway, the idea still works.

A* is usually done something like this (OPEN list begins with one entry, the starting node) Then, it performs the following:

1 - If OPEN list is empty, there is no path. End. Otherwise...
2 - Remove first node from OPEN list.
3 - Add this node to CLOSED list.
4 - If this node is the destination node, end. Otherwise...
5 - Insert NORTH neighbor node, if accessible, into OPEN list.
6 - Insert SOUTH neighbor node, if accessible, into OPEN list.
7 - Insert EAST neighbor node, if accessible, into OPEN list.
8 - Insert WEST neighbor node, if accessible, into OPEN list.
9 - Repeat.

Instead, I merely propose performing steps 5-8 in a random order. This will prevent direction from biasing placement in the OPEN list of nodes with equal weights.

hmmm

hmmm

##### Share on other sites
quote:
Original post by TerranFury
However, I don''t understand how the random order I proposed is inefficient.

I didn''t say it was... I''m sure Kylotan can elaborate further on his comments.

quote:
Original post by TerranFury
A* is usually done something like this

5 - Insert NORTH neighbor node, if accessible, into OPEN list.
6 - Insert SOUTH neighbor node, if accessible, into OPEN list.
7 - Insert EAST neighbor node, if accessible, into OPEN list.
8 - Insert WEST neighbor node, if accessible, into OPEN list.

Instead, I merely propose performing steps 5-8 in a random order. This will prevent direction from biasing placement in the OPEN list of nodes with equal weights.

Actually, for each successor node of the current node (in this case N, S, E & W), a check is made to determine if this node already exists in the CLOSED list. If it does, a cost comparison is made between the two versions of the node, with the lower cost node taking the place in the closed list.

Furthermore, a similar check is also made as to whether the node already exists in the OPEN list.

A more efficient way of avoiding bias for nodes of the same cost is to randomise the insertion into the OPEN list (presuming its ordered from lowest cost to highest cost). When inserting a node, traverse the list until a cost is found that is higher than the cost of the current node. Normally you would simply insert the node in the OPEN list one place higher than this higher cost node. However, if you find that there are several nodes with the same cost as the current node, randomly choose a place to insert the new node among them. This is a fairly trivial exercise, although it does increase the computational cost of the insertion algorithm.

Cheers,

Timkin

##### Share on other sites
Sorry, been away for a while.

Basically, it''s obviously true that a random ordering will prevent the bias element, but while that is desirable it''s not necessarily sufficient. I am assuming that the original poster is using a heuristic where diagonal moves cost the same as horizontal or vertical moves, but where straight paths are preferred where possible. I am working on this assumption because a simple pythagorean heuristic wouldn''t give this problem if the algorithm is properly implemented.

If you use a random ordering, then sometimes you are still going to get the unnecessarily jagged paths. Imagine a 2 step path from (0,0) to (2,0). Sometimes, your first step will choose to evaluate the NE step to (1, 1) before it evaluates E or SE, and therefore as soon as the 2nd step evaluates its SE neighbour you have the ''winning'' path, which goes NE and then SE instead of E and E again. For longer paths, the chance of you getting an unfavourable ordering is reduced, but is still present. To go from (0,0) to (3,0), it''s still perfectly possible for your algo to pick (1,1), (2,1), (3,0) or (1,-1), (2,-1), (3,0) as well as the desired (1,0), (2,0), (3,0). This implies that all these paths will be expanded to a similar degree as they all measure equally, yet only one will be picked.

The only decent answer that I see to this, is to subtly bias the heuristic in favour of the horizontal and vertical moves, such that diagonals cost 1.000001 where the other moves cost 1.0. This would ensure that ''straight'' paths are evaluated first. The tiny difference between the costs means that it shouldn''t ever yield a non-optimal path unless your paths are a million nodes long, yet it''s enough to be an effective tie-breaker between a slightly jagged path and a straight one. With this alteration, the straight path will be seen to be objectively better by the algorithm and therefore the alternative (jagged) paths may never get to be expanded. When you''ve got a longer path (eg. from (0,0) to (50,0) then you can know for sure that the node at (25,0) will be evaluated before all the other nodes from (25,-25) to (25,25) despite the distance remaining being virtually the same.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]

##### Share on other sites
Yes, this is similar as the solution I said, but I was using sqrt(2) for the cost of diagonal, instead of 1.00001 (euclidean distance). The solution keeps the same, and the h(x) is still understimated.

##### Share on other sites
Hi everyone

assigning higher costs to diagonal moves is a step in the right direction (i'd suggest you use sqrt(2) btw ) .. but this won't get you really nice paths (they all look very unnatural.. but perhaps good enough for a 2D-rts). I don't think you can get nice ready-to-use-paths with a* in one pass anyway. A better approach to this is a post-process-pass. The cost of this is (from my experience) close to nothing compared to the preceeding a* search. A post-processing-pass can include edge-smoothing with some spline-function (Catmull-Rom-splines are very good for this) but that would just be some finishing touches..first you have to optimize your path on a lower level: You got to check, whether the path between certain nodes is eventually free, so your units can go the straight way, instead of following the grid, which looks much nicer (and more natural...since it's the real straight way). You can do this by starting to check whether the way between the first and the last node (node n) is free..if it isn't check whether the way between the first and the n-1th node is free and so on until you reach the second node (or a valid short-cut is found). After that you do the same for your next node (the node your short-cut leads to).
This usually gives you paths that are accurate enough, but if you want to be on the sure side you can run another a* search on your pathnodes, that you got from the preceding pass (just put child-nodes on the open-list if your IsPathFree-function returns true.. that's the only difference to the normal search).
(Btw: You can disign your IsPathFree-function similar to rasterizer-line-algorythms with the only difference that you would usually want a path-check which goes like
XX00
0XX0
00XX

X000
0X00
00X0
000X

(i use a modified DDA-algorythm..actually i invented it myself and found out later that it was similar to the DDA-algorythm in the main parts)

I have to eat now i guess..

-- to be continued --

i wish you luck with your a*-algorythm..i hope this helped.. i hate bad pathfinding in RTS-games

[edited by - Jonas Witt on November 23, 2002 2:26:57 PM]