によって生成されたタイルを追跡するのに苦労していgetAdjacentTiles(..)
ます。getAdjacentTiles
以下の A* 実装のパフォーマンスの問題は、以前に見たタイルを追跡していないNode
ことopenSet
ですclosedSet
。これまでに作成されたすべてのタイルとして Node オブジェクトのリストを使用し、それを に渡して、getAdjacentTiles
生成されたタイルが既にアクセスされているかどうかを判断することにしました。
私の問題は、これらのタイルを適切に追跡できないように見えることです。私のA *がその場所に到達するために約4回以上の動きをする必要があるときはいつでも、end
それは失敗します. これは、私がどのようにタイルを追跡しようとしているかに関係していると確信しています(これもまたNode
、訪問されたものです)問題はpythonの知識にあると思わなければなり.apped(tile)
ません。セットgetAdjacentTiles(...)
をループするときallTiles
?
エラーが発生しました (場合によっては、A* パスが約 3 ステップよりも長い場合のみ..)
File "P3.py", line 67, in aStar
openSet.remove(curNode)
KeyError: <__main__.Node instance at 0xa39edcc>
ソース
#Perform an A* search to find the best path to the dirt
def aStar(self, current, end):
openSet = set()
openHeap = []
closedSet = set()
allTiles = set()
curNode = Node(0, current, self.manHatDist(current, end))
openSet.add(curNode)
allTiles.add(curNode)
openHeap.append((curNode.cost,curNode))
while openSet:
curNode = heapq.heappop(openHeap)[1]
if curNode.pos == end:
return self.getDirections(curNode)
openSet.remove(curNode)
closedSet.add(curNode)
adjNodes = self.getAdjacentNodes(curNode.pos, allTiles)
for tile in adjNodes:
t = tile
if t not in closedSet:
cost = (curNode.cost - self.manHatDist(curNode.pos, end)
+ self.euclidDist(curNode.pos, current)
+ self.manHatDist(t.pos, end))
if t not in openSet or cost < t.cost:
t.parent = curNode
t.cost = cost
openSet.add(t)
heapq.heappush(openHeap, (cost,t))
allTiles.add(t)
return []
#Get the moves made to get to this endNode
def getDirections(self, endNode):
moves = []
tmpNode = endNode
while tmpNode.parent is not None:
moves.append(tmpNode.value)
tmpNode = tmpNode.parent
moves.reverse()
return moves
#Return all possible moves from given tile as Node objects
def getAdjacentNodes(self, curPos, allTiles):
allMoves = ['North','South','East','West']
posMoves = []
for direction in allMoves:
if(self.canMove(direction, curPos)):
posMoves.append(Node(direction, self.getLocIfMove(curPos, direction)))
retNodes = []
for posLocNode in posMoves:
set = False
for tile in allTiles:
if(posLocNode.pos == tile.pos):
set = True
retNodes.append(tile)
if(not set):
retNodes.append(posLocNode)
return retNodes