Как заставить Аи работать на тороидальной 2D сетке на основе карты

Question

У меня есть несколько NPC в двумерной матрице, и я должен заставить их следовать за NPC вражеской фракции, используя тороидальную карту.

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

это то, что у меня есть сейчас, чтобы решить, куда идти:

public Position GetNextStepTowards(Position origin, Position target)
{
    Position nextStep = new Position(0, 0);

    float dx = MathF.Abs(target.X - origin.X);
    float dy = MathF.Abs(target.Y - origin.Y);

    if (dx > mapXSize / 2) nextStep.X = -1;
    else if (dx < mapXSize / 2) nextStep.X = 1;

    if (dy > mapYSize / 2) nextStep.Y = 1;
    else if (dy < mapYSize / 2) nextStep.Y = -1;

    return nextStep;
}

А позиция:

public struct Position
{
    public int X { get; set; }
    public int Y { get; set; }

    public Position(int x, int y)
    {
        this.X = x;
        this.Y = y;
    }
}

Неигровые персонажи могут перемещать только одну клетку (ячейку Мура), поэтому вектором движения должны быть значения только от -1 до 1.

Заранее спасибо за помощь!

Answer 1

Если мы рассмотрим ось X, есть два случая, как показано на диаграмме ниже:

В первом случае (вверху)цель находится справа от источника.В этом случае перемещение вправо является прямым, а перемещение влево - тороидальным.

Во втором случае (внизу) цель находится слева от начала координат.В этом случае перемещение влево является прямым, а перемещение вправо - тороидальным.

Таким образом, в коде необходимо проверить относительные положения начала и цели, а затем соответствующим образом вычислить расстояния влево и вправо.Меньшее расстояние определяет направление и величину deltaX.Та же логика применима к deltaY.

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

private int ComputeDelta(int src, int dst, int mapSize)
{
    int increasing, decreasing;
    if (dst >= src)
    {
        increasing = dst - src;               // increasing direction is direct
        decreasing = (mapSize + src) - dst;   // decreasing direction is toroidal
    }
    else
    {
        increasing = (mapSize + dst) - src;   // increasing direction is toroidal
        decreasing = src - dst;               // decreasing direction is direct
    }

    if (increasing <= decreasing) { return  increasing; }
    else                          { return -decreasing; }
}

public Position GetNextStepTowards(Position origin, Position target)
{
    Position nextStep = new Position(0, 0);

    // compute the distances
    int dx = ComputeDelta(origin.X, target.X, mapXSize);
    int dy = ComputeDelta(origin.Y, target.Y, mapYSize);

    // keep the dominant distance, and clear the other distance
    // keep both if they're equal
    if      (dx*dx > dy*dy) { dy = 0; }
    else if (dx*dx < dy*dy) { dx = 0; }

    // normalize the distances so they are -1, 0, or 1
    nextStep.X = dx.CompareTo(0);
    nextStep.Y = dy.CompareTo(0);

    return nextStep;
}

Answer 2

Итак, через некоторое время я нашел это решение, немного неуклюжее, на мой взгляд:

public Position GetNextStepTowards(Position origin, Position target)
{
    // Returned Position
    Position nextStep = new Position(0, 0);

    int dx = target.X - origin.X;
    int dy = target.Y - origin.Y;

    // Toroidal distance
    if (dx > mapXSize / 2) dx = mapXSize - dx;
    if (dy > mapYSize / 2) dy = mapXSize - dy;

    // First verify whether the difference in positions is 
    // greater on the X or Y axis.
    // Then check if the target is lower/higher/forwards/backwards
    if (MathF.Pow(dx, 2) > MathF.Pow(dy, 2))
    {
        if (dx > 0) nextStep.X = 1;
        else if (dx < 0) nextStep.X = -1;
    }
    else if (MathF.Pow(dy, 2) > MathF.Pow(dx, 2))
    {
        if (dy > 0) nextStep.Y = 1;
        else if (dy < 0) nextStep.Y = -1;
    }

    // If the difference in the X and Y axis are the same, 
    // move diagonally
    // use CompareTo do decide what direction in specific.
    else if ((int)MathF.Pow(dx, 2) == (int)MathF.Pow(dy, 2))
    {
        nextStep.X = 1 * target.X.CompareTo(origin.X);
        nextStep.Y = 1 * target.Y.CompareTo(origin.Y);
    }

    return nextStep;
}