python實現(xiàn)A-尋路算法

第python實現(xiàn)A*尋路算法有一點需要注意，如果開始節(jié)點到目標(biāo)節(jié)點實際是不連通的，即無法從開始節(jié)點移動到目標(biāo)節(jié)點，那算法在第1步判斷獲取到的節(jié)點n為空，就會退出

關(guān)鍵代碼介紹

保存基本信息的地圖類

地圖類用于隨機生成一個供尋路算法工作的基礎(chǔ)地圖信息

先創(chuàng)建一個map類，初始化參數(shù)設(shè)置地圖的長度和寬度，并設(shè)置保存地圖信息的二維數(shù)據(jù)map的值為0，值為0表示能移動到該節(jié)點。

classMap():

def__init__(self,width,height):

self.width=width

self.height=height

self.map=[[0forxinrange(self.width)]foryinrange(self.height)]

在map類中添加一個創(chuàng)建不能通過節(jié)點的函數(shù)，節(jié)點值為1表示不能移動到該節(jié)點。

defcreateBlock(self,block_num):

foriinrange(block_num):

x,y=(randint(0,self.width-1),randint(0,self.height-1))

self.map[y][x]=1

在map類中添加一個顯示地圖的函數(shù)，可以看到，這邊只是簡單的打印出所有節(jié)點的值，值為0或1的意思上面已經(jīng)說明，在后面顯示尋路算法結(jié)果時，會使用到值2，表示一條從開始節(jié)點到目標(biāo)節(jié)點的路徑。

defshowMap(self):

print("+"*(3*self.width+2))

forrowinself.map:

s='+'

forentryinrow:

s+=''+str(entry)+''

s+='+'

print(s)

print("+"*(3*self.width+2))

添加一個隨機獲取可移動節(jié)點的函數(shù)

defgeneratePos(self,rangeX,rangeY):

x,y=(randint(rangeX[0],rangeX[1]),randint(rangeY[0],rangeY[1]))

whileself.map[y][x]==1:

x,y=(randint(rangeX[0],rangeX[1]),randint(rangeY[0],rangeY[1]))

return(x,y)

搜索到的節(jié)點類

每一個搜索到將到添加到OPEN集的節(jié)點，都會創(chuàng)建一個下面的節(jié)點類，保存有entry的位置信息（x，y），計算得到的G值和F值，和該節(jié)點的父節(jié)點（pre_entry）。

classSearchEntry():

def__init__(self,x,y,g_cost,f_cost=0,pre_entry=None):

self.x=x

self.y=y

#costmoveformstartentrytothisentry

self.g_cost=g_cost

self.f_cost=f_cost

self.pre_entry=pre_entry

defgetPos(self):

return(self.x,self.y)

算法主函數(shù)介紹

下面就是上面算法主循環(huán)介紹的代碼實現(xiàn)，OPEN集和CLOSED集的數(shù)據(jù)結(jié)構(gòu)使用了字典，在一般情況下，查找，添加和刪除節(jié)點的時間復(fù)雜度為O(1),遍歷的時間復(fù)雜度為O(n),n為字典中對象數(shù)目。

defAStarSearch(map,source,dest):

openlist={}

closedlist={}

location=SearchEntry(source[0],source[1],0.0)

dest=SearchEntry(dest[0],dest[1],0.0)

openlist[source]=location

whileTrue:

location=getFastPosition(openlist)

iflocationisNone:

#notfoundvalidpath

print("can'tfindvalidpath")

break;

iflocation.x==dest.xandlocation.y==dest.y:

break

closedlist[location.getPos()]=location

openlist.pop(location.getPos())

addAdjacentPositions(map,location,dest,openlist,closedlist)

#markthefoundpathatthemap

whilelocationisnotNone:

map.map[location.y][location.x]=2

location=location.pre_entry

我們按照算法主循環(huán)的實現(xiàn)來一個個講解用到的函數(shù)。

下面函數(shù)就是從OPEN集中獲取一個F值最小的節(jié)點，如果OPEN集會空，則返回None。

#findaleastcostpositioninopenlist,returnNoneifopenlistisempty

defgetFastPosition(openlist):

fast=None

forentryinopenlist.values():

iffastisNone:

fast=entry

eliffast.f_costentry.f_cost:

fast=entry

returnfast

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

#addavailableadjacentpositions

defaddAdjacentPositions(map,location,dest,openlist,closedlist):

poslist=getPositions(map,location)

forposinposlist:

#ifpositionisalreadyinclosedlist,donothing

ifisInList(closedlist,pos)isNone:

findEntry=isInList(openlist,pos)

h_cost=calHeuristic(pos,dest)

g_cost=location.g_cost+getMoveCost(location,pos)

iffindEntryisNone:

#ifpositionisnotinopenlist,addittoopenlist

openlist[pos]=SearchEntry(pos[0],pos[1],g_cost,g_cost+h_cost,location)

eliffindEntry.g_costg_cost:

#ifpositionisinopenlistandcostislargerthancurrentone,

#thenupdatecostandpreviousposition

findEntry.g_co