A*, so close to getting it working.

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

Recommended Posts

For a while I've been learning A* and the various ways to implement using C# it and have been trying to get a version up and running for a 2d map I have. So far it works, but I have an annoying side stepping issue that you can see here: http://www.innerfilth.com/~mike/ASTAR.wmv Here's what I have. I'm using a modified version of what's shown here: http://www.codeproject.com/cs/algorithms/seunghyopback.asp I like using this because it's simple and has so far taught me a lot. I've changed a few things and all the changes are in the node class. Firstly, I've changed the Hueristic to what I'm hoping is a more accurate one shown here:
private double Euclidean_H()
{
double xd = Math.Abs(this.x - this._goalNode.x);
double yd = Math.Abs(this.y - this._goalNode.y);
return (Math.Sqrt((xd*xd) + (yd*yd)))*10;
}

And I've also added in a way for it to factor in diagonal movement costs by multiplying this result by 10, as well as multiply the gcost by 10. The last thing I did to do this was change the getMap function at the end to:
if (Map.getMap(x+xd, y+yd) != -1)
{
Node n = new Node (this,this._goalNode, Map.getMap(x+xd,y+yd), x+xd, y+yd);
if (xd != 0 && yd != 0)
n.g = this.g + 14;
if (!n.isMatch(this.parentNode) && !n.isMatch(this))
}

Despite this it's still zigzagging at weird intervals and I cannot figure out why. I'm assuming it's a math issue but does anyone know what that issue might be? If I haven't provided enough info please let me know.

Share on other sites
You've made your heuristic non-admissible. The heuristic needs to be always smaller or equal that the real cost.

private double Euclidean_H()
{
double xd = this.x - this._goalNode.x; //the abs was totally useless
double yd = this.y - this._goalNode.y;
return (Math.Sqrt((xd*xd) + (yd*yd))); //*10 making the heuristic non-admissible
}

Make the cost of non-diagonal movement as 1 and the cost of diagonal movement as sqrt(2).

Share on other sites
I think I've tried that before and the problem I run into is g is an int, and is used in the nodeComparer class. The only problem with that is it yells at me if I use anything other than an int and I've been trying to find some information on interfaces that may let me get around that. Does anyone know how I can tackle that problem, too?

[Edited by - worldspawn on September 27, 2007 10:44:10 AM]

Share on other sites
In my own implementation I discovered that it's the ratios of the costs that are important, not the specific values -- so if you use a uniform scale and set the cost of horizontal as 1000 and the cost of diagonal as 1414 it should still work and let you keep using integer types.

Actually I'm a bit confused about you implementation now, so I hope that my answer has helped ...

Share on other sites
Quote:
 Original post by Hidden AsbestosIn my own implementation I discovered that it's the ratios of the costs that are important, not the specific values -- so if you use a uniform scale and set the cost of horizontal as 1000 and the cost of diagonal as 1414 it should still work and let you keep using integer types.Actually I'm a bit confused about you implementation now, so I hope that my answer has helped ...

Thats screaming for numerical limits problems.

Share on other sites
Ya what Hidden suggested is what I was originally doing and it was still giving me an imperfect path. I've been reading up on IComparer and IComparable and it looks like what I'm trying to do with floats/doubles is possible, but I'm confused on how the IComparer was set up with the code I'm using in order to figure out how to do it here. I haven't really worked with these interfaces before so it's kind of confusing.

Share on other sites
Quote:
 Original post by SteadtlerYou've made your heuristic non-admissible. The heuristic needs to be always smaller or equal that the real cost.Make your heuristic as:private double Euclidean_H(){ double xd = this.x - this._goalNode.x; //the abs was totally useless double yd = this.y - this._goalNode.y; return (Math.Sqrt((xd*xd) + (yd*yd))); //*10 making the heuristic non-admissible}Make the cost of non-diagonal movement as 1 and the cost of diagonal movement as sqrt(2).

Ok I've got it set up like this now. When creating a path it checks to see if the tile being checked is on a diagonal, and if so applies the sqrt of 2 to the gCost instead of just 1. It still follows the same wonky zigzagging path. Any other ideas? Or is there a fundamental flaw with this pathfinder itself and I should just suck it up and start over?

Share on other sites
The original code seems to share the wonky movement. There must be a fundamental flaw in the original algorithm:

As a guess to a solution, try changing the g and h costs in the node to doubles.

Share on other sites
Ya I've done that, too. Still zigzags. Not like it does in that pic it has improved, but is still quite noticable.

Share on other sites
You'll need to debug the open and closed lists, then. Something must be wrong there. Probably assigning the costs or sorting is buggy?

1. 1
2. 2
3. 3
4. 4
Rutin
13
5. 5

• 26
• 10
• 9
• 9
• 11
• Forum Statistics

• Total Topics
633694
• Total Posts
3013372
×