Унификация поиска пути вместо различной логики ИИ

Для одной незамысловатой игры мне понадобилось реализовать поведение ИИ с базовым функционалом: патрулирование, преследование и ведение боя. Сама по себе задача простая, однако, типов локаций было два и с разными уровнями абстракций.

В одном случае действие проходило в замкнутых помещениях, а в другом - посреди городских улиц. На малых пространствах генерировалась сетка навигации, но в большой локации для сохранения производительности был использован поиск пути по графу.

Все виды поведений уже были написаны, а логика одинакова во всех локациях. Для ИИ не имело значения какой там используется поиск пути. Главное получить дорогу до цели и выполнить свою задачу!

Для себя я выделил два решения. Первое заключалось в адаптации поведения под местность, например с помощью паттерна стратегия. Но в этом случае пришлось бы для каждого типа навигации писать дополнительную логику. Второе же решение предполагало унификацию данных поиска пути. При таком подходе ИИ не нужно было дополнять излишней логикой, а всю работу на себя брали поисковики!

Реализация

Основные объекты:

• IPath<TPoint> (данные о пути)

• IPathProvider<TPoint> (поисковик или объект предоставляющий путь)

• IPathResponse<TPoint> (содержащий путь ответ, получаемый от поисковика)

• IPathRequestToken<TPoint> (токен для формирования ответа)

IPath

Определим базовый интерфейс. В нем будет текущая точка, к которой движется бот, коллекция точек всего пути и единственный метод, при вызове которого мы узнаем можно ли следовать дальше по пути. Обобщения используются для того, чтобы не писать для каждого типа точек отдельную реализацию, ведь нам не важно Vector3 или Vector2 будет, может вообще другая структура данных понадобится.

public interface IPath<TPoint>
{
    // Текущая используемая точка.
    TPoint Current { get; }
    // Коллекция всех точек.
    IEnumerable<TPoint> Points { get; }
    // Метод для перехода к следующей точке из коллекции.
    bool Continue(TPoint origin);
}

Хоть изначально IPath предназначался для простого представления данных о пути, однако в процессе написания кода лично я не хотел бы вручную контролировать смену точек, индексов, какие-то проверки на null, к тому же логика у всех ИИ в данном случае будет одинакова, а разница заключается лишь в функции перехода. Поэтому было добавлено определение метода Continue.

Сделаем реализацию пути — пустого. Но для чего? Разве нельзя представлять пустой путь как null? И это возможный вариант, но он добавит нам ручной работы для проверок на существование данных, в то время как реализация в виде конкретного объекта просто не позволит боту передвигаться, т.к. все время будет возвращать отрицательный результат.

public class EmptyPath<TPoint> : IPath<TPoint>
{
    public TPoint Current => default(TPoint);
    public IEnumerable<TPoint> Points => null;
    
    public bool Continue(TPoint origin) => false;
}

// Исключение, которое нужно бросить при пустых результатах.
public class EmptyPathException : Exception
{
    public EmptyPathException()
        : base("Path is empty! Try using EmptyPath<TPoint> instead of Path<TPoint>")
    {}
}

Добавим стандартную реализацию для пути:

public class Path<TPoint> : IPath<TPoint>
{
    // Функция перехода.
    // Проверяет необходимость смены текущей точки.
    protected readonly Func<TPoint, TPoint, bool> ContinueFunc;
    protected readonly IEnumerator<TPoint> PointsEnumerator;
    
    // Текущая точка.
    public TPoint Current { get; protected set; }
    // Коллекция точек.
    public IEnumerable<TPoint> Points { get; protected set; }
    
    // Продолжено ли движение по пути.
    // Внутреннее свойство.
    public bool Continued { get; protected set; }
    
    public Path(IEnumerable<TPoint> points, Func<TPoint, TPoint, bool> continueFunc)
    {
        // Мы не должны допускать пустых данных.
        if(points == null)
            throw new EmptyPathException();
        
        ContinueFunc = continueFunc;
        PointsEnumerator = points.GetEnumerator();
        
        Points = points;
        
        // Изначально указатель никуда не указывает 
        // и его нужно сдвинуть на первый элемент.
        MovePointer();
    }

    // Проверка на возможность продолжения перемещения.
    public bool Continue(TPoint origin)
    {
        // Если нужно двигаться к следующей точке.
        if (ContinueFunc(origin, Current))
            MovePointer();
        
        // Продолжен ли путь.
        return Continued;
    }
     
    // Передвигаем указатель на следующий элемент,
    // если возможно продолжить путь.
    protected void MovePointer()
    {
        // Если есть элементы в коллекции точек.
        if (PointsEnumerator.MoveNext())
        {
            Current = PointsEnumerator.Current;
            Continued = true;
        }
        else
        {
            // Путь невозможно продолжить
            Continued = false;
        }
    }
}

Делегат Func<TPoint, TPoint, bool> ContinueFunc — нужен для проверки текущей цели (точки, к которой мы двигаемся). Если бот подойдет к цели, то ее логично будет сменить на следующую точку в пути. Этот делегат передается извне.

Перечислитель IEnumerator<TPoint> PointsEnumerator — нужен для ручного обхода по коллекции точек.

В конструкторе Path хорошо бы убедиться, что коллекция точек существует. При ее отсутствии нужно выбрасывать исключение: ранее было оговорено о нецелесообразности проверок на null в логике ботов, да и к тому же исключение позволит нам сразу видеть причину некорректного поведения.

Имея на руках данные IPath уже можно начинать абстрагироваться от конкретных алгоритмов поиска путей. Но я посчитал это неполноценным решением. И причиной являются алгоритмы с асинхронным/многопоточным выполнением, где путь не может быть сразу возвращен при запросе.

Да и к тому же нам все еще нужно знать к кому обращаться за поиском пути :)

