Maze traversal algorithm

Since you don't know the maze in advance you must explore. This means keeping track of all the rooms that you have visited.

Since any door could lead to the solution you must explore all of them (or at least until you hit the goal). This means that you must keep track of which doors you have gone through for each room.

Since you want to be efficient it would be prefered if you only visited a room the minium number of times necessary to go through each of its doors once (well, maybe twice, once going into a blind alley and once comming back.)

This suggests a depth first search (what this means is that if you have a room with 4 doors, you do NOT step through one, then immediately back up and return the the 4 door room and try the next door. That would be breadth first.) You want to fully explore the consequences of having gone through the first door of that 4 door room, before you return to that room and try another. The suggestion that you use breadth first is correct IF you are interested in finding the shortest path from start to finish, however breadth first search involves much backtracking (extending each branch by one, then backing up to go extend some other branch by one) and is not efficient IF you are interested in wining a race if you are running blind throught the maze. Depth first optimizes the exploration of new territory. Breadth first optimizes your proximity to where you started.

So this leads to the following. Keep a map of positions that you have visited. For each such position keep track of which doors you have entered from and exited from.

Whenever you enter a room. Add it to the map of visited position if it is not already on the map. Mark the door that you entered through.

Whenever you exit a room mark the door that you use as your exit.

Whenever you are in a room choose an exit door: Pick one at random* from among the unmarked doors (ones throught which you have neither entered nor exited) or if there are none in that category choose one marked as entry but not as exit.

* Pick one at random. - well, this is a free choice. You can either go totally random or you can try to guess intelligently. I can see only a couple of intelligent guesses.

First of all. Suppose you have a door through which you have neither entered nor exited, BUT because you have your map you KNOW that on the other side of that door is a room that you have previously visited. (This only happens in a multiply connected maze). If your purpose is to explore new territory don't just randomly wander back into previously explored territory.

Secondly suppose you have explored corridors that completely surround the goal position (you were given the goal position, right, it was not just painted on the floor of the room so that you only knew you were at the goal when you actually got there) In the process of surrounding the goal state, when you come to a room with a couple of doors, one that leads into the now closed off but unexplored area that contains the goal and one that leads to the similarly closed off area that does NOT contain the goal. Which door do you choose? Well, duh, go explore the area that has the goal.

Now, doing this right could take some real code. You would have to do a little topology, Look at you map of visited territory discover connected components and have loads of fun. OR you could instead do something cheep and sleezy (known as a heuristic) that might work most times but which can occasionally be wrong, namely, when you get to choose at random you try to step closer to the goal if you can do it.

i.e. an intelligent random choice would be to prefer a door that leads to an unexplored room closer to the goal.

marlin314a at 2007-7-9 6:14:47 >