Shortest continuous path between shapes without passing thru other shapes, in a specific order? I have the following points, shapes, and paths.  I would like to find a path that goes through all of them:



I want a path that first traverses the circle, then traverses the square, then traverses the star in the middle, in that order.

It's simple to go to the circle from the bottom left and around it, hitting each point.  However, the second shape (the square) is in the top right corner, so I have to go around the star (so I don't cross it) and traverse the square. Finally, I go to the middle, hit each of the points of the star and done. Once that is done, going backwards is pretty easy.

This is an easy example.  In my situation, though, there can be hundreds of shapes in between each of them and I have to go to each shape in the order they are stated.

How do I calculate a path that avoids a particular shape (e.g., the star)? I'm not sure what algorithm to look for. Is it a Travelling salesman problem? A*?

The shapes are defined on a grid. This is what I mean:



"1" means the path must go thru here and "0" is empty space which can be used to get to from one place to another.
The key step is: get from point $Q$ to shape $S$, while avoiding shape $A$.  For instance, point $Q$ might be the last point you visit on the circle, $S$ might be the square, and $A$ might be the star.

This can be solved using breadth-first search or A*.  The vertices are the grid points labelled "0".  You star the search at point $Q$, and try to find the shortest path to some point on $S$ (while at each step you only go through squares marked 0).  You can solve this with either BFS or A*: BFS is simpler to implement, A* will run faster.



If you additionally want to find the shortest path through all of the shapes (something that's not stated in the question), then you can fo the following: for all points $Q$ in shape $S_1$, and all points $R$ in shape $S_2$, calculate the shortest way to get from $Q$ to $R$ while avoiding shape $A$.  Then add these as edges to a directed graph (where the length of the edge $Q\to R$ corresponds to the length of the shortest such path).  Also add edges $R \to R'$ for each pair of points $R,R'$ in the same shape where you can enter the shape via $R$ and exit via $R'$.  Finally, you can compute the shortest path in this directed graph.