IPathProvider и IPathResponse

Для решения проблемы обращения к конкретным объектам, в моем случае это город и комнаты которые имеют данные о сцене, я решил обернуть их в провайдер.

IPathProvider<TPoint> — интерфейс, сообщающий нам о том, что у объекта можно запросить путь нужного нам типа. Один объект может реализовывать несколько вариантов этого интерфейса. Определение поисковика:

public interface IPathProvider<TPoint>
{
    // Метод запроса, возвращающий путь, но внутри обекта ответа.
    IPathResponse<TPoint> RequestPath(TPoint entryPoint, TPoint endPoint);
}

Определение ответа на запрос:

public interface IPathResponse<TPoint>
{
    // Флаг о готовности данных пути.
    bool Ready { get; }
    // Сам путь, который может быть null.
    IPath<TPoint> Path { get; }
}

IPathResponse<TPoint> содержит в себе путь Path и флаг Ready, сигнализирующий о завершении поиска пути провайдером. При асинхронном/многопоточном вычислении флаг не сразу может быть со значением true.

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

public sealed class PathResponseSync<TPoint> : IPathResponse<TPoint>
{
    public bool Ready { get; private set; }
    public IPath<TPoint> Path { get; private set; }

    public PathResponseSync(IPath<TPoint> path)
    {
        if(path == null)
            throw new EmptyPathException();

        Path = path;
        Ready = true;
    }
}

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

Для асинхронной реализации я решил добавить токен через который можно будет передать найденный путь. Это нужно для того, чтобы объект IPathResponse не протаскивался по разным частям программы и его положение было легко определить.

Токен:

public sealed class PathRequestToken<TPoint>
{
		public bool IsReady { get; private set; }
    public IPath<TPoint> Path { get; private set; }
    
    public void Ready(IPath<TPoint> path)
    {
    		if (path == null)
        		throw new EmptyPathException();
        
        IsReady = true;
        Path = path;
    }        
}

По своему определению он действительно повторяет определение IPathResponse. По этой причине вы можете и не пользоваться токеном, а передавать и работать только с IPathResponse. Но как я уже объяснял выше, добавление данной прослойки помогает избежать протаскивания ответа через разные слои программы.

Ответ:

public sealed class PathResponse<TPoint> : IPathResponse<TPoint>
{
    private readonly PathRequestToken<TPoint> _token;
    
    public bool Ready => _token.IsReady;
    public IPath<TPoint> Path => _token.Path;

    public PathResponse(PathRequestToken<TPoint> token)
    {
        _token = token;
    }

    // Метод для упрощенного создания объектов ответа и токена.
    public static void New(out PathRequestToken<TPoint> token,
        out PathResponse<TPoint> response)
    {
        token = new PathRequestToken<TPoint>();
        response = new PathResponse<TPoint>(token);
    }
}

Реализация класса асинхронного/многопоточного ответа подходит и для синхронных вычислений.

Здесь нет установки значений, только обращение к значениям токена и один статический метод для удобства создания объектов ответа и токена.

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

Теперь у нас есть все, чтобы абстрагироваться от конкретных алгоритмов при этом не меняя логику ИИ! К тому же мы избавились от надобности знать способ выполнения алгоритма: синхронный он или нет нас не интересует благодаря IPathResponse.

Пример использования

В классе ИИ я определил поля для ответа и провайдера, а методе Update содержится логика запроса и следования:

..
private IPathProvider<Vector3> _pathProvider;
private IPathResponse<Vector3> _pathResponse;
..
  
public override void Update(float deltaTime)
{
    // Обновление пути при преследовании.
    _pathUpdateTimer += deltaTime;
    if (_pathUpdateTimer >= Owner.PathUpdateRate)
    {
        _pathUpdateTimer = 0f;
                
        if (Target == null)
            Target = _scanFunction(Owner);

        if (Target == null)
            return;
        
        // Запрашиваем путь у поисковика.
        _pathResponse = _pathProvider
            .RequestPath(Position, Target.transform.position);
    }

    // Следование по пути, если есть ответ и путь просчитан.
    if (_pathResponse != null)
    {
        // Если данные о пути готовы к использованию
        if (_pathResponse.Ready)
        {
            var path = _pathResponse.Path;
            // Объект пути вычисляет надобность в смене следующей точке
            // и возможности дальнейшего передвижения.
            if (path.Continue(Position))
            {
                // Какая-то логика передвижения
                var nextPosition = Vector3.MoveTowards( Position, path.Current,
                    Owner.MovementSpeed * deltaTime);
                    
                Position = nextPosition;
            }
        }
    }      
}

Функция для для перехода по точкам:

public static bool Vector3Continuation(Vector3 origin, Vector3 current)
{
    var distance = (origin - current).sqrMagnitude;

    return distance <= float.Epsilon;
}

Ну и пример поисковика:

public IPathResponse<Vector3> RequestPath(Vector3 entryPoint, Vector3 endPoint)
{
    // ЗДЕСЬ БЫЛА ЛОГИКА, НО ЕЕ УКРАЛО НЛО...
	
    // Найденный путь с объектами типа LinkedAPoint.
    var pathRaw = _jastar.FindPath(startPointJastar, endPointJastar);
            
    // Если пути нет, то возвращается синхронный ответ с пустым путем.
    if(pathRaw.Count == 0)
        return new PathResponseSync<Vector3>(new EmptyPath<Vector3>());
  	
    var vectorList = pathRaw.ToVector3List();
  
    // Возвращение пути со списком точек и заданной функцией продолжения.
    return new PathResponseSync<Vector3>(
        new Path<Vector3>(vectorsList, PathFuncs.Vector3Continuation));
}

Посмотреть исходники можно здесь. Также там есть пара алгоритмов из игрушки.