个人中心
gpt4 book ai didi

python实现A*寻路算法

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 25 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章python实现A*寻路算法由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

a* 算法简介

a* 算法需要维护两个数据结构：open 集和 closed 集。open 集包含所有已搜索到的待检测节点。初始状态，open集仅包含一个元素：开始节点。closed集包含已检测的节点。初始状态，closed集为空。每个节点还包含一个指向父节点的指针，以确定追踪关系.

a* 算法会给每个搜索到的节点计算一个g+h 的和值f:

  • f = g + h
  • g：是从开始节点到当前节点的移动量。假设开始节点到相邻节点的移动量为1，该值会随着离开始点越来越远而增大。
  • h：是从当前节点到目标节点的移动量估算值。
    • 如果允许向4邻域的移动，使用曼哈顿距离。
    • 如果允许向8邻域的移动，使用对角线距离。

算法有一个主循环，重复下面步骤直到到达目标节点： 1 每次从open集中取一个最优节点n（即f值最小的节点）来检测。 2 将节点n从open集中移除，然后添加到closed集中。 3 如果n是目标节点，那么算法结束。 4 否则尝试添加节点n的所有邻节点n'.

  • 邻节点在closed集中，表示它已被检测过，则无需再添加。
  • 邻节点在open集中：
    • 如果重新计算的g值比邻节点保存的g值更小，则需要更新这个邻节点的g值和f值，以及父节点；
    • 否则不做操作
  • 否则将该邻节点加入open集，设置其父节点为n，并设置它的g值和f值。

有一点需要注意，如果开始节点到目标节点实际是不连通的，即无法从开始节点移动到目标节点，那算法在第1步判断获取到的节点n为空，就会退出 。

关键代码介绍

保存基本信息的地图类

地图类用于随机生成一个供寻路算法工作的基础地图信息 。

先创建一个map类， 初始化参数设置地图的长度和宽度，并设置保存地图信息的二维数据map的值为0， 值为0表示能移动到该节点.

?
1
2
3
4
5
class map ():
     def __init__( self , width, height):
         self .width = width
         self .height = height
         self . map = [[ 0 for x in range ( self .width)] for y in range ( self .height)]

在map类中添加一个创建不能通过节点的函数，节点值为1表示不能移动到该节点.

?
1
2
3
4
def createblock( self , block_num):
     for i in range (block_num):
         x, y = (randint( 0 , self .width - 1 ), randint( 0 , self .height - 1 ))
         self . map [y][x] = 1

在map类中添加一个显示地图的函数，可以看到，这边只是简单的打印出所有节点的值，值为0或1的意思上面已经说明，在后面显示寻路算法结果时，会使用到值2，表示一条从开始节点到目标节点的路径.

?
1
2
3
4
5
6
7
8
9
def showmap( self ):
     print ( "+" * ( 3 * self .width + 2 ))
     for row in self . map :
         s = '+'
         for entry in row:
             s + = ' ' + str (entry) + ' '
         s + = '+'
         print (s)
     print ( "+" * ( 3 * self .width + 2 ))

添加一个随机获取可移动节点的函数 。

?
1
2
3
4
5
def generatepos( self , rangex, rangey):
     x, y = (randint(rangex[ 0 ], rangex[ 1 ]), randint(rangey[ 0 ], rangey[ 1 ]))
     while self . map [y][x] = = 1 :
         x, y = (randint(rangex[ 0 ], rangex[ 1 ]), randint(rangey[ 0 ], rangey[ 1 ]))
     return (x , y)

搜索到的节点类

每一个搜索到将到添加到open集的节点，都会创建一个下面的节点类，保存有entry的位置信息（x，y），计算得到的g值和f值，和该节点的父节点（pre_entry）.

?
1
2
3
4
5
6
7
8
9
10
11
class searchentry():
     def __init__( self , x, y, g_cost, f_cost = 0 , pre_entry = none):
         self .x = x
         self .y = y
         # cost move form start entry to this entry
         self .g_cost = g_cost
         self .f_cost = f_cost
         self .pre_entry = pre_entry
    
     def getpos( self ):
         return ( self .x, self .y)

算法主函数介绍

下面就是上面算法主循环介绍的代码实现，open集和closed集的数据结构使用了字典，在一般情况下，查找，添加和删除节点的时间复杂度为o(1), 遍历的时间复杂度为o(n), n为字典中对象数目.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def astarsearch( map , source, dest):
     ...
     openlist = {}
     closedlist = {}
     location = searchentry(source[ 0 ], source[ 1 ], 0.0 )
     dest = searchentry(dest[ 0 ], dest[ 1 ], 0.0 )
     openlist[source] = location
     while true:
         location = getfastposition(openlist)
         if location is none:
             # not found valid path
             print ( "can't find valid path" )
             break ;
        
         if location.x = = dest.x and location.y = = dest.y:
             break
        
         closedlist[location.getpos()] = location
         openlist.pop(location.getpos())
         addadjacentpositions( map , location, dest, openlist, closedlist)
    
     #mark the found path at the map
     while location is not none:
         map . map [location.y][location.x] = 2
         location = location.pre_entry

