koobas.hobune.stream
Understanding Dijkstra Application
Hi All, I'm currently working on making a tactical RPG type of game and need to have the possible tiles that a character can move to be highlighted and only allow movement to those tiles. It would also need to move the character to the destination after a button press. I've been scouring unityanswers and every other page I can find to understand how to do this. I've found a ton of different uses of the algorithm and a few for my specific use but I'd really like to understand whats going on with it. I understand a little about Lists and I know all the unity basics so far but I don't understand whats going on with the actual scripts themselves.
Here's a few examples of what I'd like to happen: https://www.youtube.com/watch?v=bGsrnJN7iwU https://www.youtube.com/watch?v=dhvf9KCAsVg
I've found some sample code thats pathfinding (not quite the same thing) with Dijkstra: https://letmetutoryou.wordpress.com/2009/05/26/shortest-path-with-dijkstra-and-c/ http://pastebin.com/vf32J1nk
If anybody can either help me understand how this is supposed to work or can find a step by step explanation of how this works I'd really appreciate it.
Thanks
There is some animations here.
Dijkstra is an algorithm for any graph, it's not just video game pathfinding. You'll need to understand a little what is graph theory.
To apply Dijskra: you need to set all nodes (a tile here) and all edges (the path between nodes in our case) and to have for each edges a cost (the distance for example or the "difficulty") and 2 nodes. These nodes are neighbours.
When you are looking for a path, you actually check all neighbour of your current position, discard "too expensive" path move your current position to the next position and repeat until you reach your destination.
All the difficulty of Dijskra's algorithm is to understand how to discard too expensive path.
Thanks, I'll look into graph theory a little more. Obviously I already have tiles created and I've been able to put those into a List. Do I need to create a separate object for the edges? Or how would I define those?
?? There's no discarding. All Dijkstra's does is add the "cheapest" edge, over and over.
@Superdsgross that not necessary all you need (in your case at least) is to know next tile and the distance to it, that couple neighbour/distance is an "edge".
@Owen-Reynolds I'm not a native english speaker so I might not have choose corectly my words but with Dijskra if you find A->B cost 100 and A->A1->A2->...->An->B cost 10 you discard the former path, don't you?
@$$anonymous$$ultifred How can I find adjacent tiles from a list of tiles?
That depend of your problem: on a chess board the coordinate would be enough to find that quickly.
You should check out some pathfinding tool video, most of them compute the neighbour data and serialize it, that's not something you want to calculate during runtime.
Here an interesting discussion about dynamic pathfinding
Here are some in depth explanations about some path finding algorithms, including Dijkstra and A*
http://theory.stanford.edu/~amitp/GameProgramming/
These might be of help as well
http://aigamedev.com/open/tutorials/clearance-based-pathfinding/
Thanks for the quick reply. I guess my question may be a little vague. I understand the concept and how it should work. I don't understand its implementation. I've seen a few different examples of code and I'd like to be able to get to that same conclusion in my own application.
