It looks like you’ve dropped the movement cost from both ‘h’ and ‘g’, which doesn’t seem to be correct. Also, although you’re closer with using the Manhattan distance for ‘g’, what you want is the actual cost of the path so far (not an estimate). If I’m not mistaken (which I may be), ‘g’ should be the sum of the cell-to-cell movement costs for every step in the path so far.
I think this is the place to start. Although knowing how to use the debugger is not strictly speaking a prerequisite for the kind of thing you’re doing, I’d say it’s nearly so. So, if you’re not comfortable using the debugger, I’d recommend putting everything else on hold and getting up to speed with it. Just do a search for e.g. ‘eclipse debugger tutorial’, and I think you’ll probably find some good references.
Edit: It looks like in your most recent post below, ‘g’ is correct (or closer to being correct), but the movement cost is still missing from ‘h’. Also, if by ‘crash’ you mean an exception, posting the exception message and stack trace would help us understand the problem better.
float g = parent.g + movementCost(parent, currentX, currentY);
Where movementCost() is the cost to get from parent to (currentX, currentY). (the 10-or-14)
This definition of G says: “the cost to get from the starting point to where we are now is the cost of all previous steps in the path (the parent.g) plus the cost of this one last step.”
Each node builds onto the path, so G is a running tally of how costly the path has gotten.
[/quote]
Thanks for replying
Not sure why you have arguments in movementCost(parent, currentX, currentY);
but i have tried that with my version and it is still crashing
private Node calculateNode(int currentX, int currentY, int targetTileX, int targetTileY, Node parent, int moveCost) {
// H (From current to target)
float hx = Math.abs(targetTileX - currentX);
float hy = Math.abs(targetTileY - currentY);
float h = (hx + hy);
// G (Movement Cost)
float g = parent.g + moveCost;
// F (G + H)
float f = g + h;
Node node = new Node(h,g,f, parent, currentX, currentY);
return node;
}
I notice you’re still not factoring the movement cost into ‘h’, although it sounds like the problems you’re running into are probably unrelated to that. In fact, it might be a good idea just to set ‘h’ to 0 for now in order to remove that from the equation. (With h = 0, the search algorithm should be equivalent to Dijkstra - it’ll still work, but it may take longer to find the optimal path.)
Beyond that though, I’m afraid I’m probably out of ideas. At this point, in order to figure out what’s wrong I’d probably have to do the same thing I’ve been suggesting you do, that is, set up some simple test cases and step through the code in the debugger to see, at each step, whether things are working correctly. Maybe someone else will be able to spot the problem(s) just by looking over your code, but in absence of that, I think a systematic debugging effort is probably your best bet at this point.
I will mention one more thing. The tutorial you’re following has an example case with some nice graphics showing the exact results for the search process, including the g, h, and f values for each cell visited. You could set up a test case exactly mirroring the one in the tutorial, and then see if your code produces the same results. (Note that even something minor such as adding neighbor cells in a different order may give you different results than the tutorial, but the basics, such as the cell values and resulting path, should be the same, I think.)
Not sure what you mean in your second post, but here’s what I mean about the ‘h’ value. In order for the ‘h’ value to be useful (to the best of my understanding at least), it needs to operate in the same ‘units’ as the ‘g’ value. In your current system, the cost of a horizontal or vertical move is 10. The ‘h’ path consists entirely of horizontal and/or vertical moves, therefore every step in the ‘h’ path should have a cost of 10. Therefore, you should (I think) be multiplying your current ‘h’ value by 10 (what you’re calling the ‘opposite cost’).
That said, I think it’s unlikely that’s the cause of the bugs you’re seeing, because underestimating the ‘h’ cost shouldn’t cause the algorithm to fail (in fact, a ‘maximal underestimation’ of zero should still leave you with a working algorithm, i.e. Dijkstra).
