mercredi 1 novembre 2017

How Can I Stop Corners From Touching When Generating Maze

I have been trying to develop a maze generator in Python 3, and I am nearing completion. I have it to the point where I can create the maze as seen in the picture below, however if you look closely, you may be able to see the two issues I am worried about. In some cases, the corners of the path are touching. This is something that I am explicitly trying to avoid by checking each potential cells 8 edges and corners. There are also some spots that I can see where there are "islands" that have space for an additional cell, however it is empty. If you have any idea as to how I could fix that, that would be great. Thanks!

Picture Of The Generated Maze

import random
import numpy as np
from matplotlib import pyplot as plt

# Width and height of the maze
mx = 50
my = 50

# Maze Array
maze = np.zeros((mx, my))

# Directions to move in the maze
dx = [-1, 1, 0, 0, -1, 1, 1, -1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]

# Visited Cells
stack = []

# Find Which Neighbour Cells Are Valid
def nextCell(cx, cy):

    # Set Current Cell To '1'
    maze[cy, cx] = 1

    # List Of Available Neighbour Cell Locations
    n = []

    # Check The 4 Available Neighbour Cells
    for i in range(4):

        nx = cx + dx[i]
        ny = cy + dy[i]

        # Check If Neighbours Cell Is Inbound
        if nx >= 1 and nx < my - 1 and ny >= 1 and ny < mx - 1:

            # Check If Neighbour Cell Is Occupied
            if maze[ny, nx] == 0:

                # Variable To Store Neighbour Cells Neighbours
                cn = 0

                # Loop Through Neighbour Cells Neighbours
                for j in range(8):

                    ex = nx + dx[j]
                    ey = ny + dy[j]

                    # Check If Neighbour Cells Neighbour Is Inbound
                    if ex >= 0 and ex < my and ey >= 0 and ey < mx:

                        # Check If Neighbour Cells Neighbour Is Occupied
                        if maze[ey, ex] == 1:
                            cn += 1

                # If Neighbour Cells Neighbour Has Less Than 2 Neighbours, Add Cell To List
                if cn <= 2:
                    n.append((ny, nx))



    # Return The List Of Valid Neighbours
    return n

# Generate The Maze
def GenerateMaze(sx, sy):

    # Initialize 'x,y' With Starting Location
    x = sx
    y = sy

    # Loop Until Maze Is Fully Generated
    while True:

        # Neighbour List
        n = nextCell(x, y)

        # Check If 'n'  Contains A Neighbour
        if len(n) > 0:
            stack.append((y, x))

            ir = n[random.randint(0, len(n) - 1)]

            x = ir[1]
            y = ir[0]

        # Go Back Through The Stack
        elif len(stack) > 1:
            stack.pop()

            x = stack[-1][1]
            y = stack[-1][0]

        # Maze Is Complete
        else:    
            break



if __name__ == "__main__":

    # Generate Maze
    GenerateMaze(random.randint(1,8), random.randint(1,8))

    # Show Plot
    plt.imshow(maze, interpolation='nearest')
    plt.show()




Aucun commentaire:

Enregistrer un commentaire