- Home /
Lost in Pathfinding
Edit :
Ok, well have been trying to understand the process, and think I'm getting closer. The only problem now is that it isn't returning the target, more accurately the way I am storing the target as a reference and how I am comparing where I am to that reference. If anything is obvious to you, please point it out. Here is my current script :
http://www.alucardj.net16.net/unityquestions/Pathfinding%20Current%20Code.js
Original Question :
Hello fellow Unites (YouNites) !
I'm attempting to build a pathfinding method for my troops in a tile-based strategy game, following the flow diagram on http://unitygems.com/astar-1-journeys-start-single-step/
While this chart looks easy, am having trouble implementing it. The first issue I had was an array out of range when added node to the closed list, I fixed that but now am having trouble working out where to calculate and assign the distance (G) value and the heuristic (F) value. At the line // open list node G score > tempCost? is as far as I got before a minor brain short circuit and subsequent meltdown !
Can anyone help out with some pointers like how to calculate G when checking a neighbour tile, or just expand on the flow diagram to include where the F and G values should be calculated.
The pathfinding needs to check the height of each neighbour tile and determine if the height difference is <= 1 then the tile is open/walkable.
This sounds like a fix my script question, but really if the flow diagram could be expanded on, that would be more than enough for me to continue. Thanks.
http://www.alucardj.net16.net/unityquestions/Pathfinding%20Original%20Question%20Code.js
Here is an example level to illustrate my project. Apparently when my colleague showed this on unity IRC there was alot of interest! : http://www.alucardj.net16.net/examples/HexGrid1.png
Answer by whydoidoit · Dec 09, 2012 at 08:06 AM
So I've posted a longer answer on Gems. The G score is calculated first as the temporary cost in that diagram and it becomes the G score of a node if it is the first time of reaching the node or it is lower than that node's current G score. At that point you also need to store from which mode the G score came from so that you can rebuild the path.
The F score is calculated in the last but one step of the flow chart, just before checking if there are more neighbours to consider.
Also you should use Dictionaies - those open set/closed set adds and removes really need to be O(1) operations and they are O(n/2) as you have them.
Thankyou, I was waiting to say the failing is in my comprehension, not your guide and diagrams (they are excellent). And as in the above comment, feel free to remove my posts. I just need to take a step back, and try again, possibly on a grid rather than an isometric hexagonal tile map.
Another BTW - in a hex game (and in my cube game) you can always consider the distance between a node and it's neighbour to be 1. If you are not just plotting a navmesh with points (which knows all of its neighbours) then the only thing you need is a way to work out what the unblocked neighbours are.