目錄A* 算法簡介關(guān)鍵代碼介紹保存基本信息的地圖類搜索到的節(jié)點(diǎn)類算法主函數(shù)介紹代碼的初始化完整代碼A* 算法簡介

A* 算法需要維護(hù)兩個(gè)數(shù)據(jù)結(jié)構(gòu)：OPEN 集和 CLOSED 集。OPEN 集包含所有已搜索到的待檢測節(jié)點(diǎn)。初始狀態(tài)，OPEN集僅包含一個(gè)元素：開始節(jié)點(diǎn)。CLOSED集包含已檢測的節(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)越來越遠(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)）來檢測。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集中，表示它已被檢測過，則無需再添加。 鄰節(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í)際是不連通的，即無法從開始節(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è)置地圖的長度和寬度，并設(shè)置保存地圖信息的二維數(shù)據(jù)map的值為0， 值為0表示能移動(dòng)到該節(jié)點(diǎn)。

class Map():def __init__(self, width, height):self.width = widthself.height = heightself.map = [[0 for x in range(self.width)] for y in range(self.height)]

在map類中添加一個(gè)創(chuàng)建不能通過節(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é)點(diǎn)的值，值為0或1的意思上面已經(jīng)說明，在后面顯示尋路算法結(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 = xself.y = y# cost move form start entry to this entryself.g_cost = g_costself.f_cost = f_costself.pre_entry = pre_entrydef 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] = locationwhile True:location = getFastPosition(openlist)if location is None:# not found valid pathprint('can’t find valid path')break;if location.x == dest.x and location.y == dest.y:breakclosedlist[location.getPos()] = locationopenlist.pop(location.getPos())addAdjacentPositions(map, location, dest, openlist, closedlist)#mark the found path at the mapwhile location is not None:map.map[location.y][location.x] = 2location = location.pre_entry

我們按照算法主循環(huán)的實(shí)現(xiàn)來一個(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 emptydef getFastPosition(openlist):fast = Nonefor entry in openlist.values():if fast is None:fast = entryelif fast.f_cost > entry.f_cost:fast = entryreturn fast

addAdjacentPositions 函數(shù)對(duì)應(yīng)算法主函數(shù)循環(huán)介紹中的嘗試添加節(jié)點(diǎn)n的所有鄰節(jié)點(diǎn)n’。

# add available adjacent positionsdef addAdjacentPositions(map, location, dest, openlist, closedlist):poslist = getPositions(map, location)for pos in poslist:# if position is already in closedlist, do nothingif 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 openlistopenlist[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 positionfindEntry.g_cost = g_costfindEntry.f_cost = g_cost + h_costfindEntry.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 Nonereturn (x, y)def getPositions(map, location):# use four ways or eight ways to moveoffsets = [(-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 listdef isInList(list, pos):if pos in list:return list[pos]return None

calHeuristic 函數(shù)簡單得使用了曼哈頓距離，這個(gè)后續(xù)可以進(jìn)行優(yōu)化。getMoveCost 函數(shù)根據(jù)是否是斜向移動(dòng)來計(jì)算消耗（斜向就是2的開根號(hào)，約等于1.4）

# imporve the heuristic distance more precisely in futuredef 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.4else:return 1代碼的初始化

可以調(diào)整地圖的長度，寬度和不可移動(dòng)節(jié)點(diǎn)的數(shù)目。可以調(diào)整開始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的取值范圍。

WIDTH = 10HEIGHT = 10BLOCK_NUM = 15map = 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 randintclass SearchEntry():def __init__(self, x, y, g_cost, f_cost=0, pre_entry=None):self.x = xself.y = y# cost move form start entry to this entryself.g_cost = g_costself.f_cost = f_costself.pre_entry = pre_entrydef getPos(self):return (self.x, self.y)class Map():def __init__(self, width, height):self.width = widthself.height = heightself.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] = 1def 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 Nonereturn (x, y)def getPositions(map, location):# use four ways or eight ways to moveoffsets = [(-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 futuredef 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.4else:return 1# check if the position is in listdef isInList(list, pos):if pos in list:return list[pos]return None# add available adjacent positionsdef addAdjacentPositions(map, location, dest, openlist, closedlist):poslist = getPositions(map, location)for pos in poslist:# if position is already in closedlist, do nothingif 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 openlistopenlist[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 positionfindEntry.g_cost = g_costfindEntry.f_cost = g_cost + h_costfindEntry.pre_entry = location# find a least cost position in openlist, return None if openlist is emptydef getFastPosition(openlist):fast = Nonefor entry in openlist.values():if fast is None:fast = entryelif fast.f_cost > entry.f_cost:fast = entryreturn fastopenlist = {}closedlist = {}location = SearchEntry(source[0], source[1], 0.0)dest = SearchEntry(dest[0], dest[1], 0.0)openlist[source] = locationwhile True:location = getFastPosition(openlist)if location is None:# not found valid pathprint('can’t find valid path')break;if location.x == dest.x and location.y == dest.y:breakclosedlist[location.getPos()] = locationopenlist.pop(location.getPos())addAdjacentPositions(map, location, dest, openlist, closedlist)#mark the found path at the mapwhile location is not None:map.map[location.y][location.x] = 2location = location.pre_entryWIDTH = 10HEIGHT = 10BLOCK_NUM = 15map = 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)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！