quickgen -- procedurally generating a map by repeated subdivision

quickgen.py

#!/usr/bin/env python3

# quickgen by azul (@typeswitch@gamedev.lgbt) -- generates a map
# by repeated subdivision. a simple approach to generating maps
# quickly, starting from a very rough sketch.
#
# this code is public domain! use it however you like.

import random

# initial parameters:
#   N = initial map size
#   MAP = initial map of NxN cells, this is the "rough sketch"
#     of what you want the final map to look like.
#   BOUNDARY = the boundary value, a default value for cells
#     outside of the map. used during generation of new cells.
#   LIMIT = the map subdivision is repeated until N >= LIMIT.
N = 5
MAP = [
    [-1, -1, -1, -1, -1],
    [-1,  0,  2,  1, -1],
    [-1,  0,  4,  3, -1],
    [-1,  0, -2,  3, -1],
    [-1, -1, -1, -1, -1],
]
BOUNDARY = -1
LIMIT = 20

def genpt(a,b,c,d):
    '''generate a new map cell given four neighbor cells. this function is
    called many times at each stage, to create a subdivision of the map,
    cell by cell.'''
    lo = min(a,b,c,d)
    hi = max(a,b,c,d)
    return random.uniform(lo,hi)

def valstr(x):
    '''convert a map cell for display as a character'''
    if x < 0: return ' '
    if x < 1: return '_'
    if x < 2: return '.'
    if x < 3: return ':'
    return '∴'

def show(m):
    '''display the map'''
    for row in m:
        print(' '.join(map(valstr,row)).rstrip())
    print()

def v(m,n,x,y):
    '''get the map cell from the map m (size n by n) at position (x,y).
    returns BOUNDARY if the coordinate lies outside of the map.'''
    if 0 <= x < n and 0 <= y < n:
        return m[y][x]
    return BOUNDARY

def build(n, fn):
    '''build an n by n map by calling a function for each coordinate.'''
    return [ [ fn(x,y) for x in range(n) ] for y in range(n) ]

# show the initial sketch.
show(MAP)

