Help navigating a dark maze

Discussion in 'OT Technology' started by unimatrix, Nov 30, 2004.

  1. unimatrix

    unimatrix New Member

    Joined:
    Dec 12, 2003
    Messages:
    3,133
    Likes Received:
    0
    Location:
    Atlanta
    Does anyone know of an algorithm to navigate a maze when you don't know what walls are around you? I have to write a program to do this in assembly, but I can't even figure out the algorithm. I have a function to try to move in one of four directions (up, down, left, right), and get back a value that tells me if I moved, got blocked by a wall, or exited the maze.

    My problem is that anything I try looks like it will end up in infinite recursion with me either traveling in circles or just going directly back and forth. The professor said the easiest answer was using recursion, and I would pass in the last direction moved each time I called the function. Please let me know if you have any ideas, and any code posted in another programming language would help. Thanks in advance.
     
  2. MP

    MP New Member

    Joined:
    Sep 10, 2002
    Messages:
    34,377
    Likes Received:
    0
    Location:
    Silicon Valley
    do you know how big the maze is or any other information about the maze? Does it have cells, etc etc.
     
  3. korrupshun

    korrupshun New Member

    Joined:
    Sep 8, 2004
    Messages:
    389
    Likes Received:
    0
    Location:
    YourMommasHouse
    the recursive solution should be fairly simple:

    void move(direction){
    if end of maze return; //error checks

    if !end of maze move(right);
    if !end of maze move(left);
    if !end of maze move(up);
    if !end of maze move(down);

    return;
    }

    i personally think it would be of great benefit to research breadth first search and depth first search algorithms tho....might find that a little more appealing overall
     

Share This Page