1

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?

Greg Gacura
  • 38
  • 3
  • So, just to clarify, you are looking for a way to preprocess the map such that the pathfinding is easier/faster? – Paul92 Feb 25 '17 at 23:07
  • Yes I am looking to preprocess, max map size would be 4096x4096. My current approach seems to work but is also very clunky imho and processor intense. – Greg Gacura Feb 26 '17 at 06:07

1 Answers1

2

I cannot quite follow your algorithm so perhaps mine is the same but here's what I would do, in plain language.

From the point to test, scan a ring around it. You should find at least one open space. If not, the point is boxed and the result is "confined".

With the open spaces you found, do the same thing, this time ignoring spaces that were found earlier. This will again yield a number of new open points on the rectangle around the currently evaluated space.

Each scan round yields a collection of new open points that are evaluated using the same function again, until all return confined or one reaches the outer square that is considered freedom.

Martin Maat
  • 18,218
  • 3
  • 30
  • 57
  • I ended up doing this with a few modifications. 1. Take a point, use LOS algorithm to mark grid spaces that have been explored at radius X. 2. Scan a second right around the point at a radiu x+1 that the point also has LOS to. 3. Foreach point in second scan repeat. The process. Continue until no more points. 4. Scan entire grid for points that have no been explored. Manually add them, this happens from tight turns into corridors. 5. Create a minimal spanning tree over all nodes. Explore. – Greg Gacura Feb 26 '17 at 18:07
  • The algorithm described in this answer is basically [flood fill](https://en.wikipedia.org/wiki/Flood_fill) – Daniel Jour Feb 26 '17 at 20:00
  • It just ocurred to me, after reading Daniel's comment, that the quickest and easiest solution might be to build a bitmap in memory that matches your grid and have GDI+ or whatever graphical subsystem applies to your situation do the dirty work for you. Cast a floodfil command and check if an outer pixel has changed color. – Martin Maat Feb 26 '17 at 20:19