# 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.

• Do you have to traverse the points of each shape in a specific order, or is the starting point and traversal order (of a specific shape) arbitrary? If it is fixed, then isn't it just a matter of finding the shortest path from one shape to the next (while avoiding the other shapes, which is a fairly standard problem). – Tom van der Zanden Nov 27 '15 at 11:34
• Well, if I have to pass the points in a square considering lower left is 0,0 and upper right is 1,1 I have to do something like: 0,0 to 0,1. 0,1 to 1,1. 1,1 to 1,0. 1,0 to 0,0. I cant do 1,1 to 0,0 as that would make a diagonal line and it would not be a square then. – riahc3 Nov 27 '15 at 11:38
• That's not what I asked. I take that you have to presume the shape in clockwise or anticlockwise fashion (no diagonals) but the starting point can be arbitrary? I.e. you get to choose whether you start traversing a shape in the left corner, or in the right corner, or somewhere else? – Tom van der Zanden Nov 27 '15 at 11:42
• Initially, the intitial path to go to the first shape (even if it is in the upper right corner) must be started from the lower left. But once I start that path, it doesnt matter if the shapes themselves are done clockwise, counterclockwise, reverse, forward, up, down, etc. If I need to go thru a entire shape again to go to another shape even thought I already did that path, that is fine too. – riahc3 Nov 27 '15 at 11:44

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.