A* jaggard lines?

Artificial Intelligence Programming

Started by Chris Burrows September 17, 2012 06:06 PM

15 comments, last by Chris Burrows 11 years, 7 months ago

121

Author

September 17, 2012 06:06 PM

Hello world,

Recently, I began working on an RTS. I'm using A* and it is working well, only I don't like how my paths contains long straight lines (both orthogonal and diagonal), shown in dark red below. I would prefer if the paths favoured more "jaggard" lines, as shown below in light brown.

It seems every other implementation of A* which I have seen actually favours jaggard lines by default, but for some reason mine doens't work that way, and as far as I can tell I am not doing anything differently. I can't paste my source because I am writing the game in Multimedia Fusion which doesn't use traditional code. But, I did base my "code" on this article, seemingly a pretty standard of version A*.

If anybody has any ideas why this is occuring, I'd love to hear about it!

Thanks in advance, Chris.

PS. Here is the executable if anybody is interested.

adam4813

729

September 17, 2012 06:22 PM

Its in the heuristic I bet. What is the formula you are using for that?

FLeBlanc

3,142

September 17, 2012 06:47 PM

The article you linked in turn links to this article at Gamasutra that has possible answers to your problem, in the section on smoothing the path. Specifically, you can modify your heuristic to give a higher cost penalty to choices that require a change in direction. You can also implement the path smoothing trick discussed in that article of cutting out some of the turns along the way by trying to find the path step that is furthest along the path to which the unit can move in a straight line, thus eliminating the intervening zigs and zags.

Chris Burrows

121

Author

September 17, 2012 07:04 PM

I think you're mistaken FLeBlanc, the zigs and zags is what I want! For the heuristic, I am using the manhatten distance. The formula itself is somewhat complicated because I am using a staggered iso grid and every other cell is offset..

(Max(Abs(2*TargetX+(TargetY mod 2)-2*CurentX-(CurrentY mod 2)), Abs(TargetY-CurrentY)))*10

The formula is spot on, plus, I was experiencing the same problem with a square grid, so it's not that. Is there a better choice than manhatten? Regarding the G cost, I have given orthogonal traversing a cost of 10, and diagonal a cost of 14. As described in the article I linked, yet his code favours the jaggard lines.

The Gamasutra article, Toward More Realistic Pathfinding, explains how to make zigs and zags into straight diagonal A to B distances, shown below...

.. but what I am experiencing is something different all together, see my original screenshot.

FLeBlanc

3,142

September 17, 2012 07:13 PM

Ah, sorry, I misread your post and usually folks try to eliminate the zig-zags. Maybe you could try doing that article's suggestion in reverse? That is, give a cost penalty for steps that don't change direction. That might give you some zigs, and maybe a few zags as well.

The reason most people (myself included) try to smooth the zags is that when a unit follows the path, the rapid and frequent changes in direction makes the unit look epileptic. I'm not aware of any body of research into increasing the jaggedness.

Chris Burrows

121

Author

September 17, 2012 07:20 PM

Haha, I don't want excess zig zags, I'd just like the same treatment everybody else gets.

I'm a huge fan of Warcraft 2 and I'm aiming for a similiar standard. The zig zags don't bother me, but what I have currenlty is something much worse. Either lonng straight lines or lonng straight diagonals. I guess what I am asking is has anybody seen this before? and if so, do you fix it? and if not, any ideas what is causing it?

FLeBlanc

3,142

September 17, 2012 08:02 PM

I have seen behavior like that from my own pathfinders before, but since I always smooth the paths, it isn't really an issue.

When finding a path, if several possible node choices present the exact same heuristic cost, then the deciding factor in these cases tends to be the order in which the nodes are placed in the list for consideration. If you always visit the neighbor nodes in the same exact order, the result may be a preference given to one direction over another. So you could try randomizing the order in which you visit the neighbors at each step to see if it gives you better results.

adam4813

729

September 17, 2012 08:57 PM

Maybe try using Euclidean distance as a heuristic? IIRC that created a better path on mine, but I was using non-diagonal movement. Also I removed the square-root from my heuristic.
h = cost * (abs(curNode.x - goal.x) + abs(curNode.y - goal.y));

snowmanZOMG

1,205

September 17, 2012 10:11 PM

Seems like an issue with the heuristic to me. I would suggest trying diagonal distance. Here's some more detailed examinations of heuristics and their various properties: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

IADaveMark

3,839

September 17, 2012 10:32 PM

Yep... the Manhattan distance is going to screw you up like crazy there. (Note that both paths are the same length?)

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

A* jaggard lines?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

A* jaggard lines?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines