MAP_DATA  = {'0101': [10, 'clear'], '0102': [10, 'clear'], '0103': [10, 'clear'], '0104': [10, 'clear'], '0105': [10, 'clear'],
 '0106': [10, 'clear'], '0107': [10, 'clear'], '0108': [20, 'clear'], '0109': [30, 'clear'], '0110': [30, 'clear'],
 '0111': [30, 'clear'], '0112': [20, 'clear'], '0113': [20, 'clear'], '0114': [10, 'clear'], '0115': [10, 'clear'],
 '0201': [10, 'clear'], '0202': [10, 'clear'], '0203': [10, 'road'], '0204': [10, 'clear'], '0205': [10, 'clear'],
 '0206': [10, 'clear'], '0207': [10, 'clear'], '0208': [20, 'clear'], '0209': [30, 'clear'], '0210': [30, 'clear'],
 '0211': [30, 'clear'], '0212': [20, 'clear'], '0213': [10, 'clear'], '0214': [10, 'stream'], '0215': [10, 'clear'],
 '0301': [10, 'clear'], '0302': [10, 'clear'], '0303': [10, 'clear'], '0304': [10, 'road'], '0305': [10, 'clear'],
 '0306': [10, 'town'], '0307': [10, 'clear'], '0308': [10, 'clear'], '0309': [20, 'clear'], '0310': [30, 'clear'],
 '0311': [30, 'clear'], '0312': [30, 'clear'], '0313': [20, 'clear'], '0314': [10, 'stream'], '0315': [10, 'clear'],
 '0401': [10, 'clear'], '0402': [10, 'clear'], '0403': [10, 'clear'], '0404': [10, 'road'], '0405': [10, 'clear'],
 '0406': [10, 'forest'], '0407': [10, 'clear'], '0408': [10, 'clear'], '0409': [20, 'clear'], '0410': [20, 'clear'],
 '0411': [20, 'clear'], '0412': [20, 'clear'], '0413': [10, 'stream'], '0414': [10, 'clear'], '0415': [10, 'clear'],
 '0501': [10, 'clear'], '0502': [10, 'clear'], '0503': [10, 'forest'], '0504': [10, 'clear'], '0505': [10, 'road'],
 '0506': [10, 'clear'], '0507': [10, 'forest'], '0508': [10, 'forest'], '0509': [10, 'clear'], '0510': [10, 'clear'],
 '0511': [10, 'clear'], '0512': [10, 'clear'], '0513': [10, 'stream'], '0514': [10, 'clear'], '0515': [10, 'clear'],
 '0601': [10, 'clear'], '0602': [10, 'forest'], '0603': [10, 'forest'], '0604': [10, 'clear'], '0605': [10, 'road'],
 '0606': [10, 'town'], '0607': [10, 'clear'], '0608': [10, 'forest'], '0609': [10, 'clear'], '0610': [10, 'clear'],
 '0611': [10, 'clear'], '0612': [10, 'clear'], '0613': [10, 'stream'], '0614': [10, 'clear'], '0615': [10, 'clear'],
 '0701': [20, 'clear'], '0702': [20, 'clear'], '0703': [20, 'clear'], '0704': [10, 'town'], '0705': [10, 'clear'],
 '0706': [10, 'road'], '0707': [10, 'clear'], '0708': [10, 'clear'], '0709': [10, 'clear'], '0710': [10, 'town'],
 '0711': [10, 'clear'], '0712': [10, 'clear'], '0713': [10, 'stream'], '0714': [10, 'clear'], '0715': [10, 'clear'],
 '0801': [20, 'clear'], '0802': [20, 'clear'], '0803': [20, 'clear'], '0804': [10, 'town'], '0805': [10, 'road'],
 '0806': [10, 'clear'], '0807': [10, 'clear'], '0808': [10, 'clear'], '0809': [10, 'clear'], '0810': [10, 'stream'],
 '0811': [10, 'stream'], '0812': [10, 'stream'], '0813': [10, 'clear'], '0814': [10, 'clear'], '0815': [10, 'clear'],
 '0901': [30, 'clear'], '0902': [30, 'clear'], '0903': [20, 'clear'], '0904': [10, 'forest'], '0905': [10, 'clear'],
 '0906': [10, 'road'], '0907': [10, 'clear'], '0908': [10, 'clear'], '0909': [10, 'stream'], '0910': [10, 'stream'],
 '0911': [10, 'clear'], '0912': [10, 'clear'], '0913': [10, 'clear'], '0914': [10, 'clear'], '0915': [10, 'clear'],
 '1001': [30, 'clear'], '1002': [30, 'clear'], '1003': [20, 'clear'], '1004': [10, 'forest'], '1005': [10, 'clear'],
 '1006': [10, 'road'], '1007': [10, 'clear'], '1008': [10, 'stream'], '1009': [10, 'clear'], '1010': [10, 'clear'],
 '1011': [20, 'forest'], '1012': [30, 'forest'], '1013': [20, 'clear'], '1014': [10, 'clear'], '1015': [10, 'clear'],
 '1101': [10, 'clear'], '1102': [10, 'clear'], '1103': [10, 'clear'], '1104': [10, 'clear'], '1105': [10, 'clear'],
 '1106': [10, 'clear'], '1107': [10, 'road'], '1108': [10, 'clear'], '1109': [10, 'stream'], '1110': [10, 'clear'],
 '1111': [10, 'forest'], '1112': [10, 'forest'], '1113': [10, 'clear'], '1114': [10, 'clear'], '1115': [10, 'clear'],
 '1201': [20, 'clear'], '1202': [20, 'clear'], '1203': [10, 'clear'], '1204': [10, 'clear'], '1205': [10, 'clear'],
 '1206': [10, 'clear'], '1207': [10, 'road'], '1208': [10, 'stream'], '1209': [10, 'clear'], '1210': [10, 'clear'],
 '1211': [10, 'forest'], '1212': [10, 'forest'], '1213': [10, 'clear'], '1214': [10, 'clear'], '1215': [10, 'clear'],
 '1301': [10, 'clear'], '1302': [10, 'clear'], '1303': [10, 'clear'], '1304': [10, 'clear'], '1305': [10, 'clear'],
 '1306': [10, 'clear'], '1307': [10, 'clear'], '1308': [10, 'stream'], '1309': [10, 'road'], '1310': [10, 'clear'],
 '1311': [10, 'clear'], '1312': [10, 'forest'], '1313': [10, 'clear'], '1314': [10, 'clear'], '1315': [10, 'clear'],
 '1401': [10, 'clear'], '1402': [10, 'clear'], '1403': [10, 'clear'], '1404': [10, 'clear'], '1405': [10, 'clear'],
 '1406': [10, 'clear'], '1407': [10, 'clear'], '1408': [10, 'clear'], '1409': [10, 'road'], '1410': [10, 'clear'],
 '1411': [10, 'clear'], '1412': [10, 'clear'], '1413': [10, 'clear'], '1414': [10, 'clear'], '1415': [10, 'clear'],
 '1501': [10, 'clear'], '1502': [10, 'clear'], '1503': [10, 'clear'], '1504': [10, 'clear'], '1505': [10, 'clear'],
 '1506': [10, 'clear'], '1507': [10, 'clear'], '1508': [10, 'clear'], '1509': [10, 'clear'], '1510': [10, 'road'],
 '1511': [10, 'clear'], '1512': [10, 'clear'], '1513': [10, 'clear'], '1514': [10, 'clear'], '1515': [10, 'clear']}




