29a.ch experiments by Jonas Wagner

Generating Maps/Mazes with Python

Written by

Last weekend I wrote some code to generate random mazes in python. The algorithm creates fully connected mazes using backtracking. So between two points in the maze there is always exactly one path. In a game you would probably want to remove some more walls to create loops.

#!/usr/bin/env python
import sys
from random import shuffle

def shuffled(x):
    y = list(x)
    shuffle(y)
    return y

DIRECTIONS = (
    (0, -1),
    (0, 1),
    (1, 0),
    (-1, 0),
)

def make_maze(width, height, cellsize):
    cellsize1 = cellsize+1 # cellsize including one wall
    field_width = width*cellsize1+1
    field_height = height*cellsize1+1
    field = [0]*(field_width*field_height)
    stack = [(0, 0, shuffled(DIRECTIONS))]
    while stack:
        x, y, directions = stack[-1]
        dx, dy = directions.pop()
        # no other ways to go from here
        if not directions:
            stack.pop()
        # new cell
        nx = x+dx
        ny = y+dy
        # out of bounds
        if not (0 <= nx < width and 0 <= ny < height):
            continue
        # index of new cell in field
        fx = 1+nx*cellsize1
        fy = 1+ny*cellsize1
        fi = fx+fy*field_width
        # already visited
        if field[fi]:
            continue
        # tear down walls
        if dx > 0:
            a = -1
            b = field_width
        elif dx < 0:
            a = cellsize
            b = field_width
        elif dy > 0:
            a = -field_width
            b = 1
        else:
            a = cellsize*field_width
            b = 1
        for offset in xrange(cellsize):
            field[fi+a+b*offset] = 1
        # clear cell
        for y in xrange(0, cellsize):
            for x in xrange(0, cellsize):
                field[fi+x+y*field_width] = 1
        # visit cell
        stack.append([nx, ny, shuffled(DIRECTIONS)])
    return field

if __name__ == "__main__":
    if len(sys.argv) != 4:
        raise SystemExit("Usage: %s width height cellsize" % sys.argv[0])
    width, height, cellsize = map(int, sys.argv[1:])
    fields = make_maze(width, height, cellsize)
    w = (cellsize+1)*width+1
    h = (cellsize+1)*height+1
    for y in xrange(h):
        print "".join(map(lambda x: x and " " or "#", fields[y*w:y*w+w]))

And here some examples of the output:

#############################################################
#     #           #              #        #           #     #
#     #           #              #        #           #     #
#  ####  ####  #  #  ##########  #  #  #  #  #######  #  ####
#     #  #     #     #           #  #  #     #     #  #     #
#     #  #     #     #           #  #  #     #     #  #     #
####  #  #  ##########  #############  #######  #  #  ####  #
#     #  #  #  #     #     #           #     #  #  #        #
#     #  #  #  #     #     #           #     #  #  #        #
#  #######  #  #  #  ####  #######  ####  ####  #  #######  #
#           #     #  #     #        #  #     #  #        #  #
#           #     #  #     #        #  #     #  #        #  #
#############  ####  #  ####  #######  #  #  #  #  #######  #
#                 #           #           #     #           #
#                 #           #           #     #           #
#############################################################
################
#           #  #
#           #  #
#  #  #  #  #  #
#  #  #  #  #  #
#  #  #  #  #  #
#  ####  #  #  #
#        #     #
#        #     #
#############  #
#     #        #
#     #        #
#  ####  #######
#              #
#              #
################
comments powered by Disqus