#!/usr/bin/python
#
# genmaze -- make text and SVG mazes
#
# 1.0: 2009-FEB-5: Initial release
# 1.1: 2009-FEB-5: Random seed and linestyle support, errorchecking
# 1.2: 2009-FEB-5: Border support
#
# I apologize for the hackish nature of storing which walls are on or off.
# If you run out of stack, setrecursionlimit down in main().
#
# I hereby grant this software to the public domain.
#
# Brian "Beej Jorgensen" Hall <beej@beej.us>
#

import sys
import os.path
import getopt
import random

class AppContext(object):
	OUTPUT_TEXT = 1
	OUTPUT_SVG = 2

	def __init__(self, argv):

		self.scriptname = os.path.basename(argv[0])

		try:
			opts, args = getopt.getopt(sys.argv[1:], "ho:d:s",
				["help", "output=", "dim=", "svgwidth=", 
					"svgheight=", "svg", "svgboxwidth=",
					"svgboxheight=", "svgunits=", "seed=",
					"svglinestyle=", "svgborder="])
		except getopt.GetoptError:
			self.usage()

		self.outputtype = AppContext.OUTPUT_TEXT
		self.xdim = 20
		self.ydim = 10
		self.size = 10
		self.filename = '-'
		
		self.svgwidth = None
		self.svgheight = None
		self.svgboxwidth = None
		self.svgboxheight = None
		self.svgunits = 'cm'
		self.svgborder = None

		self.svglinestyle = 'stroke:rgb(0,0,0);stroke-width:2px;stroke-miterlimit:4;stroke-linecap:round'

		for o, a in opts:
			if o in ('-h', '--help'):
				self.usage()

			elif o in ('-o', '--output'):
				self.filename = a

			elif o == '--svglinestyle':
				self.svglinestyle = a

			elif o == '--seed':
				random.seed(a)

			elif o in ('-d', '--dim'):
				try:
					self.xdim, self.ydim = map(int, a.split(','))
					if self.xdim <= 1 or self.ydim <= 1: raise Exception()
				except:
					self.usage('dimensions must be two comma-separated '
						'positive integers')

			elif o in ('-s', '--svg'):
				self.outputtype = AppContext.OUTPUT_SVG

			elif o == '--svgwidth':
				self.outputtype = AppContext.OUTPUT_SVG
				self.svgwidth = self.checkPositiveFloat('svgwidth', a)

			elif o == '--svgheight':
				self.outputtype = AppContext.OUTPUT_SVG
				self.svgheight = self.checkPositiveFloat('svgheight', a)

			elif o == '--svgboxwidth':
				self.outputtype = AppContext.OUTPUT_SVG
				self.svgboxwidth = self.checkPositiveFloat('svgboxwidth', a)

			elif o == '--svgboxheight':
				self.outputtype = AppContext.OUTPUT_SVG
				self.svgboxheight = self.checkPositiveFloat('svgboxheight', a)

			elif o == '--svgborder':
				self.outputtype = AppContext.OUTPUT_SVG
				try:
					self.svgborder = float(a)
					if self.svgborder < 0: raise Exception()
				except:
					self.usage('svgborder must be a non-negative floating-point value')

			elif o == '--svgunits':
				self.outputtype = AppContext.OUTPUT_SVG
				self.svgunits = a

		if self.outputtype == AppContext.OUTPUT_SVG:
			# didn't give anything on the command line, just make up a width:
			if self.svgwidth == None and self.svgheight == None and \
				self.svgboxwidth == None and self.svgboxheight == None:
					self.svgwidth = self.xdim

			if self.svgwidth != None:
				self.svgboxwidth = self.svgwidth / self.xdim
				if self.svgheight == None:
					if self.svgboxheight == None:
						self.svgboxheight = self.svgboxwidth
					self.svgheight = self.svgboxheight * self.ydim

			elif self.svgheight != None:
				self.svgboxheight = self.svgheight / self.ydim
				if self.svgwidth == None:
					if self.svgboxwidth == None:
						self.svgboxwidth = self.svgboxheight
					self.svgwidth = self.svgboxwidth * self.xdim

			elif self.svgboxwidth != None:
				self.svgwidth = self.xdim * self.svgboxwidth
				if self.svgheight == None:
					if self.svgboxheight == None:
						self.svgboxheight = self.svgboxwidth
					self.svgheight = self.svgboxheight * self.ydim

			elif self.svgboxheight != None:
				self.svgheight = self.ydim * self.svgboxheight
				if self.svgwidth == None:
					if self.svgboxwidth == None:
						self.svgboxwidth = self.svgboxheight
					self.svgwidth = self.svgboxwidth * self.xdim

			else:
				self.usage("must specify svgwidth, svgheight, boxwidth, "
					"or boxheight")

			# we might have gotten here without calculating some of the box
			# heights, depending on what command line args were used:
			self.svgboxwidth = self.svgwidth / self.xdim
			self.svgboxheight = self.svgheight / self.ydim

			if self.svgborder == None:
				self.svgborder = (self.svgboxwidth + self.svgboxheight) / 2

		if len(args) != 0: self.usage()


	def usage(self, msg=None, exitStatus=1):
		if msg == None:
			sys.stderr.write('usage: %s [options]\n'
				'      -h       --help              help\n'
				'               --seed=s            set random number seed\n'
				'      -o       --output=file       set output file\n'
				'      -d x,y   --dim=x,y           set dimensions\n'
				'      -s       --svg               SVG output\n'
				'               --svgunits          SVG output units\n'
				'               --svgwidth=w        SVG width\n'
				'               --svgheight=h       SVG height\n'
				'               --svgboxwidth=bw    SVG box width\n'
				'               --svgboxheight=bh   SVG box height\n'
				'               --svglinestyle=st   SVG line style\n'
				% self.scriptname)
		else:
			sys.stderr.write('%s: %s\n' % (self.scriptname, msg))

		sys.exit(exitStatus)

	def checkPositiveFloat(self, name, strval):
		try:
			v = float(strval)
			if v <= 0: raise Exception()
			return v

		except:
			self.usage('%s must be a positive floating-point value' % name)

