#!BPY
# coding: utf-8
"""
Name: 'Maze'
Blender: 249a
Group: 'Add'
Tooltip: 'A maze generator'
"""

__author__ = 'Julian Habrock'
__version__ = '0.7 12/2009'
__email__ = ["jug:fantasymail*de"]
__bpydoc__ = """\
     
     Maze Generator Script<br>
<br>
Generate perfect maze meshes with individual sizes. <br>
Perfect mazes are those with exactly one way between any two points.

"""

import Blender
from Blender import NMesh, Mesh
from Blender.BGL import *
from Blender.Draw import *

import math
from math import *

default = ""
selected = Blender.Object.GetSelected()
if selected:
    for obj in selected:
        if type(obj.data) in (Blender.Types.MeshType, Blender.Types.NMeshType):
            default = obj.data.name
            break
            
T_Object = Create(default)
T_Realtime = Create(True)
# Polygon Parameters
# width/height of the maze (2d)
T_CellRows = Create(5)
T_CellCols = Create(5)


# height [px] of the walls
T_Height = Create(0.7)
# width of cells
T_CellWidth = Create(0.5)
# width of walls, must be smaller than CellWidth
T_WallThickness = Create(50.0)


# Events
EVENT_NOEVENT = 1
EVENT_DRAW    = 2
EVENT_EXIT    = 3
EVENT_USE_SELECTED = 4
EVENT_REALTIME = 5
EVENT_HELP = 6
######################################################
# Draw GUI
######################################################


def draw():
    global T_CellRows, T_CellCols, T_WallThickness, T_CellWidth, T_Height
    global T_Object, T_Realtime
    global EVENT_NOEVENT, EVENT_DRAW, EVENT_EXIT

    ########## Title
    glClear(GL_COLOR_BUFFER_BIT)
    title = 'Maze Generator'
    x = 300
    str_w = GetStringWidth(title)
    glRasterPos2d((220-str_w)/2, x)
    Text(title)
    
    ######### Object Selector 
    x -= 30
    
    T_Object = String("OB:", EVENT_NOEVENT, 10, x, 140, 18, 
                      T_Object.val, 20, "Name of a mesh data object")
    Button('auto',EVENT_USE_SELECTED, 160, x, 60, 18, 
           "Get name from selected Object")
    
    x -= 30
    T_Realtime = Toggle("Apply changes instantly", EVENT_REALTIME, 35,x,150,18,
                       T_Realtime.val,
                       "Regenerate maze whenever an option was changed")

    # alternative to select a mesh object?!

#    name = "OB: %t"
#    objects = Blender.Object.Get()
#    i = 1
#    for obj in objects:
#        if "Maze" in obj.getData(name_only=True):
#            name += ("|%s %%x%i" % (obj.name, i))
#    name += "|%l|create new"
#    T_Object = Menu(name, EVENT_NOEVENT, 10, x, 100, 18, T_Object.val, 
#                    "what object do you want to change?")

    ######### Options
    x -= 30
    glRasterPos2d(10, x)
    Text("Parameters:")
    
    x-= 35
    T_CellRows = Number('Rows: ', EVENT_NOEVENT, 10, x, 210, 18,
                    T_CellRows.val, 2, 1000, 'Number of cell rows')
    x -= 25
    T_CellCols = Number('Columns: ', EVENT_NOEVENT, 10, x, 210, 18,
                    T_CellCols.val, 2, 1000, 'Number of cell columns')
                    
    ####
    x -= 25
    T_Height = Number('Height: ', EVENT_NOEVENT, 10, x, 210, 18,
                    T_Height.val, 0, 100, 'Height of the walls')
    
    x -= 25
    T_CellWidth = Number('Cell Width: ', EVENT_NOEVENT, 10, x, 210, 18,
                    T_CellWidth.val, 0, 100, 'Size of one cell')
                    
    ####
    x -= 35
    T_WallThickness = Slider('Wall Size: ', EVENT_NOEVENT, 10, x, 210, 18,
                    T_WallThickness.val, 0, 100, 1, 'Amount of wall per cell');
                    

    ######### Action Buttons
