Find the shortest path from a list of points

Suppose I want a function that returns the shortest path from Green point to Orange point, and each point can only go to its connections (so you can't go from red to orange): Can anyone point me in the right direction for how to go about this? I'd be willing to buy an asset from the store, but all the path finding assets seem to be tied up in so much other stuff I don't want. I want to write my own implementation of what to do with the list of points, and my own extension to author the points.

In the following code I'll call each point a waypoint, and a waypoint is simply a position and an array of its connecting waypoints:

Code (CSharp):

1. public class Waypoint {
2.     public Vector3 position;
3.     public Waypoint[] connections;
4. }
5.  
6. Vector3[] GetShortestPath ( Waypoint[] AllWaypoints ) {
7.     Vector3[] ShortestPath;
8.     // do some sweet pathfinding stuff
9.     ShortestPath = null;
10.     return ShortestPath;
11. }

 

The standard (and probably best, in this case) algorithm to do this is called A* (pronounced A-star). It is one of a family of related search algorithms. It's basically just a tree search algorithm, where newly expanded nodes are added to your to-do list in order of estimated least cost (distance) to the goal.

A google search should get you the details you need to write your own implementation. I've done it in Unity/C# a couple of times — it's not too hard, but plan a couple of days to iron out all the kinks, especially if you've never done it before.

Best,
- Joe