- Home /
[C#] Find shortest path from point A to B?
My game is a turn-based strategy with a bord of hexes that players use to order units around. I'm trying to write a function for moving units to find (one of) the shortest paths from their hex to the clicked hex, where all hexes along the path are uninhabited (i have an isInhabited bool function). I was taught Dijkstra's algorithm in class but in this instance, I am not able to assign a value to the hex's, and since there could be 500+, doing so could take too much time/space. So if you can think of a good way to write a method like this, I would really appreciate the help :) Pseudo-code is fine of course.
Private Hex[] getPath(hex unitHex, hex targetDestination)
Looked it up and spent a good hour or two trying to understand and implement it, but I just couldnt make it work..
All A* is is a Dykstra on a grid, plus a heuristic to make it more efficient.
You can start with Dykstra. Your confusion is that you have seen Dykstra done with static routing tables. The algorithm is the same, its just that you have to re-generate the table each time you do a path find based on your starting position.
This is also called a "flood fill" path find because, when you dykstra on a grid, the effect is to start at your start point and flood fill outwards with the value that reprints the shortest distance to that square 9ot hex).
The way yo duo that is by starting with a very high number in the cell and, every time you encounter it during a flood fill, replace it IF the number you are replacing it with (the current iteration out from the start square) is less then what is already in it.
Hopefully, with that explanation, you can understand what you a re reading about A*
in all honesty.. I took a 0 on the Dijkstra assignment (something I'm now seriously regretting) :/ So I'm not familiar/comfortable with anything graph-related
Then your kinda screwed. All path finding is graph searching.
I would go look on the forums for someone who may have already written what you need and/or is willing to modify something close for you
Answer by Jeff-Kesselman · Jun 07, 2014 at 07:28 PM
Fo what its worth, here's the psuedo code for A*
http://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode
While A* is usually done on a grid, doing it on hexes is the same but with a different number of neighbors. Its actually easier since all neighbors are the same distance away and you don't have to worry about weighting the corners.
Alright I found this helpful video on the algorithm (https://www.youtube.com/watch?v=eTx6HQ9Veas) and wrote the search algorithm for my game, however I'm still having some issues..
The commented out part with "if(n.PathParent.PathG + current.PathG < n.PathParent.PathG)": If it's commented out, I get an endless loop. If it's not commented out, then after 4 or 5 hexes I get an Object Not Set To Instance Of An Object error.
$$anonymous$$y code: http://pastebin.com/j4$$anonymous$$$$anonymous$$uWwg
Your answer
Follow this Question
Related Questions
(Pathfinding) How to take a particular path, while avoiding others on a flat terrain ? 2 Answers
Astar Pathfinding ai moves more nodes than it should 0 Answers
How can I get my pathfinding algorithm to know that it cant go through certain sides of tiles 1 Answer
Grid-based path-finding, similar to Legend of Grimrock/Eye of the Beholder... 2 Answers
Pathfinding on Instantiated AI Vehicles 0 Answers