Проблемы с Pathfinder

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;
            }

Проблема, с которой я столкнулся, заключается в том, что персонаж продолжает двигаться вперед и назад в начальной точке пути. Как кто-то правильно указал ...

"он думает, что идет"далее «это хорошая идея, поэтому она идет таким образом. Затем, когда она проверяет полсекунды спустя, она думает, что« назад »- хорошая идея, и возвращается».

Кто-то предложил мне придать точкам, которые существуют на текущем пути, меньший вес, чем новым точкам на пути.Я пытался реализовать это безрезультатно, любая помощь с этим была бы полезна.

Этот метод содержит алгоритм Астара

/// <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 или менее.

Я склонен предпочесть пороговое решение, а не решение «приоритет по току». Я нахожу это более элегантным и естественным. Он также более мощный, так как позволяет добавить немного реалистичности в поведение (только компьютер всегда выбирал математически лучший подход каждый раз). Единственная сложность - найти хороший порог, для этого требуется некоторое время при тестировании.