零基础编写MUSH机器人笔记：（四）同城快递的最短路径算法 python版 源代码

白发魔女(kkndbdra@tj)

这个图代表一个大理城的简化模型
楼主对LUA不熟悉，只会写python的，请谅解。
不过原理都是一样的，习惯LUA的同学请参照馆长机器人的lujing.lua里面的函数自行改写。
附件中有源文件

图中绿色代表 大理城左下角 起点
红点代表右边的那条街上的任意一点 终点
灰色的房间代表障碍物
每个房间可能的行走方向有s;e;w;n;ne,nw,sw，se  一共8个方向




蓝色的方块 代表你曾经在地图上不断尝试走过的点
黄色的星星代表终点到起点的最优节点
将这些黄色星星的最优节点串联起来然后反转顺序就是起点到终点的最短路径
# -*- coding: GBK
#1 网格化地图并设立坐标
#2 确立各个节点之间的关系
#3 明确节点应该有哪些属性
#4
node0={'id':'0',
    'neighbours':{
        '1':['e'],
        '9':['n'],
        '8':['ne']

  }
}


node1={'id':'1',
    'neighbours':{
        '0':['w'],
        '2':['e'],
        '9':['nw'],
        '8':['n'],

  }
}
node2={'id':'2',
    'neighbours':{
        '1':['w'],
        '3':['e'],

  }
}
node3={'id':'3',
    'neighbours':{
        '2':['w'],
        '4':['e'],


  }
}
node4={'id':'4',
    'neighbours':{
        '3':['w'],
        '5':['n'],

  }
}
node5={'id':'5',
    'neighbours':{
        '4':['s'],
        '14':['n'],

  }
}
node8={'id':'8',
    'neighbours':{
        '0':['sw'],
        '1':['s'],
        '9':['w'],
        '10':['nw'],
        '11':['n'],

  }
}
node9={'id':'9',
    'neighbours':{
        '0':['s'],
        '1':['se'],
        '8':['e'],
        '10':['n'],
        '11':['ne'],

  }
}
node10={'id':'10',
    'neighbours':{
        '8':['se'],
        '9':['s'],
        '11':['e'],
        '15':['n'],
        '16':['ne']

  }
}
node11={'id':'11',
    'neighbours':{
        '8':['s'],
        '9':['sw'],
        '10':['w'],
        '12':['e'],
        '15':['nw'],
        '16':['n']
  }
}
node12={'id':'12',
    'neighbours':{
        '11':['w'],


  }
}
node14={'id':'14',
    'neighbours':{
        '5':['s'],
        '19':['n'],

  }
}
node15={'id':'15',
    'neighbours':{
        '10':['s'],
        '11':['se'],
        '16':['e'],
        '20':['n'],
        '21':['ne']

  }
}
node16={'id':'16',
    'neighbours':{
        '11':['s'],
        '10':['sw'],
        '15':['w'],
        '20':['nw'],
        '21':['n']
  }
}
node19={'id':'19',
    'neighbours':{
        '24':['n'],
        '14':['s'],



  }
}
node20={'id':'20',
    'neighbours':{
        '15':['s'],
        '16':['se'],
        '21':['e'],


  }
}

node21={'id':'21',
    'neighbours':{
        '16':['s'],
        '15':['sw'],
        '20':['w'],
        '22':['e']


  }
}
node22={'id':'22',
    'neighbours':{
        '21':['w'],
        '23':['e'],



  }
}
node23={'id':'23',
    'neighbours':{
        '22':['w'],
        '24':['e'],



  }
}
node24={'id':'24',
    'neighbours':{
        '23':['w'],
        '19':['s'],



  }
}





citynodes=[node0,node1,node2,node3,node4,node5,node8,node9,node10,
           node11,node12,node14,node15,node16,node19,node20,node21,
           node22,node23,node24]

start_node=node9 #起点
end_node=node19 #终点
start_node_id=start_node['id']
end_node_id=end_node['id']
open_g_list=[]# 开启列表 （包含从起点开始，所有等待被处理的节点的集合）
open_g_list.append([start_node_id,'',0,''])#将起点加入待处理列表数据结构：[当前节点，当前父节点，当前G值]
closed_g_list=[]# 关闭列表 （包含所有已经考虑过的可能选择的节点）

