The first step is for the user to give a ship a move command. In this example, I told the ship to move to two waypoints. The list of waypoints are stored and a waypoint is removed when the ship arrives at each one.
However, there are some objects in the ship's way: Obstruction 1 and Obstruction 2.
To calculate the path, the list of input waypoints (which is really treated like a queue) are put onto a stack of proto-waypoints. (see a visualization below)
The green line is the path from the ship's current location through the waypoints.
Then the algorithm enters into a loop. The first step of the loop is to test the first proto-waypoint on the stack. A sphere is cast from the ship toward the proto-waypoint, using a radius that is approximately that of the ship. In this case the sphere cast detects Obstruction 1. A point is then calculated as an intermediate waypoint to avoid the obstacle using this formula:
The new waypoint is pushed onto the stack of proto-waypoints and the loop repeats.
On the next iteration of the loop, the route between the ship and the first proto-waypoint is tested, just like before, except now the first proto-waypoint is the new avoidance waypoint. (see the image below)
The green line represents the currently calculated path. The red line is the direct path between the ship and the first user-input waypoint. The blue line is showing the obstacle that was detected when testing the proto-waypoint. The black line is the avoidance vector, between the avoidance waypoint and the spherecast collision point.
Since there are no obstacles between the ship and the proto-waypoint, the proto-waypoint is popped off the stack and added to the real waypoint list.
Now the loop switches perspectives from the ship to the new real waypoint, so route tests originate from there.
The loop begins another iteration, testing the route from the avoidance waypoint to the first proto-waypoint on the stack, which is the first user-input waypoint. Another avoidance waypoint is calculated and put onto the stack.
The loop iterates again and sees no obstacles on the route to the first proto-waypoint on the stack, popping it from the stack, adding it to the real waypoint list, and shifting perspective again.
Now clear of the first obstacle, the loop sees no obstacles en route to the first proto-waypoint on the stack, which is the first user-input waypoint. The proto-waypoint is popped, added, and the perspective is shifted.
The loop continues this way until there are no more proto-waypoints on the stack, or the iteration limit is reached.
The final path.
The iteration limiter ensures that very complicated paths do not create lag in the game by not calculating paths that will be traversed far in the future.
The path is calculated when the move command is given, then every few seconds after that, in case new obstacles get in the way. Below is a video of the path being updated every 0.5 seconds.
It is important to note that the green line is not the exact path of the ship. The ship's movement system is responsible for producing thrust in the appropriate direction to get the ship to the next waypoint. This system will account for unexpected collisions/forces such as incoming weapons fire by adjusting the ship's thrust.