# returns the manhattan distance between two tiles, calculated as:
# 	|x1 - x2| + |y1 - y2|
def manhattan_distance(start, end):

	distance = abs(start[0] - end[0]) + abs(start[1] - end[1])

	return distance

# given a tile location as an (x,y) tuple
# return the surrounding tiles as a list


def get_surrounding_tiles(location):

    # find all the surrounding tiles relative to us
    # location[0] = x-index; location[1] = y-index
    tile_up = (location[0], location[1]+1)
    tile_down = (location[0], location[1]-1)
    tile_left = (location[0]-1, location[1])
    tile_right = (location[0]+1, location[1])

    # combine these into a list
    all_surrounding_tiles = [tile_up, tile_down, tile_left, tile_right]

    # include only the tiles that are within the game boundary
    # empty list to store our valid surrounding tiles
    valid_surrounding_tiles = []

    # loop through tiles
    for tile in all_surrounding_tiles:
        # check if the tile is within the boundaries of the game
        # note: the map is size 9x9
        if tile[0] >= 0 and tile[0] < 9 and tile[1] >= 0 and tile[1] < 9:
            # add valid tiles to our list
            valid_surrounding_tiles.append(tile)

    return valid_surrounding_tiles

# this function returns the object tag at a location


def entity_at(x, y, game_state):
    for entity in game_state["entities"]:
        if entity["x"] == x and entity["y"] == y:
            return entity["type"]


def get_map(width, height, game_state, enemy_loc):
    field = [[0]]

    for y in range(height):
        field[y].remove(0)
        for x in range(width):
            # print(entity_at(x,y, game_state))
            if (entity_at(x, y, game_state) is not None and entity_at(x, y, game_state) != 'a' and entity_at(x, y, game_state) != "bp") or (x == enemy_loc[0] and y == enemy_loc[1]):
                field[y].append(1)
            else:
                field[y].append(0)

        if y != height-1:
            field.append([0])

    # new_field = []

    # for i in range(height-1, -1, -1):
    #     new_field.append(field[i])

    return field

# given a list of tiles
# return the ones which are actually empty


def get_empty_tiles(tiles, game_state):

	# empty list to store our empty tiles
    empty_tiles = []

    for tile in tiles:
        # if tile==enemy_location:
        #     print("SAMAAAA WOIIIIIIIIIIIIIIIIIIIIIIIIII")
        if entity_at(tile[0], tile[1], game_state) is None:
            empty_tiles.append(tile)
            # print(tile,enemy_location)
# the tile isn't occupied, so we'll add it to the list
    return empty_tiles

