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.