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 ]

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.

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

instead of

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]