python - 为什么开集永远不会变为 0？

Question

我正在尝试创建 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

预期的结果应该是在窗口上绘制一条从起始节点到结束节点的非对角线路径。 (另外，如果我的缩进不正确，我很抱歉。我对这个网站还是很陌生)

Answer 1

我不确定您为什么要检查 openSets == 0 ，您正在寻找 currentNode = destination 或所有邻居都已关闭，这意味着所有内容都已检查但未找到路径。