koobas.hobune.stream
How to find the shortest path?
So I have a unit on the screen (the one with a green box around it) and lets say I want to move to the target star (circle in red).
I know how to make the unit move to that star in a straight line, but how would I make it find the shortest path to the star (bottom picture)?
All the stars randomly generate when the scene starts.
I've been looking at A* but couldn't figure out a way to get this working the way I want too.
I just don't know how to start with this.
A little help please?
Thank you!
First off, great question, and great with images to give examples. :)
This is a very typical use case for Dijkstra's Shortest Path algorithm. Read the wiki article - it has code examples too. It finds the shortest path in a graph, which is what you've got here, if you imagine that the stars are connected by edges (the yellow paths in the final image).
This kind of algorithm would also typically be used to find the shortest path between cities in travel planning (with the roads as edges in the graph).
Bonus: There are variants of this algorithm that allow you to assign weights to the edges, so some become more favourable than others. These algorithms then select the lowest edge weight sum.
But Dijkstra's and A* are pretty much the same thing. They both use open/closed sets to grow a blob of places you know how to get to. A* just complicates it with the f,g,h functions, to make it hopefully reach the target faster (Dijkstra's blindly grows until it accidentally reaches the target.)
Also, textbook Dijkstra's does assume there are edge weights. (you look for the shortest edge from your blob to a new spot.)
@Owen Reynolds: Thanks for the clarification. :) I wasn't aware A* had so much in common with Dijkstra's.
@tgnass: I think your choice to begin with should come down to a performance consideration. $$anonymous$$y immediate thought in that regard is that, judging by your screenshots, it doesn't look like you're going to have that many stars in the graph. So, I don't think there is terribly much to be gained from choosing a more complicated scheme for performance reasons. Thus, the choice ultimately becomes a matter of convenience. I would go with whatever is simpler to implement, and only upgrade to something faster if its performance becomes an issue later.
Thank you for the help, I'll have to look into both and see which one would work for me.
