import random, math
import core.model
from core.model import DIRECTION_UP, DIRECTION_DOWN, DIRECTION_LEFT, DIRECTION_RIGHT
from core.event import TickEvent, AgentMovedEvent, QuitEvent
from core.event import SimulationStartedEvent
from core.utils import GreedyPath, AStar, Dijkstra

from utils import PacmanLevel, AStarPacman

class Pacman(core.model.Agent):
    def __init__(self, disp, env):
        core.model.Agent.__init__(self, disp)
        self.ghosts = []

        self.next_update = 0
        self.path = []

        self.env = env

        #self.fic = open("pacstats", "w")
        self.ite = 0

    def __repr__(self):
        return "Pacman@(Sector = %s)" % self.sector

    def move3(self):
        def try_move(to):
            if to == self.sector:
                print "BUG!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"
            if to.occupant != None:
                if isinstance(to.occupant, Ghost):
                    print "DEAD"
                    self.disp.post(QuitEvent())
                    return

            # Let's move
            self.sector.occupant = None
            self.sector = to
            self.sector.occupant = self
            self.disp.post(AgentMovedEvent(self))

        if self.next_update > 0:
            self.next_update -= 1
            
            if len(self.path) != 0:
                to = self.path[0]
                self.path.remove(self.path[0])
                try_move(to)
                return



        d = Dijkstra(Wall)


        # Generate ghost map
        ghostmap = {}
        for g in self.ghosts:
            ghostmap = d.eval(g.sector, ghostmap)

        
        # Generate pacman map
        pacmap = d.eval(self.sector, {})

        diffmap = ghostmap.copy()
        for k in ghostmap.keys():
            diffmap[k] = ghostmap[k] - pacmap[k]
            
        #self.ite += 1
        #self.fic.write("%d %d %d %d %d\n"%(self.ite, diffmap[self.sector], pacmap[self.ghosts[0].sector], pacmap[self.ghosts[1].sector], pacmap[self.ghosts[2].sector]))


#         def find_path(start, ghostmap, pacmap, safe_dst=15):
#             closed = []
#             path = []
#             opened = []
#             parent = {}
            
#             opened.append(start)

#             dpl = 0
#             while len(opened) != 0:
#                 cur = opened.pop()
#                 closed.append(cur)
                
#                 best = None
#                 for succ in cur.get_neighbors():
#                     if succ in closed:
#                         continue

#                     if succ not in ghostmap:
#                         continue

#                     if best == None:
#                         best = succ

#                     if (ghostmap[succ] - dpl) >= (ghostmap[best] - dpl):
#                         best = succ

#                 if best == None:
#                     break

#                 score = ghostmap[best] - dpl
#                 if score <= 0:
#                     print "Warning : using a path with a zero, we may die!"

#                 if score >= safe_dst:
#                     print "Found a safe point, stop here."
#                     path.append(best)
#                     break

#                 print score

#                 opened.append(best)
#                 path.append(best)
#                 parent[best] = cur
#                 dpl += 1

#             return path

        #a = AStarPacman(lambda a, b: math.fabs(a.pos[0]-b.pos[0]) + math.fabs(a.pos[1]-b.pos[1]))
        #a = AStarPacman()
        a = AStar()

        path_exact = True

#         bests = []
        
#         best = None
#         for i in ghostmap.keys():
#             if best == None:
#                 best = i
            
#             if ghostmap[i] > ghostmap[best]:
#                 best = i


#         for i in ghostmap.keys():
#             if best in bests:
#                 continue

#             if ghostmap[best] == ghostmap[i]:
#                 bests.append(best)

#         ###
#         bests = []
#         for i in ghostmap.keys():
#             if ghostmap[i] > 7:
#                 bests.append(i)
        
        def maxlocal():
            # meilleure position locale dans la grille
            x = 0
            y = 0
            best = None
            for k in ghostmap.keys():
                if diffmap[k] > 0 and best == None:
                    best = k

                if best == None:
                    continue

                if ghostmap[k] > ghostmap[best] and diffmap[k] > 0:
                    best = k
            
            if best == None:
                return None
            else:
                print "Found max local", diffmap[best]
                return best

        bests = [maxlocal()]

        print bests
        
        bests.sort(cmp=lambda x, y: ghostmap[x] < ghostmap[y], reverse=True)

        best = bests[0]
        
        for b in bests:
            self.path = a.find_path(self.sector, b)#, ghostmap)
            if self.path != None and len(self.path) > 0:
                break

        if self.path == None or len(self.path) == 0:
            path_exact = False
            best = None
            for n in self.sector.get_neighbors():
                if n.occupant != None:
                    continue

                if best == None:
                    best = n
                
                if ghostmap[n] > ghostmap[best]:
                    best = n

            # Try a kamakazee path
            for b in bests:
                self.path = a.find_path(self.sector, b)#, ghostmap, True)
                if self.path != None and len(self.path) > 0:
                    print "KAMIKAAAZZZEEEEE"
                    break
            
            # Try to escape...
            if self.path == None:
                self.path = [best]


        if self.path == None:
            print "No path found !!"
            self.next_update = 0
            self.disp.post(AgentMovedEvent(self))
            return

        if len(self.path) == 0:
            print "Already at best position..."
            self.next_update = 0
            self.disp.post(AgentMovedEvent(self))
            return



        def dump_map(map):
            for i in range(30):
                for j in range(28):
                    if self.env.sectors[i][j] in map:
                        print "%3d"%map[self.env.sectors[i][j]],
                    else:
                        print "###",

                print

