O código abaixo gera e resolve labirintos usando backtracking. Por exemplo, o labirinto abaixo e sua solução foi resolvida usando esse código.
# A modified version of https://gist.github.com/hqt08/de225b4e679653c06e71
import numpy as np
import matplotlib.pyplot as plt
fig=plt.figure(num=None, figsize=(8, 8), dpi=80, facecolor='w', edgecolor='k')
plt.hold(True)
class Cell:
def __init__(self, x, y):
self.x = x
self.y = y
#Up,Right,Down,LEft
self.walls = [1,1,1,1] # All walls are set in the beginning
self.border = [0,0,0,0] # Only points in the border will have borders
self.visited = False
def draw_cell(self):
if self.walls[0] == 1:
plt.hlines(y=self.y, xmin=self.x, xmax=self.x+1, linewidth=1, color='b')
if self.walls[1] == 1:
plt.vlines(x=self.x+1, ymin=self.y, ymax=self.y+1, linewidth=1, color='b')
if self.walls[2] == 1:
plt.hlines(y=self.y+1, xmin=self.x, xmax=self.x+1, linewidth=1, color='b')
if self.walls[3] == 1:
plt.vlines(x=self.x, ymin=self.y, ymax=self.y+1, linewidth=1, color='b')
def setup_border(self,xmax,ymax):
if self.y == 0: #N borders
self.border[0] = 1
if self.x == xmax: #E borders
self.border[1] = 1
if self.y == ymax: #S borders
self.border[2] = 1
if self.x == 0: #W borders
self.border[3] = 1
def check_neighbours(cells, currentCell, x, y):
# It checks if one of the neighbors is not available due to border constraints
neighbours = []
if currentCell.border[0] == 0: #top
nt = cells[x][y-1]
if nt.walls == [1,1,1,1]:
neighbours.append(nt)
if currentCell.border[1] == 0: #right
nr = cells[x+1][y]
if nr.walls == [1,1,1,1]:
neighbours.append(nr)
if currentCell.border[2] == 0: #bottom
nb = cells[x][y+1]
if nb.walls == [1,1,1,1]:
neighbours.append(nb)
if currentCell.border[3] == 0: #left
nl = cells[x-1][y]
if nl.walls == [1,1,1,1]:
neighbours.append(nl)
return neighbours
def knock_down_wall(cell, neighbour):
#compare Up,Right,Down,LEft direction to discern wall direction
if neighbour.y == cell.y-1:
cell.walls[0] = 0
neighbour.walls[2] = 0
return
if neighbour.x == cell.x+1:
cell.walls[1] = 0
neighbour.walls[3] = 0
return
if neighbour.y == cell.y+1:
cell.walls[2] = 0
neighbour.walls[0] = 0
return
if neighbour.x == cell.x-1:
cell.walls[3] = 0
neighbour.walls[1] = 0
return
def maze_generation(height,width):
shape = (height, width)
# Initialize 2D cell arrray: This is going to be a list of cells
cells = [[0 for y in xrange(0,height)] for x in xrange(0,width)]
# Initialize all walls (all present)
for y in xrange(0,height):
for x in xrange(0,width):
c = Cell(x,y)
c.setup_border(width-1, height-1)
cells[x][y] = c
# Initialize 2D cell arrray: This is going to be a list of cells
cells = [[0 for y in xrange(0,height)] for x in xrange(0,width)]
# Initialize all walls (all present)
for y in xrange(0,height):
for x in xrange(0,width):
c = Cell(x,y)
c.setup_border(width-1, height-1)
cells[x][y] = c
# Setup Cell Stack
stack = []
num_total = width*height
num_visited = 0 #keep track of total no. of cells visited
# Get random starting cell
rand_x = np.random.randint(0,width)
rand_y = np.random.randint(0,height)
print 'Starting cell:(',rand_x,',',rand_y,')'
currentCell = cells[rand_x][rand_y]
num_visited += 1
# DFS Algo
while num_visited < num_total:
neighbours_with_all_walls = check_neighbours(cells, currentCell, currentCell.x, currentCell.y)
n = len(neighbours_with_all_walls)
if n > 0:
index = np.random.randint(0,n)
randNeighbour = neighbours_with_all_walls[index]
# knock down the wall btw current cell and chosen neighbour
knock_down_wall(currentCell, randNeighbour)
stack.append(currentCell)
currentCell = randNeighbour
num_visited += 1
else:
cell = stack.pop()
currentCell = cell
# Final Drawing
for y in xrange(0,height):
for x in xrange(0,width):
c = cells[x][y]
c.draw_cell()
# Get Solution for given start/end point
return cells
def get_all_neighbours_not_yet_visited(cells, c):
neighbours = []
if c.border[0] == 0 and c.walls[0] == 0:
neighbour = cells[c.x][c.y-1]
if not neighbour.visited:
neighbours.append(neighbour)
if c.border[1] == 0 and c.walls[1] == 0:
neighbour = cells[c.x+1][c.y]
if not neighbour.visited:
neighbours.append(neighbour)
if c.border[2] == 0 and c.walls[2] == 0:
neighbour = cells[c.x][c.y+1]
if not neighbour.visited:
neighbours.append(neighbour)
if c.border[3] == 0 and c.walls[3] == 0:
neighbour = cells[c.x-1][c.y]
if not neighbour.visited:
neighbours.append(neighbour)
return neighbours
# Gets the maze solution route for any given start/end point
def calc_solution(cells, startx, starty, endx, endy):
start_cell = cells[startx][starty]
end_cell = cells[endx][endy]
# DFS again...
stack = []
currentCell = start_cell
currentCell.visited = True
while currentCell != end_cell:
# get random possible neighbour
neighbours = get_all_neighbours_not_yet_visited(cells, currentCell)
n = len(neighbours)
if n > 0:
index = np.random.randint(0,n)
randNeighbour = neighbours[index]
randNeighbour.visited = True
stack.append(currentCell)
currentCell = randNeighbour
else: # dead end, backtrack
cell = stack.pop()
currentCell = cell
# Plot solution
for c in stack:
plt.plot(c.x+0.5, c.y+0.5, linestyle='None', marker="o", color="b")
plt.plot(start_cell.x+0.5, start_cell.y+0.5, linestyle='None', marker="o", color="b", markersize=20)
plt.plot(end_cell.x+0.5, end_cell.y+0.5, linestyle='None', marker="o", color="b", markersize=20)
if __name__ == '__main__':
width=12
height=12
# Build cells' fill
cells=maze_generation(height,width)
plt.axis([0,width,height,0])
calc_solution(cells, 0, 0, width-1, height-1)
plt.savefig('maze.eps')