# Algorithm for detecting windows in a room

I am dealing with the following problem and i was looking to write a Pseudo-code for developing an algorithm that can be generic for such a problem.

Here is what i have come up with thus far.

STEP 1

In this step i try to get the robot where it maybe placed to the top left corner.

``````Turn Left -> If no window or Wall detected keep going forward 1 unit..

if window or wall detected ->Turn right --> if no window or Wall detected keep going forward..

if window or wall detected then top left corner is reached.
``````

STEP 2 (We start counting windows after we get to this stage to avoid miscounting)

I would like to declare a variable called turns as it will help me keep track if robot has gone around entire room.

``````Turns = 4;
``````

Now we are facing north and placed on top left corner.

``````while(turns>0){

If window or wall detected (if window count++)

Turn Right

Turn--;

While(detection!=wall || detection!=window){

move 1 unit forward

Turn left (if window count++)

Turn right

}

}
``````

I believe in doing so the robot will go around the entire room and count windows and it will stop once it has gone around the entire room as the turns get decremented. I don't feel this is the best solution and would appreciate suggestions on how i can improve my Pseudo-code. I am not looking for any code just a algorithm on solving such a problem and that is why i have not posted this in stack overflow. I apologize if my Pseudo-code is poorly written please make suggestions if i can improve that as i am new to this. Thanks.

• The robot doesn't have to know what corner it's starting in; just go any direction until you hit a wall, and then apply your four-corners algorithm. Commented May 27, 2014 at 0:11
• Yea you are right actually...do u see other than that how else this can be improved? Commented May 27, 2014 at 0:24
• Don't be so quick to assume there are four walls/corners. You may be better off trying to go clockwise/counterclockwise, keep track of the direction your facing, and positions you have traveled. If you find yourself at a position you've been at before, then you know you've gone all the way around the room.
– Jay
Commented May 27, 2014 at 4:09
• In this problem we are assuming the room has 4 walls. Commented May 27, 2014 at 4:24
• If the shape of the room is not known just make to variables xOffset and yOffset. Both set to 0 when you start at the wall. Increase yOffset each time you drive up once and decrease for driving down. Same for xOffset and left/right. If you reach 0/0 again you drove around the room (special case: a corridor with width 1 and you start there).
– kufi
Commented May 27, 2014 at 11:18

You need to find the top left corner. Instead, move forward (no matter the current orientation of the robot) until you hit the wall, then turn right. Those are the steps 1 and 2 in the illustration below. At the step 2, the robot turns right, orienting itself to the top.

The second phase is to move forward, constantly turning left to see whether you're near a wall or a window. For example, at step 6, the robot will turn to be oriented to the left, see that it's a wall, and turn back to be able to move to the top. At step 7, the robot turns left, sees that it's near a wall, and can now turn right twice, since it knows that there is also a wall at the top of it. It performs a similar operation at step 16, 23 and 32.

At step 9, it records that it's near a window. At step 10, he knows that it previously had a window at the top of it, so there is no need to count a different window.

The approach supposes that:

• The room is rectangular. Having a non-rectangular room would require a slightly more complicated approach.

• There is no walls or windows inside the room itself, i.e. in the middle of the room. Having walls or windows inside a room would require an overly-complex approach where the robot should scan nearly the whole surface.

• The robot knows that it has already visited a given cell. If it doesn't know that, it should be at least able to know the size of the room.

The algorithm may further be improved, for example by handling the case where the robot touches the wall in its initial position, but I suppose such optimizations are outside the scope of the exercise.

• Yea good suggestions, other than that do you see how else this algorithm can be improved or would you have more efficient solution? Commented May 27, 2014 at 0:25
• @user2733436: if you look for something more efficient, you have to be more specific. What are the constraints? What sort of efficiency do you require? Commented May 27, 2014 at 0:43
• Yes your solution actually makes more sense. i just wanted to know whether my answer also made sense so that i have an idea of how i am doing with such problem. So please let me know apart from not needing to go to the top left corner was there anything else wrong with my answer. thanks. Commented May 27, 2014 at 1:04
• @user2733436: if I understand your approach correctly, it is the same as mine, except the top-left corner point. Commented May 27, 2014 at 1:24
• Yea i decide to go to top-left corner first than i start the counting and decreasing the number of turns until all turns are used up to terminate the main loop.. Commented May 27, 2014 at 1:27