#         print "Shortest distance to :", ghostmap[self.sector]
#         print "Ghost 0 is at : ", pacmap[self.ghosts[0].sector]
#         print "Ghost 1 is at : ", pacmap[self.ghosts[1].sector]
#         print "Safety of destination : ", ghostmap[self.path[-1]]
#         print "Path length : ", len(self.path)

        print "Pacmap :"
        dump_map(pacmap)
        print "Ghostmap :"
        dump_map(ghostmap)
        print "Diffmap :"
        dump_map(diffmap)


        # Let's move
        to = self.path[0]
        self.path.remove(self.path[0])
        #if path_exact:
        #self.next_update = len(self.path)
        #else:
        self.next_update = 0
        try_move(to)




    def move2(self):
        def try_move(to):
            if to == self.sector:
                print "BUG!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"
            if to.occupant != None:
                if isinstance(to.occupant, Ghost):
                    print "DEAD"
                    self.disp.post(QuitEvent())
                    return

            # Let's move
            self.sector.occupant = None
            self.sector = to
            self.sector.occupant = self
            self.disp.post(AgentMovedEvent(self))
        
        if self.next_update > 0:
            self.next_update -= 1
            
            if len(self.path) != 0:
                to = self.path[0]
                self.path.remove(self.path[0])
                try_move(to)
                return


        self.next_update = 10



        def barycentre():
            x = 0
            y = 0
            for g in self.ghosts:
                x += g.sector.pos[0]
                y += g.sector.pos[0]

            x /= len(self.ghosts)
            y /= len(self.ghosts)

            return (x, y)

        b = barycentre()

        def safe_path(start, centres, safe_dist):
            def dst(a, centers):
                worst = math.fabs(a.pos[0]-b[0]) + math.fabs(a.pos[1]-b[1])
                for c in centers:
                    tmp = math.fabs(a.pos[0]-b[0]) + math.fabs(a.pos[1]-b[1])
                    if tmp < worst:
                        worst = tmp

                return worst

            path = []
            closed = []
            cur = self.sector
            cur_dist = dst(start, centres)
            notes = {}
            notes[start] = dst(start, centres)

            while cur_dist < safe_dist:
                closed.append(cur)
                # Note adjacent sectors and find the best one
                best = None
                for d in (DIRECTION_UP, DIRECTION_DOWN, DIRECTION_LEFT, DIRECTION_RIGHT):
                    if cur.neighbors[d] in closed:
                        continue

                    if cur.move_possible(d):
                        if best == None:
                            best = cur.neighbors[d]

                        notes[cur.neighbors[d]] = dst(cur.neighbors[d], centres)

                        if notes[best] < notes[cur.neighbors[d]]:
                            best = cur.neighbors[d]

                # Unable to find a single valid sector, abort (dead-end)
                if best == None:
                    print "Not optimal !"
                    return path
                else:
                    if notes[best] >= cur_dist:
                        path.append(best)
                        cur = best
                    else:
                        print "No crescent!"
                        return path


            return path

        self.path = safe_path(self.sector, self.ghosts, 30)

        if len(self.path) == 0:
            print "Stuck -> Emergency A*"
           
            def dst(a, b):
                return math.fabs(a.pos[0]-b.pos[0]) + math.fabs(a.pos[1]-b.pos[1])
            a = AStar(dst)

            self.path = a.find_path(self.sector, self.test_sectors[0])
            if self.path == None or len(self.path) == 0:
                print "REALLY STUCK!!"
                return
            
        # Let's move
        to = self.path[0]
        self.path.remove(self.path[0])
        try_move(to)

    def move(self):
        if self.next_update > 0 and self.path != None and len(self.path) > 0:
            self.next_update -= 1
            n = self.path[0]
            self.path.remove(n)

            # Let's move
            self.sector.occupant = None
            self.sector = n
            self.sector.occupant = self
            self.disp.post(AgentMovedEvent(self))
            return
            
        self.next_update = 20

        def score(pacman, ghosts):
            def dst(a, b):
                return math.fabs(a[0]-b[0]) + math.fabs(a[1]-b[1])

            score = 0

            # only keep the worst score
            for g in ghosts:
                my = dst(pacman, g)
                if my > score:
                    score = my

            return score



        # Get ghosts positions
        ghosts_pos = []
        for g in self.ghosts:
            ghosts_pos.append(g.sector.pos)

        # note adjacent sectors
        def note_sectors():
            notes = {}
            closed = []
            opened = []

            opened.append(self.sector)

            while len(opened) != 0:
                s = opened.pop()

                
                for d in (DIRECTION_UP, DIRECTION_DOWN, DIRECTION_LEFT, DIRECTION_RIGHT):
                    if s.neighbors[d] in closed:
                        continue

                    if s.move_possible(d):
                        notes[s.neighbors[d]] = score(s.neighbors[d].pos, ghosts_pos)
                        opened.append(s.neighbors[d])
                
                closed.append(s)                

            
            return notes

        notes = note_sectors()

        # Choose best move
        best = notes.keys()[0]
        for s in notes:
            print s, notes[s]
            if notes[s] > notes[best]:
                best = s

        def dst(a, b):
            return math.fabs(a.pos[0]-b.pos[0]) + math.fabs(a.pos[1]-b.pos[1])

        gp = GreedyPath(dst)
        self.path = gp.find_path(self.sector, best)

        if self.path == None:
            return

        # Let's move
        self.sector.occupant = None
        self.sector = self.path[0]
        self.sector.occupant = self
        self.disp.post(AgentMovedEvent(self))
            

    def notify(self, e):
        if isinstance(e, TickEvent):
            self.move3()

        elif isinstance(e, SimulationStartedEvent):
            self.ghosts = e.sim.ghosts