while True:
    flag_1=0
    for closed_node in closed_g_list:
        if closed_node[0]==end_node_id:#如果终点在关闭列表中表示
            print('考察过的路径列表',closed_g_list)
            flag_1=1
            break
    if flag_1==1:
        break
    if not open_g_list:   #open_list为空时表示：没有再可供探查的新生可抵达节点。（地图上所有可抵达地点已遍历完毕）
                         # 例如终点在一个被水环绕的孤岛里，在地图中是存在的，但是周边节点无任何一个有可抵达路径。
                         # 这个点看得见摸不着，不属于可抵达节点
                         #而此时，循环过无数遍以后，所遍历过的点已经包含了所有可抵达节点的可能性（被探查过的点），说明该点在一个无法抵达的节点里
        print('该点可看不可达')
        break

        #选取open_g_list 中 G值最小的二维元素
        #1- 对open_g_list 中的元素，key =x[n][3]进行升序排序，然后 选取取x[0][1]
    sorted(open_g_list,key=lambda x:x[2])#将openlist 按照G值排序
    current_node_id= open_g_list[0][0] # 提取待处理列表中Gmin的节点作为当前节点
    print('当前节点为：',current_node_id)
    current_node=open_g_list[0]
    neighbours_g_list=[]

    flag_0 = 0# 循环变量
    for node in  citynodes:
        if current_node_id==node['id']:
            current_node_dict= node     # 将current_node_id转化为对应的current_node
            neighbours = current_node_dict['neighbours']  # 预提取当前节点的邻居节点字典式列表
            neighbours_list = list(neighbours)  # 正式生成当前节点ID的邻居节点ID列表

            for nei_node_id in neighbours_list: #新延伸节点ID---新延伸节点[nei_node_id,father_node_id,G2father+fatherG，route]列表
                father_id = current_node_id
                G2father = len(current_node_dict['neighbours'][nei_node_id])
                fatherG  = current_node[2]
                totalG=G2father+fatherG
                neighbours_g_list.append([nei_node_id,father_id,totalG,current_node_dict['neighbours'][nei_node_id]])
            else:
                break


    # 从新延伸节点中剔除已经处理过的节点
    for closed_node in closed_g_list:
        for nei_node in neighbours_g_list:
            if closed_node[0]==nei_node[0]:
                neighbours_g_list.remove(nei_node)
                break
    '''else:
        print('和closedlist对比以后的邻居列表：',neighbours_g_list)'''
    # 将新延伸节点与open_g_list中的节点比较
    for nei_node2 in neighbours_g_list:
        for open_node in open_g_list:
            #如果延伸节点在开启列表中存在则比较新值与旧值之间的大小
            if nei_node2[0]==open_node[0] and nei_node2[2]<open_node[2]:
                #用nei_node顶替open_node
                open_node=nei_node2 #用新节点更新同名节点的更优父节点，G值，路径
                break

    #如果新延伸节点不在openlist 中,则将新延伸
    openlist=[]
    for open_node2 in open_g_list:
        openlist.append(open_node2[0])
    for nei_node3 in neighbours_g_list:
        if nei_node3[0] not in openlist:
            open_g_list.append(nei_node3)


    # open_g_list更新完毕
    '''print('更新后的open_g_list',open_g_list)'''
    # 将current_node 从open_g_list 中移除
    open_g_list.remove(current_node)
    #将current_node 加入closed list
    closed_g_list.append(current_node)

#在关闭列表中沿着父节点找寻最短路径
traceback_nodes=[]
traceback_route=[]
trace_node_id = closed_g_list[-1][0]
trace_list=closed_g_list.reverse()

for trace_node in closed_g_list:
    if trace_node[0]==trace_node_id:
        trace_node_id=trace_node[1]
        traceback_nodes.append(trace_node)
        if trace_node[1]==start_node_id:#当父节点==起点时跳出循环
            break

print(traceback_nodes)
#取出从终点返回起点节点中的路径形成路径序列
for node_route in traceback_nodes:
    traceback_route.append(node_route[3])
print(traceback_route)
#将路径序列反转形成从起点到终点的路径
traceback_route.reverse()
print(traceback_route)