import queue


def str_to_tuple(str):
    return(int(str[:2]),int(str[2:]))

def int_to_str(x,y):
    '''
    行列换算成格标签，比如int_to_str(6,6)返回第6列第6行的格子编号
    结果是'0606'
    :param x:
    :param y:
    :return:
    '''
    if (x <1 or x >15) or (y <1 or y > 15):
        return None
    else:
        a = str(x) if x> 9 else '0'+str(x)
        b = str(y) if y >9 else '0'+str(y)
        return a + b

def tile_neighbours(tile):
    '''
    返回相邻的6个格标签,如果在边角处不一定是6个
    比如 tile_neighbours('0101')返回'0101'相邻的格子编号
    结果是 ['0102','0201']
    :param tile:
    :return:
    '''
    n = []
    x, y = int(tile[:2]),int(tile[2:])
    n1 = int_to_str(x,y-1)
    n2 = int_to_str(x,y+1)
    n.extend([n1,n2])
    if x %2 ==0:
        n3 = int_to_str(x-1,y)
        n4 = int_to_str(x-1,y+1)
        n5 = int_to_str(x+1,y)
        n6 = int_to_str(x+1,y+1)
    elif x%2 ==1:
        n3 = int_to_str(x-1,y)
        n4 = int_to_str(x-1,y-1)
        n5 = int_to_str(x+1,y)
        n6 = int_to_str(x+1,y-1)
    n.extend([n3,n4,n5,n6])
    neighbours = [neighbour for neighbour in n if neighbour]
    return neighbours


def mp_cost(current,next):
    '''
    计算进入格子消耗的机动力值，比如从'0603'移动到'0704'
    mp_cost('0603','0704')，返回3，说明消耗3机动力值
    :param current:
    :param next:
    :return:
    '''
    if MAP_DATA[current][1] == 'road' and MAP_DATA[next][1] == 'road':
        return 0.5
    elif MAP_DATA[next][1] in ('forest','stream'):
        return 2
    elif MAP_DATA[next][1] == 'town':
        return 3
    elif MAP_DATA[next][0] == 20:
        return 2
    elif MAP_DATA[next][0] == 30:
        return 3
    else:
        return 1

def heuristic(current,next):
    '''
    启发式算法，可以自定义，这里是简单的计算距离
    比如heuristic('0101','0102'),返回'0101'到'0102'的距离,返回1
    :param current:
    :param next:
    :return:
    '''
    x_1, y_1 = int(current[:2]), int(current[2:])
    x_2,y_2 = int(next[:2]),int(next[2:])
    return abs(x_1-x_2) + abs(y_1 - y_2)

def a_start_path(start,end):
    '''
    A*算法，注释掉碰到目标停止，继续遍历找到最优解，纯A*寻路不用注释掉
    返回消耗的机动力值和格子序列
    :param start:
    :param end:
    :return:
    '''
    frontier = queue.PriorityQueue()
    frontier.put((0,start))
    came_from = {}
    cost_so_far = {}
    came_from[start] = start
    cost_so_far[start] = 0
    while not frontier.empty():
        current = frontier.get()[1]
##        if current == end:
##            break
        for next in tile_neighbours(current):
            new_cost = cost_so_far[current] + mp_cost(current, next)
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                cost_so_far[next] = new_cost
                priority = new_cost + heuristic(end, next)
                frontier.put((priority,next))
                came_from[next] = current
    min_mp = cost_so_far[end]
    path = []
    node = end
    while node != start:
        path.append(node)
        node = came_from[node]
    path.reverse()
    return  min_mp, path

