from random import *
import util
import math
import time


coord_to_dir = {
    (0,0): "C",
    (0,1): "S",
    (1,1): "SE",
    (1,0): "E",
    (1,-1): "NE",
    (0,-1): "N",
    (-1, -1): "NW",
    (-1, 0): "W",
    (-1, 1): "SW",
}

dir_to_coord = {
    "C": (0,0),
    "S": (0,1),
    "SE": (1,1),
    "E": (1,0),
    "NE": (1,-1),
    "N": (0,-1),
    "NW": (-1, -1),
    "W": (-1, 0),
    "SW": (-1, 1),   
}

def calculate_dir(start, target):
    """
    Calculate the direction in which to go to get from start to target.
    start: a tuple representing an (x,y) point
    target: a tuple representing an (x,y) point
    as_coord: whether you want a coordinate (-1,0) or a direction (S, NW, etc.)
    """
    dx = target[0] - start[0]
    dy = target[1] - start[1]
    if dx < 0:
        dx = -1
    elif dx > 0:
        dx = 1
    
    if dy < 0:
        dy = -1
    elif dy > 0: 
        dy = 1
    
    return (dx, dy)

rotate_arr = [    
    (0,1),
    (1,1),
    (1,0),
    (1,-1),
    (0,-1),
    (-1, -1),
    (-1, 0),
    (-1, 1)
]

def get_list_index(lst, tup):
    # only works for 2-tuples
    if len(lst)==0:
        return -1
    for i in range(len(lst)):
        if lst[i][0] == tup[0] and lst[i][1] == tup[1]:
            return i
    return -1

def rotate(orig_dir, amount):
    direction = rotate_arr[(get_list_index(rotate_arr, orig_dir) + amount) % 8]
    return direction

def reflect(full_map, loc, horizontal=True):
    #need to use len-1 not len as a 57x57 board will only go up to a tile 56, start on that the h mirror should be zero
    v_reflec = (len(full_map[0])-1 - loc[0], loc[1])
    h_reflec = (loc[0], len(full_map)-1 - loc[1])
    if horizontal:
        return h_reflec if full_map[h_reflec[1]][h_reflec[0]] else v_reflec
    else:
        return v_reflec if full_map[v_reflec[1]][v_reflec[0]] else h_reflec

def is_passable(full_map, loc, coord_dir, robot_map=None):
    new_point = (loc[0] + coord_dir[0], loc[1] + coord_dir[1])
    if new_point[0] < 0 or new_point[0] >= len(full_map):
        return False
    if new_point[1] < 0 or new_point[1] >= len(full_map):
        return False
    if not full_map[new_point[1]][new_point[0]]:
        return False
    if robot_map is not None and robot_map[new_point[1]][new_point[0]] > 0:
        return False
    return True
    

def apply_dir(loc, dir):
    return (loc[0] + dir[0], loc[1] + dir[1])

# def goto(loc, target, full_map, robot_map, already_been):
#     goal_dir1 = calculate_dir(loc, target) 
#     loc1=apply_dir(loc,goal_dir1)
#     goal_dir2 = calculate_dir(loc1, target)
#     goal_dir2=goal_dir2[0]+goal_dir1[0],goal_dir2[1]+goal_dir1[1]
#     loc2=apply_dir(loc1,goal_dir2)
#     goal_dir3 = calculate_dir(loc2, target)
#     goal_dir3=goal_dir3[0]+goal_dir2[0],goal_dir3[1]+goal_dir2[1]
#     # calculate three goal directions, run at three, if it doesnt work run at two...
#     goal_dir=goal_dir3
#     loc=loc2
#     if goal_dir is (0,0):
#         return (0,0)
#     # self.log("MOVING FROM " + str(my_coord) + " TO " + str(nav.dir_to_coord[goal_dir]))
#     if goal_dir3[0]**2 +goal_dir3[1]**2>9:
#         goal_dir=goal_dir2
#         loc=loc1
#     i = 0
#     while not is_passable(full_map, loc, goal_dir, robot_map) and i < 4:# or apply_dir(loc, goal_dir) in already_been: # doesn't work because `in` doesn't work :(
#         # alternate checking either side of the goal dir, by increasing amounts (but not past directly backwards)
#         if i > 0:
#             i = -i
#         else:
#             i = -i + 1
#         goal_dir = rotate(goal_dir, i)
#     return goal_dir

