cellularMaze.py

#!/usr/bin/env python3

import sys
from random import random

import networkx as nx

def updateAliveNeighbors(G, changedNodes, alive_neighbors):
    for n in set(changedNodes):
        alive_neighbors[n] = 0
        for nn in G.neighbors(n):
            if G.node[nn]["alive"]:
                alive_neighbors[n] += 1


# conways game of live: b=(3,), s=(2, 3)
# maze: b=(3,), s=(1, 2, 3, 4, 5)
# mazectric: b=(3,), s=(1, 2, 3, 4)
# http://www.conwaylife.com/w/index.php?title=Maze
def celluarAutomaton(G, b=(3,), s=(1, 2, 3, 4)):
    changed = G.nodes()
    generation = 0

    alive_neighbors = {}
    updateAliveNeighbors(G, changed, alive_neighbors)

    while changed:
        generation += 1
        print(generation)
        changed = []

        for i in G.nodes():
            if alive_neighbors[i] in b and not G.node[i]["alive"]:
                G.node[i]["alive"] = True
                changed += G.neighbors(i)
            elif alive_neighbors[i] not in s and G.node[i]["alive"]:
                G.node[i]["alive"] = False
                changed += G.neighbors(i)

        updateAliveNeighbors(G, changed, alive_neighbors)
        writeSVG(G, "maze_{:04d}.svg".format(generation))


def writeSVG(G, filename="maze.svg"):
    scale = 6
    offset = scale/2

    x, y = zip(*G.nodes())
    x, y = max(x), max(y)

    height = (y-1)*scale+2*offset
    width  = (x-1)*scale+2*offset

    header = "<svg version='1.1' baseProfile='full' width='{x}' height='{y}'>\n"
    header +="<rect fill='white' width='{x}' height='{y}' />\n"
    header = header.format(x=width, y=height)
    line = "<line x1='{x1}' x2='{x2}' y1='{y1}' y2='{y2}' stroke='black' stroke-width='{w}' />\n"
    rect = "<rect x='{x}' y='{y}' width='{scale}' height='{scale}' stroke='black' fill='black' stroke-width='0' />\n"
    footer = "</svg>\n\n"

    with open(filename, "w") as f:
        f.write(header)

        for n in G.nodes():
            x, y = n
            if not G.node[n]["alive"]:
                continue

            f.write(rect.format(x=x*scale, y=y*scale, scale=scale))

        f.write(footer)


def addDiagonals(G):
    for n in G.nodes():
        for offset in ((-1, 1), (1, 1), (1, -1), (-1, -1)):
            dx, dy = offset
            x, y = n
            try:
                G.add_edge(n, (x+dx, y+dy))
            except:
                pass


if __name__ == "__main__":
    x,y = 320,180
    G = nx.grid_2d_graph(x,y)
    addDiagonals(G)
    
    for i in G.nodes():
        if 155 < i[0] < 165 and 85 < i[1] < 95:
            G.node[i]["alive"] = random() > 0.5
        else:
            G.node[i]["alive"] = False

    celluarAutomaton(G)
    writeSVG(G)