#    Button('Generate',EVENT_DRAW , 10, 10, 60, 18)
#    Button('Help',EVENT_HELP , 85, 10, 60, 18)
#    Button('Exit',EVENT_EXIT , 160, 10, 60, 18)
    Button('Generate',EVENT_DRAW , 30, 10, 80, 18)
    Button('Exit',EVENT_EXIT , 120, 10, 80, 18)

def event(evt, val):
    """
    handle key events
    """    
    if (evt == QKEY and not val) or evt == Blender.Draw.ESCKEY:
            Exit()

def bevent(evt):
    """
    handle custom events
    """
    global T_Object
    global EVENT_NOEVENT, EVENT_DRAW, EVENT_EXIT

    if (evt == EVENT_EXIT):
            Exit()
    elif (evt== EVENT_DRAW) or (T_Realtime.val and evt== EVENT_NOEVENT):
            make_maze(T_CellCols.val, T_CellRows.val, T_CellWidth.val, 
                      T_Height.val, 
                      T_WallThickness.val*T_CellWidth.val/100., T_Object.val)
#! This does not work. But why?
#    elif (evt == EVENT_HELP):
#        Blender.ShowHelp("maze.py")
    elif (evt == EVENT_USE_SELECTED):
        selected = Blender.Object.GetSelected()
        if selected:
            for obj in selected:
                if type(obj.data) in (Blender.Types.MeshType,
                                      Blender.Types.NMeshType):
                    T_Object.val = obj.data.name
                    Blender.Redraw()
                    break

Register(draw, event, bevent)

######################################################
# Maze Logic
######################################################

import random

class Cell(object):
    """
    One cell in a maze
    """
    def __init__(self, maze, i):
        """
        :type maze: :class:`Maze`
        :param maze: reference to the Maze object
        :type i: int
        :param i: cell index in maze
        """
        #: reference to the maze
        self.maze = maze
        #: index in maze
        self.index = i
        #: used for backtracing
        self.visited = False
        #: col and row of the cell
        self.position = i % maze.width, i / maze.width
        
    def get_neighbours(self):
        """
        :rtype: list
        :return: Top, right, bottom and left neighbour cells or None. 
                 Eg. for the cell at (0,0) it will return 
                 ``[None, <cell>, <cell>, None]``\ .
        """
        n = []
        for i in (self.index-self.maze.width, self.index+1,
                  self.index+self.maze.width, self.index-1):
            # need to validate positions in case of a edge cell that has not
            # neighbours at all 4 possible positions
            if 0<=i<len(self.maze):
                c = self.maze.cells[i]
                cx, cy = c.position
                if cx == self.position[0] or cy == self.position[1]:
                    n.append(c)
                    continue
            n.append(None)
#        if n[1] and n[1].position[0] == 0:
#            n[1] = None
        return n
    
    def get_free_neighbour(self, ignore_walls=True):
        """
        :type ignore_walls: boolean
        :param ignore_walls: If True only the ``visited`` flag will be used
                             to consider a cell as free.
        :rtype: :class:`Cell` or None
        :return: Any random free neighbour Cell or None, if there are no free
                 Cells left.
        """
        l = []
        for c in self.get_neighbours():
            if (c and not c.visited and 
               (ignore_walls or not self.maze.walls[tuple(sorted((self, c)))])):
                l.append(c)
        return l and random.choice(l) or None
    
    def __cmp__(self, other):
        """
        :type other: :class:`Cell`
        :rtype: boolean
        When comparing Cells compare their indices.
        """
        return self.index - other.index
    
    def __repr__(self):
        """
        :rytpe: String
        :return: String representation with some information about the Cell 
        (for debugging).
        """
        return "<cell obj at index %i; (%i|%i)>" % ((self.index,)+self.position)
                
    