def goto(loc, target, full_map, robot_map, already_been):
    goal_dir = calculate_dir(loc, target)
    if goal_dir is (0,0):
        return (0,0)
    # self.log("MOVING FROM " + str(my_coord) + " TO " + str(nav.dir_to_coord[goal_dir]))
    i = 0
    while not is_passable(full_map, loc, goal_dir, robot_map) and i < 4:# or apply_dir(loc, goal_dir) in already_been: # doesn't work because `in` doesn't work :(
        # alternate checking either side of the goal dir, by increasing amounts (but not past directly backwards)
        if i > 0:
            i = -i
        else:
            i = -i + 1
        goal_dir = rotate(goal_dir, i)
    return goal_dir
    # while not is_passable(full_map, loc, goal_dir, robot_map) and not in_list(already_been,loc):# or apply_dir(loc, goal_dir) in already_been: # doesn't work because `in` doesn't work :(
    #     # alternate checking either side of the goal dir, by increasing amounts (but not past directly backwards)
    #     # if i > 0:
    #     #     i = -i
    #     # else:
    #     #     i = -i + 1
    #     goal_dir = rotate(goal_dir, -i)
    #     loc=apply_dir(loc,goal_dir)
    # return goal_dir 
    
    

def in_list(dict,key):
 
    if key in dict.keys(): 
        return True
    else: 
        return False


def get_closest_karbonite(loc, karb_map):
    closest_karb = (-100, -100)
    karb_dist_sq = 100000
    for x in range(len(karb_map)):
        if abs(x - loc[0]) > karb_dist_sq:
            break
        for y in range(len(karb_map)):
            if abs(y - loc[1]) > karb_dist_sq:
                break
            if karb_map[y][x] and sq_dist((x,y), loc) < karb_dist_sq:
                karb_dist_sq = sq_dist((x,y), loc)
                closest_karb = (x,y)
    return closest_karb

def sq_dist(p1, p2):
    return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2

def spawn(loc,full_map,robot_map):
    goal_dir=(-1,0)
    counter=0
    while not is_passable(full_map, loc, goal_dir, robot_map) and counter<9:
        goal_dir = rotate(goal_dir, 1)
        counter=counter+1

    return goal_dir

def symmetric(full_map):
    l=len(full_map)-1

    coord1=randint(0,l),randint(0,l)
    coord1_h=coord1[0],l-coord1[1]
    coord2=randint(0,l),randint(0,l)
    coord2_h=coord2[0],l-coord2[1]
    coord3=randint(0,l),randint(0,l)
    coord3_h=coord3[0],l-coord3[1]
    coord4=randint(0,l),randint(0,l)
    coord4_h=coord4[0],l-coord4[1]
    coord5=randint(0,l),randint(0,l)
    coord5_h=coord5[0],l-coord5[1]
    coord6=randint(0,l),randint(0,l)
    coord6_h=coord6[0],l-coord6[1]
    coord7=randint(0,l),randint(0,l)
    coord7_h=coord7[0],l-coord7[1]
    coord8=randint(0,l),randint(0,l)
    coord8_h=coord8[0],l-coord8[1]
    coord9=randint(0,l),randint(0,l)
    coord9_h=coord9[0],l-coord9[1]
    coord10=randint(0,l),randint(0,l)
    coord10_h=coord10[0],l-coord10[1]


    while not full_map[coord1[1]][coord1[0]]:
        coord1=randint(0,l),randint(0,l)
    coord1_h=coord1[0],l-coord1[1]
    while not full_map[coord2[1]][coord2[0]]:
        coord2=randint(0,l),randint(0,l)
    coord2_h=coord2[0],l-coord2[1]
    while not full_map[coord3[1]][coord3[0]]:
        coord3=randint(0,l),randint(0,l)
    coord3_h=coord3[0],l-coord3[1]
    while not full_map[coord4[1]][coord4[0]]:
        coord4=randint(0,l),randint(0,l)
    coord4_h=coord4[0],l-coord4[1]




    if full_map[coord1_h[1]][coord1_h[0]]==full_map[coord1[1]][coord1[0]]:
        if full_map[coord2_h[1]][coord2_h[0]]==full_map[coord2[1]][coord2[0]]:
            if full_map[coord3_h[1]][coord3_h[0]]==full_map[coord3[1]][coord3[0]]:
                if full_map[coord4_h[1]][coord4_h[0]]==full_map[coord4[1]][coord4[0]]:
                    if full_map[coord5_h[1]][coord5_h[0]]==full_map[coord5[1]][coord5[0]]:
                        if full_map[coord6_h[1]][coord6_h[0]]==full_map[coord6[1]][coord6[0]]:
                            if full_map[coord7_h[1]][coord7_h[0]]==full_map[coord7[1]][coord7[0]]:
                                if full_map[coord8_h[1]][coord8_h[0]]==full_map[coord8[1]][coord8[0]]:
                                    if full_map[coord9_h[1]][coord9_h[0]]==full_map[coord9[1]][coord9[0]]:
                                        if full_map[coord10_h[1]][coord10_h[0]]==full_map[coord10[1]][coord10[0]]:
                                            return True
    return False

