## the Maze Generator 2.00:
## this program shows the creation of unique 2D mazes
## November 2003
## aMAZING algorithms by Wolfgang.Urban@schule.at
## and Gregor Lingl (glingl@aon.at)
########################################################
## history: my little daughter likes to solve mazes,
## so I once wrote a routine to plot random mazes on my
## printer. Amazed by the power of Python and Tkinter
## I rewrote my old Oberon-code and beefed it up with
## a bit of GUI to be a demonstration tool showing
## some famous algorithms for creating labyrinths at work.  (W. U.)
##
## This is an alternate implementation to Wolfgang's original
## one (V.1.03) using Cell-Objects knowing their walls and their neigbours.
## However the algorithms as well as the structure of main parts of the program
## and also its capabilities are nearly exactly the same as in version 1.03
##
## A couple of Python features are used, e.g.:
## - inheritance for decoupling maze-algorithms from grapical display
##   Maze now contains the essential creation-algorithms and does no output.
##   It creates however some information concerning output in the cell attribute
##   display.
## - Graphical display and user interaction (break, quick) is added by
##   overwriting Maze.update().
## - raise and try-except is used for terminating running algorithms
## - docstrings for documenting and transferring information to the gui
## - moreover I've also visualized the search for the solution. Both, creation
##   and solution can be done quickly by selecting the quick - checkbox.
##
## As this is a tool for visually demonstrating algorithms, for me speed of
## execution was no issue. I've tried to achieve good readability of the code
## (with at least moderate success, I hope).
##                                                          (G. L.)
##############################################################
##
## If you happen to find bugs, errors, improvements,...
## please feel free to contact Wolfgang.Urban@schule.at or glingl@aon.at
##

## How to use:
## 1.) select desired algorithm using buttons on left side
## 2.) press 'Start' for animated creation
## 3.) Adjust animation-'Speed' as desired or select "quick"-checkbox
##     for a quick calculation without animation.
## 4.) Try 'Solve' to check the solution (animated or "quick")
##
## 5.) our program starts by calling MazeDemo(16,16,30)
##     i.e. (num_of_cells_horizontal, num_of_cells_vertical, cell_size).
##     Play around with these values!

## Have fun.   W.U. & G.L.

########################################################################

version = "[V 2.00]"

import random

########################################
## the cell with its walls and neighbors
########################################

class Cell:
    """Cell - objects are the building-blocks of the maze."""
    def __init__(self, (x,y), maze):
        """creates the cell's index, the cell's walls
        with their entries in the maze's walls-dictionary
        and a list of possible directions to go"""
        self.maze = maze
        self.index = (x,y)
        self.display = Maze.DOMAIN
        self.memo = 0
        self.closed = True
        self.walls = {}
        if y > 0:
            self.walls[maze.N] = (x,y,x+1,y)
        if x > 0:
            self.walls[maze.W] = (x,y,x,y+1)
        if y < maze.rows - 1:
            self.walls[maze.S] = (x,y+1,x+1,y+1)
        if x < maze.cols - 1:
            self.walls[maze.E] = (x+1,y,x+1,y+1)
        for w in self.walls.values():
            self.maze.walls[w] = Maze.CLOSED
        self.directions = self.walls.keys()

    def setNeighbors(self):
        """creates pointers to the neighbor-cells -
        only after all cells are created."""
        x,y = self.index
        self.neighbor = {}
        wl = self.directions
        if Maze.N in wl:
            self.neighbor[Maze.N] = self.maze.cells[(x,y-1)]
        if Maze.W in wl:
            self.neighbor[Maze.W] = self.maze.cells[(x-1,y)]
        if Maze.S in wl:
            self.neighbor[Maze.S] = self.maze.cells[(x,y+1)]
        if Maze.E in wl:
            self.neighbor[Maze.E] = self.maze.cells[(x+1,y)]
        self.neighbors = self.neighbor.values()

    def directionTo(self, neighbor):
        """returns N, W, S, E according to position of neighbor"""
        for dir, nei in self.neighbor.items():
            if nei == neighbor: return dir

    def carveinto(self, neighbor):
        """removes wall between self and neighbor"""
        self.opendoor(neighbor)
        return neighbor

    def opendoor(self,neighbor):
        """removes the wall between self and neighbor
        and update gui correspondingly - if applicable"""
        w = self.walls[self.directionTo(neighbor)]
        self.maze.walls[w] = Maze.OPEN
        neighbor.closed = False
        self.maze.update(w)

    def ispassage(self,neighbor):
        """returns True if wall between self and neighbor is open."""
        wall = self.walls[self.directionTo(neighbor)]
        return self.maze.walls[wall] == Maze.OPEN

    def mark(self, value=None,delay=0):
        """sets the cell's display-attribute to value
        and - if coupled to an appropriate gui - waits
        delay ms."""
        if value != None:
            self.display = value
        self.maze.update(self, delay)