class Maze(object):
    """
    A perfect Maze that generates and solves itself.
    """
    def __init__(self, width, height):
        """
        Create the basic structure and attributes. This does not yet generate
        an actual maze.
        """
        self.width, self.height =  width, height
        #: list of Cell objects from topleft to downright
        self.cells = [Cell(self, i) for i in xrange(self.width * self.height)]
        #: dict of *walls* with ordered cell pairs as keys and booleans (that
        #: indicate if there is a wall) as values
        self.walls = {}
        # create all possible walls
        for cell in self.cells:
            right, bottom = cell.get_neighbours()[1:3]
            if right:
                self.walls[(cell, right)] = True
            if bottom:
                self.walls[(cell, bottom)] = True
        print "generated %i cells and %i walls" % (len(self.cells), len(self.walls))
                
    def reset_walls(self):
        """
        recreate all possible walls
        """
        for k in self.walls:
            self.walls[k] = True
    def reset_cells(self):
        """
        reset all Cells to *not visited*
        """
        for cell in self.cells:
            cell.visited = False
                
    def generate(self):
        """
        generate the maze
        """
        i = 0
        stack = [self.cells[random.randint(0,len(self.cells)-1)]]
        while stack:
            cell = stack[-1]
            cell.visited = True
            nc = cell.get_free_neighbour()
            if nc:
                stack.append(nc)
                self.walls[tuple(sorted((cell, nc)))] = False
            else:
                stack.pop()
            i += 1
        print "generated in %i steps" % i
        # count walls
        walls, gaps = 0,0
        for v in self.walls.itervalues():
            if v:
                walls += 1
            else:
                gaps += 1
        self.reset_cells()
        print "%i connections: %i walls and %i gaps" % (walls+gaps, walls, gaps)
        
        
    def search_way(self, start, end):
        """
        :type start: :class:`Cell`
        :param start: Cell to start the search at.
        :type end: :class:`Cell`
        :param end: Cell to search for.
        :rtype: list
        :return: Cells on the calculated path.
        
        Find a way from one cell to another.
        """
        stack = [start]
        while stack:
            cell = stack[-1]
            cell.visited = True
            if cell == end:
                break
            nc = cell.get_free_neighbour(ignore_walls=False)
            if nc:
                stack.append(nc)
            else:
                stack.pop()
        if not stack:
            print "No way"
        else:
            print "Found way: %i steps" % len(stack)
        self.reset_cells()
        return stack
                
                
        
    def __len__(self):
        """
        :rtype: int
        :return: number of cells
        """
        self.width * self.height
        assert self.width * self.height == len(self.cells)
        return self.width * self.height



######################################################
# Create Mesh from Maze Data
######################################################

def make_maze(w, h, cell_width, wall_height, wall_thickness, name):
    # x/y: col/row
    # add: absolute pixel amount to add
    fx = lambda x, add: x*cell_width+add -(w*cell_width/2.)
    fy = lambda y, add: y*cell_width+add -(h*cell_width/2.)
    #fy = lambda y, add: ((h/2.)-y) * cell_width 
    maze = Maze(w, h)
    maze.generate()
    
    poly = NMesh.GetRaw()
    # x, y, anchor -> vert
    verts = {}
    # vert -> vert
    u_verts = {}
    
    for x in xrange(w+1):
        for y in xrange(h+1):
            i = 1
            f = NMesh.Face()
            poly.faces.append(f)
            for x_add, y_add in ((1,-1), (1, 1), (-1, 1), (-1, -1)):
                v = NMesh.Vert(fx(x, x_add * wall_thickness/2.),
                               fy(y, y_add * wall_thickness/2.), 0)
                poly.verts.append(v)
                verts[x, y, i] = v
                v2 = NMesh.Vert(v.co[0], v.co[1], v.co[2] + wall_height)
                poly.verts.append(v2)
                u_verts[v] = v2
                f.append(v2)
                i += 1

                
    # border faces
    faces = []
    
    for x in xrange(w):
        for i in (0, h):
            v1, v2 = verts[x,i, 2], verts[x+1, i, 3]
            v3, v4 = verts[x,i, 1], verts[x+1, i, 4]
            faces += [(v1, v2, u_verts[v2], u_verts[v1]),
                     (u_verts[v1], u_verts[v2], u_verts[v4], u_verts[v3]),
                     (v3, v4, u_verts[v4], u_verts[v3])]
            if i == 0:
                v5 = verts[x,i, 4]
                faces.append((v3, v5, u_verts[v5], u_verts[v3]))
            else:
                v5 = verts[x,i, 3]
                faces.append((v1, v5, u_verts[v5], u_verts[v1]))                

