# todo
# make a game? (just show the next n cells -> too hard?)
# gui
# statistics

# done
# movable end points to compare ways

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.
    """
    #: dimensions of the Maze
    width = 40#35
    height = 40#20
    def __init__(self):
        """
        Create the basic structure and attributes. This does not yet generate
        an actual maze.
        """
        #: 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


## pygame part
import pygame
import pygame.locals as loc
import os
COLORS = {
            "background": (200,130,22),
            "foreground": (0,0,0),
            "marker": (76, 136, 255),
            "path": (130, 0, 0),
         }
CELL_WIDTH = 10
OFFSET_X, OFFSET_Y = 50, 50
class Main(object):
    def __init__(self):
        # Initialize Everything
        os.environ["SDL_VIDEO_WINDOW_POS"] = "center"
        pygame.init()
    #    icon = pygame.Surface((32, 32))
    #    icon.set_colorkey((0, 0, 0))
    #    offset = (32 - min(STONE_SIZE, 30)) / 2
    #    rect = (offset, offset, STONE_SIZE, STONE_SIZE)
    #    icon.fill((0, 150, 0), rect)
    #    pygame.draw.rect(icon, COLORS["stone_border"], rect, 1)
    #    pygame.display.set_icon(icon)
        self.screen = pygame.display.set_mode((Maze.width*CELL_WIDTH+100, Maze.height*CELL_WIDTH+100))
        self.screen.fill(COLORS["background"])
        pygame.display.set_caption('MAZE - by jug')
        # create game objects
        self.clock = pygame.time.Clock()
        self.maze = Maze()
        self.maze.generate()
        
        self.markers = [self.maze.cells[0], self.maze.cells[0]]
        self.moving_marker = None
        self.show_markers = True
        self.show_path = True
        
        self.player_cell = self.maze.cells[0]

        self.fx = lambda x: x * CELL_WIDTH + OFFSET_X
        self.fy = lambda y: y * CELL_WIDTH + OFFSET_Y
        self.draw_maze()
        self.run()
    
    def _mark_cell(self, cell, color):
        col, row = cell.position
        pygame.draw.rect(self.screen, color, 
                        (self.fx(col), self.fy(row), 
                        CELL_WIDTH, CELL_WIDTH))
    
    def draw_maze(self):
        # show markers
        if self.show_markers:
            for marker in self.markers:
                self._mark_cell(marker, COLORS["marker"])
            # path between markers
            if self.show_path:
                cells = self.maze.search_way(*self.markers)
                # exclude markers
                for cell in cells[1:-1]:
                    self._mark_cell(cell, COLORS["path"])
                    
        # actual maze
        for wall, exists in self.maze.walls.iteritems():
            if exists:
                cell1, cell2 = wall
                cell1x, cell1y = cell1.position
                
                cell2x, cell2y = cell2.position
                if cell1x == cell2x:
                    pygame.draw.line(self.screen, COLORS["foreground"], 
                             (self.fx(cell2x), self.fy(cell2y)),
                             (self.fx(cell2x+1), self.fy(cell2y)))
                elif cell1y == cell2y:
                    pygame.draw.line(self.screen, COLORS["foreground"], 
                             (self.fx(cell2x), self.fy(cell2y)),
                             (self.fx(cell2x), self.fy(cell2y+1)))
                else:
                    raise ValueError, "cell %s and cell %s are not neighbours" % (cell1, cell2)
        pygame.draw.lines(self.screen, COLORS["foreground"], True,
                          [(OFFSET_X, OFFSET_Y), 
                           (OFFSET_X+self.maze.width*CELL_WIDTH, OFFSET_Y),
                           (OFFSET_X+self.maze.width*CELL_WIDTH,
                            OFFSET_Y+self.maze.height*CELL_WIDTH),
                           (OFFSET_X, OFFSET_Y+self.maze.height*CELL_WIDTH)])
        self._mark_cell(self.player_cell, (222,0,111))
        pygame.display.flip()

        
    def run(self):
        """mainloop"""
        while 1:
            self.clock.tick(40)
            events = pygame.event.get()
    #        if generate:
    #            try:
    #                print generator.next()
    #            except StopIteration:
    #                generate = False
    #                print "done"
                    
                        
            for event in events:
                if ((event.type == loc.KEYDOWN and event.key == loc.K_ESCAPE) or 
                    event.type == loc.QUIT):
                    return
                if (event.type == loc.MOUSEBUTTONDOWN or 
                    (event.type == loc.MOUSEMOTION 
                     and self.moving_marker is not None)):
                    old_markers = self.markers[:]
                    row = (event.pos[1] - OFFSET_Y) / CELL_WIDTH
                    col = (event.pos[0] - OFFSET_X) / CELL_WIDTH
                    if (0 <= row < self.maze.height and
                        0 <= col < self.maze.width):
                        
                        index = self.maze.width*row+col
                        cell = self.maze.cells[index]
                        if (self.moving_marker is not None
                            and event.type == loc.MOUSEMOTION):
                            self.markers[self.moving_marker] = cell
                        elif (cell in self.markers and 
                              event.type == loc.MOUSEBUTTONDOWN):
                            self.moving_marker = self.markers.index(cell)
                        if not old_markers == self.markers:
                            self.screen.fill(COLORS["background"])    
                            self.draw_maze()
                    else:
                        self.moving_marker = None
                if event.type == loc.MOUSEBUTTONUP:
                    self.moving_marker = None
                        
                    
               # elif event.type == loc.MOUSEBUTTONUP:
               #     generate = False
                elif event.type == loc.KEYDOWN and event.key == loc.K_RETURN:
                    self.maze.reset_walls()
                    self.maze.reset_cells()
    #                maze.__init__()
                    self.maze.generate()
                    self.screen.fill(COLORS["background"])
                    self.draw_maze()
                    
                    
                # game actions
               
                elif event.type == loc.KEYDOWN:
                    dirs = [loc.K_UP, loc.K_RIGHT, loc.K_DOWN, loc.K_LEFT]
                    if event.key in dirs:
                        i = dirs.index(event.key)
                        neighbour_cell = self.player_cell.get_neighbours()[i]
                        if neighbour_cell:                                
                            wall_key = tuple(sorted((self.player_cell, 
                                                     neighbour_cell)))
                            if not self.maze.walls.get(wall_key):
                                self.player_cell = neighbour_cell
                                self.screen.fill(COLORS["background"])    
                                self.draw_maze()
                            # else: "there is a wall"
                                
                        # else: "no next cell there"
                        
                    
                        
            

            
                               
                    
            pygame.display.flip()
            #pygame.display.update(board.blit())

if __name__ == '__main__': 
    Main()