def get_impacted_tiles(bombs, my_bomb_range, enemy_bomb_range, game_state):
    impacted_tiles = []
    
    for tile in bombs[0]:
        if bombs[1][bombs[0].index(tile)] == 0:
            bomb_range = my_bomb_range
        else:
            bomb_range = enemy_bomb_range
    
        for x in range(1, (bomb_range-1)//2 + 1):
            # print("entity_at(tile[0]+x, tile[1], game_state):", entity_at(tile[0]+x, tile[1], game_state))
            # print("tile[0]: ", tile[0], "tile[0]+x", tile[0] + x)
            if entity_at(tile[0] + x, tile[1], game_state) is None and tile[0] + x < 9:
                # print("Kosong bro 1!")
                impacted_tiles.append((tile[1], tile[0]+x))
            if entity_at(tile[0]-x,tile[1], game_state) is None and tile[0] - x >= 0:
                # print("Kosong bro 2!")
                impacted_tiles.append((tile[1], tile[0]-x))
        for y in range(1, (bomb_range-1)//2 + 1):
            if entity_at(tile[0],tile[1]+y, game_state) is None and tile[1] + y < 9:
                # print("Kosong bro 3!")
                impacted_tiles.append((tile[1]+y, tile[0]))
            if entity_at(tile[0],tile[1]-y, game_state) is None and tile[1] - y >= 0:
                # print("Kosong bro 4!")
                impacted_tiles.append((tile[1]-y, tile[0]))
    temp = []
    
    for tile in impacted_tiles:
        if tile not in temp:
            temp.append(tile)
        
    return temp
 
# given an adjacent tile location, move us there
def move_to_tile(location, tile):
 
    # see where the tile is relative to our current location
    diff = tuple(x-y for y, x in zip(location, tile))
    
    # return the action that moves in the direction of the tile
    if diff == (0,1):
        action = 'right'
    elif diff == (0,-1):
        action = 'left'
    elif diff == (1,0):
        action = 'up'
    elif diff == (-1,0):
        action = 'down'
    else:
        action = ''
 
    return action
 
def get_ammo(start,game_state):
 
    list_of_ammo = []
 
    for i in game_state["entities"]:
        if i["type"] == "a":
            x = i["x"]
            y = i["y"]
            list_of_ammo.append((2,manhattan_distance(start,(x,y)),x,y));
            # list_of_ammo.append((x,y))
 
    return list_of_ammo
 
def get_available_ammo(start, game_map, game_state):
    path=[]
    ammo = get_ammo(start, game_state)
    ammo.sort()
    for i in ammo:
        temp=astar(game_map,start,(i[3],i[2]))
        if(temp==None):
            continue
        else:
            path.append(temp)
        
    return path
 
def get_nearest_ammo(location, ammo_location):
    nearest_ammo = [0, 0]
    nearest_distance = 100
 
    for tile in ammo_location:
        distance = manhattan_distance(location, tile)
        if distance < nearest_distance:
            nearest_ammo = tile
            nearest_distance = distance  
 
    return nearest_ammo
 
def get_bp(start,game_state):
 
    list_of_bp = []
 
    for i in game_state["entities"]:
        if i["type"] == "bp":
            x = i["x"]
            y = i["y"]
            list_of_bp.append((1,manhattan_distance(start,(x,y)),x,y));
            # list_of_bp.append((x,y))
 
    return list_of_bp
 
def get_nearest_bp(location, bp_location):
    nearest_bp = [0, 0]
    nearest_distance = 100
 
    for tile in bp_location:
        distance = manhattan_distance(location, tile)
        if distance < nearest_distance:
            nearest_bp = tile
            nearest_distance = distance  
 
    return nearest_bp
 
def get_available_bp(start, game_map, game_state):
    path=[]
    bp = get_bp(start, game_state)
    bp.sort()
    for i in bp:
        temp=astar(game_map,start,(i[3],i[2]))
        if(temp==None):
            continue
        else:
            path.append(temp)
        
    return path

def get_available_ammo_bp(start, game_map, game_state):
    path=[]
    list_ammo = get_ammo((start[1], start[0]), game_state)
    list_bp = get_bp((start[1], start[0]), game_state)
    list_ammo_bp = list_ammo + list_bp
    list_ammo_bp.sort()
    
    for i in list_ammo_bp:
        temp=astar(game_map,start,(i[3],i[2]))
        if(temp==None):
            continue
        else:
            path.append(temp)
            # break
    
    return path
# return a list of bombs on the map
def get_bombs(game_state, enemy_location, our_location):
 
    list_of_bombs = [[],[]]
 
    for i in game_state["entities"]:
        if i["type"] == "b":
            x = i["x"]
            y = i["y"]
            bomb_loc = (x,y)
            list_of_bombs[0].append(bomb_loc)
            if enemy_location == bomb_loc:
                list_of_bombs[1].append(1)
            else:
                list_of_bombs[1].append(0)
            
 
    return list_of_bombs
 
# return a list of the bomb positions that are nearby
def get_bombs_in_range(location, bombs):
 
    # empty list to store our bombs that are in range of us
    bombs_in_range = []
 
    # loop through all the bombs placed in the game
    for bomb in bombs:
 
        # get our manhattan distance to a bomb
        distance = manhattan_distance(location, bomb)
 
        # set to some arbitrary threshold for distance
        # if we are below this threshold, we want flee bot to runaway
        if distance <= 5:
            bombs_in_range.append(bomb)
 
    return bombs_in_range

# given a list of tiles and bombs
# find the tile that's safest to move to
def get_safest_tile(tiles, bombs, location):
 
    # which bomb is closest to us?
    bomb_distance = 10  # some arbitrary high distance
    closest_bomb = bombs[0]  # set this to the first bomb in the list for now
 
    # loop through the list of bombs
    for bomb in bombs:
        # calculate the manhattan distance
        new_bomb_distance = manhattan_distance(bomb,location)
 
        if new_bomb_distance < bomb_distance:
            # this bomb is the closest one to us so far, let's store it
            bomb_distance = new_bomb_distance
            closest_bomb = bomb
 
    # start with an empty dictionary
    manhattan_distances = {}
 
    # now we'll figure out which tile is furthest away from that bomb
    for tile in tiles:
        # get the manhattan distance from this tile to the closest bomb
        distance = manhattan_distance(tile,closest_bomb)
        # store this in a dictionary
        manhattan_distances[tile] = distance

    # return the tile with the furthest distance from any bomb
    safest_tile = max(manhattan_distances, key=manhattan_distances.get)

    return safest_tile


def get_future_safest_tile(tiles, bombs, game_state):

    print("Im getting safest tile bro")
    safest_cost = -(10**9 + 7)
    safest_cost2 = -(10**9 + 7)
    cost = 0
    cost2 = [[] for i in range(len(tiles))]
    safest_tile = []
    safest_tile2 = []
    
    for tile in tiles:
        cost = 0
        surrounding_tiles_1 = get_empty_tiles(get_surrounding_tiles(tile),game_state)
        cost += 1
        if (tile[1], tile[0]) in bombs:
            cost -= 10

        for tile2 in surrounding_tiles_1:
            surrounding_tiles_2 = get_empty_tiles(get_surrounding_tiles(tile2),game_state)
            cost += 1
            if (tile2[1], tile2[0]) in bombs:
                cost -= 10

            for tile3 in surrounding_tiles_2: 
                #surrounding_tiles_3 = self.get_empty_tiles(self.get_surrounding_tiles(tile3))
                
                #for tile4 in surrounding_tiles_3:
                cost += 1
                if (tile3[1], tile3[0]) in bombs:
                    cost -= 10

        if cost >= safest_cost:
            safest_tile = tile
            safest_cost = cost

    for i in range(len(tiles)):
        surrounding_tiles = get_empty_tiles(get_surrounding_tiles(tiles[i]), game_state)
        for tile in surrounding_tiles:
            cost2[i] = 0
            surrounding_tiles_1 = get_empty_tiles(get_surrounding_tiles(tile),game_state)
            cost2[i] += 1
            if (tile[1], tile[0]) in bombs:
                cost2[i] -= 10

            for tile2 in surrounding_tiles_1:
                surrounding_tiles_2 = get_empty_tiles(get_surrounding_tiles(tile2),game_state)
                cost2[i] += 1
                if (tile2[1], tile2[0]) in bombs:
                    cost2[i] -= 10

                for tile3 in surrounding_tiles_2: 
                    #surrounding_tiles_3 = self.get_empty_tiles(self.get_surrounding_tiles(tile3))
                    
                    #for tile4 in surrounding_tiles_3:
                    cost2[i] += 1
                    if (tile3[1], tile3[0]) in bombs:
                        cost2[i] -= 10
                        
        if cost2[i] >= safest_cost:
            safest_tile2 = tile
            safest_cost2 = cost2[i]
            
    if safest_cost2 > safest_cost:
        safest_tile = safest_tile2
        
    return safest_tile


class Node():
    # A node class for A* Pathfinding
 
    def __init__(self, parent=None, position=None):
        self.parent = parent
        self.position = position
 
        self.g = 0
        self.h = 0
        self.f = 0
 
    def __eq__(self, other):
        return self.position == other.position
 
def astar(maze, start, end):
    # Returns a list of tuples as a path from the given start to the given end in the given maze
 
    # Create start and end node
    start_node = Node(None, start)
    start_node.g = start_node.h = start_node.f = 0
    end_node = Node(None, end)
    end_node.g = end_node.h = end_node.f = 0
 
    # Initialize both open and closed list
    open_list = []
    closed_list = []
 
    # Add the start node
    open_list.append(start_node)
 
    # Loop until you find the end
    while len(open_list) > 0:
        
        # print("a")
        # Get the current node
        current_node = open_list[0]
        current_index = 0
        for index, item in enumerate(open_list):
            if item.f < current_node.f:
                current_node = item
                current_index = index
 
        # Pop current off open list, add to closed list
        open_list.pop(current_index)
        closed_list.append(current_node)
 
        # Found the goal
        if current_node == end_node:
            path = []
            current = current_node
            while current is not None:
                # print("b")
                path.append(current.position)
                current = current.parent
            return path[::-1] # Return reversed path
 
        # Generate children
        children = []
        for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0)]: # Adjacent squares
            # print("c")
            # Get node position
            node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])
 
            # Make sure within range    
            if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (len(maze[len(maze)-1]) -1) or node_position[1] < 0:
                continue
 
            # Make sure walkable terrain
            if maze[node_position[0]][node_position[1]] != 0:
                continue
 
            # Create new node
            new_node = Node(current_node, node_position)
 
            # Append
            children.append(new_node)
 
        
 
        # Loop through children
        for child in children:
            # print(child.position[0], "-",child.position[1], "--", len(open_list))
            # print(child.g, "-", child.h, "-", child.f)
            # Child is on the closed list
            is_in_closed_list = False
 
            check = False
            for closed_child in closed_list:
                if child == closed_child:
                    check = True
                    continue
            if check:
                continue
            
 
            # Create the f, g, and h values
            # if is_in_closed_list == False:   
            child.g = current_node.g + 1
            child.h = (abs(child.position[0] - end_node.position[0])) + (abs(child.position[1] - end_node.position[1]))
            child.f = child.g + child.h
 
            
            # Child is already in the open list
            check = False
            for open_node in open_list:
                if child == open_node and child.g > open_node.g:
                    check = True
                    continue
            if check:
                continue
            
            # Add the child to the open list
            open_list.append(child)