###
    for y in xrange(h):
        for i in (0, w):
            v1, v2 = verts[i, y, 2], verts[i, y+1, 1]
            v3, v4 = verts[i, y, 3], verts[i, y+1, 4]
            faces += [(v1, v2, u_verts[v2], u_verts[v1]),
                     (u_verts[v1], u_verts[v2], u_verts[v4], u_verts[v3]),
                     (v3, v4, u_verts[v4], u_verts[v3])]
            if i == 0:
                v5 = verts[i, y, 4]
                faces.append((v3, v5, u_verts[v5], u_verts[v3]))
            else:
                v5 = verts[i, y, 1]
                faces.append((v1, v5, u_verts[v5], u_verts[v1]))

###                    

    # last corners        
    # -> x
    v1, v2 = verts[w, 0, 1], verts[w, 0, 4]
    v3, v4 = (verts[w, h, 3],
              verts[w, h, 2])
    faces += [(v1, v2, u_verts[v2], u_verts[v1]),
              (v3, v4, u_verts[v4], u_verts[v3])]                  
    # -> y
    v1, v2 = verts[0, h, 3], verts[0, h, 4]
    v3, v4 = (verts[w, h, 1],
              verts[w, h, 2])
    faces += [(v1, v2, u_verts[v2], u_verts[v1]),
              (v3, v4, u_verts[v4], u_verts[v3])]                  
               
    # create faces           
    for face in faces:
        f = NMesh.Face()
        for vert in face:
            f.append(vert)
        poly.faces.append(f)
        
        
        
    # actual maze
    for wall, exists in maze.walls.iteritems():
        
        cell1, cell2 = wall
        cell1x, cell1y = cell1.position
        
        cell2x, cell2y = cell2.position
        if cell1x == cell2x:
            vc1a = verts[cell1x, cell2y, 1]
            vc1b = verts[cell1x, cell2y, 2]
            
            vc2a = verts[cell1x+1, cell2y, 4]
            vc2b = verts[cell1x+1, cell2y, 3]

        elif cell1y == cell2y:
            vc1a = verts[cell2x, cell2y, 3]
            vc1b = verts[cell2x, cell2y, 2]
            vc2a = verts[cell2x, cell2y+1, 4]
            vc2b = verts[cell2x, cell2y+1, 1]                
        else:
            print "cell %s and cell %s are not neighbours" % (cell1, cell2)
            continue
            
        if exists:
            # make wall
            faces = [(vc1a, vc2a, u_verts[vc2a], u_verts[vc1a]),
                     (vc1b, vc2b, u_verts[vc2b], u_verts[vc1b]),
                     (u_verts[vc2a], u_verts[vc2b],
                      u_verts[vc1b], u_verts[vc1a])
                     ]
        else:
            # make passage
            faces = [(vc1a, vc1b, u_verts[vc1b], u_verts[vc1a]),
                     (vc2a, vc2b, u_verts[vc2b], u_verts[vc2a])]
            
            
        # make faces
        for face in faces:
            f = NMesh.Face()
            for vert in face:
                f.append(vert)
            poly.faces.append(f)
            
            

    if name in NMesh.GetNames():
        mesh = Mesh.Get(name)
        mat = mesh.materials or []
    else:
        mesh = None
        mat = []
    NMesh.PutRaw(poly, name)
    if mesh: 
        mesh.materials = mat
        
    Blender.Redraw()