###############################
## the maze with its algorithms
###############################

class Maze:
    """Composes a maze out of cells and defines a couple
    of creation-algorithms as well as a solving algorithm
    which finds a way through the maze."""
    N, W, S, E = directions = range(4)
    DOMAIN, TESTED, APPENDED, ACCEPTED, REJECTED = range(5)
    OPEN, CLOSED = 0, 1
    LONG, MEDIUM, SHORT, VERYSHORT = 1, 2, 3, 4

    def __init__(self,cols,rows):
        """creates cols*rows cells along with their walls and neigbors.
        Then defines dictionaries containing the maze's algorithms."""
        self.cols = cols
        self.rows = rows
        self.numcells = rows*cols

        self.cells = {}
        self.walls = {}
        for x in range(cols):
            for y in range(rows):
                self.cells[(x,y)] = Cell((x,y),self)
        self.startcell = self.cells[(0,0)]
        self.goal  = self.cells[(cols-1,rows-1)]
        for cell in self.cells:
                self.cells[cell].setNeighbors()
        ### discard the dictionary for the cells:
        self.cells = self.cells.values()

        self.algorithms =    { 1:self.create_DFS,   2:self.create_Prim,   3:self.create_Kruskal,
                               4:self.create_Aldus, 5:self.create_Wilson, 6:self.create_Tree     }
        self.treeSelectors = { 1:self.random1, 2:self.random2, 3:self.random2a, 4:self.random2b,
                               5:self.random3, 6:self.random4, 7:self.random5,  8:self.random6   }

    ## start the selected algorithm
    def start(self):
        """starts the selected algorithm."""
        self.reset()
        code, selector = divmod(self.create_select, 10)
        if selector == 0:
            self.algorithms[code]()
        else:
            self.algorithms[code](selector)

    def update(self, element=None, delay = 10):
        """ must be overridden by a method (of some "GraphicMaze"),
        which updates the display. elemen can be a Cell or
        the index of some wall to be updated. if element is None,
        an update of the whole display should be done."""
        pass

    def markall(self, value, delay=0):
        """updates all cells of the maze with value"""
        for cell in self.cells:
            cell.display = value
        self.update(delay = delay)

    def setcreate(self,code):
        """stores the code of the algorithm to be executed"""
        self.create_select = code

    def reset(self):
        """resets the maze in order to create a new maze"""
        for cell in self.cells:
            cell.display = Maze.DOMAIN
            cell.memo = 0
            cell.closed = True
        for w in self.walls:
            self.walls[w] = Maze.CLOSED
        self.update()

    def randomcell(self):
        """returns a randomly chosen cell of the maze"""
        cell = random.choice(self.cells)
        cell.closed = False
        return cell

    def solve(self):
        """finds (and marks) a path from upper left corner
        to lower right corner (by backtracking)"""
        class Success(Exception):
            """to be raised if goal-cell is found"""
            pass
        def search(cell):
            """recursive search-method starting from cell"""
            if cell == self.goal:
                raise Success
            candidates = [neighbor for neighbor in cell.neighbors
                              if cell.ispassage(neighbor)]
            for cell in candidates:
                if cell.display == Maze.ACCEPTED:
                    cell.mark(Maze.TESTED, Maze.MEDIUM)
                    search(cell)
                    cell.mark(Maze.REJECTED, Maze.SHORT)
        self.startcell.mark(Maze.TESTED, Maze.MEDIUM)
        try:
            search(self.startcell)
        except Success:
            pass

