# Como implementar um código para gerar e resolver labirintos usando backtracking?

0 votos
862 visitas

## 1 Resposta

+1 voto
respondida Mai 11, 2016 por (5,806 pontos)

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 == 1:
plt.hlines(y=self.y, xmin=self.x, xmax=self.x+1, linewidth=1, color='b')
if self.walls == 1:
plt.vlines(x=self.x+1, ymin=self.y, ymax=self.y+1, linewidth=1, color='b')
if self.walls == 1:
plt.hlines(y=self.y+1, xmin=self.x, xmax=self.x+1, linewidth=1, color='b')
if self.walls == 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 = 1
if self.x == xmax: #E borders
self.border = 1
if self.y == ymax: #S borders
self.border = 1
if self.x == 0: #W borders
self.border = 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: #top
nt = cells[x][y-1]
if nt.walls == [1,1,1,1]:
neighbours.append(nt)
if currentCell.border == 0: #right
nr = cells[x+1][y]
if nr.walls == [1,1,1,1]:
neighbours.append(nr)
if currentCell.border == 0: #bottom
nb = cells[x][y+1]
if nb.walls == [1,1,1,1]:
neighbours.append(nb)
if currentCell.border == 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
neighbour.walls = 0
return
if neighbour.x == cell.x+1:
cell.walls = 0
neighbour.walls = 0
return
if neighbour.y == cell.y+1:
cell.walls = 0
neighbour.walls = 0
return
if neighbour.x == cell.x-1:
cell.walls = 0
neighbour.walls = 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 and c.walls == 0:
neighbour = cells[c.x][c.y-1]
if not neighbour.visited:
neighbours.append(neighbour)
if c.border == 0 and c.walls == 0:
neighbour = cells[c.x+1][c.y]
if not neighbour.visited:
neighbours.append(neighbour)
if c.border == 0 and c.walls == 0:
neighbour = cells[c.x][c.y+1]
if not neighbour.visited:
neighbours.append(neighbour)
if c.border == 0 and c.walls == 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
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')