def distance(x1,y1):
    x_dist = x1[0] - y1[0]
    y_dist = x1[1] - y1[1] 
    return x_dist**2 + y_dist**2

def astar(pprint,check_vis,vis,full_map,start,goal,moves):
    # pprint(str(goal))

    approx = False

    start_time = time.time()
    visible = []
    for v in range(8320):
        visible.append(0)

    for v in vis:
        if not check_vis(v):
            continue
        visible[int(util.nodeHash(v['x'],v['y']))] = 1

    if visible[util.nodeHash(*goal)]:
        approx = True

    # pprint(str(vis))

    size = len(full_map)
    settled = []
    visited = []
    frontier = []
    expanded_nodes = []
    for i in range(size):
        row = []
        vrow = []
        vrow1 = []
        for k in range(size):
            row.append(0)
            vrow.append(0)
            vrow1.append(0)
        visited.append(vrow)
        settled.append(row)
        expanded_nodes.append(vrow1)

    start_node = util.Node(None, start[0], start[1])
    end_node = util.Node(None, goal[0], goal[1])

    # for v in vis:
    #     settled[v['y']][v['x']] = 1

    frontier.append(start_node)

    visited[start_node.y][start_node.x] = start_node
    j = -1
    current_node = None
    # expanded = 1
    # expanded_nodes = [start]
    expanded_nodes[start[1]][start[0]] = 1

    while len(frontier) > 0:
        j += 1
        # print(current_node == frontier[0])
        # pprint("Iteration: " + str(j) + " Nodes expanded: " + str(expanded))
        # pprint("Nodes: " + str(expanded_nodes))
        # pprint("Frontier: " + str(frontier))

        current_node = frontier[0]
        current_index = 0

        for index, n in enumerate(frontier):
            if n.f < current_node.f:
                current_index = index 
                current_node = n

        # if current_node == None:
        #     pprint("We get a null pointer")
        #     pprint(str(frontier))
        #     return [start_node,start_node]

        frontier.pop(current_index)
        # settled[current_node.y][current_node.x] = 1
        # pprint(current_node)

        # pprint(j,current_node.x,current_node.y,current_node.f)

        if util.nodeHash(current_node.x,current_node.y) == util.nodeHash(end_node.x,end_node.y) or (time.time() - start_time)*1000 > 18:
        # if (time.time() - start_time)*1000 > 18:
            # pprint("COMPLETE: "+ str((current_node)))
            path = []
            current = current_node
            while current != None:
                path.insert(0,current)
                current = current.parent
            # pprint(str(path))

            # pprint("Time: " + str((time.time() - start_time)*1000))
            return path

        if approx and util.euclidianDistance((current_node.x,current_node.y), (end_node.x,end_node.y)) <= 3:
            path = []
            current = current_node
            while current != None:
                path.insert(0,current)
                current = current.parent
            # pprint(str(path))

            # pprint("Time: " + str((time.time() - start_time)*1000))
            return path

        children = []
        for move in moves:
            newx = current_node.x + move[0]
            newy = current_node.y + move[1]

            collision = False
            if visible[int(util.nodeHash(newx,newy))]:
                collision = True

            if collision:
                # pprint("collision")
                continue


            if newx > size - 1 or newx < 0 or newy > size - 1 or newy < 0:
                continue

            if expanded_nodes[newy][newx] == 1:
                continue

            # print(full_map[newy][newx])
            if full_map[newy][newx] == False:
                continue

            new_node = util.Node(current_node, newx, newy)
            # pprint("Nodes: " + str((newx,newy)))
            children.append(new_node)


        for child in children:

            # if settled[child.y][child.x]:
            #     continue

            child.g = child.g + 1
            child.h = (child.y - end_node.y)**2 + (child.x - end_node.x)**2
            child.f = child.g + child.h

            open_node = visited[child.y][child.x]
            if open_node != 0:
                if open_node.f < child.f:
                    continue

            frontier.append(child)
            expanded_nodes[child.y][child.x] = 1
            # expanded_nodes.append((child.x,child.y))
            # expanded += 1



def defense(full_map, loc):
    spoke=randint(1,4)
    target=loc[0],loc[1]
    size = len(full_map)

    if spoke==1:
        target=target[0],target[1]+3
        while not full_map[target[1]][target[0]]:
            target=target[0],target[1]+1
            if target[1] >= size:
                target[1] = size
    if spoke==2:
        target=target[0]+3,target[1]
        while not full_map[target[1]][target[0]]:
            target=target[0]+1,target[1]
            if target[0] >= size:
                target[0] = size
    if spoke==3:
        target=target[0],target[1]-3
        while not full_map[target[1]][target[0]]:
            target=target[0],target[1]-1
            if target[1] < 0:
                target[1] = 0
    if spoke==4:
        target=target[0]-3,target[1]
        while not full_map[target[1]][target[0]]:
            target=target[0]-1,target[1]
            if target[0] < 0:
                target[0] = 0
    return target