# this is the main loop, this is where we generate the map!
while N < LIMIT:
    # At each step, we subdivide the map. This turns an NxN map into
    # a (2N-1)x(2N-1) map. We achieve this by generating new cells
    # in between other cells.

    # the map from the previous stage.
    OLD = MAP

    # first we generate (N-1)x(N-1) midpoints between every four
    # old map cells. conceptually, we're generating a MID value
    # in between every four OLD values, like so:
    #
    #            ...             ...             ...
    #             |               |               |
    #    ... --- OLD ----------- OLD ----------- OLD --- ...
    #             |               |               |
    #             |      MID      |      MID      |
    #             |               |               |
    #    ... --- OLD ----------- OLD ----------- OLD --- ...
    #             |               |               |
    #             |      MID      |      MID      |
    #             |               |               |
    #    ... --- OLD ----------- OLD ----------- OLD --- ...
    #             |               |               |
    #            ...             ...             ...
    #
    MID = build(N-1,lambda x,y: genpt(
        v(OLD, N, x,   y  ),
        v(OLD, N, x+1, y  ),
        v(OLD, N, x,   y+1),
        v(OLD, N, x+1, y+1),
    ))

    # then we use both OLD and MID values to generate the "edges"
    # in the above diagram. see the diagram below for how the TOP
    # and SID maps relate to OLD and MID.
    TOP = build(N,lambda x,y: genpt(
        v(MID, N-1, x,   y-1),
        v(OLD, N,   x,   y  ),
        v(OLD, N,   x+1, y  ),
        v(MID, N-1, x,   y  ),
    ))
    SID = build(N, lambda x,y: genpt(  # (SID stands for "side")
        v(OLD, N,   x,   y  ),
        v(MID, N-1, x,   y  ),
        v(OLD, N,   x,   y+1),
        v(MID, N-1, x-1, y  ),
    ))

    # then we interleave these four maps to make one big map that is
    # roughly twice the size of the original. we interleave like this:
    #
    #            ...     ...     ...     ...     ...
    #             |       |       |       |       |
    #    ... --- OLD --- TOP --- OLD --- TOP --- OLD --- ...
    #             |       |       |       |       |
    #    ... --- SID --- MID --- SID --- MID --- SID --- ...
    #             |       |       |       |       |
    #    ... --- OLD --- TOP --- OLD --- TOP --- OLD --- ...
    #             |       |       |       |       |
    #    ... --- SID --- MID --- SID --- MID --- SID --- ...
    #             |       |       |       |       |
    #    ... --- OLD --- TOP --- OLD --- TOP --- OLD --- ...
    #             |       |       |       |       |
    #            ...     ...     ...     ...     ...
    #
    maps = [OLD,TOP,SID,MID]
    MAP = build(2*N-1, lambda x,y:
        v(maps[x%2 + 2*(y%2)], N, x//2, y//2)
    )
    # (note that although we only generated (N-1)x(N-1) midpoints,
    # we are calling v on MID as if it were an NxN map. this is fine
    # here because we're never calling it v on MID x=N-1 or y=N-1)

    # increase N accordingly.
    N = 2*N-1

    # show the map after each stage
    show(MAP)

# This version of the algorithm generates a map with a hard boundary.
# To generate a wrapping map instead:
#   - change v to wrap x and y around n instead of returning BOUNDARY
#   - in the main loop, replace N-1 and 2*N-1 with N and 2*N respectively.
# These changes actually make the algorithm a bit cleaner, and remove
# boundary artifacts. It just depends on what you want out of it.

# Instead of using numbers for each cell, you can use any data type.
# You just have to change:
#   - the initial sketch, MAP, to use the new data type
#   - the boundary value, BOUNDARY, to use the new data type
#   - how genpt works ... make it appropriate for the new data type
#   - valstr, to display the map cells
# Have fun and experiment!
#
# For example, using characters directly as map cells:
#
#     N = 5
#     MAP = [
#         [' ', ' ', ' ',  ' ',  ' '],
#         [' ', '/', '\\', '\\', ' '],
#         [' ', '/', '/',  '\\', ' '],
#         [' ', '/', '_',  '_',  ' '],
#         [' ', ' ', ' ',  ' ',  ' '],
#     ]
#     BOUNDARY = ' '
#     LIMIT = 20
#     def genpt(a,b,c,d):
#         return random.choice([a,b,c,d])
#     def valstr(x): return x
#
# You could get the following output:
#
#   / \ \
#   / / \
#   / _ _
#
#
#       \
#     / / \ \ \ \
#       / / \ \ \
#   / / / / / \ \
#   / / / / _ \ _
#     / / _ _ _ _
#             _
#
#
#               \
#             \ \
#           \ \ \   \
#       / / \ \ \   \ \ \ \   \ \
#       / / / / \ \ \ \ \ \ \ \
#       / / / / / / \ \ \ \ \ \
#           / / / / / \ \ \ \ \ \
#           / / / / / / \ \ \ \ \
#     / / / / / / / / / \ \ \ \
#   / / / / / / / / / \ \ \ \ \ \ \
#     / / / / / / / / _ \ \ \ _
#         / / / / / _ _ _ _ _ _
#       / / / / / _ _ _ _ _ _ _
#           /       _ _ _ _ _ _ _
#           /             _ _
#                         _ _
#
#
#                           \ \ \
#                       \ \ \ \ \ \
#                       \ \ \ \
#                   \ \ \ \ \ \
#                   \ \ \ \ \ \     \ \ \
#             /     \ \ \ \ \ \       \ \     \ \ \
#             /   / \ \ \ \ \ \       \ \ \ \ \ \ \       \   \
#             / / / / \ \ \ \ \ \     \ \ \ \ \ \ \ \   \ \ \ \
#           / / / / / / \ / \ \ \ \   \ \ \ \ \ \ \ \ \ \ \ \
#           / / / / / / / / \ \ \ / \ \ \ \ \ \ \ \ \ \ \ \
#           / / / /   / / / \ / / / / \ \ \ \ \ \ \ \ \ \ \
#             /       / / / / / / / / / \ \ \ \ \ \ \ \ \ \
#                     / / / / / / / / / \ \ \ \ \ \ \ \ \ \   \ \
#                     / / / / / / / / / / / \ \ \ \ \ \ \ \ \ \ \
#                     / / / / / / / / / / / / \ \ \ \ \ \ \ \ \ \
#         /         / / / / / / / / / / / / \ \ \ \ \ \ \ \   \ \ \
#       / / / /   / / / / / / / / / / / / / \ \ \ \ \ \ \ \ \   \
#         / / / / / / / / / / / / / / / / / \ \ \ \ \ \ \ \   \ \ \
#     /   / / / / / / / / / / / / / / / / \ \ \ \ \ \ \ \ \ \ \ \ \
#           / / / / / / / / / / / / / / / / \ \ \ \ \ \ \ \
#         /   / / / / / / / / / / / / / _ _ \ \ \ \ \ \ _ _
#       / /     / / / / / / / / / / / / _ _ _ _ \ \ _ _ _ _
#                 / / / / / / / _ / _ _ _ _ _ _ \ _ _ _ _ _ _
#             / / / / / / / / / _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
#             / / / / /   / / /   _ _ _ _ _ _ _ _ _ _ _ _ _ _
#             / /     /   /   /       _ _ _ _ _ _ _ _ _ _     _
#                   / /             _ _ _ _ _ _ _ _ _ _ _ _   _
#                 / /                   _     _ _ _ _         _
#                     / /               _       _ _ _ _
#                                             _ _ _ _ _ _
#                                               _ _ _ _ _
#                                             _ _ _ _ _
#                                                   _