######################################################################
## Maze by DepthFirstSearch
######################################################################

    def create_DFS(self):
        """Depth First Search (Recursive Backtracker):
Start with a random cell.
If an unvisited neighbor exists, push cell to stack, carve
into neighbor. Repeat this as often as possible.
If you get stuck (no unvisited neighbors), pop the last
coordinate from the stack, backtrack and try carving again.
End with empty stack.
"""
        ## random starting point
        cell = self.randomcell()
        ## stack for backtracking cells
        stack = [cell]
        while stack:
            ## find all unvisited cells around this one
            candidates = [neighbor for neighbor in cell.neighbors
                              if neighbor.closed]

            if candidates:
                ## push cell and carve into one of the above
                stack.append(cell)
                cell.mark(Maze.TESTED, Maze.MEDIUM)
                cell = cell.carveinto(random.choice(candidates))
            #    cell.mark(Maze.ACCEPTED)
            else:
                ## go back to last used cell
                cell = stack.pop()
            cell.mark(Maze.ACCEPTED, Maze.MEDIUM)

######################################################################
## Maze by Prim's - Algorithm
######################################################################

    def create_Prim(self):
        """Prim's Algorithm:
Set all cells to OUTSIDE (red). Move start cell to
INSIDE (orange) and all its neighbors to FRONTIER (blue).
Now take FRONTIER cells, move them to INSIDE and all its
unvisited neighbors to FRONTIER.
End when run out of frontier cells.

"""
        OUTSIDE, INSIDE, FRONTIER = 1,2,3
        frontier = []

        for cell in self.cells:
            cell.display = Maze.DOMAIN
            cell.memo = OUTSIDE
        self.update()

        # random starting cell
        cell = self.randomcell()
        cell.memo = INSIDE
        cell.mark(Maze.TESTED)

        # all its neighbors to frontier
        for c in cell.neighbors:
            c.memo = FRONTIER
            frontier.append(c)
            c.mark(Maze.APPENDED, Maze.MEDIUM)

        while frontier:
            # put random cell from frontier to inside
            cell = random.choice(frontier)
            frontier.remove(cell)
            cell.memo = INSIDE
            cell.mark(Maze.TESTED, Maze.MEDIUM)

            # all its neighbors from out to frontier
            for c in cell.neighbors:
                if c.memo == OUTSIDE:
                    c.memo = FRONTIER
                    frontier.append(c)
                    c.mark(Maze.APPENDED, Maze.SHORT)

            # find all neighbors of cell belonging to inside
            candidates = [neighbor for neighbor in cell.neighbors
                              if neighbor.memo == INSIDE]
            # choose one at random
            cell.opendoor(random.choice(candidates))

        for i in range(4): self.update(delay = Maze.LONG)
        self.markall(Maze.ACCEPTED, Maze.LONG)


######################################################################
## Maze by Kruskal - Algorithm
## (we use a fast merging technique here)
######################################################################

    def create_Kruskal(self):
        """Kruskal's Algorithm:
Assign a unique number to each cell.
Make a list of all walls.
Keep selecting walls and check the two cells touching it.
If they have different numbers, they are not yet connected.
Open the wall and assign both regions to the same number.
End with all walls inspected.
"""
        ## recursive find
        def find(n):
            if self.uf[n]<0 : return n
            else:
                self.uf[n] = find(self.uf[n])
                return self.uf[n]

        ## union-by-size
        def union(r1,r2):
            if self.uf[r1]<=self.uf[r2]:
                self.uf[r1] += self.uf[r2]
                self.uf[r2] = r1
            else:
                self.uf[r2] += self.uf[r1]
                self.uf[r1] = r2


        ## all cells in different equiv.classes (their own)
        self.uf = [-1]*(self.cols*self.rows)

        ## make list of all walls, N and W are sufficient
        pairs = []
        for cell in self.cells:
            for dir in self.N, self.W:
                if dir in cell.directions:
                     pairs.append((cell,cell.neighbor[dir]))

        visited = 1
        root1 = 0
        root2 = 0

        ## we need randomly selected pairs,
        ## if we shuffle now, we can just pop() later
        random.shuffle(pairs)

        while visited < self.numcells:
            ## fetch random (cell and) wall
            (cell1,cell2) = pairs.pop()

            cell1.mark(Maze.TESTED, Maze.MEDIUM)
            cell2.mark(Maze.APPENDED, Maze.MEDIUM)

            ## find roots of these cells
            x1, y1 = cell1.index
            x2, y2 = cell2.index
            root1 = find(x1+y1*self.cols)
            root2 = find(x2+y2*self.cols)

            ## are roots in different classes?
            if root1 != root2:
                ## if not, connect the two trees
                union(root1,root2)
                visited += 1
                cell1.opendoor(cell2)

            cell1.mark(Maze.ACCEPTED)
            cell2.mark(Maze.ACCEPTED)