我们按照算法主循环的实现来一个个讲解用到的函数。 下面函数就是从open集中获取一个f值最小的节点，如果open集会空，则返回none.

?
1
2
3
4
5
6
7
8
9
# find a least cost position in openlist, return none if openlist is empty
def getfastposition(openlist):
     fast = none
     for entry in openlist.values():
         if fast is none:
             fast = entry
         elif fast.f_cost > entry.f_cost:
             fast = entry
     return fast

addadjacentpositions 函数对应算法主函数循环介绍中的尝试添加节点n的所有邻节点n'.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# add available adjacent positions
def addadjacentpositions( map , location, dest, openlist, closedlist):
     poslist = getpositions( map , location)
     for pos in poslist:
         # if position is already in closedlist, do nothing
         if isinlist(closedlist, pos) is none:
             findentry = isinlist(openlist, pos)
             h_cost = calheuristic(pos, dest)
             g_cost = location.g_cost + getmovecost(location, pos)
             if findentry is none :
                 # if position is not in openlist, add it to openlist
                 openlist[pos] = searchentry(pos[ 0 ], pos[ 1 ], g_cost, g_cost + h_cost, location)
             elif findentry.g_cost > g_cost:
                 # if position is in openlist and cost is larger than current one,
                 # then update cost and previous position
                 findentry.g_cost = g_cost
                 findentry.f_cost = g_cost + h_cost
                 findentry.pre_entry = location

getpositions 函数获取到所有能够移动的节点，这里提供了2种移动的方式:

  • 允许上，下，左，右 4邻域的移动
  • 允许上，下，左，右，左上，右上，左下，右下 8邻域的移动
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def getnewposition( map , locatioin, offset):
     x,y = (location.x + offset[ 0 ], location.y + offset[ 1 ])
     if x < 0 or x > = map .width or y < 0 or y > = map .height or map . map [y][x] = = 1 :
         return none
     return (x, y)
    
def getpositions( map , location):
     # use four ways or eight ways to move
     offsets = [( - 1 , 0 ), ( 0 , - 1 ), ( 1 , 0 ), ( 0 , 1 )]
     #offsets = [(-1,0), (0, -1), (1, 0), (0, 1), (-1,-1), (1, -1), (-1, 1), (1, 1)]
     poslist = []
     for offset in offsets:
         pos = getnewposition( map , location, offset)
         if pos is not none:        
             poslist.append(pos)
     return poslist

isinlist 函数判断节点是否在open集 或closed集中 。

?
1
2
3
4
5
# check if the position is in list
def isinlist( list , pos):
     if pos in list :
         return list [pos]
     return none

calheuristic 函数简单得使用了曼哈顿距离，这个后续可以进行优化。 getmovecost 函数根据是否是斜向移动来计算消耗（斜向就是2的开根号，约等于1.4） 。

?
1
2
3
4
5
6
7
8
9
# imporve the heuristic distance more precisely in future
def calheuristic(pos, dest):
     return abs (dest.x - pos[ 0 ]) + abs (dest.y - pos[ 1 ])
    
def getmovecost(location, pos):
     if location.x ! = pos[ 0 ] and location.y ! = pos[ 1 ]:
         return 1.4
     else :
         return 1

代码的初始化

可以调整地图的长度，宽度和不可移动节点的数目。 可以调整开始节点和目标节点的取值范围.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
width = 10
height = 10
block_num = 15
map = map (width, height)
map .createblock(block_num)
map .showmap()
 
source = map .generatepos(( 0 ,width / / 3 ),( 0 ,height / / 3 ))
dest = map .generatepos((width / / 2 ,width - 1 ),(height / / 2 ,height - 1 ))
print ( "source:" , source)
print ( "dest:" , dest)
astarsearch( map , source, dest)
map .showmap()

执行的效果图如下，第一个表示随机生成的地图，值为1的节点表示不能移动到该节点。 第二个图中值为2的节点表示找到的路径.

python实现A*寻路算法

完整代码

使用python3.7编译 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
from random import randint
 
class searchentry():
     def __init__( self , x, y, g_cost, f_cost = 0 , pre_entry = none):
         self .x = x
         self .y = y
         # cost move form start entry to this entry
         self .g_cost = g_cost
         self .f_cost = f_cost
         self .pre_entry = pre_entry
    
     def getpos( self ):
         return ( self .x, self .y)
 
