How to easily know if a maze has a road from start to goal?

Question

I implemented a maze using 0,1 array. The entry and goal is fixed in the maze. Entry always be 0,0 point of the maze. Goal always be m-1,n-1 point of the maze. I'm using breadth-first search algorithm for now, but the speed is not good enough. Especially for large maze (100*100 or so). Could someone help me on this algorithm?

Here is my solution:

queue = []
position = start_node
mark_tried(position)
queue << position
while(!queue.empty?)
  p = queue.shift  #pop the first element
  return true if maze.goal?(p)
  left = p.left
  visit(queue,left) if can_visit?(maze,left)
  right = p.right
  visit(queue,right) if can_visit?(maze,right)
  up = p.up
  visit(queue,up) if can_visit?(maze,up)
  down = p.down
  visit(queue,down) if can_visit?(maze,down)
end
return false

the can_visit? method check whether the node is inside the maze, whether the node is visited, whether the node is blocked.

Answer 1

worst answer possible.

1) go front until you cant move

2) turn left

3) rinse and repeat.

if you make it out , there is an end.

A better solution.

Traverse through your maze keeping 2 lists for open and closed nodes. Use the famous A-Star algorithm to choose evaluate the next node and discard nodes which are a dead end. If you run out of nodes on your open list, there is no exit.

Answer 2

Here is a simple algorithm which should be much faster:

• From start/goal move to to the first junction. You can ignore anything between that junction and the start/goal.

• Locate all places in the maze which are dead ends (they have three walls). Move back to the next junction and take this path out of the search tree.

After you have removed all dead ends this way, there should be a single path left (or several if there are several ways to reach the goal).

Answer 3

I would have solved this with an AStar implementation. If you want even more speed, you can optimize to only generate the nodes from the junctions rather than every tile/square/step.

Answer 4

A method you can use that does not need to visit all nodes in the maze is as follows:

• create an integer[][] with one value per maze "room"
• create a queue, add [startpoint, count=1, delta=1] and [goal, count=-1, delta=-1]
• start coloring the route by:
  • popping an object from the head of the queue, put the count at the maze point.
  • check all reachable rooms for a count with sign opposite to that of the rooms delta, if you find one the maze is solved: run both ways and connect the routes with the biggest steps up and down in room counts.
  • otherwise add all reachable rooms that have no count to the tail of the queue, with delta added to the room count.
  • if the queue is empty no path through the maze is possible.

This not only determines if there is a path, but also shows the shortest path possible through the maze.

You don't need to backtrack, so its O(number of maze rooms)

Answer 5

I would not use the AStar algorithm there yet, unless I really need to, because this can be done with some simple 'coloring'.

# maze is a m x n array
def canBeTraversed(maze):
  m = len(maze)
  n = len(maze[0])

  colored = [ [ False for i in range(0,n) ] for j in range(0,m) ]

  open = [(0,0),]

  while len(open) != 0:
    (x,y) = open.pop()
    if x == m-1 and y == n-1:
      return True
    elif x < m and y < n and maze[x][y] != 0 not colored[x][y]:
      colored[x][y] = True
      open.extend([(x-1,y), (x,y-1), (x+1,y), (x,y+1)])

  return False

Yes it's stupid, yes it's breadfirst and all that.

Here is the A* implementation

def dist(x,y):
  return (abs(x[0]-y[0]) + abs(x[1]-y[1]))^2

def heuristic(x,y):
  return (x[0]-y[0])^2 + (x[1]-y[1])^2

def find(open,f):
  result = None
  min = None
  for x in open:
    tmp = f[x[0]][x[1]]
    if min == None or tmp < min:
      min = tmp
      result = x
  return result

def neighbors(x,m,n):
  def add(result,y,m,n):
    if x < m and y < n: result.append(y)
  result = []
  add(result, (x[0]-1,x[1]), m, n)
  add(result, (x[0],x[1]-1), m, n)
  add(result, (x[0]+1,x[1]), m, n)
  add(result, (x[0],x[1]+1), m, n)
  return result

def canBeTraversedAStar(maze):
  m = len(maze)
  n = len(maze[0])

  goal = (m-1,n-1)

  closed = set([])
  open = set([(0,0),])

  g = [ [ 0 for y in range(0,n) ] for x in range(0,m) ]
  h = [ [ heuristic((x,y),goal) for y in range(0,n) ] for x in range(0,m) ]
  f = [ [ h[x][y] for y in range(0,n) ] for x in range(0,m) ]

  while len(open) != 0:
    x = find(open,f)
    if x == (m-1,n-1):
      return True
    open.remove(x)
    closed.add(x)

    for y in neighbors(x,m,n):
      if y in closed: continue

      if y not in open:
        open.add(y)

        g[y[0]][y[1]] = g[x[0]][x[1]] + dist(x,y)
        h[y[0]][y[1]] = heuristic(y,goal)
        f[y[0]][y[1]] = g[y[0]][y[1]] + h[y[0]][y[1]]

  return True

Here is my (simple) benchmark code:

def tryIt(func,size, runs):
  maze = [ [ 1 for i in range(0,size) ] for j in range(0,size) ]
  begin = datetime.datetime.now()
  for i in range(0,runs): func(maze)
  end = datetime.datetime.now()

  print size, 'x', size, ':', (end - begin) / runs, 'average on', runs, 'runs'

tryIt(canBeTraversed,100,100)
tryIt(canBeTraversed,1000,100)

tryIt(canBeTraversedAStar,100,100)
tryIt(canBeTraversedAStar,1000,100)

Which outputs:

# For canBeTraversed
100 x 100 : 0:00:00.002650 average on 100 runs
1000 x 1000 : 0:00:00.198440 average on 100 runs

# For canBeTraversedAStar
100 x 100 : 0:00:00.016100 average on 100 runs
1000 x 1000 : 0:00:01.679220 average on 100 runs

The obvious here: going A* to run smoothly requires a lot of optimizations I did not bother to go after...

I would say:

1. Don't optimize
2. (Expert only) Don't optimize yet

How much time are you talking about when you say too much ? Really a 100x100 grid is so easily parsed in brute force it's a joke :/