# Algorithm for finding all empty tiles in rectangular grid?

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:

• Would you be able to provide us with an image of the sample grid? Even something basic like an Excel Chart with cells shaded a different color for if they are blocked or not to show your basic problem, like this Commented Mar 10, 2016 at 17:20
• And as long as your making a sample grid, it would be helpful to see what the desired outcome for that grid would be. Would like you the description of an unblocked path back to your current position or to another position? Is it allowed to use a tile more than once? Commented Mar 10, 2016 at 17:28
• Do you know the grid size? or maximum dimensions?
– user40980
Commented Mar 10, 2016 at 18:03
• I actually find this question interesting. I am assuming this is more of a "room" with a grid interface and randomly placed "objects" in the room, and less of a "maze", and you need an algorithm to traverse every free square in the room from any starting point. Like a Security Guard pathing AI for a randomly generated room. I am guessing that it doesn't matter if the algorithm overlaps anywhere, due to the randomness of it. Commented Mar 10, 2016 at 18:33

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.

Lets start out by writing a function that interrogates the surrounding walls.

``````bit field = 0
can move forward?
if y: bit field |= 1;
rotate R
can move forward?
if y: bit field |= 2;
rotate R
can move forward?
if y: bit field |= 4;
rotate R
can move forward?
if y: bit field |= 8;
rotate R
``````

Now we're pointing back the same way we were and have the bitfield containing something like `0111` or the like. From that we can go forward or to the right or backwards.

So, in an infinite field (or working from known maximum dimensions), put a block to the left and behind us.

``````  ?
? . ?
X ^ . ?
? . ?
?
``````

Now we move into in one of those empty spots. Lets move forward. The new interrogation gives us `1010` and we update the world map.

``````? X ?
X ^ . ?
X . . ?
? . ?
?
``````

So now we place into this data structure the new information about the world.

We move to another location that has adjacent `?` and repeat the interrogation of the surroundings and update the world map. If we happen to move into a location that doesn't have any `?` adjacent spots, we use our path finding algorithms to go to the nearest `.` that has an adjacent `?`.

When there are no paths to a `.` that has an adjacent `?`, the map of the available world is complete.