Skip to content

Instantly share code, notes, and snippets.

@surt91
Last active Sep 17, 2016
Embed
What would you like to do?
draws a maze based on a randomized dfs, see http://en.wikipedia.org/wiki/Maze_generation
#!/usr/bin/env python3
import sys
from random import shuffle
import networkx as nx
# pythons recursion limit is quite low
# increase it, the worst that can happen is a Stack overflow
sys.setrecursionlimit(20000)
def dfs(g, u=0, path=None, explorer=None):
"""Recursive Depth First Search
returns the path it took and an ancestor dictionary `explorer`
"""
if path is None:
path = []
# no path means, we are starting right now
# init all nodes as unvisited
for n in g.nodes_iter():
g.node[n]['visited'] = False
if explorer is None:
explorer = {u:u}
path.append(u)
g.node[u]['visited'] = True
neighbors = g.neighbors(u)
shuffle(neighbors)
for n in neighbors:
if not g.node[n]['visited']:
dfs(g, n, path, explorer)
explorer.update({n:u})
return path, explorer
def createSquareLattice(x,y):
G=nx.Graph()
for i in range(x):
for j in range(y):
G.add_node(i+j*x)
for n in G.nodes():
if n+1 < x*y and n%x != x-1:
G.add_edge(n,n+1) # right
if n+x < x*y:
G.add_edge(n,n+x) # below
return G
def writeSVG(path, explorer, x, y, filename="maze.svg"):
scale = 30
offset = scale/2
thickness = scale/3
join = thickness/2
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"
footer = "</svg>\n\n"
with open(filename, "w") as f:
f.write(header)
for p1 in path:
p2 = explorer[p1]
cX1, cY1 = p1%x, p1//x
cX2, cY2 = p2%x, p2//x
# do not draw a line if the jump is longer than one node
if abs(cX1 - cX2) + abs(cY1 - cY2) == 1:
f.write(line.format(x1=cX1*scale+offset+(cX1-cX2)*join,
x2=cX2*scale+offset-(cX1-cX2)*join,
y1=cY1*scale+offset+(cY1-cY2)*join,
y2=cY2*scale+offset-(cY1-cY2)*join,
w=thickness))
f.write(footer)
if __name__ == "__main__":
x,y = 64,36
G = createSquareLattice(x,y)
start_node = 0
p, ex = dfs(G, start_node)
writeSVG(p, ex ,x,y)
for i in range(len(p)):
writeSVG(p[:i+1], ex , x, y, "maze_{:04d}.svg".format(i))
#!/bin/bash
for i in *.svg
do inkscape -z -b \"#fff\" -e $(basename -s .svg $i).png -h 1080 $i
done
ffmpeg -f image2 -pattern_type glob -framerate 60 -i "maze*.png" -vcodec libx264 maze.mp4
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment