A*寻路初学-_-

A星寻路是一种非常有趣的寻路算法。

相比较bfs与dfs它更具体更科学。

个人推荐讲的最清楚的一篇文章

http://www.gamedev.net/reference/articles/article2003.asp

以下是我学习时的一些理解

*地图中的每个节点 都有自己对于终点、起点的移动代价。

F = G + H

F 是成本总和

G = 从起点移动到指定方格的移动代价。

H = 从指定的方格移动到终点 B 的估算成本。

-------------------------------------------------------------------------------

1.我们会从终点开始进行遍历,把当前的节点放到open list。

添加节点相邻节点到open list 并且计算他们的代价。

如果发现更少代价,则更新值。

2.我们会从起点开始再次遍历,把每个节点再次放入open list。

添加相邻节点到open list 并且计算他们的代价。

如果发现更少代价,则更新值。

最后的路径是这么产生的:反复遍历 open list ,选择 F 值最小的方格。

-----------------------------------------------------------------------------------


这张图看了就能理解了


以当前节点看相邻节点(上下左右1步可达) 用 ‘+ 10’ 表示基础代价

以当前节点看 左下 右上 右下 左上 斜角节点时,用 ‘+14’ 计算基础代价

-为什么代价这么取值?

之所以,是因为实际的对角移动距离是 2 的平方根,或者是近似的 1.414 倍的横向或纵向移动代价。使用 10 和 14 就是为了简单起见。比例是对的,我们避免了开放和小数的计算。

-我的python代码

# 定义节点类,节点类呢会有一些属性来区别自身与其他节点的区别

class Node:

    def __int__(self):

        self.unable = False

        self.distanceFromDes = -1  # 距离终点的距离

        self.distanceFromOri = -1  # 距离起点的距离

        self.allDistance = -1 # 所有距离总和

        self.added = False    # 是否添加过

        self.closed = False  # 是否已经走过

        self.parent = None    # 上层节点是什么

        self.x = -1          # 坐标位置 x轴

        self.y = -1


#  2.生成地图 m长 n宽

def GenerateMap(m, n):

    map = list()

    for j in range(m):

        nodeRow = list()

        map.append(nodeRow)

        for i in range(n):

            node = Node()

            node.y = j

            node.x = i

            node.unable = False

            node.distanceFromDes = -1  # 距离终点的距离

            node.distanceFromOri = -1  # 距离起点的距离

            node.allDistance = -1

            node.added = False

            node.closed = False

            node.parent = None

            nodeRow.append(node)

    return map

# 放置障碍物

def SetUnableMapNode(map, ls=()):  # 要求一个坐标队列,里边的点上的Node的unable == True

    for index in ls:

        map[index[0]][index[1]].unable = True

    return map

# # 添加终点,并计算每个节点与终点的距离

def GetDistanceFromDes(map, mapSize, endNode):  # map二维数组,mapsize(m,n),desIndex终点坐标

    # 这里再次对所有节点初始化 屬性為未添加

    for ls in map:

        for node in ls:

            node.added = False

    desNode = map[endNode[0]][endNode[1]]

    # 終點與終點的距離肯定0

    desNode.distanceFromDes = 0

    # TODO ...

    addedList = list()  # 已经加入的队列,已有值distanceFromDes

    needList = list()  # 待加入的队列,需要评估值distanceFromDes


    addedList.append(desNode) # 将终点节点加入到已添加列表

    desNode.added = True      # 更改终点节点的属性为已添加

    while(len(addedList) != 0):  # 当地图上所有可以遍历的点还没全确定

        while(len(addedList) != 0):  # 当一个大循环中,addedList还没被needList取代

            # 从addedList中选出来的一个点,找needList中的needNode

            mainNode = addedList.pop(0)

            #print("main node:",mainNode)

            # 主节点的距离是从addedList中拿出来的node距离终点的距离

            mainDistanceFromDes = mainNode.distanceFromDes

            y = mainNode.y

            x = mainNode.x

            print("mainDistanceFromDes:",mainDistanceFromDes)

            print("y:",y)

            print("x:",x)

            for needNodey in (y + 1, y, y - 1):

                # 超出的情况就忽略了

                #print("needNodey:",needNodey)


                if needNodey < 0 or needNodey >= mapSize[0]:

                    continue

                for needNodex in (x + 1, x, x - 1):

                    #print("inner needNodex:",needNodey)

                    if needNodex < 0 or needNodex >= mapSize[1]:

                        continue

                    needNode = map[needNodey][needNodex]  # 坐标不出界

                    if needNode.unable == True or needNode.added == True:

                        continue  # 坐标也满足add的要求

                    yOffset = needNodey - y

                    xOffset = needNodex - x

                    allOffset = yOffset + xOffset

                    print("yOffset:",yOffset,"xOffset:",xOffset,"allOffset=",allOffset) 

                    if allOffset == 1 or allOffset == -1:

                        distanceFromDes = mainDistanceFromDes + 1

                    elif allOffset == -2 or allOffset == 0 or allOffset == 2:

                        distanceFromDes = mainDistanceFromDes + 1.4

                    else:

                        print("终点代价计算错误")

                    if needNode in needList:  # 设置needNode的距离,要求最小

                        if distanceFromDes < needNode.distanceFromDes:

                            needNode.distanceFromDes = distanceFromDes

                    else:  # needNode 不在needList中 distanceFromDes一定是-1

                        needNode.distanceFromDes = distanceFromDes

                        needList.append(needNode)

                    # print(needNode.y,needNode.x,needNode.distanceFromDes)

        # needList 装满了 addedList排空了

        addedList = needList

        for node in addedList:

            node.added = True

        needList = list()

    return map

# # 添加起点,并生成起点到终点的节点队列

def GetMinDistanceNodeList(map, mapSize, oriIndex, desIndex):

    for ls in map:

        for node in ls:

            node.added = False

    openedList = list()

    node = map[oriIndex[0]][oriIndex[1]]

    node.distanceFromOri = 0

    node.allDistance = 0

    openedList.append(node)

    node.added = True

    while len(openedList) != 0:

        # 从openlist拿出一个节点

        node = openedList.pop(0)

        # 标示为close过

        node.closed = True

        if node.y == desIndex[0] and node.x == desIndex[1]:

            finalListNeedReverse = list()

            while node != None:

                finalListNeedReverse.append(node)

                node = node.parent

            finalListNeedReverse.reverse()

            return finalListNeedReverse

        neighboursList = list()

        y = node.y

        x = node.x

        parentDistanceFromOri = node.distanceFromOri

        for needNodey in (y + 1, y, y - 1):

            if needNodey < 0 or needNodey >= mapSize[0]:

                continue

            for needNodex in (x + 1, x, x - 1):

                if needNodex < 0 or needNodex >= mapSize[1]:

                    continue

                needNode = map[needNodey][needNodex]  # 坐标不出界

                if needNode.unable == True or needNode.closed == True or needNode.added == True:

                    continue  # 坐标也满足add的要求

                yOffset = needNodey - y

                xOffset = needNodex - x

                allOffset = yOffset + xOffset

                if allOffset == 1 or allOffset == -1:

                    distanceFromOri = parentDistanceFromOri + 1

                elif allOffset == -2 or allOffset == 0 or allOffset == 2:

                    distanceFromOri = parentDistanceFromOri + 1.4

                else:

                    print("终点代价计算错误")

                if needNode in neighboursList:  # 设置needNode的距离,要求最小

                    if distanceFromOri < needNode.distanceFromOri:

                        needNode.distanceFromOri = distanceFromOri

                else:  # needNode 不在needList中 distanceFromDes一定是-1

                    needNode.distanceFromOri = distanceFromOri

                    neighboursList.append(needNode)  # 距离计算完成

        for needNode in neighboursList:  # 开始添加至openedList

            needNode.parent = node

            needNode.allDistance = needNode.distanceFromOri + needNode.distanceFromDes

            needNode.added = True

            openedList.append(needNode)

            # print(needNode.x,needNode.y,needNode.allDistance)

        openedList.sort(key=lambda x: x.allDistance)  # 最小距离的排在前边

    print("无路可循!")

    return None

# 打印具体的方向

def TestGetMinDistanceNodeList(map, mapSize, oriIndex, desIndex):

    finalList = GetMinDistanceNodeList(

        map, mapSize, oriIndex, desIndex)  # 添加起点,并生成起点到终点的节点队列

    # 行动路线

    directions = (('↘', '↓', '↙'), ('→', "S", '←'), ('↗', '↑', '↖'))

    print('行动路线示意')

    for nodeRow in map:

        for node in nodeRow:

            if node in finalList:

                #print('  *  ',end ='')

                parent = node.parent

                if parent != None:

                    if node.y != desIndex[0] or node.x != desIndex[1]:

                        (y, x) = (parent.y - node.y+1, parent.x - node.x+1)

                        print('  '+directions[y][x]+'  ', end='')

                    else:

                        print('Final', end='')

                else:

                    print('Start', end='')

            else:

                if node.allDistance != -1:

                    print('{:^4.1f}'.format(node.allDistance), end=" ")

                else:

                    print('  X  ', end=" ")

        print()

    print()

def aStartGo(startNode=(4,6),endNode=(0,0)):

    """

    两个参数分别为起点和终点节点的坐标

    """

    m = 5  # 设置地图的长

    n = 7  # 设置地图的宽


    map = GenerateMap(m, n)  # 2.生成地图节点 

    # for nodeRow in map:

    #    for node in nodeRow:

    #        print("(",node.y,",",node.x,")",end=" ")


    # 放的障碍物位置       

    obstacleList = [(4, 3),(3,3),(2,3),(0,1),(1,1),(2,1)] 


    map = SetUnableMapNode(map, obstacleList)  # 在地图中添加障碍


    # 添加终点,并计算节点与终点的距离(代价)

    GetDistanceFromDes(map, (m, n), endNode) 

    print("-------------------------------------")

    # 先打印一下所有节点的到终点的代价,总所周知终点自己到自己是没有代价的,上下左右的一次代价为10

    for nodeRow in map:

        for node in nodeRow:

            if node.distanceFromDes != -1:

                print('{:^5.1f}'.format(node.distanceFromDes), end=" ")

                #print('{:.2f}'.format(node.distanceFromDes), end=" ")

            else:

                print('  X  ', end=" ")

        print()


    TestGetMinDistanceNodeList(

        map, (m, n), startNode, endNode)  # 终点距离测试完了,演示行动路线

#运行a*

aStartGo()

我的示例代码中,地图是 5 * 7 的,其中 startNode=(4,6),endNode=(0,0)

看看我打印的结果把


最后附上一个视频https://video.tudou.com/v/XNDE1NjMyMTUwMA==.html

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,552评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,666评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,519评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,180评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,205评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,344评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,781评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,449评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,635评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,467评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,515评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,217评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,775评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,851评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,084评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,637评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,204评论 2 341

推荐阅读更多精彩内容