def goto_bp_and_ammo(game_map, start,enemy_location, bombs, game_state):
    list_bp = get_bp((start[1], start[0]), game_state)
    list_ammo = get_ammo((start[1], start[0]), game_state)
    list_ammo_bp=list_ammo+list_bp
    list_ammo_bp.sort()
    
    path=[]
    for i in list_ammo_bp:
        temp=astar(game_map,start,(i[3],i[2]))
        i_surrounding_tiles = get_surrounding_tiles((i[2],i[3]))
        empty_tiles_around_i=get_empty_tiles(i_surrounding_tiles, game_state)
        if(temp==None or len(empty_tiles_around_i)<=1):
            continue
        else:
            path.append(temp)
    
    surrounding_tiles = get_surrounding_tiles((start[1], start[0]))
    empty_tiles = get_empty_tiles(surrounding_tiles, game_state)
    if  len(path)>=1:
        print("path luar = ",path[0])
        if len(path[0])<=1:
            if (len(path)>1):
                path.pop(0)
                print("path dalem = ",path[0])
                action=move_to_tile(start,path[0][1])
            else:
                safest_tile = get_future_safest_tile(empty_tiles, bombs, game_state) 
                if (start[1], start[0]) != safest_tile:
                    action = move_to_tile(start,(safest_tile[1], safest_tile[0]))
                else:
                    # if we are in the safest tile we stop moving
                    action = ''
        else:
            action=move_to_tile(start,path[0][1])
    else:
        safest_tile = get_future_safest_tile(empty_tiles, bombs, game_state)  
        if (start[1], start[0]) != safest_tile:
            action = move_to_tile(start,(safest_tile[1], safest_tile[0]))
        else:
            # if we are in the safest tile we stop moving
            action = ''
            
    return action