我正在尝试创建 A Star 算法并将其应用于贪吃蛇游戏。我遇到的问题是我从来没有在窗口上绘制任何东西,因为它永远不会到达该代码。尝试在方法 run() 中计算路径时卡住。具体来说,开集永远不会变为零,它会添加已经存在的节点。
我试过将各种列表打印到控制台,但我发现的只是“current”在随机点重复图 block ,并且“openSet”和“closedSet”随着这些重复的图 block 继续变大。我我还测试了我的 Tile 对象、我的 contains 方法和我的 giveNeighbors 方法,所有这些似乎都有效并给出了预期的结果。另外,作为引用,我将使用此处找到的伪代码:https://en.wikipedia.org/wiki/A*_search_algorithm
import Tile
import pygame
class A_star:
def __init__(self):
self.closedSet = []
self.openSet = []
def run(self, start, goal):
self.closedSet = []
self.openSet = [start]
path = []
#THE LENGTH OF OPEN SET NEVER GOES TO ZERO!
while len(self.openSet) > 0:
#Set current to node in openSet with lowest fscore
current = self.openSet[0]
currindex = 0
for i, node in enumerate(self.openSet):
if node.fScore < current.fScore:
current = node
currindex = i
#romove from Open set and add to closed
self.openSet.pop(currindex)
self.closedSet.append(current)
#Reached the end
if current.tileEquals(goal):
print("Done")
while current != None:
path.append(current)
current = current.cameFrom
return path[::-1]
neighbors = self.giveNeighbors(current)
print("Current: " + str(current.posx) + ", " + str(current.posy))
print("Neighbors")
for i in neighbors:
print(str(i.posx) + ", " + str(i.posy))
for i in neighbors:
#if neighbor is already checked, then ignore it.
if not self.contains(self.closedSet, i):
#Distance between start adn neighbor. tenative gscore
tempGScore = current.gScore + 1
#if neighbor is not in openset. Discovered a new node!
if not self.contains(self.openSet, i):
self.openSet.append(i)
elif tempGScore < i.gScore:
i.gScore = tempGScore
i.cameFrom = current
i.fScore = i.gScore + self.heuristicCost(i, goal) #f = g + h
print("Open:")
for i in self.openSet:
print(str(i.posx) + ", " + str(i.posy))
print("Closed")
for i in self.closedSet:
print(str(i.posx) + ", " + str(i.posy))
#Calculates the estimated distance from a given tile to end
def heuristicCost(self, neighbor, goal):
#The snake never goes diagonal, therefore calculate manhatten distance
distance = abs(neighbor.posx - goal.posx) + abs(neighbor.posy - goal.posy)
return distance
def giveNeighbors(self, current):
neighbors = []
if current.posx > 0:
neighbors.append(Tile(current.posx - 10, current.posy))
if current.posx < 200:
neighbors.append(Tile(current.posx + 10, current.posy))
if current.posy > 0:
neighbors.append(Tile(current.posx, current.posy - 10))
if current.posy < 200:
neighbors.append(Tile(current.posx, current.posy + 10))
return neighbors
def contains(self, s, tile):
for i in s:
if i.tileEquals(tile):
return True
else:
return False
def testAStar():
pygame.init()
window = pygame.display.set_mode((200, 200))
pygame.display.set_caption("AStar Test")
window.fill((255,255,255))
clock = pygame.time.Clock()
start = Tile(0, 0)
end = Tile(190, 190)
astar = A_star()
path = astar.run(start, end)
run = True
while run:
for event in pygame.event.get():
if event.type == pygame.QUIT:
run = False
pygame.draw.rect(window, (0, 255, 0), (start.posx, start.posy, 10, 10))
pygame.draw.rect(window, (255, 0, 0), (end.posx, end.posy, 10, 10))
for i in path:
pygame.draw.rect(window, (0, 0, 255), (i.posx, i.posy, 10, 10))
print("drew stuff")
pygame.display.update()
window.fill((255,255,255))
clock.tick(10)
pygame.quit()
if __name__== "__main__":
testAStar()
class Tile:
def __init__(self, x, y):
self.posx = x
self.posy = y
self.fScore = 0
self.gScore = 0
self.cameFrom = None
def nextTileRight(self):
self.posx = self.posx + 10
def nextTileDown(self):
self.posy = self.posy + 10
def nextTileUp(self):
self.posy = self.posy - 10
def nextTileLeft(self):
self.posx = self.posx - 10
def tileEquals(self, t):
if self.posx == t.posx and self.posy == t.posy:
return True
else:
return False
预期的结果应该是在窗口上绘制一条从起始节点到结束节点的非对角线路径。 (另外,如果我的缩进不正确,我很抱歉。我对这个网站还是很陌生)
最佳答案
我不确定您为什么要检查 openSets == 0 ,您正在寻找 currentNode = destination 或所有邻居都已关闭,这意味着所有内容都已检查但未找到路径。
关于python - 为什么开集永远不会变为 0?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53983917/