Algorithm for traversing a maze

Question

I need some help in writing a set of if-then rules for traversing a maze. This is the problem:

"Assume that the maze is constructed on a grid of square cells by placing walls across some of the edges of cells in such a way that there is a path from any cell within the maze to an outer edge of the maze that has no wall.

One way is left-hand rule, but this strategy can take you around in cycles.

Write if-then rules in English for traversing the wall and detecting a cycle. Assume you know size of grid and max distance you may have to travel to escape the maze."

This is what I have so far:

Start
If only one path (Left or Right or Straight) is found, follow the path.
Else If Multiple path is found:

If left path is found, take a left turn.

Else if straight path is found, follow straight path.

Else if right path is found, take a right turn.
Else If Dead End is found, take a 'U' turn.

Go To step 2
End

But this is not solving the cycle problem. Can anyone help please?

Usually be remembering where you have visited. Unless you are not allowed to do that (is it even possible, then)? — nhahtdh
– nhahtdh, Commented May 16, 2013 at 2:29
If you have started at an edge of a rectangular, planar, labyrinth and the exit/goal is also on an edge, then either right or left hand rule will, eventually, get you there. If your starting point is inside of such a labyrinth then you need the ability to detect cycles; at which point you switch to the other wall. It's still possible to end up in some degenerate case where your traversing a shape topologically equivalent to a figure eight (lemniscate). That implies multiple valid solution routes. From there you'd need a means to switch walls more than once (past path tracking). — Jim Dennis
– Jim Dennis, Commented May 16, 2013 at 2:38
Remembering any adjacent pair of steps and detecting when you've encountered the older of them without immediately crossing the second one will detect a cycle (eventually, though not necessarily efficiently). — Jim Dennis
– Jim Dennis, Commented May 16, 2013 at 2:42

TheRookierLearner · Accepted Answer · 2024-09-16 04:31:59Z

3

There are two generic algorithms for exploring graphs: Breadth First Search (BFS) and Depth First Search (DFS). The trick to these algorithms is they start out with all paths in the unexplored list, and as they visit paths they add those to the explored list. As you visit each node you remove it from the unexplored list so you won't revisit it. By only pulling nodes from the unexplored list in each case you don't have a case where you would double back upon yourself.

Here are examples of DFS with checks to prevent cycles and BFS:

function DFS(G,v):
  label v as explored
  for all edges e in G.adjacentEdges(v) do
      if edge e is unexplored then
          w ← G.adjacentVertex(v,e)
          if vertex w is unexplored then
              label e as a discovery edge
              recursively call DFS(G,w)
          else
              label e as a back edge

Now BFS:

procedure BFS(G,v):
  create a queue Q
  enqueue v onto Q
  mark v
  while Q is not empty:
      t ← Q.dequeue()
      if t is what we are looking for:
          return t
      for all edges e in G.adjacentEdges(t) do
           u ← G.adjacentVertex(t,e)
           if u is not marked:
                mark u
                enqueue u onto Q
  return none

edited Sep 16, 2024 at 4:31

TheRookierLearner

4,2419 gold badges39 silver badges55 bronze badges

answered May 16, 2013 at 2:46

chubbsondubs

39.4k25 gold badges110 silver badges143 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

tripleee Over a year ago

Maybe also mention "backtracking" here so that Google will find you. (-:

user2303699 Over a year ago

Thank you! I have a much better understanding of this now!

Collectives™ on Stack Overflow

Algorithm for traversing a maze

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related