Jump to content
  • Advertisement
Sign in to follow this  
worldspawn

A*, so close to getting it working.

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

If you intended to correct an error in the post then please contact us.

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))
          successors.Add(n);
}
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 this post


Link to post
Share on other sites
Advertisement
You'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).

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Hidden Asbestos
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 ...


Thats screaming for numerical limits problems.

Share this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Steadtler
You'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 this post


Link to post
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 this post


Link to post
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?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!