ИИ в играх на платформе Unity. Алгоритм A*.

Опубликовано от

 Введение

           Сложно представить игры без искусственного интеллекта для NPC. Неигровые персонажи создают наполняемость мира и являются двигателями игрового процесса. Для проектов в жанрах RTS и Shooter особенно важно адекватное поведение юнитов.

Одним из важных элементов поведения персонажа является способ построения маршрута из точки А в точку Б. В данной статье рассмотрим один из самых популярных алгоритмов поиска пути - А*.

Алгоритм А*.

Алгоритм А* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдет минимальный. Сам поиск выглядит следующим образом:

  1. Создаем 2 списка вершин - ожидающие рассмотрения и уже рассмотренные. В список ожидающих добавляем точку старта, а список рассмотренных оставляем пустым.

  2. Для каждой точки рассчитываем цена F = G + H, где G - расстояние от старта до точки, H - примерное расстояние от точки до цели. Каждая узел должен хранить ссылку на точку, из которой в него пришли.

  3. Из списка узлов на рассмотрение выбираем точку с наименьшим F. Обозначим ее за X.

  4. Если Х - целевая точка, то мы нашли маршрут.

  5. Переносим Х из списка ожидающих в список рассмотренных.

  6. Для каждой соседней с Х точки делаем следующее:

  7. Обозначим соседнюю точку за Y. Если Y уже находится в рассмотренных - пропускаем ее.

  8. Если Y еще нет в списке на ожидание - добавляем ее туда, запомнив ссылку на Х, рассчитав Y.G (это X.G + distance(X, Y)) и Y.H.

  9. Если же У в списке на рассмотрение - проверяем, если X.G + distance(X, Y) < Y.G, значит мы пришли в точку Y более коротким путем, заменяем Y.G на X.G + distance(X, Y), а точку, из которой пришли в Y, на X.

  10. Если список точек на рассмотрение пуст, а до цели мы так и не дошли - значит маршрут не существует.

В качестве функции примерной оценки расстояния до цели возьмем вычисление длины между двумя точками без препятствий.

Зададим ноды следующим образом:

public class Node { public Vector3 Position { get; set; } public Vector3 TargetPosition { get; set; } public Node PrevNode { get; set; } public int F { get; set; } public int G { get; set; } public int H { get; set; } public bool IsWalkable { get; set; } public Node(Vector3 nodePosition, Vector3 targetPosition, Node prevNode, int g) { Position = nodePosition; TargetPosition = targetPosition; PrevNode = prevNode; G = g; H = (int)Mathf.Abs(targetPosition.x - Position.x) + (int)Mathf.Abs(targetPosition.y - Position.y); F = G + H; } }

Сам метод для поиска пути выглядит следующим образом:

    public List<Vector3> GetPath(Vector3 target)
    {
        PathToTarget = new List<Vector3>();
        CheckedNodes = new List<Node>();
        WaitingNodes = new List<Node>();
        Vector3 StartPosition = new Vector3(Mathf.Round(transform.position.x), Mathf.Round(transform.position.y), Mathf.Round(transform.position.z));
        Vector3 TargetPosition = new Vector3(Mathf.Round(Target.transform.position.x), Mathf.Round(Target.transform.position.y), Mathf.Round(Target.transform.position.z));
        if (IsEqualVector(StartPosition, TargetPosition)) 
            return PathToTarget;
        Node startNode = new Node(StartPosition, TargetPosition, null, 0);
        CheckedNodes.Add(startNode);
        WaitingNodes.AddRange(GetNeighboursNodes(startNode));
        while (WaitingNodes.Count > 0)
        {
            Node nodeToCheck = WaitingNodes.Where(x => x.F == WaitingNodes.Min(y => y.F)).FirstOrDefault();
            if (IsEqualVector(nodeToCheck.Position, TargetPosition))
            {
                return CalculatePathFromNode(nodeToCheck);
            }
            var walkable = (Physics.OverlapSphere(nodeToCheck.Position, 0.1f, SolidLayer).Length == 0);
            nodeToCheck.IsWalkable = walkable;
            if (!walkable)
            {
                WaitingNodes.Remove(nodeToCheck);
                CheckedNodes.Add(nodeToCheck);
            }
            else
            {
                WaitingNodes.Remove(nodeToCheck);
                if (!CheckedNodes.Where(x => IsEqualVector(x.Position, nodeToCheck.Position)).Any())
                {
                    CheckedNodes.Add(nodeToCheck);
                    WaitingNodes.AddRange(GetNeighboursNodes(nodeToCheck));
                }
            }
        }
        FreeNodes = CheckedNodes;
        return null;
    }

Заключение

    У алгоритма есть несколько плюсов:
        1. Быстрый поиск на открытых пространствах.
        2. Универсальность алгоритма.
    Но, если взять сложный ландшафт с множеством препятствий, при этом размер игровой карты будет довольно большой, то появляется самый главный минус алгоритма. Он заключается в том, что требуется много памяти для вычисления маршрута.
    Также в алгоритм можно добавить цену для каждого типа ландшафта. Это добавит некоторую предпочтительность маршрута. Например, юниту выгоднее будет воспользоваться маршрутом через поле, а не через болото.

Рис.1. Демонстрация работы алгоритма