How to find the shortest path?

Questions & Answers
1

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?

Star

[16068-target+star.png|16068]

[16069-path+to+star.png|16069]

Thank you!

2

First off, great question, and great with images to give examples. :slight_smile:

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.