class Ghost(core.model.Agent):
    (ATTACK, REST) = range(2)
    def __init__(self, disp):
        core.model.Agent.__init__(self, disp)
        self.last_pacman_sector = None
        self.last_dir = None

        self.last_path = None

        self.mode = Ghost.ATTACK
        self.mode_count = 20

        self.count = 0

    def move(self):
        # Prevent crash
        if self.last_pacman_sector == None or self.sector == None:
            return

        # Switch mode
        if self.mode_count == 0:
            if self.mode == Ghost.ATTACK:
                self.mode = Ghost.REST
                self.mode_count = 5
            else:
                self.mode = Ghost.ATTACK
                self.mode_count = 15


        self.mode_count -= 1

        if self.mode == Ghost.ATTACK:
            self.attack()
        else:
            self.rest()

    def rest(self):
        self.last_path = None
        self.last_dir = None

        choices = [DIRECTION_UP, DIRECTION_RIGHT, DIRECTION_DOWN, DIRECTION_LEFT]
        while len(choices) != 0:
            d = random.choice(choices)

            if self.sector.move_possible(d):
                self.sector.occupant = None
                self.sector = self.sector.neighbors[d]
                self.sector.occupant = self

                self.disp.post(AgentMovedEvent(self))
                return

            choices.remove(d)
        
    def attack(self):
        if self.count == 0 or self.last_path == None or len(self.last_path) == 0:
            print "Generating path..."
            def dst(a, b):
                return math.fabs(a.pos[0]-b.pos[0]) + math.fabs(a.pos[1]-b.pos[1])

            gp = GreedyPath(dst)
            self.last_path = gp.find_path(self.sector, self.last_pacman_sector, Pacman)
            self.count = 10

        self.count -= 1

        if self.last_path == None or len(self.last_path) == 0:
            return

        next = self.last_path[0]
        self.last_path.remove(next)
        
        self.sector.occupant = None
        self.sector = next
        self.sector.occupant = self

        self.disp.post(AgentMovedEvent(self))        
        
    def notify(self, e):
        if isinstance(e, TickEvent):
            self.move()

        elif isinstance(e, AgentMovedEvent):
            if isinstance(e.agent, Pacman):
                self.last_pacman_sector = e.agent.sector

class Wall(core.model.Agent):
    def __init__(self, disp):
        self.disp = disp
        self.sector = None


class PacmanSimulation(core.model.Simulation):
    def __init__(self, disp, lev_path):
        self.level = PacmanLevel(disp, lev_path)
        # A pacman level is alway 28x30
        env = core.model.ToricEnvironment(disp, 28, 30)
        core.model.Simulation.__init__(self, disp, env)


    def start(self):
        self.env.build(do_diags=False)
        self.pacman, self.ghosts = self.level.load(self.env)
        self.disp.post(SimulationStartedEvent(self))
        self.state = PacmanSimulation.RUNNING

    def notify(self, e):
        core.model.Simulation.notify(self, e)

        if isinstance(e, SimulationStartedEvent):
            print "Go!"