def defense_2(pprint, full_map, castle_loc, visible, defense_fields):
    # pprint("Starting!")
    vis = []
    for i in range(8320):
        vis.append(0)

    for bot in visible:
        vis[int(util.nodeHash(bot['x'],bot['y']))] = 1

    pos = castle_loc
    initial_branch = util.crossBranch()
    size = len(full_map)
    # pprint("Before the loop")
    start = time.time()
    timer = time.time() - start
    while defense_fields['state'] != 'STOP' and timer*1000 < 30:
        # pprint("Time: " + timer)
        # pprint("Pos: " + pos)
        if defense_fields['state'] == 'EXPAND':
            if pos[0] < 0:
                pos[0] = 0
            if pos[1] < 0:
                pos[1] = 0
            if pos[0] >= size:
                pos[0] = size-1
            if pos[1] >= size:
                pos[1] = size-1

            if not full_map[pos[1]][pos[0]]:
                # Case 1: Position is impassable
                if castle_loc[1] > len(full_map) // 2 and castle_loc[0] > len(full_map) // 2:
                    while not full_map[pos[1]][pos[0]]:
                        pos = pos[0] - 1, pos[1] - 1
                elif castle_loc[1] > len(full_map) // 2 and castle_loc[0] < len(full_map) // 2:
                    while not full_map[pos[1]][pos[0]]:
                        pos = pos[0] + 1, pos[1] - 1
                elif castle_loc[1] < len(full_map) // 2 and castle_loc[0] > len(full_map) // 2:
                    while not full_map[pos[1]][pos[0]]:
                        pos = pos[0] - 1, pos[1] + 1
                elif castle_loc[1] < len(full_map) // 2 and castle_loc[0] < len(full_map) // 2:
                    while not full_map[pos[1]][pos[0]]:
                        pos = pos[0] + 1, pos[1] + 1

                
            if vis[int(util.nodeHash(*pos))]:
                # pprint("SOMEONES HOME")
                # Case 2: Position has already been taken by another bot
                if defense_fields['level'] > 2:
                    # Sub-case: Already filled branch
                    angle = util.crossAngle(util.crossBranch())
                    pos = math.cos(angle)*util.crossLength(), math.sin(angle)*util.crossLength()
                    if vis[int(util.nodeHash(*pos))]:
                        # Sub-sub-case: If new branch has already been expanded and we see that someone is there
                        defense_fields = {'parent' : None, 'level': 1, 'state': 'FOLLOW', 'branch': 0, 'branch_type': 'active', 'length': util.crossLength()}
                    else:
                        # Sub-sub-case: New Diamond has not been started
                        defense_fields['level'] = 0
                        defense_fields['state'] = 'STOP'
                        defense_fields['branch_type'] = 'head'

                # sub case: unfilled branch
                defense_fields['level'] += 1
                # defense_fields['branch'] = util.crossBranch()
                # defense_fields['length'] = defense_fields['length']*util.crossScale()
                defense_fields['state'] = 'FOLLOW'


            else:
                # Case 3: Resource location? (Edge Case we ignore for now)

                # Case 4: Reach Expansion destination
                defense_fields['state'] = 'STOP'

        elif defense_fields['state'] == 'FOLLOW':

            defense_fields['branch'] = util.crossBranch()
            if defense_fields['branch_type'] != 'head':
                defense_fields['state'] = 'EXPAND'
                defense_fields['length'] = util.crossScale()*defense_fields['length']
                angle = util.crossAngle(defense_fields['branch'])
                # pprint("Angle is " + angle + ", Cos and Sine respectively: " + (math.cos(angle),math.sin(angle)))
                x, y = math.cos(angle)*defense_fields['length'], math.sin(angle)*defense_fields['length']
                # pprint("X is " + x + ", Y is " + y)
                pos = int(round(pos[0]+x,0)), int(round(pos[1]+y,0))
            else:
                defense_fields['length'] = util.crossScale()*defense_fields['length']
                defense_fields['level'] += 1
            # Still need to do case analysis

        # timer = time.time() - start

    defense_pos = pos
    # pprint("Final Pos: " + defense_pos)
    return defense_pos, defense_fields


