I am trying to write an algorithm for an AI bot to search a 2D rectangular grid for a stationary object to destroy. The bot is constrained by a set number of moves that will not allow it to reach every corner of the space. The bot is only able to sense walls and objects in the squares directly adjacent to it (N/S/E/W), though not diagonally. The size of the space is constant and known, but the starting point of the bot and object is unknown. I want to search the room in the most effective manner to increase the likelihood of finding the object over a number of tests.
So far I figure if the bot moves in a straight line until it hits the nearest wall takes a step back and turns left and continues until it hits another wall. From there the bot should be able to take a step back and turn left again. Then follow the wall along and move back through the remainder of the room in a zig-zag fashion. (Let me know if that description of movement need clarification.)
Is there a more efficient way of moving through this space to find the object?
You said the bot is constrained by a set number of moves that will not allow it to reach every corner of the space. In that case I would maybe suggest a "G" pattern.
I think the zig zag will "eventually" cover every tile, but it is also much more likely for it to re-scan the first few tile you begin with. Since you don't have unlimited moves, every extra tile you scan counts. What I meant by a "G" pattern, is that the robot starts in the middle of "G", hits a wall, and go around the room following the walls. I think that would minimize the chance of revisting the tiles you've already scan. After the "G" scan if you have extra moves then maybe you can zig-zag the remaining space in the inner-rectangle which you have full knnowledge of how big it is.
Also, keep the length/width of the room in your program after it hits the third wall so it knows when to turn early before hitting the 4th wall, saving a few moves to take 1 step back.
lastly, you shouldrecord where in the room you started and the initial path you've scan(you can calculate that once the first "G" is scanned). With that info, if you can determine if your initial path is on your side of the room or closer to the other side. If it is closer to your side where you first "G" scan ends, maybe take another "C" scan around it to reach the other side of the room before starting the zig-zag to minimize the chance of re-scanning the initial path before the moves end. The moves required for "C" and zig-zag should be the same.