#!/usr/bin/env python
# -*- coding: utf-8 -*-

import random


class Maze(object):

    def __init__(self, width=21, height=21, exit_cell=(1, 1)):
        self.width = width
        self.height = height
        self.exit_cell = exit_cell
        self.create()

    def create(self):
        self.maze = [[1] * self.width for _ in range(self.height)] 
        self.start_cell = None
        self.steps = None
        self.recursion_depth = None
        self._visited_cells = []
        self._visit_cell(self.exit_cell)

    def _visit_cell(self, cell, depth=0):
        x, y = cell
        self.maze[y][x] = 0 # Wand entfernen
        self._visited_cells.append(cell)
        neighbors = self._get_neighbors(cell)
        random.shuffle(neighbors)
        for neighbor in neighbors:
            if not neighbor in self._visited_cells:
                self._remove_wall(cell, neighbor)
                self._visit_cell(neighbor, depth+1)
        self._update_start_cell(cell, depth)

    def _get_neighbors(self, cell):
        """
        Die benachbarten Zellen nehmen.
        Beispiel:
          b sind die benachbarten Zellen von a 
          # # # # # # #     # # # # # # #
          # # # b # # #     # a # b # # #
          # # # # # # #     # # # # # # #
          # b # a # b #     # b # # # # #
          # # # # # # #     # # # # # # #
          # # # b # # #     # # # # # # #
          # # # # # # #     # # # # # # #
        """
        x, y = cell
        neighbors = []

        # Links
        if x - 2 > 0:
            neighbors.append((x-2, y))
        # Rechts
        if x + 2 < self.width:
            neighbors.append((x+2, y))
        # Hoch
        if y - 2 > 0:
            neighbors.append((x, y-2))
        # Runter
        if y + 2 < self.height:
            neighbors.append((x, y+2))

        return neighbors

    def _remove_wall(self, cell, neighbor):
        """
        Entfernen der Wand zwischen zwei Zellen
        Example:
          gegeben sind die Zellen a und b
          Die Wand dazwischen ist w
          # # # # #
          # # # # #
          # a w b #
          # # # # #
          # # # # #
        """
        x0, y0 = cell
        x1, y1 = neighbor
        # Vertikal
        if x0 == x1:
            x = x0
            y = (y0 + y1) / 2
        # Horizontal
        if y0 == y1:
            x = (x0 + x1) / 2
            y = y0
        self.maze[y][x] = 0 # Wand entfernen

    def _update_start_cell(self, cell, depth):
        if depth > self.recursion_depth:
            self.recursion_depth = depth
            self.start_cell = cell
            self.steps = depth * 2 # Wand + Zelle

    def show(self, verbose=False):
        MAP = {0: ' ', # Durchgang
               1: '#', # Wand
               2: 'B', # Ausgang
               3: 'A', # Start
              }
        x0, y0 = self.exit_cell
        self.maze[y0][x0] = 2
        x1, y1 = self.start_cell
        self.maze[y1][x1] = 3
        for row in self.maze:
            print ' '.join([MAP[col] for col in row])
        if verbose:
            print "Schritte von A nach B:", self.steps


if __name__ == '__main__':

    from optparse import OptionParser
    parser = OptionParser(description="Maze random generator")
    parser.add_option('-W', '--width', type=int, default=21,
                      help="maze width (muss ungerade sein)")
    parser.add_option('-H', '--height', type=int, default=21,
                      help="maze height (muss ungerade sein)")
    parser.add_option('-v', '--verbose', action='store_true',
                      help="zeigt Schritte von Start bis Ziel")
    args, _ = parser.parse_args()

    for arg in ('width', 'height'):
        if getattr(args, arg) % 2 == 0:
            setattr(args, arg, getattr(args, arg) + 1)
            print "Warnung: %s muss ungerade sein, benutze %d stattdessen" % (arg, getattr(args, arg))

    exit_cell = (args.width-2, args.height-2)
    maze = Maze(args.width, args.height, exit_cell)
    maze.show(args.verbose)