def get_closest_resources(pprint,loc,full_map,fuel_map,karbonite_map):
    closest_resources=[]
    closest_resources_large=[]

    all_resources = []
    for i in range(len(fuel_map)):
        for k in range(len(fuel_map)):
            if fuel_map[i][k] or karbonite_map[i][k]:
                all_resources.append((k,i))

    #ill get the closest resources in a radius of 25, then ill go through that list and make all the resources in a radius of two,
    #then each castle or church should send pilgrims to any in their radius two circle then send three more out to the next two elements
    #on the radius 25 list
    x_start=loc[0]-(len(full_map)//2)
    y_start=loc[1]-(len(full_map)//2)
    if x_start<0:
        x_start=0
    if y_start<0:
        y_start=0
    x_end=loc[0]+(len(full_map)//2)
    y_end=loc[1]+(len(full_map)//2)
    if x_end>len(full_map):
        x_end=len(full_map)
    if y_end>len(full_map):
        y_end=len(full_map)
    for x in range(x_start,x_end):
        for y in range(y_start,y_end):
            if fuel_map[y][x] or karbonite_map[y][x]:
                # pprint("Adding Resource: " + str([x,y]))
                closest_resources_large.append((x,y))
    
    x_start=loc[0]-2
    x_end=loc[0]+3
    y_start=loc[1]-2
    y_end=loc[1]+3
    if x_start<0:
        x_start=0
    if y_start<0:
        y_start=0
    if x_end>len(full_map):
        x_end=len(full_map)
    if y_end>len(full_map):
        y_end=len(full_map)
    for x in range(x_start,x_end):
        for y in range(y_start,y_end):
            if fuel_map[y][x] or karbonite_map[y][x]:
                closest_resources.append((x,y))


    #now have order both lists by distance
    util.insertionSortLoc(pprint, closest_resources, loc)
    util.insertionSortLoc(pprint, closest_resources_large, loc)
    util.insertionSortLoc(pprint, all_resources, loc)
    # quickSort(closest_resources,closest_resources[0],closest_resources[len(closest_resources)+1],loc)
    # quickSort(closest_resources_large,closest_resources_large[0],closest_resources_large[len(closest_resources_large)+1],loc)
    if len(closest_resources)<len(closest_resources_large):
        closest_resources.append(closest_resources_large[len(closest_resources)])
    if len(closest_resources)<len(closest_resources_large):
        closest_resources.append(closest_resources_large[len(closest_resources)])
    # pprint("my closest resources are "+ str(closest_resources) + " with a location of: " + str(loc))
    # pprint(str(closest_resources_large))
    return closest_resources_large

def quickSort(l,min,max,loc):
    if min<max:
        j=partition(l,min,max,loc)

        quickSort(l,min,j-1,loc)
        quickSort(l,j,max,loc)

def partition(l,min,max,loc):
    t=min+1
    j=max
    temp=None
    pivot_dist=(l[0][0]-loc[0])**2+(l[0][1]-loc[1])**2
    t_dist=(l[t][0]-loc[0])**2+(l[t][1]-loc[1])**2
    j_dist=(l[j][0]-loc[0])**2+(l[j][1]-loc[1])**2
    while t<j:
        if t_dist<=pivot_dist:
            t=t+1
            t_dist=(l[t][0]-loc[0])**2+(l[t][1]-loc[1])**2
        elif j_dist>=pivot_dist:
            j=j-1
            j_dist=(l[j][0]-loc[0])**2+(l[j][1]-loc[1])**2
        else:
            temp=l[t]
            l[t]=l[j]
            l[j]=temp
            t=t+1
            j=j-1
            t_dist=(l[t][0]-loc[0])**2+(l[t][1]-loc[1])**2
    j_dist=(l[j][0]-loc[0])**2+(l[j][1]-loc[1])**2
    return j




#first send pilgrims to nearest resources alternating between type  when the robots get there and are full they check if there is 
#a church within radius 5, if they can build a church they then see if there are any other resources within radius 5 if there are
#find the middle and test if it is viable, if not move slightly
def church_or_no(me,loc,map,visible,karb,fuel):
    churches = []
    #could make this a little faster by making it a while loop that exists once weve reached the length of visible or returns once we find a church
    for r in visible:
        if not me.is_visible(r):
            # this robot isn't actually in our vision range, it just turned up because we heard its radio broadcast. disregard.
            continue
        # now all in vision range, can see x, y etc
        #check of 
        bot_loc=r['x'],r['y']
        dist=distance(bot_loc,loc)
        # pprint('i am this far away'+dist +'from a bot that is at'+bot_loc)
        # pprint('and i am at '+loc)
        if r['team'] == me.me['team'] and (r['unit']=='1' or r['unit']=='0') and dist<10:
            churches.append(r)

    # pprint(str(churches))
    # total_karbonite=karbonite+my_karbonite
    # total_fuel=fuel+my_fuel

    return len(churches)==0 #and karb>=50 and fuel>=200
#returns a boolean on whether or not a church needs to be built
#when were standing on the location to build a church we need to check once more that it is still necessary and that another robot
#hasnt built one before

#return the coordinates of a good buidling site
#use self.get_visible_robot_map() for this
def church_build_site(me,SPECS,pprint,loc,full_map,fuel_map,karbonite_map,robot_map):
    #like attackable want to get all the tiles that are in vision that have resources
    #loop through grid around loc
    # center = loc[0]-2,loc[1]-2
    resources=[]
    x_start=loc[0]-2
    y_start=loc[1]-2
    for x in range(x_start,loc[0]+3):
        for y in range (y_start,loc[1]+3):
            if x >= len(full_map) or y >= len(full_map) or x < 0 or y < 0:
                continue
            if fuel_map[y][x]==True or karbonite_map[y][x]==True:
                resources.append([x,y])
    #now we have all the tiles nearby that have resources, have to find a sort of center
    x_cent=0
    y_cent=0
    for i in range(len(resources)):
        x_cent=x_cent+resources[i][0]
        y_cent=y_cent+resources[i][1]
    # pprint('the number of resources found was '+len(resources) +'i am at '+loc)
    x_cent=int(x_cent/len(resources))
    y_cent=int(y_cent/len(resources))
    site=(x_cent,y_cent)
    #we now have the geographical middle but it may not be a whole number and it may not be a buildable location
    dirs=[(0,1),
    (1,1),
    (1,0),
    (1,-1),
    (0,-1),
    (-1, -1),
    (-1, 0),
    (-1, 1)]
    temp=site
    site_final=site
    x=temp[0]
    y=temp[1]
    if not fuel_map[y][x] and not karbonite_map[y][x] and full_map[y][x]:
        num=number_adjacent_resources(pprint,site,full_map,fuel_map,karbonite_map)
    else:
        num=0
    if robot_map[y][x]>0:
        if me.get_robot(robot_map[y][x])['unit']==SPECS['CHURCH'] or me.get_robot(robot_map[y][x])['unit']==SPECS['CASTLE'] or me.get_robot(robot_map[y][x])['unit']==SPECS['PROPHET']:
            num=0
    for i in range(0,len(dirs)):
        temp=apply_dir(site,dirs[i])
        x=temp[0]
        y=temp[1]
        if robot_map[y][x]>0:
            if me.get_robot(robot_map[y][x])['unit']==SPECS['CHURCH'] or me.get_robot(robot_map[y][x])['unit']==SPECS['CASTLE'] or me.get_robot(robot_map[y][x])['unit']==SPECS['PROPHET']:
                continue
        # pprint('testing '+temp)
        # pprint('fuel '+fuel_map[y][x])
        # pprint('karb '+karbonite_map[y][x])
        if fuel_map[y][x] or karbonite_map[y][x]:
            continue
        if full_map[y][x]:
            temp_num=number_adjacent_resources(pprint,temp,full_map,fuel_map,karbonite_map)
            # pprint('number of adjacent resources '+temp_num)
            if temp_num>num:
                site_final=temp
                num=temp_num
    # return (loc[0]-1,loc[1]-1)
    return site_final

def number_adjacent_resources(pprint,site,full_map,fuel_map,karbonite_map):
    start_x=site[0]-1
    num_resources=0
    if start_x<0:
        start_x=0
    start_y=site[1]-1
    if start_y<0:
        start_y=0
    end_x=site[0]+2
    if end_x>len(full_map):
        end_x=len(full_map)
    end_y=site[1]+2
    if end_y>len(full_map):
        end_y=len(full_map)
    # pprint('start x '+start_x)
    for x in range(start_x,end_x):
        for y in range(start_y,end_y):
            # pprint('resources at '+x+','+y)
            if fuel_map[y][x] or karbonite_map[y][x]:
                num_resources=num_resources+1
    return num_resources

def get_closest_dropoff(self, visible,homePath):
    best=None
    best_dist=1000
    for r in visible:
        if not self.is_visible(r):
            # this robot isn't actually in our vision range, it just turned up because we heard its radio broadcast. disregard.
            continue
        # now all in vision range, can see x, y etc
        dist = (r['x'] - self.me['x'])**2 + (r['y'] - self.me['y'])**2
        #check of 
        if r['team'] == self.me['team'] and (r['unit']==1 or r['unit']==0):
            if dist<best_dist:
                best_dist=dist
                best=r
    if best != None:          
        return best['x'],best['y']
    return homePath

def aiming(check_vis, pprint, loc, visible, team, attackmin, attackmax):
    attkmax = int(math.sqrt(attackmax))
    attkmin = int(math.sqrt(attackmin))

    attack_map = []
    for i in range(-attkmax,attkmax+1):
        row = []
        for k in range(-attkmax, attkmax+1):
            row.append(0)
        attack_map.append(row)

    size = len(attack_map)
    centroid = (size // 2, size // 2)
    attack_map[centroid[1]][centroid[0]] = -10

    rel_pos_bot = {}
    for r in visible:
        if not check_vis(r):
            continue
        if r['team'] != team:
            rel_pos_bot[(r['x'] - loc[0], r['y'] - loc[1])] = 1
        else:
            rel_pos_bot[(r['x'] - loc[0], r['y'] - loc[1])] = -1

    for y in range(-attkmax,attkmax+1):
        for x in range(-attkmax,attkmax+1):
            if x**2 + y**2 > attackmax or x**2 + y**2 < attackmin:
                continue
            attack_pos = (x + centroid[0], y + centroid[1])
            for splash in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
                hit = splash[0]+attack_pos[0], splash[1]+attack_pos[1]
                if hit[0] < 0 or hit[1] < 0 or hit [0] >= size or hit[1] >= size:
                    continue
                if (hit[0] - centroid[0], hit[1] - centroid[1]) in rel_pos_bot:
                    # pprint("Modifying Map")
                    attack_map[hit[1]][hit[0]] = attack_map[hit[1]][hit[0]] + rel_pos_bot[(hit[0] - centroid[0], hit[1] - centroid[1])]

    # pprint(str(visible))
    max_point = (0,0)
    hits = attack_map[centroid[1]][centroid[0]]
    for y in range(-attkmax,attkmax+1):
        for x in range(-attkmax,attkmax+1):
            if x**2 + y**2 > attackmax or x**2 + y**2 < attackmin:
                continue

            if attack_map[y + centroid[1]][x + centroid[0]] > hits:
                max_point = (x, y)
                hits = attack_map[y + centroid[1]][x + centroid[0]]

    # pprint(str(attack_map))

    return max_point


def resource_occupied(self,SPECS,me,loc,target,visible):
    # self.log("target: " + target[1])
    # self.log("visible " + str(visible))
    for r in visible:
        if not self.is_visible(r):
            continue
        if r['x'] == target[0] and r['y'] == target[1] and r['unit'] == SPECS['PILGRIM'] and r['id'] != me['id']:
            return True
    return False



def new_resource_target(self,SPECS,pprint,me,loc,full_map,fuel_map,karbonite_map,visible):
    closest_resources=get_closest_resources(pprint,loc,full_map,fuel_map,karbonite_map)
    # pprint("new resources: " + str(closest_resources))
    i=0
    occupied=resource_occupied(self,SPECS,me,loc,closest_resources[0],visible)
    dist=distance(closest_resources[i],loc)
    # pprint("got this far")
    # pprint("Occupied: " + occupied)
    # if occupied:
    #     i = i + 1
    #     occupied=resource_occupied(self,SPECS,me,loc,closest_resources[i],visible)
    #     pprint("Occupied again? " + occupied)

    while occupied and dist < 100:
        if i >= len(closest_resources) - 1:
            break
        i += 1
        # pprint("closest_resources_new: " + str(closest_resources[i]))
        occupied=resource_occupied(self,SPECS,me,loc,closest_resources[i],visible)
        dist=distance(closest_resources[i],loc)
    # pprint("Return Value: " + closest_resources[i])
    return closest_resources[i]
    # return closest_resources[0]


def homies(self,SPECS,loc,visible,team,unit):
    buddies=0
    for r in visible:
        if not self.is_visible(r):
            continue
        if r['team']==team and r['unit']==SPECS[unit]:
            buddies=buddies+1
    return buddies>4



def get_closest_resources_church(pprint,loc,robot_map,full_map,fuel_map,karbonite_map):
    closest_resources=[]

    #ill get the closest resources in a radius of 25, then ill go through that list and make all the resources in a radius of two,
    #then each castle or church should send pilgrims to any in their radius two circle then send three more out to the next two elements
    #on the radius 25 list

    
    x_start=loc[0]-2
    x_end=loc[0]+3
    y_start=loc[1]-2
    y_end=loc[1]+3
    if x_start<0:
        x_start=0
    if y_start<0:
        y_start=0
    if x_end>len(full_map):
        x_end=len(full_map)
    if y_end>len(full_map):
        y_end=len(full_map)
    for x in range(x_start,x_end):
        for y in range(y_start,y_end):
            if (fuel_map[y][x] or karbonite_map[y][x]) and robot_map[y][x]<=0:
                closest_resources.append((x,y))


    #now have order both lists by distance
    util.insertionSortLoc(pprint, closest_resources, loc)
    # quickSort(closest_resources,closest_resources[0],closest_resources[len(closest_resources)+1],loc)
    # quickSort(closest_resources_large,closest_resources_large[0],closest_resources_large[len(closest_resources_large)+1],loc)

    return closest_resources



def get_closest_resources_pilgrim(pprint,loc,robot_map,full_map,fuel_map,karbonite_map,filled_resources):
    closest_resources_large=[]
    #getting all the closest resources where a pilgrim is
    if x_end>len(full_map):
        x_end=len(full_map)
    if y_end>len(full_map):
        y_end=len(full_map)
    for x in range(0,len(full_map)):
        for y in range(0,len(full_map)):
            if (x,y) in filled_resources:
                continue
            if (fuel_map[y][x] or karbonite_map[y][x]) and robot_map[y][x]<=0:
                closest_resources_large.append((x,y))
    

    util.insertionSortLoc(pprint, closest_resources_large, loc)
    # quickSort(closest_resources,closest_resources[0],closest_resources[len(closest_resources)+1],loc)
    # quickSort(closest_resources_large,closest_resources_large[0],closest_resources_large[len(closest_resources_large)+1],loc)

    return closest_resources_large


def meeting_place(me,loc,target,moves,pprint):
    # #if the map is symmetric(ie its horizontal), then we want the meeting place to be closer to the enemy y axis wise
    # if symmetric:
    #     if loc[1]<len(full_map):
    #         #so the enemies are south of us
    #         #lets just try moving straight down
    #         destination=loc[0],loc[1]+6
    #         passable=full_map[destination[1]][destination[0]]
    #         resource=karb_map[destination[1]][destination[0]] or fuel_map[destination[1]][destination[0]]
    #         occupied=visible[destination[1]][destination[0]] 
    #         if not passable or resource or occupied:
    #             destination=loc[0]-1,loc[1]
    #             passable=full_map[destination[1]][destination[0]]
    #             resource=karb_map[destination[1]][destination[0]] or fuel_map[destination[1]][destination[0]]
    #             occupied=visible[destination[1]][destination[0]] 
    #         if not passable or resource or occupied:
    #             destination=loc[0]+2,loc[1]
    #             passable=full_map[destination[1]][destination[0]]
    #             resource=karb_map[destination[1]][destination[0]] or fuel_map[destination[1]][destination[0]]
    #             occupied=visible[destination[1]][destination[0]] 
    #         if not passable or resource or occupied:
    #             destination=loc[0]-1,loc[1]-1
    #             passable=full_map[destination[1]][destination[0]]
    #             resource=karb_map[destination[1]][destination[0]] or fuel_map[destination[1]][destination[0]]
    #             occupied=visible[destination[1]][destination[0]] 
    #         if not passable or resource or occupied:
    #             destination=loc[0]+2,loc[1]+2
    #             passable=full_map[destination[1]][destination[0]]
    #             resource=karb_map[destination[1]][destination[0]] or fuel_map[destination[1]][destination[0]]
    #             occupied=visible[destination[1]][destination[0]] 

    #     else:
    #         #the enemies are north of us
    #         #lets just try moving straight up
    #         destination=loc[0],loc[1]-6
    #     #now if taken or impassable try left or right one, then take a step forward or backwards
    # else:
    #     if loc[0]<len(full_map):
    #         #the enemies must be east of us
    #         #lets try moving straight right
    #         destination=loc[0]+6,loc[1]
    #     else:
    #         #the enemies must be west of us
    #         #lets try moving straight left
    #         destination=loc[0]-6,loc[1]
    #     #now if taken or impassable try up or down one, then take a step left or right
    # return destination


    #just going to take his desitnation, look at the path to it, return the third element of the path
    path = astar(me.log, me.is_visible, me.get_visible_robots(), me.get_passable_map(), loc, target, moves)
    pprint('length of the path is '+len(path))
    return path[2]

def get_safe_tile(loc,full_map,karb_map,fuel_map,church_site):
    moves=[
       (0,1),(1,0),(0,-1),(1,0),(1,1),(-1,1),(1,-1),(-1,-1),(0,2),(2,0),(0,-2),(-2,0),
    ]
    x=loc[0]
    y=loc[1]
    passable=full_map[y][x]
    resource= karb_map[y][x] or fuel_map[y][x]
    temp_loc=loc
    i=0
    while not passable or resource or temp_loc==church_site:
        temp_loc=apply_dir(loc,moves[i])
        i=i+1
        x=temp_loc[0]
        y=temp_loc[1]
        passable=full_map[y][x]
        resource= karb_map[y][x] or fuel_map[y][x]
    return temp_loc


def get_nearby_resources(full_map,fuel_map,karb_map,loc):
    x_start=loc[0]-7
    x_end=loc[0]+8
    y_start=loc[1]-7
    y_end=loc[1]+8
    if x_start<0:
        x_start=0
    if x_end>len(full_map):
        x_end=len(full_map)
    if y_start<0:
        y_start=0
    if y_end>len(full_map):
        y_end=len(full_map)
    num_resources=0
    for x in range(x_start,x_end):
        for y in range(y_start,y_end):
            if karb_map[y][x] or fuel_map[y][x]:
                num_resources += 1
    return num_resources






    









