   A*, so close to getting it working.
  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.wmvHere's what I have. I'm using a modified version of what's shown here:http://www.codeproject.com/cs/algorithms/seunghyopback.aspI 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.   
  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 uselessdouble 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).   ;  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];  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 ...   ;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.   ;  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.   ;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 uselessdouble 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?   ;  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.   ;  Ya I've done that, too. Still zigzags. Not like it does in that pic it has improved, but is still quite noticable.   ;  You'll need to debug the open and closed lists, then.  Something must be wrong there.  Probably assigning the costs or sorting is buggy?   