探路者问题

Question

我从此示例中采用了 A* 算法 XNA Pathfinder 示例 这样它将能够为移动目标绘制一条路径。

我更改了方法，使其每半秒计算一条新路径，以便计算到达目标的路径，从列表中清除以前的点并向其添加新点。

            timer += gameTime.ElapsedGameTime;

            if (timer.Seconds >= 0.5)
            {
                timer = TimeSpan.Zero;
                pathFinder.NewPath(position);
            }

            if (pathFinder.SearchStatus == SearchStatus.PathFound)
            {
                waypoints.Clear();
                foreach (Point point in pathFinder.FinalPath())
                {
                    Waypoints.Enqueue(level.MapToWorld(point, true));
                }
                moving = true;
            }

我遇到的问题是角色在路径的起点不断地来回移动。正如有人正确指出的那样......

“它认为“向前”是一个好主意，所以它就那样走。然后，当半秒后它会检查，它认为“返回”是个好主意并返回“。

有人建议我应该给当前路径上存在的点赋予比路径上新点更小的权重。我尝试过实施此操作但无济于事，对此的任何帮助都会很棒。

该方法包含 Astar 算法。

/// <summary>
/// This Method looks at everything in the open list and chooses the next 
/// path to visit based on which search type is currently selected.
/// </summary>
/// <param name="result">The node to be visited</param>
/// <returns>Whether or not SelectNodeToVisit found a node to examine
/// </returns>
private bool SelectNodeToVisit(out SearchNode result)
{
    result = new SearchNode();
    bool success = false;
    float smallestCost = float.PositiveInfinity;
    float currentCost = 0f;

    if (openList.Count > 0)
    {
        foreach (SearchNode node in openList)
        {
            currentCost = Heuristic(node);
            // The heuristic value gives us our optimistic estimate 
            // for the path length, while any path with the same 
            // heuristic value is equally ‘good’ in this case we’re 
            // favoring paths that have the same heuristic value 
            // but are longer.
            if (currentCost <= smallestCost)
            {
                if (currentCost < smallestCost)
                {
                    success = true;
                    result = node;
                    smallestCost = currentCost;
                }
                else if (currentCost == smallestCost &&
                    node.DistanceTraveled < result.DistanceTraveled)
                {
                    success = true;
                    result = node;
                    smallestCost = currentCost;
                }
            }
        }
    }
    return success;
}

这是计算节点启发式值的修改方法，现在根据节点是否在当前路径上为其赋予权重。

     /// <summary>
    /// Generates an optimistic estimate of the total path length to the goal 
    /// from the given position.
    /// </summary>
    /// <param name="location">Location to examine</param>
    /// <returns>Path length estimate</returns>
    private float Heuristic(SearchNode location)
    {
        int Nodecost = 10;

        foreach (Point point in Currentpath)
        {
            if (location.Position == point)

                Nodecost = 7;
                break;
        }
        return location.DistanceTraveled + location.DistanceToGoal + Nodecost;
    }

这是将节点添加到打开列表或关闭列表的方法。

 /// <summary>
/// This method find the next path node to visit, puts that node on the 
/// closed list and adds any nodes adjacent to the visited node to the 
/// open list.
/// </summary>
private void DoSearchStep(TileMap tileMap)
{
    SearchNode newOpenListNode;

    bool foundNewNode = SelectNodeToVisit(out newOpenListNode);
    if (foundNewNode)
    {
        Point currentPos = newOpenListNode.Position;
        foreach (Point point in level.OpenMapTiles(currentPos, tileMap))
        {
            SearchNode mapTile = new SearchNode(point,
                StepDistanceToEnd(point),
                newOpenListNode.DistanceTraveled + 1);

            if (!InList(openList, point) &&
                !InList(closedList, point))
            {
                openList.Add(mapTile);
                paths[point] = newOpenListNode.Position;
            }
        }
        if (currentPos == endPlace)
        {
            searchStatus = SearchStatus.PathFound;
        }
        openList.Remove(newOpenListNode);
        closedList.Add(newOpenListNode);
    }
    else
    {
        searchStatus = SearchStatus.NoPath;
    }
}

如何杜绝“来回”问题？

Answer 1

在尝试实现目标的可能方法之一的同时重新评估实现目标的最佳方法是一个相当常见的问题：这通常会导致行为不一致，例如您所描述的行为不一致。

• 解决这个问题的一个好方法是让当前的方式比任何其他具有相同分数的方式具有更高的优先级。

• 另一个可行的解决方案是使用阈值。这是一个例子：

  • 当前路径的评估值为 100。当我们谈论 A* 时，假设这是当前考虑的路径到目标的距离。

  • 重新评估时，我们发现另一条路径的评估值为 95。

  • 但我们使用 10% 的阈值来防止角色的想法发生改变，除非最佳解决方案比当前解决方案好 10%

  所以在这个例子中我们不会改变角色的想法，因为我们只会获得 5%。但我们会改变主意，选择一条评估为 90 或更低的路径。

我倾向于选择阈值解决方案而不是优先当前方式的解决方案。我觉得它更加优雅和自然。它也更强大，因为它允许您为行为添加一些现实性（只有计算机每次总是选择数学上最好的方法）。唯一的困难是找到好的阈值，这需要一些时间的测试。