Hi (I hope I posted this message on the right page :) ) Anyway, I am looking for an algorithm for a robot I am building as a final project at school. I need the robot to be able to go through a maze (without an ending) from a beginning spot and enter each room it encounters on it's way... Rooms can be on the left or right side of the robot and can be told apart from corridor entrances. It should only enter each room once and should check all the rooms without missing any of them. It can turn around abd go back on it's tracks but only when really necessary (like where there is no where else to proceed - a dead end :) ). Now, I already know an algorithm to do what I need but, it uses some previous knowledge of the maze's turns and rooms whereabouts before even beginning to run in the maze. I am looking for an algorithm which will be able to run in any maze without having previous knowledge of how it's built. Thanks in advance for all of the help... :) I tried to think of such an algorithm but couldn't find any...

Don't use an algorithm but use some kind of dectors or something so that whenever it sees a room it turns into it, follows the wall until it goes out of the room then keeps going? Basically changing direction on collision :P.

Only other thing I know to do would be to scan the level and put it into some kind of array and then you can use pathfinding like normal (think of it like forsight :P).

Without any knowledge of the maze beforehand, you have to use a very inefficient algorithm. You can guarantee you will traverse every room by just following the right wall -- if there is a right turn, then you will turn right, and if there is a dead end you will turn around, just like the wall does.

I thought of the follow the right wall algorithm as well but, in my case, it wouldn't have worked because there is a room in the middle of the building, not connected to any of the outer walls and it's entrance is on the left...

The only way I found to solve this maze (thought of it after posting the message) was to actually use an array (like you suggested, shadowisadog), but, instead of scanning it beforehand, "drawing" it into memory as you go through the maze so you wouldn't visit rooms you have already visited... Then, you could use the "stick to the right wall method" but enter rooms on your right and LEFT as well (but not corridors on the left, only rooms).
This was the only algorithm I thought of that could actually work...

Thanks for trying everyone anyway :)

I don't see any way of solving the problem without keeping track of rooms visited. You can try to mimimize backtracking by using some kind of heuristic to decide which unvisited room or corridor should be visited next. Probably best to choose the nearest, unless there are multiple unvisited rooms apart from each other, then you'd probably do best to find the shortest route though all of them.

Ooo, I dug up a link I'd read some time ago that might help. The pledge algo, or Tremaux's may be what you're looking for.

Maze Solving Techniques

As I've said on the other similar post, you may start with a recursive (or backtraking) fill algorithm (marking the visited rooms) and when it works optimize it for speed or path length.

>following the right wall -- if there is a right turn, then you will turn right

The 'follow the right'-wall trick doesn't work if the goal is on
an island in the middle of the maze

Quote: Original post by LinkOfTime
Hi (I hope I posted this message on the right page :) )

Anyway, I am looking for an algorithm for a robot I am building as a final project at school.
I need the robot to be able to go through a maze (without an ending) from a beginning spot and enter each room it encounters on it's way... Rooms can be on the left or right side of the robot and can be told apart from corridor entrances. It should only enter each room once and should check all the rooms without missing any of them. It can turn around abd go back on it's tracks but only when really necessary (like where there is no where else to proceed - a dead end :) ).
Now, I already know an algorithm to do what I need but, it uses some previous knowledge of the maze's turns and rooms whereabouts before even beginning to run in the maze.
I am looking for an algorithm which will be able to run in any maze without having previous knowledge of how it's built.

Thanks in advance for all of the help... :)
I tried to think of such an algorithm but couldn't find any...

I believe that if you make it follow the wall on one side of it, it will, no matter what, always find the exit - if there is one.

I've done something like this before. What you want to do is to put detectors, as many as possible on the robot(you can do it with one though). Now the detector should be able to measure the distance to a solid in front of it. Spin the robot. You now have a record of everything in the area of your detector radius. Now move to the edge of the area and try again. Keeping expanding your area. Now here is the tricky part. You need to be able to convert the detector readings into a grid of somekind.

One way to test it is to simulate it on the computer. That will probably help a lot.