Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I need to write a program that will solve maze. Maze has graph structure, where each node - some room, and edges - exits to other rooms:

enter image description here

Specification:

  • We start from a random room.
  • Maze has dead-ends, 0 or few exits.
  • We don't know anything about all maze, only the number of current room and list of doors from it.
  • When we enter new room we don't know where we came from (what door from current room leads us back to previous room).
  • We can recognize when we reach exit.
  • Each step we move from current room to some available door from it.
  • If we are at room 6 for example, we can't just jump to begin. It's like robot movement.
  • We know exactly ID of current room. We know ID of each door in current room (not in all maze).
  • We control robot.

I looked all known algorithms, but they all require at least additional ability to return to previous room. According to specification we can't use any algorithms that search for shortest path (actually, I don't need the shortest), because we know only about current room. We can't use Left-(Right-)hand following algorithms, because don't know direction of exits. Probably, the only solution that meets specification is choosing random exit in every room in hope that some time exit will be found...

Any suggestion how to solve such maze in more smart way?

share|improve this question

migrated from programmers.stackexchange.com Aug 4 '11 at 13:30

This question came from our site for professional programmers interested in conceptual questions about software development.

2  
Is this homework? –  Byte56 Aug 3 '11 at 21:13
2  
It's a part of homework. (Should I mark this somehow?). All rooms has unique ID. –  kirmir Aug 3 '11 at 21:19
2  
Are the rooms numbered as such in the drawing? Maybe something about moving towards higher numbers? (or lower depending on where you started) –  Byte56 Aug 3 '11 at 21:23
2  
Are the lists of exits always in the same order? As in, could we create a map as we go? I'm in room 5 and I go to the 2nd room in the list of rooms, I find room 4. So now I know that room 5->2(room 4). –  Byte56 Aug 3 '11 at 21:35
4  
@archer, while double-posting might get you more answers - now, someone else who wants an answer to the question, has to find two different sites, with different sets of answers. That's why the rules want single questions, to make it easier for other people to get help. –  Cyclops Aug 4 '11 at 13:32

6 Answers 6

up vote 3 down vote accepted

Hmm, you know the number of the actual room. So you can build a data structure. I guess the list of exits does not have the room numbers attached to it. But after choosing one randomly, you know at least, that there is a connection.

Say you are in room 4 and choose one of three random exit. Now the system tells you, you are in room 6 and have only one exit left. You choose that and are back in room 4. At this point you have gathered some information about the structure of the maze. You now choose another exit and end in room 5. Moe information about room 4 (one exit to 6, one exit to 5)

Can you choose a specific exit? are they numbered, say if in room 4 you choose exit one you always end in 6? Otherwise you at least can find out about possible routes.

