A*算法生成的噪声路径

Question

我正在为一个机器人项目开发前端界面（这是一个“自动”汽车，它通过一些传感器和从SVG文件生成的地图来定位自己）。

为了让机器人可以被控制，我们必须在它当前的位置和目标之间生成路径。我使用了最简单的算法：A*算法。

但是我得到了些奇怪的结果：汽车倾向于沿着45°的倍数行驶，还有一个特别烦人的问题：一些生成的路径非常不平滑！

看看这个橙色矩形附近的噪声路径：

有没有办法避免这些奇怪或不平滑的结果？最终我们希望构建一条转向角度变化最少的路径。（汽车可以在不移动的情况下转向，所以我们不需要对路径进行“平滑处理”）。

这是我实现的A*算法：

def search(self, begin, goal):
    if goal.x not in range(self.width) or goal.y not in range(self.height):
        print "Goal is out of bound"
        return []
    elif not self.grid[begin.y][begin.x].reachable:
        print "Beginning is unreachable"
        return []
    elif not self.grid[goal.y][goal.x].reachable:
        print "Goal is unreachable"
        return []
    else:

        self.cl = set()
        self.ol = set()

        curCell = begin
        self.ol.add(curCell)

        while len(self.ol) > 0:

            # We choose the cell in the open list having the minimum score as our current cell
            curCell = min(self.ol, key = lambda x : x.f)

            # We add the current cell to the closed list
            self.ol.remove(curCell)
            self.cl.add(curCell)

            # We check the cell's (reachable) neighbours :
            neighbours = self.neighbours(curCell)

            for cell in neighbours:
                # If the goal is a neighbour cell :
                if cell == goal:
                    cell.parent = curCell
                    self.path = cell.path()
                    self.display()
                    self.clear()
                    return self.path
                elif cell not in self.cl:
                    # We process the cells that are not in the closed list
                    # (processing <-> calculating the "F" score)
                    cell.process(curCell, goal)

                    self.ol.add(cell)

编辑 1：应大家要求，这里是评分计算函数（过程）：

def process(self, parent, goal):
    self.parent = parent
    self.g = parent.distance(self)
    self.h = self.manhattanDistance(goal)
    self.f = self.g + self.h

编辑 这是邻居方法（根据用户1884905的回答更新）：

def neighbours(self, cell, radius = 1, unreachables = False, diagonal = True):
    neighbours = set()
    for i in xrange(-radius, radius + 1):
        for j in xrange(-radius, radius + 1):
            x = cell.x + j
            y = cell.y + i
            if 0 <= y < self.height and 0 <= x < self.width and ( self.grid[y][x].reachable or unreachables ) and (diagonal or (x == cell.x or y == cell.y)) :
                neighbours.add(self.grid[y][x])

    return neighbours

（这看起来复杂，但它只是给出一个单元格的8个邻居，包括对角邻居；它还可以使用不同于1的半径，因为它用于其他功能）

还有距离计算（取决于是否使用对角邻居：）

def manhattanDistance(self, cell):
    return abs(self.x - cell.x) + abs(self.y - cell.y)

def diagonalDistance(self, cell):

    xDist = abs(self.x - cell.x)
    yDist = abs(self.y - cell.y)

    if xDist > yDist:
        return 1.4 * yDist + (xDist - yDist)
    else:
        return 1.4 * xDist + (yDist - xDist)

Answer 1

看起来这个实现有点问题，因为它在移动到离目标最近的那个“还没有被检查过的单元格”时，应该是“尝试一下”，如果发现有障碍物就撤回路径，这样才能找到最优路径。你可以看看这个维基百科上的动画，能帮助你理解这个概念。

这里的问题和你计算cell.f的方式有关，可能在计算时没有把当前单元格的得分加上。一般来说，A*算法应该按照这里红色标记的步骤来走，这样会生成一些次优路径。

由于空间被划分成离散的单元格，当在一个连续的世界中最佳路径（总是最短的）正好在两个离散移动之间时，它会尽量用那条奇怪的路径来逼近。

我看到这里有两种解决方法：

1. 修正算法（这里有伪代码），保持每个评估单元格的正确距离值（在粘贴的代码中没有关于cell.f是怎么计算的信息）。
2. 使用Djikstra算法，只需对当前算法做一些小改动就能轻松实现。实际上，A*算法就是它的优化版本。

Answer 2

虽然我看不到你是怎么实现你的 neighbour 和 distance 函数的，但我可以猜测一下可能出错的地方：

如果你允许对角线移动，就不要使用曼哈顿距离。

在目标函数中，曼哈顿距离应该是到达目标的最短距离。（如果你可以斜着穿过建筑物，这个距离就不再准确了。）

解决这个问题最简单的方法是保持曼哈顿距离作为目标函数，同时把邻居的定义改为只包括上下左右四个相邻的单元格。

补充说明

你的代码还有问题。下面的伪代码来自于维基百科。我标出了你需要检查的重要行。你必须确保 i) 如果找到更好的解决方案，就更新开放集合中的节点，ii) 始终考虑之前走过的距离。

function A*(start,goal)
     closedset := the empty set    // The set of nodes already evaluated.
     openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
     came_from := the empty map    // The map of navigated nodes.

     g_score[start] := 0    // Cost from start along best known path.
     // Estimated total cost from start to goal through y.
     f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

     while openset is not empty
         current := the node in openset having the lowest f_score[] value
         if current = goal
             return reconstruct_path(came_from, goal)

         remove current from openset
         add current to closedset
         for each neighbor in neighbor_nodes(current)
             // -------------------------------------------------------------------
             // This is the way the tentative_g_score should be calculated.
             // Do you include the current g_score in your calculation parent.distance(self) ?
             tentative_g_score := g_score[current] + dist_between(current,neighbor)
             // ------------------------------------------------------------------- 
             if neighbor in closedset
                 if tentative_g_score >= g_score[neighbor]
                     continue

             // -------------------------------------------------------------------
             // You never make this comparrison
             if neighbor not in openset or tentative_g_score < g_score[neighbor]
             // -------------------------------------------------------------------
                 came_from[neighbor] := current
                 g_score[neighbor] := tentative_g_score
                 f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
                 if neighbor not in openset
                     add neighbor to openset

     return failure

 function reconstruct_path(came_from, current_node)
     if current_node in came_from
         p := reconstruct_path(came_from, came_from[current_node])
         return (p + current_node)
     else
         return current_node