class map ():
     def __init__( self , width, height):
         self .width = width
         self .height = height
         self . map = [[ 0 for x in range ( self .width)] for y in range ( self .height)]
    
     def createblock( self , block_num):
         for i in range (block_num):
             x, y = (randint( 0 , self .width - 1 ), randint( 0 , self .height - 1 ))
             self . map [y][x] = 1
    
     def generatepos( self , rangex, rangey):
         x, y = (randint(rangex[ 0 ], rangex[ 1 ]), randint(rangey[ 0 ], rangey[ 1 ]))
         while self . map [y][x] = = 1 :
             x, y = (randint(rangex[ 0 ], rangex[ 1 ]), randint(rangey[ 0 ], rangey[ 1 ]))
         return (x , y)
 
     def showmap( self ):
         print ( "+" * ( 3 * self .width + 2 ))
 
         for row in self . map :
             s = '+'
             for entry in row:
                 s + = ' ' + str (entry) + ' '
             s + = '+'
             print (s)
 
         print ( "+" * ( 3 * self .width + 2 ))
    
 
def astarsearch( map , source, dest):
     def getnewposition( map , locatioin, offset):
         x,y = (location.x + offset[ 0 ], location.y + offset[ 1 ])
         if x < 0 or x > = map .width or y < 0 or y > = map .height or map . map [y][x] = = 1 :
             return none
         return (x, y)
        
     def getpositions( map , location):
         # use four ways or eight ways to move
         offsets = [( - 1 , 0 ), ( 0 , - 1 ), ( 1 , 0 ), ( 0 , 1 )]
         #offsets = [(-1,0), (0, -1), (1, 0), (0, 1), (-1,-1), (1, -1), (-1, 1), (1, 1)]
         poslist = []
         for offset in offsets:
             pos = getnewposition( map , location, offset)
             if pos is not none:        
                 poslist.append(pos)
         return poslist
    
     # imporve the heuristic distance more precisely in future
     def calheuristic(pos, dest):
         return abs (dest.x - pos[ 0 ]) + abs (dest.y - pos[ 1 ])
        
     def getmovecost(location, pos):
         if location.x ! = pos[ 0 ] and location.y ! = pos[ 1 ]:
             return 1.4
         else :
             return 1
 
     # check if the position is in list
     def isinlist( list , pos):
         if pos in list :
             return list [pos]
         return none
    
     # add available adjacent positions
     def addadjacentpositions( map , location, dest, openlist, closedlist):
         poslist = getpositions( map , location)
         for pos in poslist:
             # if position is already in closedlist, do nothing
             if isinlist(closedlist, pos) is none:
                 findentry = isinlist(openlist, pos)
                 h_cost = calheuristic(pos, dest)
                 g_cost = location.g_cost + getmovecost(location, pos)
                 if findentry is none :
                     # if position is not in openlist, add it to openlist
                     openlist[pos] = searchentry(pos[ 0 ], pos[ 1 ], g_cost, g_cost + h_cost, location)
                 elif findentry.g_cost > g_cost:
                     # if position is in openlist and cost is larger than current one,
                     # then update cost and previous position
                     findentry.g_cost = g_cost
                     findentry.f_cost = g_cost + h_cost
                     findentry.pre_entry = location
    
     # find a least cost position in openlist, return none if openlist is empty
     def getfastposition(openlist):
         fast = none
         for entry in openlist.values():
             if fast is none:
                 fast = entry
             elif fast.f_cost > entry.f_cost:
                 fast = entry
         return fast
 
     openlist = {}
     closedlist = {}
     location = searchentry(source[ 0 ], source[ 1 ], 0.0 )
     dest = searchentry(dest[ 0 ], dest[ 1 ], 0.0 )
     openlist[source] = location
     while true:
         location = getfastposition(openlist)
         if location is none:
             # not found valid path
             print ( "can't find valid path" )
             break ;
        
         if location.x = = dest.x and location.y = = dest.y:
             break
        
         closedlist[location.getpos()] = location
         openlist.pop(location.getpos())
         addadjacentpositions( map , location, dest, openlist, closedlist)
        
     #mark the found path at the map
     while location is not none:
         map . map [location.y][location.x] = 2
         location = location.pre_entry  
 
    
width = 10
height = 10
block_num = 15
map = map (width, height)
map .createblock(block_num)
map .showmap()
 
source = map .generatepos(( 0 ,width / / 3 ),( 0 ,height / / 3 ))
dest = map .generatepos((width / / 2 ,width - 1 ),(height / / 2 ,height - 1 ))
print ( "source:" , source)
print ( "dest:" , dest)
astarsearch( map , source, dest)
map .showmap()

到此这篇关于python实现a*寻路算法的文章就介绍到这了,更多相关python a*寻路算法内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。

原文链接：https://blog.csdn.net/marble_xu/article/details/87882921 。

最后此篇关于python实现A*寻路算法的文章就讲到这里了,如果你想了解更多关于python实现A*寻路算法的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： Python OpenCV实现传统图片格式与base64转换
文章推荐： 一篇文章带你搞懂Map接口、HashMap集合
文章推荐： 浅析 Kubelet 驱逐机制
文章推荐： 后端视野学 Webpack ，文武双全？
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com