Here is my use case:
I have a two dimensional grid and each grid space is either open or blocked. I know the entire grid beforehand and as I traverse the grid I explore in a radius of 10 units in all directions that are not obstructed by an obstacle.
I would like to 100% explore the grid in the shortest amount of time. I'm having trouble coming up with a way to do so.
Example: Here is a simple example that does not take into account the explore radius. The grid could look like anything though. In this simple example the question is when exploring how no i know to turn down the middle corridor on the right so I don't need to backtrack later.
XXXXXXXXX XOOOOOOOX XOOOOOOOX XOXXXXXXX XOOOOOOOX XXXXXXXXX
Thoughts I have so far.
1.) Overlay a set of nodes in a grid at a given resolution lets say 10 grid spaces apart.
2.)Process the entire grid for the explore radius from those nodes.
3.)Check the grid for anywhere that has not been explored, add additional nodes to make 100% exploration.
4.)Prune the grid for nodes that can be removed that do not take away from exploration.
5.) Use a Minimum spanning path algorithm on the remaining nodes and use that path for the exploration.
I would love an easier way to accomplish this. Any algorithms or approaches that would simplify?