######################################################################
## Maze by Aldus-Broder - Algorithm
## red: success, orange: already carved in
######################################################################

    def create_Aldus(self):
        """Aldus-Broder Algorithm:

Start anywhere and keep doing a random walk in the grid.
Whenever you meet an unvisited cell, carve into it.
End with no cell uncarved.

"""
        ## random starting point
        cell = self.randomcell()
        visited = 1

        while visited < self.numcells:
            ## step in random direction
            newcell = random.choice(cell.neighbors)

            ## make unvisited cell member of maze
            if newcell.closed:
                newcell.mark(Maze.TESTED, Maze.MEDIUM)
                cell.opendoor(newcell)
                visited += 1
            else:
                newcell.mark(Maze.APPENDED, Maze.MEDIUM)
            cell.mark(Maze.ACCEPTED, Maze.SHORT)
            cell = newcell

        newcell.mark(Maze.ACCEPTED)

######################################################################
## Maze by Wilson - Algorithm
######################################################################

    def create_Wilson(self):
        """Wilson's Algorithm:
Start with a single cell in the maze.
Take any unvisited cell and do a random walk, until you
meet a cell already belonging to the maze. Now carve into
all cells of that walk, eliminating loops. Repeat walking.
End with no cell uncarved.

"""
        # all cells outside
        unvisited = []
        INSIDE = -1
        for cell in self.cells:
            unvisited.append(cell)
            cell.display = Maze.DOMAIN
            cell.memo = -2

        self.update()

        ## random point starts maze, put it INSIDE
        cell = self.randomcell()
        unvisited.remove(cell)
        visited = 1
        cell.memo = INSIDE
        cell.mark(Maze.ACCEPTED)

        while visited < self.numcells:
            ## random unvisited cell as starting point for random walk
            cell = random.choice(unvisited)
            unvisited.remove(cell)
            startcell = cell

            ## now do a random walk until we meet a maze cell
            colcells = []
            while cell.memo != INSIDE:
                ## random direction
                cell.mark(Maze.TESTED, Maze.LONG)
                if colcells and cell!=startcell:
                    cell.mark(Maze.APPENDED, Maze.MEDIUM)
                colcells.append(cell)
                direction = random.choice(cell.directions)
                cell.memo = direction
                cell = cell.neighbor[direction]


            ## now redo the walk
            cell = startcell
            colcells2 = []
            while cell.memo != INSIDE:
                colcells2.append(cell)
                cell.mark(Maze.TESTED, Maze.MEDIUM)

                neighbor = cell.neighbor[cell.memo]
                cell.memo = INSIDE
                cell = cell.carveinto(neighbor)
                visited += 1

            for c in colcells:
                 if c not in colcells2:
                    c.display = Maze.DOMAIN
                    if len(colcells) < 5: self.update(c)
            if len(colcells) >=5: self.update()

            colcells = []

            for c in colcells2:
                c.mark(Maze.ACCEPTED)
            colcells2 = []


