python實(shí)現(xiàn)A*尋路算法
A* 算法簡(jiǎn)介
A* 算法需要維護(hù)兩個(gè)數(shù)據(jù)結(jié)構(gòu)：OPEN 集和 CLOSED 集。OPEN 集包含所有已搜索到的待檢測(cè)節(jié)點(diǎn)。初始狀態(tài)，OPEN集僅包含一個(gè)元素：開始節(jié)點(diǎn)。CLOSED集包含已檢測(cè)的節(jié)點(diǎn)。初始狀態(tài)，CLOSED集為空。每個(gè)節(jié)點(diǎn)還包含一個(gè)指向父節(jié)點(diǎn)的指針，以確定追蹤關(guān)系。
A* 算法會(huì)給每個(gè)搜索到的節(jié)點(diǎn)計(jì)算一個(gè)G+H 的和值F：
- F = G + H
- G：是從開始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的移動(dòng)量。假設(shè)開始節(jié)點(diǎn)到相鄰節(jié)點(diǎn)的移動(dòng)量為1，該值會(huì)隨著離開始點(diǎn)越來(lái)越遠(yuǎn)而增大。
- H：是從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的移動(dòng)量估算值。
- 如果允許向4鄰域的移動(dòng)，使用曼哈頓距離。
- 如果允許向8鄰域的移動(dòng)，使用對(duì)角線距離。
算法有一個(gè)主循環(huán)，重復(fù)下面步驟直到到達(dá)目標(biāo)節(jié)點(diǎn)：
1 每次從OPEN集中取一個(gè)最優(yōu)節(jié)點(diǎn)n（即F值最小的節(jié)點(diǎn)）來(lái)檢測(cè)。
2 將節(jié)點(diǎn)n從OPEN集中移除，然后添加到CLOSED集中。
3 如果n是目標(biāo)節(jié)點(diǎn)，那么算法結(jié)束。
4 否則嘗試添加節(jié)點(diǎn)n的所有鄰節(jié)點(diǎn)n'。
- 鄰節(jié)點(diǎn)在CLOSED集中，表示它已被檢測(cè)過(guò)，則無(wú)需再添加。
- 鄰節(jié)點(diǎn)在OPEN集中：
- 如果重新計(jì)算的G值比鄰節(jié)點(diǎn)保存的G值更小，則需要更新這個(gè)鄰節(jié)點(diǎn)的G值和F值，以及父節(jié)點(diǎn)；
- 否則不做操作
- 否則將該鄰節(jié)點(diǎn)加入OPEN集，設(shè)置其父節(jié)點(diǎn)為n，并設(shè)置它的G值和F值。
有一點(diǎn)需要注意，如果開始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)實(shí)際是不連通的，即無(wú)法從開始節(jié)點(diǎn)移動(dòng)到目標(biāo)節(jié)點(diǎn)，那算法在第1步判斷獲取到的節(jié)點(diǎn)n為空，就會(huì)退出
關(guān)鍵代碼介紹
保存基本信息的地圖類
地圖類用于隨機(jī)生成一個(gè)供尋路算法工作的基礎(chǔ)地圖信息
先創(chuàng)建一個(gè)map類， 初始化參數(shù)設(shè)置地圖的長(zhǎng)度和寬度，并設(shè)置保存地圖信息的二維數(shù)據(jù)map的值為0， 值為0表示能移動(dòng)到該節(jié)點(diǎn)。
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類中添加一個(gè)創(chuàng)建不能通過(guò)節(jié)點(diǎn)的函數(shù)，節(jié)點(diǎn)值為1表示不能移動(dòng)到該節(jié)點(diǎn)。
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類中添加一個(gè)顯示地圖的函數(shù)，可以看到，這邊只是簡(jiǎn)單的打印出所有節(jié)點(diǎn)的值，值為0或1的意思上面已經(jīng)說(shuō)明，在后面顯示尋路算法結(jié)果時(shí)，會(huì)使用到值2，表示一條從開始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑。
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))
添加一個(gè)隨機(jī)獲取可移動(dòng)節(jié)點(diǎn)的函數(shù)
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)
搜索到的節(jié)點(diǎn)類
每一個(gè)搜索到將到添加到OPEN集的節(jié)點(diǎn)，都會(huì)創(chuàng)建一個(gè)下面的節(jié)點(diǎn)類，保存有entry的位置信息（x，y），計(jì)算得到的G值和F值，和該節(jié)點(diǎn)的父節(jié)點(diǎn)（pre_entry）。
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)
算法主函數(shù)介紹
下面就是上面算法主循環(huán)介紹的代碼實(shí)現(xiàn)，OPEN集和CLOSED集的數(shù)據(jù)結(jié)構(gòu)使用了字典，在一般情況下，查找，添加和刪除節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1), 遍歷的時(shí)間復(fù)雜度為O(n), n為字典中對(duì)象數(shù)目。
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
我們按照算法主循環(huán)的實(shí)現(xiàn)來(lái)一個(gè)個(gè)講解用到的函數(shù)。
下面函數(shù)就是從OPEN集中獲取一個(gè)F值最小的節(jié)點(diǎn)，如果OPEN集會(huì)空，則返回None。
# 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 函數(shù)對(duì)應(yīng)算法主函數(shù)循環(huán)介紹中的嘗試添加節(jié)點(diǎn)n的所有鄰節(jié)點(diǎn)n'。
# 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 函數(shù)獲取到所有能夠移動(dòng)的節(jié)點(diǎn)，這里提供了2種移動(dòng)的方式：
- 允許上，下，左，右 4鄰域的移動(dòng)
- 允許上，下，左，右，左上，右上，左下，右下 8鄰域的移動(dòng)
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 函數(shù)判斷節(jié)點(diǎn)是否在OPEN集 或CLOSED集中
# check if the position is in list def isInList(list, pos): if pos in list: return list[pos] return None
calHeuristic 函數(shù)簡(jiǎn)單得使用了曼哈頓距離，這個(gè)后續(xù)可以進(jìn)行優(yōu)化。
getMoveCost 函數(shù)根據(jù)是否是斜向移動(dòng)來(lái)計(jì)算消耗（斜向就是2的開根號(hào)，約等于1.4）
# 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
代碼的初始化
可以調(diào)整地圖的長(zhǎng)度，寬度和不可移動(dòng)節(jié)點(diǎn)的數(shù)目。
可以調(diào)整開始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的取值范圍。
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()
執(zhí)行的效果圖如下，第一個(gè)表示隨機(jī)生成的地圖，值為1的節(jié)點(diǎn)表示不能移動(dòng)到該節(jié)點(diǎn)。
第二個(gè)圖中值為2的節(jié)點(diǎn)表示找到的路徑。
完整代碼
使用python3.7編譯
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()
到此這篇關(guān)于python實(shí)現(xiàn)A*尋路算法的文章就介紹到這了,更多相關(guān)python A*尋路算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
大家好，本篇文章主要講的是帶你了解Python語(yǔ)言的神奇世界，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
python實(shí)現(xiàn)教務(wù)管理系統(tǒng)
這篇文章主要介紹了python實(shí)現(xiàn)教務(wù)管理系統(tǒng)，實(shí)現(xiàn)了管理員、教職工、學(xué)生三種不同身份的操作，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-03-03
Python操作Redis數(shù)據(jù)庫(kù)的超詳細(xì)教程
大家應(yīng)該都知道redis是一個(gè)基于內(nèi)存的高效的鍵值型非關(guān)系數(shù)據(jù)庫(kù),下面這篇文章主要給大家介紹了關(guān)于Python操作Redis的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-06-06
Python實(shí)現(xiàn)的計(jì)算馬氏距離算法示例
這篇文章主要介紹了Python實(shí)現(xiàn)的計(jì)算馬氏距離算法,簡(jiǎn)單說(shuō)明了馬氏距離算法原理,并結(jié)合實(shí)例形式分析了Python實(shí)現(xiàn)與使用馬氏距離算法的相關(guān)操作技巧,需要的朋友可以參考下2018-04-04
python密碼學(xué)對(duì)稱和非對(duì)稱密碼教程
這篇文章主要為大家介紹了python密碼學(xué)對(duì)稱和非對(duì)稱密碼教程，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05
這篇文章主要介紹了Python中的異常處理簡(jiǎn)明介紹,本文講解了try-except檢測(cè)異常、上下文管理器(with…as…語(yǔ)句)、raise引發(fā)異常、斷言等內(nèi)容,需要的朋友可以參考下2015-04-04
這篇文章主要介紹了Python基礎(chǔ)之函數(shù)的定義與使用,結(jié)合實(shí)例形式分析了Python函數(shù)的定義、參數(shù)、變量作用域、返回值等相關(guān)概念與使用技巧,需要的朋友可以參考下2019-03-03
詳解如何使用Python實(shí)現(xiàn)復(fù)制粘貼的功能
pandas?里面有一個(gè)?pd.read_clipboard?函數(shù)，可以根據(jù)你復(fù)制的內(nèi)容生成DataFrame。本文就利用這個(gè)函數(shù)實(shí)現(xiàn)復(fù)制粘貼的功能，感興趣的可以了解一下2023-01-01
解決pycharm導(dǎo)入本地py文件時(shí),模塊下方出現(xiàn)紅色波浪線的問題
這篇文章主要介紹了解決pycharm導(dǎo)入本地py文件時(shí),模塊下方出現(xiàn)紅色波浪線的問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-06-06
Python 轉(zhuǎn)換時(shí)間戳為指定格式日期
這篇文章主要為大家介紹了Python轉(zhuǎn)換時(shí)間戳，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2021-12-12