maze_generator.py

#!/usr/bin/env python3
import numpy
from numpy.random import random_integers as rand
import matplotlib.pyplot as pyplot


# Source: https://en.wikipedia.org/wiki/Maze_generation_algorithm
# License: Creative Commons Attribution-ShareAlike 3.0 Unported License
#     https://en.wikipedia.org/wiki/Wikipedia:Text_of_Creative_Commons_Attribution-ShareAlike_3.0_Unported_License
def generate_maze(width=81, height=51, complexity=0.75, density=0.75):
    # Only odd shapes
    shape = ((height // 2) * 2 + 1, (width // 2) * 2 + 1)
    # Adjust complexity and density relative to maze size
    complexity = int(complexity * (5 * (shape[0] + shape[1])))
    density = int(density * ((shape[0] // 2) * (shape[1] // 2)))
    # Build actual maze
    Z = numpy.zeros(shape, dtype=bool)
    # Fill borders
    Z[0, :] = Z[-1, :] = 1
    Z[:, 0] = Z[:, -1] = 1
    # Make aisles
    for i in range(density):
        x, y = rand(0, shape[1] // 2) * 2, rand(0, shape[0] // 2) * 2
        Z[y, x] = 1
        for j in range(complexity):
            neighbours = []
            if x > 1:
                neighbours.append((y, x - 2))
            if x < shape[1] - 2:
                neighbours.append((y, x + 2))
            if y > 1:
                neighbours.append((y - 2, x))
            if y < shape[0] - 2:
                neighbours.append((y + 2, x))
            if len(neighbours):
                y_, x_ = neighbours[rand(0, len(neighbours) - 1)]
                if Z[y_, x_] == 0:
                    Z[y_, x_] = 1
                    Z[y_ + (y - y_) // 2, x_ + (x - x_) // 2] = 1
                    x, y = x_, y_
    return Z


def convert_maze(maze):
    """
    Convert maze to format required by given task and add target to random
    empty space
    """
    # convert to desired format
    array = maze.astype(int)
    array[array == 1] = -1

    # add random target cell to non-wall coordinates
    zero_cells = numpy.where(array == 0)
    position = numpy.random.randint(0, len(zero_cells[0]))
    array[zero_cells[0][position], zero_cells[1][position]] = 1

    return array


def main():
    maze = generate_maze(30, 15)
    maze = convert_maze(maze)

    pyplot.figure(figsize=(10, 5))
    pyplot.imshow(maze, cmap=pyplot.cm.binary, interpolation='nearest')
    pyplot.xticks([]), pyplot.yticks([])
    pyplot.show()


if __name__ == "__main__":
    main()