class Maze(object):
	N = 0  # warning: used for array indexes!!
	E = 1
	S = 2
	W = 3

	def __init__(self, xdim, ydim):
		self.xdim = xdim
		self.ydim = ydim

		self.hwall = []
		for y in xrange(self.ydim+1):
			self.hwall.append([])
			for x in xrange(self.xdim):
				self.hwall[-1].append(True)

		self.vwall = []
		for y in xrange(self.ydim):
			self.vwall.append([])
			for x in xrange(self.xdim+1):
				self.vwall[-1].append(True)

		self._visited = []
		for y in xrange(self.ydim):
			self._visited.append([])
			for x in xrange(self.xdim):
				self._visited[-1].append(False)

		# x,y offsets for going N,E,S,W
		self._posoffsets = [ [0,-1], [1,0], [0,1], [-1,0] ]

		self.generate()

	def _canDigTo(self, dir, nx, ny):
		val =  \
			nx >= 0 and \
			ny >= 0 and \
			nx <= self.xdim-1 and \
			ny <= self.ydim-1 and \
			not self._visited[ny][nx]

		return val

	def _dig_r(self, x, y):
		self._visited[y][x] = True
		
		a = [Maze.N, Maze.E, Maze.S, Maze.W]
		random.shuffle(a)

		for dir in a:
			nx = x + self._posoffsets[dir][0]
			ny = y + self._posoffsets[dir][1]
			if self._canDigTo(dir, nx, ny):
				if dir == Maze.N:
					self.hwall[y][x] = False
				elif dir == Maze.S:
					self.hwall[y+1][x] = False
				elif dir == Maze.W:
					self.vwall[y][x] = False
				elif dir == Maze.E:
					self.vwall[y][x+1] = False

				self._dig_r(nx, ny)

	def generate(self):
		self._dig_r(0, 0)

		# cut entrance and exit

		# left/right
		#self.vwall[0][0] = False
		#self.vwall[self.ydim-1][self.xdim] = False

		# top/bottom
		self.hwall[0][0] = False
		self.hwall[self.ydim][self.xdim-1] = False

	def writeText(self, filename):
		fp = openFileByName(filename)
		for y in xrange(self.ydim+1):
			for x in xrange(self.xdim):
				fp.write('+')
				if self.hwall[y][x]:
					fp.write('--')
				else:
					fp.write('  ')

			fp.write('+\n')
			if y < self.ydim:
				for x in xrange(self.xdim+1):
					if self.vwall[y][x]:
						fp.write('|')
					else:
						fp.write(' ')
					fp.write('  ')

				fp.write('\n')

	def writeSVG(self, filename, width, height, border, boxwidth, boxheight, units, style):
		fp = openFileByName(filename)
		width = width + border * 2
		height = height + border * 2
		fp.write('<?xml version="1.0" standalone="no"?>\n'
			'<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">\n'
			'\n'
			'<svg width="%s%s" height="%s%s" version="1.1" xmlns="http://www.w3.org/2000/svg">\n\n' % (width, units, height, units))

		for y in xrange(self.ydim+1):
			state = 0  # 0 not in line, 1 in line
			cy = y * boxheight
			for x in xrange(self.xdim):
				if state == 0:  # not in line
					if self.hwall[y][x]:
						state = 1
						x1 = x

				if state == 1: # in line
					if not self.hwall[y][x] or x == self.xdim-1:

						# check for weird last case to draw full line
						if x == self.xdim-1 and self.hwall[y][x]:
							finaloff = 1
						else:
							finaloff = 0

						state = 0
						x2 = x
						fp.write('<line x1="%s%s" y1="%s%s" x2="%s%s" y2="%s%s" style="%s"/>\n'
						% (x1 * boxwidth + border, units, cy + border, units,
							(x2+finaloff) * boxwidth + border, units,
							cy + border, units, style))

		for x in xrange(self.xdim+1):
			state = 0  # 0 not in line, 1 in line
			cx = x * boxwidth

			for y in xrange(self.ydim):

				if state == 0:  # not in line
					if self.vwall[y][x]:
						state = 1
						y1 = y

				if state == 1: # in line
					if not self.vwall[y][x] or y == self.ydim-1:

						# check for weird last case to draw full line
						if y == self.ydim-1 and self.vwall[y][x]:
							finaloff = 1
						else:
							finaloff = 0

						state = 0
						y2 = y
						fp.write('<line x1="%s%s" y1="%s%s" x2="%s%s" y2="%s%s" style="%s"/>\n'
						% (cx + border, units, y1 * boxheight + border, units,
							cx + border, units,
							(y2 + finaloff) * boxheight + border, units,
							style))


		fp.write('</svg>\n')

def openFileByName(name):
	if name == None or name == '-':
		return sys.stdout
	else:
		return file(name, 'w')

def main(argv):
	sys.setrecursionlimit(2000)

	ac = AppContext(argv)
	maze = Maze(ac.xdim, ac.ydim)
	if ac.outputtype == AppContext.OUTPUT_SVG:
		maze.writeSVG(ac.filename, ac.svgwidth, ac.svgheight, ac.svgborder,
			ac.svgboxwidth, ac.svgboxheight, ac.svgunits, ac.svglinestyle)
	else:
		maze.writeText(ac.filename)


if __name__ == "__main__": sys.exit(main(sys.argv))