######################################################################
## Maze by GrowTree-Methode
## red: cell on stack, orange flash: just worked at
######################################################################

    def random1(self,list):
        "SELECTOR: take last (youngest) element of stack (LIFO)"
        return list[-1]

    def random2(self,list):
        "SELECTOR: take first (oldest) element of stack (FIFO queue)"
        return list[0]

    def random2a(self,list):
        "SELECTOR: take first element, but 20% random"
        if random.randrange(5)<1:
            return random.choice(list)
        else: return list[0]

    def random2b(self,list):
        "SELECTOR: first or last element at random"
        return list[-random.randrange(2)]

    def random3(self,list):
        "SELECTOR: take random element"
        return random.choice(list)

    def random4(self,list):
        "SELECTOR: random from last 25%"
        return random.choice(list[3*len(list)//4:])

    def random5(self,list):
        "SELECTOR: random from first 25%"
        return random.choice(list[:1+len(list)//4])

    def random6(self,list):
        "SELECTOR: take last element, but 10% random"
        if random.randrange(10)<1: return list[-1]
        else: return random.choice(list)

    def create_Tree(self,selectnr):
        """Growing Tree Algorithm:
Each time you carve into a cell, push it on a stack.
Repeat fetching a cell from the stack using a SELECTOR and
carve into it. If a cell has no unvisited neighbors, remove
it from the stack. End with empty stack.

"""
        selector = self.treeSelectors[selectnr]

        ## random starting point
        cell = self.randomcell()
        visited = 1
        ## stack for cells being processed
        stack = [cell]

        while stack:
            ## get a cell from the stack
            cell = selector(stack)
            cell.mark(Maze.TESTED, Maze.SHORT)
            ## find all unvisited cells around this one
            candidates = [neighbor for neighbor in cell.neighbors
                              if neighbor.closed]
            if candidates:
                ## carve into new cell and push it to stack
                neighbor = random.choice(candidates)
                cell = cell.carveinto(neighbor)
                visited += 1
                stack.append(cell)
                cell.mark(Maze.APPENDED, Maze.LONG)
                cell.mark(Maze.TESTED)
            else:
                ## no unvisited neighbors - cell is finished
                stack.remove(cell)
                cell.mark(Maze.ACCEPTED)
        self.update(delay = Maze.SHORT)

######################################################################
## !!! GMaze connects Maze to canvas - output !!!
######################################################################

class GMaze(Maze):
    """subclass of Maze, which contains a canvas-attribute with
    a graphical maze structure do display the running algorithms of Maze"""
    def setcanvas(self, mazeCanvas):
        self.mcv = mazeCanvas
    def update(self,element=None, delay = 0):
        self.mcv.updateMaze(element, delay)

class Termination(Exception):
    """exception to be raised when running algorithm is stopped by the user."""
    pass

######################################################################
## !!! Graphics !!!
######################################################################

from Tkinter import *

########################################################################
#### Canvas
########################################################################
class MazeCanvas(Canvas):
    """subclass of Tkinter-Canvas capable of displaying a graphical
    representation of the actual state of a maze."""

    cellcolor = ["darkblue", "red", "orange", "black", "gray40"]
    wallcolor = ["","green"]

    def __init__(self,parent,numx,numy,cellsize, maze):
        """defines graphical elements (rectangles, circles) to reperesent
        the state of the maze's cells including their walls"""
        self.showgraphics = True
        Canvas.__init__(self)
        self.SIZE = cellsize
        self.OFFS = 5
        self.m = maze
        self.SC = self.SIZE*3/4
        self.numx, self.numy = numx, numy
        self.termination = False

        # Delay Values
        self.D0 = [80,40,20,10]
        self.DELAY = self.D0[:]

        self.configure(width=self.SIZE*numx+6,height=self.SIZE*numy+6,
                         background="#000000")
        self.grid(row=1,column=1,padx=3,pady=3)
        self.create_rectangle(3,3,self.SIZE*numx+6,self.SIZE*numy+6,
                              outline = "green", width=3)

        self.cwall = {}
        for w in maze.walls:
            self.cwall[w] = self.create_line(
                map(lambda x: 5+self.SIZE*x, w), width=3, fill="green")

        self.cfield = {}
        for cell in maze.cells:
            f = cell.index
            self.cfield[f] = self.create_oval(
                map(lambda x: self.OFFS+(x+0.2)*self.SIZE, f),
                map(lambda x: self.OFFS+(x+0.8)*self.SIZE, f),
                outline = "black", fill = "" )
        self.update()

    def updateMaze(self, el=None, delay = 0, override = False):
        """updates the graphical representation of the maze.
        updateMaze is called by update of GMaze (which overrides update of Maze).
        if el is given (cell or wall), this is updated, otherwise the whole maze
        is updated."""
        if self.termination:
            raise Termination
        if not self.showgraphics:
            if not override: return
        ### try - except clause in order to catch possible Tcl-Errors (when user
        ### exits maze)
        try:
            if isinstance(el,Cell):        ### cell given
                el, s = el.index, el.display
                self.itemconfigure(self.cfield[el],fill=self.cellcolor[s])
            elif isinstance(el, tuple):    ### wall given
                c = self.m.walls[el]
                self.itemconfigure(self.cwall[el],fill=self.wallcolor[c])
            else:                          ### update whole maze
                for cell in self.m.cells:
                    f, s = cell.index, cell.display
                    self.itemconfigure(self.cfield[f],fill=self.cellcolor[s])
                for w in self.m.walls:
                    c = self.m.walls[w]
                    self.itemconfigure(self.cwall[w],fill=self.wallcolor[c])
            if 1<=delay<=4:
                self.after(self.DELAY[delay-1])
                self.update()
        except: pass

    def setspeed(self,value):
        """calculates four speed-values (LONG...VERYSHORT) according to
        the actual value of the speed - Scale of the GUI"""
        if value==0: factor=1
        elif value>0:
            factor=1.0/(1.50*value)
            if value >5: factor = factor/2.0
            if value==10: factor=0.000001
        else: factor = 1.25*abs(value)
        for x in range(len(self.D0)):
            self.DELAY[x]=int(self.D0[x]*factor)


######################################################################
## Creation-Frame
######################################################################
class CreationFrame(Frame):
    """Frame containing radio buttons to select maze creating algorithm."""
    def job(self):
        """performs selection of algorithm and associated description"""
        self.showdescription(self.select.get())
        self.maze.setcreate(self.select.get())


    def __init__(self,parent,maze,gui,**options):
        """creates radio buttons and associates them with codes determining
        the algorithms implemented in Maze"""
        Frame.__init__(self,parent,**options)
        self.maze = maze

        self.select = IntVar()
        self.select.set(10)
        self.descriptvar = gui.description
        self.job()

        for text,value in [("DFS",10), ("Prim",20), ("Kruskal",30), ("Aldus",40), ("Wilson",50),
                           ("Tree-1",61), ("Tree-2",62), ("Tree-2a",63),
                           ("Tree-2b",64), ("Tree-3",65), ("Tree-4",66), ("Tree-5",67),
                           ("Tree-6",68)
                          ]:
            Radiobutton(self,text=text,font=("Arial",10),variable=self.select,
                        value=value, indicatoron=0,selectcolor="#608060",
                        command=self.job).pack(side=TOP,fill=X,padx=7)

    ## show description text
    def showdescription(self,code):
        """extracts the description of the algorithm difined by code from the
        doc-strings of the corresponding method(s) - there are two of them, when a
        tree algorithm is selected. then displays it on the gui."""
        code,select = divmod(code,10)
        s = self.maze.algorithms[code].__doc__
        if select > 0:
            s += self.maze.treeSelectors[select].__doc__
            s+="\n"
        self.descriptvar.set(s)

######################################################################
## Command-Frame
######################################################################
class CommandFrame(Frame):
    """defines a frame with four buttons for maze-actions. sort of "finite state machine"
    with the states: "START", "RUNNING", "LABYRINTH", "SOLVING", "SOLVED" """

    def __init__(self,parent,maze,canvas,**options):
        Frame.__init__(self,parent,**options)
        self.maze = maze
        self.canvas = canvas
        self.quick = IntVar()
        self.quick.set(0)
        self.SOLVED = 0

        self.knoepfe = {
            "START"   : Button(self,text="Start"  ,font=("Arial",14),command=self.start),
            "STOP"    : Button(self,text="Stop"   ,font=("Arial",14),command=self.stop),
            "SOLVE"   : Button(self,text="Solve"  ,font=("Arial",14),command=self.solve),
            "UNSOLVE" : Button(self,text="Unsolve",font=("Arial",14),command=self.unsolve) }
        for btn in ["START","STOP"]:    self.knoepfe[btn].pack(side=TOP,fill=X,padx=2,pady=2)
        Label(self,text="",font=("Arial",10)).pack(side=TOP,pady=0)
        for btn in ["SOLVE","UNSOLVE"]: self.knoepfe[btn].pack(side=TOP,fill=X,padx=2,pady=2)

        Label(self,text="",font=("Arial",10)).pack(side=TOP,pady=0)
        self.chkbtn = Checkbutton(self,font=("Arial",12,"bold"), text = "quick",
                variable = self.quick, command = self.setquick).pack(side=TOP,fill=X)
        Label(self,text="",font=("Arial",10)).pack(side=TOP,pady=0)

        self.spl = Label(self,text="Speed:",font=("Arial",12,"bold"))
        self.spl.pack(side=TOP,anchor=CENTER,pady=3)

        self.tempo = Scale(self,orient=VERTICAL, from_=10, to_=-10,
                length=80,showvalue=0,repeatinterval=10, command=self.speedset)
        self.tempo.pack(side=TOP,padx=0,pady=4)

        self.enableButtons("START")
        self.state = "START"

    def enableButtons(self, *knoepfe):
        """arguments ar button-names. enables it's arguments, disables the rest"""
        ### try - except clause in order to catch possible Tcl-Errors (when user
        ### exits maze)
        try:
            for name in self.knoepfe:
                if name in knoepfe:
                    self.knoepfe[name].configure(state="normal")
                else:
                    self.knoepfe[name].configure(state="disabled")
        except: pass

    def start(self):
        """"action of start - button"""
        self.canvas.termination = False
        self.state = "RUNNING"
        self.enableButtons("STOP")
        try:
            self.maze.start()
        except Termination:
            pass
        if self.state == "RUNNING":
            self.canvas.updateMaze(override = True) ### if quick is selected
            self.state = "LABYRINTH"
            self.enableButtons("START", "SOLVE")

    def stop(self):
        """action of stop - button"""
        if self.state == "RUNNING":
            self.enableButtons("START")
            self.state = "START"
        elif self.state == "SOLVING":
            self.state = "LABYRINTH"
            self.enableButtons("START", "SOLVE", "UNSOLVE")
        self.canvas.termination = True

    def solve(self):
        """action of solve - button"""
        self.canvas.termination = False
        if self.state == "LABYRINTH":
            self.hidesolution()
            self.state = "SOLVING"
            self.enableButtons("STOP")
            try:
                self.maze.solve()
            except Termination:
                pass
            if self.state == "SOLVING":
                self.canvas.updateMaze(override = True) ### if quick is selected
                self.state = "SOLVED"
                self.enableButtons("START","UNSOLVE")

    def unsolve(self):
        """action of unsolve - button"""
        self.canvas.termination = False
        self.state = "LABYRINTH"
        self.hidesolution()
        self.enableButtons("START", "SOLVE")

    def speedset(self,event):
        """action of change of speed - Scale"""
        self.canvas.setspeed(self.tempo.get())

    def hidesolution(self):
        """removes solution-search-markers from maze and gui"""
        for cell in self.maze.cells:
            cell.display = Maze.ACCEPTED
        self.canvas.updateMaze(override=True)

    def setquick(self):
        """inhibits action of updateMaze(). so no graphical output
        is done during calculations. Can be selected also during
        calculations"""
        q = self.quick.get()
        self.canvas.showgraphics = not q
        ### if quick: speed-label is "grayed"
        if q: self.spl.configure(fg="gray70")
        else: self.spl.configure(fg="black")

class MazeDemo:
    """composes the maze creating application"""
    def quit(self):
        self.root.destroy()

    def __init__(self,nx,ny,cellsize):
        self.root = Tk()
        self.root.title("a-MAZE-ing PYTHON tool by Wolfgang.Urban@schule.at" +
                        " / Gregor Lingl (glingl@aon.at) (c)2003 " + version)
        self.m = GMaze(nx,ny)

        Label(self.root,text="L A B Y R I N T H",font=("Arial",24)). \
        grid(row=0,column=0,columnspan=3,pady=6)

        self.description = StringVar()
        self.textlabel = Label(self.root,textvariable=self.description,font=("Courier",8),
                                  justify=LEFT)
        self.textlabel.grid(row=2,column=0,columnspan=2)

        canvas = MazeCanvas(self.root,nx,ny,cellsize,self.m)
        # now we associate the GMaze m with the canvas:
        self.m.setcanvas(canvas)

        frame_cr = CreationFrame(self.root,self.m,self,relief=FLAT, borderwidth=2)
        frame_cr.grid(row=1,column=0,padx=3,pady=3,sticky=N)

        frame_co = CommandFrame(self.root,self.m,canvas,relief=RIDGE, borderwidth=2)
        frame_co.grid(row=1,column=2,padx=3,pady=3,sticky=N)

        self.killer = Button(self.root,text="Quit",font=("Arial",11),
                             command=self.quit,padx=4,pady=20)
        self.killer.grid(row=2,column=2)

def start():
    MazeDemo(16,16,30)
    mainloop()

start()