Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


A* jaggard lines?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
16 replies to this topic

#1 Chris Burrows   Members   -  Reputation: 111

Like
0Likes
Like

Posted 17 September 2012 - 12: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.

Posted Image

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.

Sponsor:

#2 adam4813   Members   -  Reputation: 662

Like
0Likes
Like

Posted 17 September 2012 - 12:22 PM

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

#3 FLeBlanc   Crossbones+   -  Reputation: 3109

Like
0Likes
Like

Posted 17 September 2012 - 12: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.

#4 Chris Burrows   Members   -  Reputation: 111

Like
0Likes
Like

Posted 17 September 2012 - 01: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...

Posted Image

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

Edited by Chris Burrows, 17 September 2012 - 01:10 PM.


#5 FLeBlanc   Crossbones+   -  Reputation: 3109

Like
0Likes
Like

Posted 17 September 2012 - 01: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.

#6 Chris Burrows   Members   -  Reputation: 111

Like
0Likes
Like

Posted 17 September 2012 - 01: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?

#7 FLeBlanc   Crossbones+   -  Reputation: 3109

Like
0Likes
Like

Posted 17 September 2012 - 02: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.

#8 adam4813   Members   -  Reputation: 662

Like
0Likes
Like

Posted 17 September 2012 - 02: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));

#9 snowmanZOMG   Members   -  Reputation: 889

Like
0Likes
Like

Posted 17 September 2012 - 04: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

Edited by snowmanZOMG, 17 September 2012 - 04:12 PM.


#10 IADaveMark   Moderators   -  Reputation: 2509

Like
0Likes
Like

Posted 17 September 2012 - 04: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-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
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!"

#11 jefferytitan   Crossbones+   -  Reputation: 2218

Like
0Likes
Like

Posted 17 September 2012 - 06:13 PM

I'd suggest simple Euclidean distance. Think about how the cost estimate works. You take the distance traveled so far plus the heuristic of the rest of the distance. If you use Manhattan distance and a cost of 14 for diagonal, this is how it pans out:
  • Travelling 1 unit horizontally towards the target costs 10 and gets you 10 closer.
  • Travelling 1 unit vertically towards the target costs 10 and gets you 10 closer.
  • Travelling 1 unit diagonally towards the target costs 14 and gets you 20 closer.
So of course it would pick diagonal paths first.

Edit: Also I believe that using the Manhattan distance if a unit can travel diagonally actually makes it an inadmissible heuristic. The heuristic should never overestimate the remaining cost. Not that I'm morally against inadmissible heuristics - they can cut down the search space nicely. But they aren't good if you're doing them by accident.

Edited by jefferytitan, 17 September 2012 - 07:39 PM.


#12 Chris Burrows   Members   -  Reputation: 111

Like
0Likes
Like

Posted 17 September 2012 - 11:10 PM

Thanks everybody for your help, it seems it is the Manhattan heuristic after all. I found a program called PathDemo which allows you to test and modify a variety of path finding algorithms. The image below shows A* using both the Euclidien and Manhattan distances for a heuristic.

Posted Image

The path found using the Euclidiean distance is definitely more natural. So that's solves one problem, but presents another: How do I caculate the Euclidean distance? Traditionally it is simply sqr((ax-bx)^2+(ay-by)^2), but that won't work for me because I am using a staggered iso grid in which each X grid co-ordinate actually represents 2 different tiles depending on if the Y co-ordinate is odd of even.

Posted Image

I just can't seem to crack it. Any help would be greatly appreciated!

Edited by Chris Burrows, 17 September 2012 - 11:15 PM.


#13 jefferytitan   Crossbones+   -  Reputation: 2218

Like
0Likes
Like

Posted 17 September 2012 - 11:55 PM

Oh dear, the way you're handling X values is... unusual. I would use co-ordinates as if the tiles were flat and axis aligned. You could convert it before getting distance, e.g:

yadjusted = y;
xadjusted = x - floor(y/2); // can go negative.

Hopefully my sleepy brain got that right. ;)

#14 Chris Burrows   Members   -  Reputation: 111

Like
0Likes
Like

Posted 18 September 2012 - 01:27 AM

Thanks Jefferytitan,

The formular for xadjusted is correct, but the yadjusted is a little off.

Posted Image

Both red tiles are 2 below the yellow tile. But, according to your formular, the leftmost tile is 3 below (2 - 5 = -3). However, I noticed a correlation between your two formulars, and this works:

x adjusted = x - floor(y/2)

x distance = (A.x - floor(A.y/2)) - (B.x - floor(B.y/2))
y distance = (A.x - floor(A.y/2)) - (B.x - floor(B.y/2)) - (A.y - B.y)

So, using pythagoras, I calculated the correct Euclidiean distance, but the strange thing is, it hasn't changed my paths. They still favour the same long straight lines shown in my original screenshot (in dark red). I've decided the staggered iso grid only adds an extra layer of compexity to my problem, so I will re-write the code for a square grid and see if I can achieve my desired zig zags there.

On a side note, Jefferytitan, you mentioned my staggered grid is unusual. The alternative of a titled square grid means that if I want the entire screen to be filled with tiles, then some squares with have negative co-ordinates, shown below (the top left and bottom left white regions).

Posted Image

And seeing as there are no negative array cells, this was not an option.

Thanks again! I'm open to all suggestions.

#15 Chris Burrows   Members   -  Reputation: 111

Like
0Likes
Like

Posted 18 September 2012 - 01:17 PM

VICTORY!

I re-implemented A* from scratch and found the problem!

I am using a 3d array to store the G, H, F, ParentX and ParentY values for each tile during the search. But the thing is, in Multimedia Fusion 2, arrays are unable to store floating point values. All non-whole numbers are rounded down to the closest integer. The Heuristic is rarely a whole number and that was the direct cause of my A* blues.

My solution was to use a cost of 1000 orthogonal and 1400 diagonal as opposed to 10 and 14 allowing for the equivalent of 2 decimal places of percision.

However, if you examine the G, H and F values for each square, you will notice they don't quite match 1000 and 1400. This is because I am multiplying every G value by 0.9925 and every H value by 0.0075 to break the tie between F values which would otherwise be the same for multiple tiles. This causes A* to favour tiles which are closer to the target.

Posted Image

Thank you everybody for your help.

Posted Image Yarrr! Until next tyme me hearty!

#16 IADaveMark   Moderators   -  Reputation: 2509

Like
0Likes
Like

Posted 18 September 2012 - 06:05 PM

You can't do an array of floats? Whoa... Posted Image
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
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!"

#17 Chris Burrows   Members   -  Reputation: 111

Like
0Likes
Like

Posted 18 September 2012 - 10:02 PM

Not in Multimedia Fusion 2. The closest would be a string array, in which you would convert the float to a string before you store it, and then back to a float when you retrieve it. Obviously, this is not very efficient.

But, now I've solved the problem, I will re-write the code in c++, although that would have worked from the beginning. Silly integer arrays!




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS