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:
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.
0,0
) in an array ofknownSquares
1,0
,0,1
,-1,0
, or0,-1
)knownSquares
that it is blocked and pick a new directionAt 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 theknownSquares
array, or a separate list altogether if you want a full transcript of each square visited, in order.