Algorithms – Finding All Empty Tiles in Rectangular Grid

algorithmsartificial intelligencepath finding

I have a rectangular grid of square tiles, some of which are blocked/filled. I start at a random tile inside the grid with the blocked tiles, randomly placed. I can turn in 90° steps and check whether I can enter the tile in front of me, which is possible if the tile in front of me is not a blocked tile or the edge of the grid. I cannot distinguish both cases from each other, I also have no coordinates and don't "know" my position in the grid.

I now need an algorithm to run through all open tiles of the grid. Using maze-solving algorithms (e.g. Pledge) makes me run along the walls of blocked tiles and the grid's borders, however it is possible that there are free tiles that are not adjacent to a wall, which do not get hit with these algorithms.

What kind of algorithm or logic do I need to use to make sure I cover all empty tiles?

Sample image:

enter image description here

Best Answer

I think you'll want an algorithm something similar to this. The question deals with mapping an unlimited size dynamic "maze", but the solution I think would be the same.

The basic idea is to record each square as you traverse or check it in an array of "known" squares, until you have every square mapped.

  1. Start by recording where you are (0,0) in an array of knownSquares
  2. Pick a direction to move (1,0, 0,1, -1,0, or 0,-1)
  3. Check if new coordinate already exists in array of known squares
    1. If yes, pick the next direction.
      • If no new direction, go back a room
    2. If no, add new coordinate to array of known squares, and check if blocked
      • If blocked, set flag on item in knownSquares that it is blocked and pick a new direction
  4. repeat steps 2-3 until you are out of new squares to visit.

At the end, you should have visited every "square" that was available to the starting spot, and could even graphically display the results of the knownSquares in a UI grid if you wanted to draw the room or verify your results.

Only thing that might cause problems is tracking the order you visit rooms in, but that could easily be solved by a visitOrder property on the object in the knownSquares array, or a separate list altogether if you want a full transcript of each square visited, in order.

Related Topic