Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

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

0 votos
862 visitas
perguntada Mai 11, 2016 em Ciência da Computação por danielcajueiro (5,806 pontos)  
Compartilhe

1 Resposta

+1 voto
respondida Mai 11, 2016 por danielcajueiro (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 imagem será apresentada aqui.

# 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')
...