Ok, just read you comment. So if the exits have IDs and those are statically linked to a room (even if you don't know which one for a start) you just choose a new one and remember the exit/room connections and remember which exit was already tried. Try untried exits until you have searched each single room.

That way it's actually simple. After a few steps you should have a more or less complete list of connections. Only when you enter a new room you may (for a few steps) run around randomly. But with every step you get more info and whenever you enter a room visited before, you can make a smarter decision (not testing dead end room 6 again for example when you find back to 4, since it has no exits that are untested).

Edit The idea is to make random steps first and log the information you find as I described (Dan's description is more concise). If you find yourself in a room with no unknown exits, you can use any known pathfinder to find the shortest way to a room that has exits which you didn't explore yet.

Not 100% sure, but I think Peter Norvig wrote about a similar problem (The Wumpus maze) in his book "Artificial Intelligence: A Modern Approach". Though if I remember right, it was less about path finding and more about decision making regarding some information the system could get about neighboring rooms.

Edit:

No, it's not only random. By keeping track of already tried exits you remove unnecessary redundancy. Actually you do no even need to choose randomly.

Assume you start in room 4. Info you get: 3 exits A,B,C You always choose the first by now unused exit. So start with A. You end in room 6. Now you remember 4A => 6 (and used) in room 6 you get the info 1 exit A. Again you choose the first unused (and in this case only exit) Back in room for knowing 6A => 4 (and no further exits in room 6) Now you choose the next exit B and reach room 5...

Sooner or later you will have searched all rooms that way. But in a systematic matter.

The only reason for what you would need a path finding is, when you find yourself in a room where all exits are already explored. Then you will want to find a direct way to the next room with unexplored exits to go own with your search. So the main trick is less to know which exit leads to which room (though this may be helpful) but to keep track of yet not tried exits.

This way for example you can avoid running in circles all the time, what would be a risk for a purely random approach.

In you example maze this would most likely not matter much. But in a large maze with many rooms and connections and maybe tricky circular arranged rooms this system guarantees that you will find the exit with as few trials as possible.

(I think that's probably the same system as Byte56 came up with in Gamers)

share|improve this answer
    
Yes, I can choose specific exit (door) out of room. They have unique IDs. So, your suggestion is to explore full maze first and then use any known algorithm? –  kirmir Aug 3 '11 at 21:31
    
Thanks for additional information. –  kirmir Aug 3 '11 at 21:54
    
I started to write the program and got a new question... First I explore all rooms to build structure with all connections. Second step will be to find path. But I will stop building when all connections will be added. But that way I will reach exit anyway... So this is just a choosing random direction algorithm... –  kirmir Aug 3 '11 at 23:25

I recognise that you've probably got the gist from other answers, but it was a fun question and I felt like doing a little Python coding. This is my object-oriented approach. Indentation defines scope.

Graph Representation

The graph can easily be stored as a key, value dictionary where the key is the room id, and the value is an array of the rooms it leads to.

map = {
1:[5, 2],
2:[1, 3, 5],
3:[2, 4],
4:[3, 5, 6],
5:[2, 4, 1],
6:[4]
}

Agent Interface

First we should think about what information the agent should be able to learn from the environment, and the operations it should be able to perform. This will simplify thinking about the algorithm.

In this case the agent should be able to query the environment for the id of the room it is in, it should be able to get a count of the doors in the room it is in (note this is not the id's of the rooms the doors lead to!) and he should be able to move through a door by specifying a door index. Anything else an agent knows has to be figured out by the agent itself.

class AgentInterface(object):
    def __init__(self, map, starting_room):
        self.map = map
        self.current_room = starting_room

    def get_door_count(self):
        return len(self.map[self.current_room])

    def go_through_door(self, door):
        result = self.current_room = self.map[self.current_room][door]
        return result

Agent Knowledge

When the agent first enters the map it only knows the amount of doors in the room, and the id of the room it's currently in. I needed to create a structure that would store information the agent had learned such as which doors it had not been through, and where the doors lead to that is had been through.

This class represents the information about a single room. I chose to store the unvisited doors as a set and the visited doors as a dictionary, where the key is the door id and the value is the id of the room it leads to.

class RoomKnowledge(object):
    def __init__(self, unvisited_door_count):
        self.unvisited_doors = set(range(unvisited_door_count))
        self.visited_doors = {}

Agent algorithm

  • Each time the agent enters a room it searches its knowledge dictionary for information on the room. If there are no entries for this room then it creates a new RoomKnowledge and adds this to it's knowledge dictionary.

  • It checks to see if the current room is the target room, if so then it returns.

  • If there are doors in this room we haven't visited, we go through the door and store where it lead to. We then continue the loop.

  • If there weren't any unvisited doors, we backtrack through the rooms we have visited to find one with unvisited doors.

The Agent class inherits from the AgentInterface class.

class Agent(AgentInterface):

    def find_exit(self, exit_room_id):
        knowledge = { }
        room_history = [] # For display purposes only
        history_stack = [] # Used when we need to backtrack if we've visited all the doors in the room
        while True:
            room_knowledge = knowledge.setdefault(self.current_room, RoomKnowledge(self.get_door_count()))
            room_history.append(self.current_room)

            if self.current_room==exit_room_id:
                return room_history

            if len(room_knowledge.unvisited_doors)==0:
                # I have destination room id. I need door id:
                door = find_key(room_knowledge.visited_doors, history_stack.pop())
                self.go_through_door(door)
            else:   
                history_stack.append(self.current_room)
                # Enter the first unopened door:
                opened_door = room_knowledge.unvisited_doors.pop()
                room_knowledge.visited_doors[opened_door]=self.go_through_door(opened_door)

Supporting functions

I had to write a function that would find a key in a dictionary given a value, since when backtracking we know the id of the room we are trying to get to, but not which door to use to get to it.

def find_key(dictionary, value):
    for key in dictionary:
        if dictionary[key]==value:
            return key

Testing

I tested all combinations of start/end position in the map given above. For each combination it prints out the visited rooms.

for start in range(1, 7):
    for exit in range(1, 7):
        print("start room: %d target room: %d"%(start,exit))
        james_bond = Agent(map, start)
        print(james_bond.find_exit(exit))

Notes

The backtracking isn't very efficient - in the worst case scenario it could go through every room to get to an adjacent room, but backtracking is fairly rare - in the above tests it only backtracks three times. I've avoided putting exception handling in to keep the code concise. Any comments on my Python appreciated :)

share|improve this answer
    
Monumental answer! Sadly can't be two answers :( I already wrote the program in C# and generally used almost the same ideas. For backtracking was used Breath-depth search algorithm. –  kirmir Aug 4 '11 at 23:19

Essentially, you have a directional graph, where every connected room is connected by two unknown passages - one in either direction. Say you start in node 1, and doors A and B lead out. You don't know what lies beyond each door, so you just pick door A. You get to room 2, which has doors C, D, and E. You now know that door A leads from room 1 to room 2, but you don't know how to get back, so you randomly pick door C. You get back to room 1! Now you know how to get between rooms 1 and 2. Continue to explore through the closest unknown door until you find the exit!

share|improve this answer
    
Thanks for detailed explanation. –  kirmir Aug 3 '11 at 21:53

Since the rooms are always in the same order in the exit lists, we can make a quick map of the rooms while looking for an exit.

My pseudo code is somewhat Javaish, sorry, I've been using it a lot lately.

Unvisited_Rooms is a hashmap holding a room ID, and a list of indexes of the un-mapped rooms Or a 2d array, whatever works.

I imagine the algorithm could go something like this:

Unvisited_Rooms.add(currentRoom.ID, currentRoom.exits) //add the starting room exits
while(Unvisited_Rooms.Keys.Count > 0 && currentRoom != end) //keep going while there are unmapped exits and we're not at the end
    Room1 = currentRoom
    ExitID = Room1.get_first_unmapped_Room() //returns the index of the first unmapped room
    if(ExitID == -1) //this room didn't have any more unmapped rooms, it's totally mapped
        PathTo(Get_Next_Room_With_Unmapped_Exits) //we need to go to a room with unmapped exits
        continue //we need to start over once we're there, so we don't create false links
    GoToExit(ExitID) //goes to the room, setting current room to the room on the other side
    Room1.Exits[exitID].connection = currentRoom.ID //maps the connection for later path finding
    Unvisited_Rooms[Room1.ID].remove(exitID) //removes the index so we don't worry about it
    if(Unvisited_Rooms[Room1.ID].size < 1) //checks if all the rooms exits have been accounted for
        Unvisited_Rooms.remove(Room1.ID)  //removes the room if it's exits are all mapped
    Unvisited_Rooms.add(currentRoom.ID, currentRoom.unvisited_exits) //adds more exits to the list

If(currentRoom != end && Unvisited_Rooms.Keys.Count < 1)
   print(No exit found!)
else
   print(exit is roomID: currentRoom.ID)

You'll need to use one of the common node path finders to PathTo() rooms across "the map" Hopefully that's clear enough to get you started on something.

share|improve this answer
1  
Thank you. I caught your idea. –  kirmir Aug 3 '11 at 22:31
    
Here's an upvote, @Byte56 - that makes up for 2/3 of the checkmark you lost. :) –  Cyclops Aug 8 '11 at 17:51

I'm not too clear on your requirements, but if the following is allowed, it may be a simple to follow algorithm. Probably a bug in there, especially since it uses a recursive function. Also, it checks if a door leads to the room you came from, but I don't know how a three room circular path would handle, it may just keep looping forever in those three rooms. You may have to add a history to ensure no room is checked twice. But by reading your description that may not be allowed.

solved = FALSE

SearchRoom(rooms[0], rooms[0])    // Start at room 1 (or any room)
IF solved THEN
  // solvable
ELSE
  // unsolvable
ENDIF
END

// Recursive function, should run until it searches every room or finds the exit
FUNCTION SearchRoom: curRoom, prevRoom
  // Is this room the 'exit' room
  IF curRoom.IsExit() THEN
    solved = TRUE
    RETURN
  ENDIF

  // Deadend?  (skip starting room)
  IF (curRoom.id <> prevRoom.id) AND (curRoom.doors <= 1) THEN RETURN

  // Search each room the current room leads to
  FOREACH door IN curRoom
    // Skip the room we just came from
    IF door.id <> prevRoom.id THEN
      SearchRoom(door, curRoom)
    ENDIF
    IF solved THEN EXIT LOOP
  NEXT

  RETURN
ENDFUNCTION

[Edit] Added 'id' to previous check, and updated to make more object oriented.

share|improve this answer
1  
I don't know on each step where I came from. So, this algorithms doesn't solve the task. But thanks for trying. –  kirmir Aug 3 '11 at 21:39
3  
So you're saying that you're NOT ALLOWED to know the previous room? Or that you DON'T know the previous room? The code above keeps track of the previous rooms for you. If you're not allowed to know, I don't think there is a valid solution other than randomly iterating the maze for 'x' number of attempts, and if you can't find an exit, you can assume the maze is unsolvable. –  Doug.McFarlane Aug 3 '11 at 22:32
1  
"I don't know". I looked again code. The second problem is that using recursion is problematic. Imagine, that you are inside such maze. How would you use recursive algorithm to find exit? –  kirmir Aug 4 '11 at 10:35
    
Also, what happens if you start in room 6? curRoom.doors <= 1, so the function returns immediately, knowing that it is in a dead end, but thinking that it already explored the entirety of the maze. –  dlras2 Aug 4 '11 at 13:16
    
This is close, but it will blow the stack if there are cycles in the graph of length greater than two. –  munificent Aug 4 '11 at 15:28

The short answer is depth-first search with backtracking. You can do breadth-first if you prefer, but your little robot will do a lot more walking back and forth then.

More concretely, assume we're given:

// Moves to the given room, which must have a door between
// it and the current room.
moveTo(room);

// Returns the list of room ids directly reachable from
// the current room.
getDoors();

// Returns true if this room is the exit.
isExit();

To find the exit, we just need:

void escape(int startingRoom) {
  Stack<int> path = new Stack<int>();
  path.push(startingRoom);
  escape(path);
}

boolean escape(Stack<int> path) {
  for (int door : getDoors()) {
    // Stop if we've escaped.
    if (isExit()) return true;

    // Don't walk in circles.
    if (path.contains(door)) continue;

    moveTo(door);
    path.push(door);
    if (escape(path)) return true;

    // If we got here, the door didn't lead to an exit. Backtrack.
    path.pop();
    moveTo(path.peek());
  }
}

Call escape() with the ID of the start room and it will move the robot to the exit (by calling moveTo()).

share|improve this answer
    
I think escape(int startingRoom) should call escape(Stack<int> path) –  CiscoIPPhone Aug 4 '11 at 16:01
1  
I think if (path.contains(door)) continue; violates his requirements - the agent doesn't actually know if a door leads back to a room he's already been in unless he goes through the door. –  CiscoIPPhone Aug 4 '11 at 16:04
    
Thanks, fixed! Yeah, now that I look at the requirements, the problem seems a little fishy. If you can't backtrack, the best you can hope for is a random walk. –  munificent Aug 5 '11 at 2:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.