Skip to main content
 首页 » 编程设计

Python A* 算法搜索不当

2025年05月04日8mfryf

所以我正在尝试编写 A* 算法的 Python 实现。我的算法可以毫不费力地找到通往目标的路径,但是当我让程序可视化封闭和开放列表时,我注意到封闭列表,只要障碍物有点复杂,就会膨胀成一个大而完美的菱形。换句话说,我的算法将节点添加到封闭列表中,这些节点与目标的距离比“预期”封闭列表的任何邻居都应该远得多。

为了说明,当封闭列表中的一个点距离目标 (2, 1) 远,但一堵墙挡住了去路时,算法将同时添加距离目标 (2, 2) 处的节点 (尝试越过墙)和 (3, 1) 处的算法远离目标...没有充分的理由,因为它显然更远。

我不确定我做错了什么。此距离计算旨在使用“曼哈顿方法”(对我的目的而言不完美,但它不应该导致此类问题),但其他方法继续提供相同的问题(或实际上更糟糕的问题)。

def distance(self, tile1, tile2): 
    self.xDist = abs(tile1.col * TILE_SIZE - tile2.col * TILE_SIZE) 
    self.yDist = abs(tile1.row * TILE_SIZE - tile2.row * TILE_SIZE) 
    self.totalDist = self.straightCost * (self.xDist + self.yDist) 
    return self.totalDist 

填充关闭列表的代码如下所示。在这里,.score 2是 H 值,使用上面显示的距离方法计算。

    while self.endTile not in self.openList: 
        self.smallestScore = MAX_DIST * 50 
        self.bestTile = None 
        for tile in self.openList: 
            if tile.score[2] <= self.smallestScore: 
                self.bestTile = tile 
                self.smallestScore = tile.score[2] 
        self.examine(self.bestTile) 

“检查”功能将检查过的图 block 添加到关闭列表并将其可行的邻居添加到打开列表,并且似乎工作正常。该算法似乎承认所有 H 分数为 X 的图 block (其中 X 根据目标所在迷宫的复杂性而变化)。

将其放慢到逐个节点的可视化基本上表明它正在填充一个大小为 X 的区域,并在迷宫的入口被填充击中时找到路径。我真的不知道我做错了什么,两天来我一直在努力解决这个问题。

编辑:为了解决问题,这里是更完整的代码摘录。这是 examine() 函数:

def examine(self, tile): 
    #Add the tile to the closed list, color it in, remove it from open list. 
    self.closedList.append(tile) 
    tile.color = CLOSED 
    pygame.draw.rect(windowSurface, tile.color, tile.rect) 
    pygame.display.update(tile.rect) 
    self.openList.remove(tile) 
    #Search all neighbors. 
    for a, b in ((tile.col + 1, tile.row), (tile.col - 1, tile.row), 
                 (tile.col + 1, tile.row + 1), (tile.col + 1, tile.row - 1), 
                 (tile.col - 1, tile.row + 1), (tile.col - 1, tile.row - 1), 
                 (tile.col, tile.row + 1), (tile.col, tile.row - 1)): 
        #Ignore if out of range. 
        if a not in range(GRID_WIDTH) or b not in range(GRID_HEIGHT): 
            pass 
        #If the neighbor is pathable, add it to the open list. 
        elif self.tileMap[b][a].pathable and self.tileMap[b][a] not in self.openList and self.tileMap[b][a] not in self.closedList: 
            self.where = abs((a - tile.col)) + abs((b - tile.row)) 
            if self.where == 0 or self.where == 2: 
                self.G = tile.score[1] + self.diagCost 
                self.H = self.distance(self.endTile, self.tileMap[b][a]) 
                self.F = self.G + self.H 
            elif self.where == 1: 
                self.G = tile.score[1] + self.straightCost 
                self.H = self.distance(self.endTile, self.tileMap[b][a]) 
                self.F = self.G + self.H 
 
            #Append to list and modify variables. 
            self.tileMap[b][a].score = (self.F, self.G, self.H) 
            self.tileMap[b][a].parent = tile 
            self.tileMap[b][a].color = OPEN 
            pygame.draw.rect(windowSurface, self.tileMap[b][a].color, self.tileMap[b][a].rect) 
            pygame.display.update(self.tileMap[b][a].rect) 
            self.openList.append(self.tileMap[b][a]) 
        #If it's already in one of the lists, check to see if this isn't a better way to get to it. 
        elif self.tileMap[b][a] in self.openList or self.tileMap[b][a] in self.closedList: 
            self.where = abs((a - tile.col)) + abs((b - tile.row)) 
            if self.where == 0 or self.where == 2: 
                if tile.score[1] + self.diagCost < self.tileMap[b][a].score[1]: 
                    self.tileMap[b][a].score = (self.tileMap[b][a].score[0], tile.score[1] + self.diagCost, self.tileMap[b][a].score[2]) 
                    self.tileMap[b][a].parent = tile 
                    print "parent changed!" 
            elif self.where == 1: 
                if tile.score[1] + self.straightCost < self.tileMap[b][a].score[1]: 
                    self.tileMap[b][a].score = (self.tileMap[b][a].score[0], tile.score[1] + self.straightCost, self.tileMap[b][a].score[2]) 
                    self.tileMap[b][a].parent = tile 
                    print "parent changed!" 

这是一个较新版本的迭代,它放慢了速度,因此我可以看到它的进展。意思是找到得分最低的节点[0](得分是F,G,H得分的元组)。

def path(self): 
    self.openList.append(self.startTile) 
    self.startTile.score = (self.distance(self.startTile, self.endTile), 0, self.distance(self.startTile, self.endTile)) 
    self.examine(self.openList[0]) 
    self.countDown = 0 
    while self.endTile not in self.openList: 
        if self.countDown <= 0: 
            self.countDown = 5000 
            self.smallestScore = MAX_DIST * 50 
            self.bestTile = self.startTile 
            for tile in self.openList: 
                if tile.score[0] <= self.smallestScore: 
                    self.bestTile = tile 
                    self.smallestScore = tile.score[0] 
            self.examine(self.bestTile) 
        else: 
            self.countDown -= timePassed 

下图是使用 self.totalDist = self.diagCost * math.sqrt(pow(self.xDist, 2) + pow(self.yDist, 2))

或者,从等式中删除 TILE_SIZE 常量得到这个看起来同样低效的搜索区域:

在我看来,它不应该搜索所有额外区域 - 只搜索紧邻障碍物的区域。

请您参考如下方法:

我的理论:这是因为曼哈顿距离不是 admissible在这种情况下,因为您也可以沿对角线移动。

试试这个:

def distance(self, tile1, tile2): 
    self.xDist = abs(tile1.col * TILE_SIZE - tile2.col * TILE_SIZE) 
    self.yDist = abs(tile1.row * TILE_SIZE - tile2.row * TILE_SIZE) 
    self.totalDist = self.diagCost * math.sqrt(self.xDist*self.xDist + self.yDist*self.yDist) 
                     # or it might be self.straightCost, depending on their values. 
                     # self.diagCost is probably right, though. 
    return self.totalDist