Поиск пути A* для 2-мерных платформеров, основанных на сетке: захват уступа

() translation by (you can also view the original English article)

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

Демонстрация

Вы можете сыграть в Unity демо, или в WebGL версию (16MB), чтобы увидеть в действии конечный результат. Используйте WASD, чтобы перемещать персонажа, левый клик на точку, чтобы найти путь, по которому вы можете в нее добраться, правый клик в ячейку, чтобы переключить наличие площадки в этой точке, средний клик, чтобы поместить одностороннюю платформу, и клик + перетаскивание ползунков, чтобы изменить их значения.

Механика захвата уступа

Обзор управления

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

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

Когда персонаж захватил уступ, у игрока есть два варианта: он может подпрыгнуть вверх или упасть вниз. Прыжок работает как обычно; игрок нажимает кнопку прыжка и сила прыжка идентична силе, прилагаемой при прыжке с земли. Падение вниз производится нажатием кнопки вниз (S), или кнопки направления, которая указывает в сторону от уступа.

Реализация управления

Давайте разберемся, как управление захватом уступа работает в коде. Первое, что здесь надо сделать - это определить, справа или слева от персонажа находится уступа:

1	bool ledgeOnLeft = mLedgeTile.x * Map.cTileSize < mPosition.x;
2	bool ledgeOnRight = !ledgeOnLeft;

Мы можем использовать эту информацию, чтобы определить, собирается ли персонаж упасть с уступа. Как видите, чтобы упасть вниз, игрок должен либо:

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

bool ledgeOnLeft = mLedgeTile.x * Map.cTileSize < mPosition.x;
bool ledgeOnRight = !ledgeOnLeft;

if (mInputs[(int)KeyInput.GoDown]
    || (mInputs[(int)KeyInput.GoLeft] && ledgeOnRight)
    || (mInputs[(int)KeyInput.GoRight] && ledgeOnLeft))
{

}

Здесь есть маленький нюанс. Представьте ситуацию, когда мы удерживаем кнопки вниз и вправо, когда персонаж держится за край уступа. Это приведет к следующей ситуации:

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

Простое решение для этой проблемы - это блокировать движение в направлении уступа на несколько кадров после того, как мы упали с него. Именно это делает следующий фрагмент:

bool ledgeOnLeft = mLedgeTile.x * Map.cTileSize < mPosition.x;
bool ledgeOnRight = !ledgeOnLeft;

if (mInputs[(int)KeyInput.GoDown]
    || (mInputs[(int)KeyInput.GoLeft] && ledgeOnRight)
    || (mInputs[(int)KeyInput.GoRight] && ledgeOnLeft))
{
    if (ledgeOnLeft)
        mCannotGoLeftFrames = 3;
    else
        mCannotGoRightFrames = 3;
}

После этого мы изменяем состояние персонажа на Jump, которое обрабатывает физику прыжка:

bool ledgeOnLeft = mLedgeTile.x * Map.cTileSize < mPosition.x;
bool ledgeOnRight = !ledgeOnLeft;

if (mInputs[(int)KeyInput.GoDown]
    || (mInputs[(int)KeyInput.GoLeft] && ledgeOnRight)
    || (mInputs[(int)KeyInput.GoRight] && ledgeOnLeft))
{
    if (ledgeOnLeft)
        mCannotGoLeftFrames = 3;
    else
        mCannotGoRightFrames = 3;

    mCurrentState = CharacterState.Jump;
}

Наконец, если персонаж не падал с уступа, мы проверяем нажималась ли кнопка прыжка; если да, мы устанавливаем вертикальную скорость прыжка и изменяем состояние:

bool ledgeOnLeft = mLedgeTile.x * Map.cTileSize < mPosition.x;
bool ledgeOnRight = !ledgeOnLeft;

if (mInputs[(int)KeyInput.GoDown]
    || (mInputs[(int)KeyInput.GoLeft] && ledgeOnRight)
    || (mInputs[(int)KeyInput.GoRight] && ledgeOnLeft))
{
    if (ledgeOnLeft)
        mCannotGoLeftFrames = 3;
    else
        mCannotGoRightFrames = 3;

    mCurrentState = CharacterState.Jump;
}
else if (mInputs[(int)KeyInput.Jump])
{
    mSpeed.y = mJumpSpeed;
    mCurrentState = CharacterState.Jump;
}

Определение точки захвата уступа

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

Желтый контур обозначает границы персонажа. Красные сегменты обозначают сенсоры стен; они используются для реализации физики персонажа. Синие сегменты обозначают места, которыми персонаж может захватить уступ.

Чтобы определить, может ли персонаж захватить уступ, наш код постоянно проверяет сторону, в направлении которой он движется. Он ищет пустой тайл на вершине синего сегмента и затем сплошной тайл под ним, который может схватить персонаж.

Заметьте: Захват уступа заблокирован, если персонаж прыгает вверх. Это можно легко заметить в демо и в анимации в секции Обзор управления.

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

Теперь мы прояснили, как работает механика захвата уступа, давайте посмотрим, как встроить ее в наш алгоритм поиска пути.

Изменения навигатора

Сделаем возможным отключение и включение захвата уступа

Прежде всего давайте добавим новый параметр в нашу функцию Findpath, который показывает должен ли навигатор рассматривать захват уступа. Мы назовем его useLedges:

1	public List<Vector2i> FindPath(Vector2i start, Vector2i end, int characterWidth, int characterHeight, short maxCharacterJumpHeight, bool useLedges)

Обнаружение узлов захвата уступа

Условия

Теперь нам нужно изменить функцию, чтобы определять, может ли использоваться конкретный узел для захвата уступа. Мы можем сделать это после проверки, не является ли узел узлом "на земле" или узлом "на потолке", потому что в обоих случаях он не может быть использован для захвата уступа.

if (onGround)
  newJumpLength = 0;
else if (atCeiling)
{
    if (mNewLocationX != mLocationX)
        newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2 + 1, jumpLength + 1);
    else
        newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 2);
}
else if (/*check whether there's a ledge grabbing node here */)
{
}
else if (mNewLocationY < mLocationY)
{

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

... и вот как это может выглядеть в игре:

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

Красные клетки обозначают проверенные узлы; вместе с зелеными клетками, они представляют персонажа в нашем алгоритме. Две верхние ситуации показывают персонажа 2х2, захватывающего уступ справа и слева соответственно. Два нижних показывают то же самое, на размер персонажа теперь 1х3 вместо 2х2.

Как видите, должно быть довольно легко обнаружить эти случаи в алгоритме. Условия для узла захвата уступа будут следующими:

Рядом с верхним-правым / верхним-левым тайлом персонажа есть сплошной тайл.
Над найденным сплошным тайлом есть пустой тайл.
Под персонажем нет сплошного тайла (если он стоит на поверхности, захватывать уступа не нужно).

Обратите внимание, что о третьем условии мы позаботились, так как мы проверяем узел захвата уступа, только если персонаж не стоит на поверхности.

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

1	else if (useLedges)

Теперь давайте проверим, есть ли тайл справа от верхнего правого узла персонажа:

1	else if (useLedges
2	&& mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight - 1] == 0)

И затем, если над этим тайлом есть пустое пространство:

1	else if (useLedges
2	&& mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight - 1] == 0
3	&& mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight] != 0)

Теперь нам нужно сделать то же самое с левой стороны:

else if (useLedges

        && ((mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight - 1] == 0 && mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight] != 0)

            || (mGrid[mNewLocationX - 1, mNewLocationY + characterHeight - 1] == 0 && mGrid[mNewLocationX - 1, mNewLocationY + characterHeight] != 0)))

Есть еще одна необязательная вещь, которую мы можем сделать: отключать поиск узлов захвата уступа, если скорость падения слишком высока, чтобы путь не возвращал экстремальные позиции захвата уступа, которым будет тяжело следовать боту:

else if (useLedges 
        && jumpLength <= maxCharacterJumpHeight * 2 + 6
        && ((mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight - 1] == 0 && mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight] != 0)
            || (mGrid[mNewLocationX - 1, mNewLocationY + characterHeight - 1] == 0 && mGrid[mNewLocationX - 1, mNewLocationY + characterHeight] != 0)))
{
}

После всего этого мы можем быть уверены в том, что найденный узел - это узел захвата уступа.

Добавление специального узла

Что мы делаем, когда нашли узел захвата уступа? Нам нужно установить его значение прыжка.

Вспомните, значение прыжка это число, которое обозначает, в какой фазе прыжка будет персонаж, когда он достигнет этой клетки. Если вам нужно резюме, как работает алгоритм, посмотрите еще раз теоретическую статью.

Кажется, что все, что нам нужно сделать, это установить значение прыжка в узле в 0, так как из точки захвата уступа персонаж может эффективно сбросить состояние прыжка, как если бы он был на земле - но здесь есть несколько моментов для рассмотрения.

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

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

1	const short cLedgeGrabJumpValue = -9;

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

else if (useLedges 
        && jumpLength <= maxCharacterJumpHeight * 2 + 6
        && ((mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight - 1] == 0 && mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight] != 0)
            || (mGrid[mNewLocationX - 1, mNewLocationY + characterHeight - 1] == 0 && mGrid[mNewLocationX - 1, mNewLocationY + characterHeight] != 0)))
{
    newJumpLength = cLedgeGrabJumpValue;
}

Мы сделали cLedgeGrabJumpValue отрицательным, это даст эффект при вычислении стоимости узла - тем самым мы заставим алгоритм предпочитать использовать уступы вместо того, чтобы избегать их. Здесь есть две вещи, на которые нужно обратить внимание:

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

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

Мы пока оставим вычисление стоимости так, как есть, но достаточно просто изменить его, чтобы сделать узлы захвата краев более дорогими.

Модификация значения прыжка во время прыжка или падения с уступа

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

Когда персонаж находится на земле, он может свободно перемещаться влево или вправо и прыгнуть в самый подходящий момент.

Во-первых, давайте определим тот случай, когда персонаж падает вниз с захвата уступа:

else if (mNewLocationY < mLocationY)
{
    if (jumpLength == cLedgeGrabJumpValue)
        newJumpLength = (short)(maxCharacterJumpHeight * 2 + 4);
    else if (jumpLength % 2 == 0)
		newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 2);
	else
		newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 1);
}

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

Далее случай, когда персонаж падает в одну сторону из захвата уступа:

else if (!onGround && mNewLocationX != mLocationX)
{
    if (jumpLength == cLedgeGrabJumpValue)
        newJumpLength = (short)(maxCharacterJumpHeight * 2 + 3);
    else
        newJumpLength = (short)Mathf.Max(jumpLength + 1, 1);
}

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

Игнорируем остальные узлы

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

Прежде всего, когда мы прыгаем из положения захвата уступа, нам нужно двигаться вверх, а не в сторону. Это работает аналогично простому прыжку с земли. В этой точке вертикальная скорость намного выше, чем возможная горизонтальная, и нам нужно смоделировать этот факт в алгоритме:

1	if (jumpLength == cLedgeGrabJumpValue && mLocationX != mNewLocationX && newJumpLength < maxCharacterJumpHeight * 2)
2	continue;

Если мы хотим позволить падение с уступа в противоположную сторону, вот так:

Тогда нам нужно отредактировать условие, которое не позволяет горизонтальное движение при странном значении прыжка. Это потому, что в данный момент, наше специальное значение захвата уступа равно -9, и поэтому правильно только исключить все отрицательные числа из этого условия.

1	if (jumpLength >= 0 && jumpLength % 2 != 0 && mLocationX != mNewLocationX)
2	continue;

Обновляем фильтр узла

И наконец, давайте перейдем к фильтрации узла. Все, что нам нужно здесь сделать - это добавить условие для узлов захвата уступа, так, чтобы мы их не отфильтровывали. Нам просто надо проверить, равно ли cLedgeGrabJumpValue значение прыжка узла:

1	\|\| (fNodeTmp.JumpLength == cLedgeGrabJumpValue)

Полная фильтрация теперь выглядит вот так:

if ((mClose.Count == 0)
    || (mMap.IsOneWayPlatform(fNode.x, fNode.y - 1))
    || (mGrid[fNode.x, fNode.y - 1] == 0 && mMap.IsOneWayPlatform(fPrevNode.x, fPrevNode.y - 1))
    || (fNodeTmp.JumpLength == 3)
    || (fNextNodeTmp.JumpLength != 0 && fNodeTmp.JumpLength == 0)                                                                                                       //mark jumps starts
    || (fNodeTmp.JumpLength == 0 && fPrevNodeTmp.JumpLength != 0)                                                                                                       //mark landings
    || (fNode.y > mClose[mClose.Count - 1].y && fNode.y > fNodeTmp.PY)
    || (fNodeTmp.JumpLength == cLedgeGrabJumpValue)
    || (fNode.y < mClose[mClose.Count - 1].y && fNode.y < fNodeTmp.PY)
    || ((mMap.IsGround(fNode.x - 1, fNode.y) || mMap.IsGround(fNode.x + 1, fNode.y)) 
        && fNode.y != mClose[mClose.Count - 1].y && fNode.x != mClose[mClose.Count - 1].x))
    mClose.Add(fNode);

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

Изменения бота

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

Останавливаем перерасчет reachedX и reachedY

Прежде всего, чтобы все прояснить для бота, давайте обновим функцию GetContext(). В данный момент проблема с ней заключается в том, что значения reachedX и reachedY постоянно перерасчитываются, из-за чего теряется некоторая информация о ситуации. Эти значения используются для того, чтобы видеть, достиг ли уже бот целевого узла по своим осям x и y, соответственно. (Если вам нужно освежить в памяти, как это работает, посмотрите мой урок о кодировании бота.)

Давайте просто изменим это так, что если персонаж достиг узла по оси x или y, тогда эти значения остаются истинными до тех пор, пока мы не переместимся в следующий узел.

Чтобы сделать это возможным, мы должны объявить переменные reachedX и reachedY, как членов класса:

1	public bool mReachedNodeX;
2	public bool mReachedNodeY;

Это означает, что нам больше не нужно передавать их в функцию GetContext():

1	public void GetContext(out Vector2 prevDest, out Vector2 currentDest, out Vector2 nextDest, out bool destOnGround)

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

if (path != null && path.Count > 1)
{
    for (var i = path.Count - 1; i >= 0; --i)
        mPath.Add(path[i]);

    mCurrentNodeId = 1;
    mReachedNodeX = false;
    mReachedNodeY = false;

Второй - это когда мы достигли текущего целевого узла и хотим пойти к следующему:

if (mReachedNodeX && mReachedNodeY)
{
    int prevNodeId = mCurrentNodeId;
    mCurrentNodeId++;
    mReachedNodeX = false;
    mReachedNodeY = false;

Чтобы остановить пересчет переменных, мы должны заменить следующие строки:

1	reachedX = ReachedNodeOnXAxis(pathPosition, prevDest, currentDest);
2	reachedY = ReachedNodeOnYAxis(pathPosition, prevDest, currentDest);

... вот этими, которые которые будут определять, достигли ли мы узел по оси, только если мы еще не достигли его:

if (!mReachedNodeX)
    mReachedNodeX = ReachedNodeOnXAxis(pathPosition, prevDest, currentDest);

if (!mReachedNodeY)
    mReachedNodeY = ReachedNodeOnYAxis(pathPosition, prevDest, currentDest);

Конечно, нам также нужно заменить каждое вхождение reachedX и reachedY заново объявленными версиями mReachedNodeX и mReachedNodeY.

Посмотрим, нужно ли персонажу захватывать уступ

Давайте объявим ряд переменных, которые мы будем использовать для выяснения, нужно ли боту захватывать уступ, и если да, то какой:

1	public bool mGrabsLedges = false;
2	bool mMustGrabLeftLedge;
3	bool mMustGrabRightLedge;

mGrabsLedges это флаг, который мы передаем в алгоритм, чтобы дать ему знать, должен ли он искать путь, включающий захваты уступов. mMustGrabLeftLedge и mMustGrabRightLedge будут использоваться для определения, является ли следующий узел захватом уступа, и должен ли бот схватить уступ слева или справа.

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

Нам понадобится для этого две функции: одна будет проверять, может ли персонаж схватить уступ слева, а вторая будет проверять, может ли персонаж схватить уступ справа. Эти функции будут работать по тому же принципу, что и наш код поиска пути при обнаружении уступов:

public bool CanGrabLedgeOnLeft(int nodeId)
{
    return (mMap.IsObstacle(mPath[nodeId].x - 1, mPath[nodeId].y + mHeight - 1)
        && !mMap.IsObstacle(mPath[nodeId].x - 1, mPath[nodeId].y + mHeight));
}

public bool CanGrabLedgeOnRight(int nodeId)
{
    return (mMap.IsObstacle(mPath[nodeId].x + mWidth, mPath[nodeId].y + mHeight - 1)
            && !mMap.IsObstacle(mPath[nodeId].x + mWidth, mPath[nodeId].y + mHeight));
}

Как видите, мы проверяем, есть ли сплошной тайл рядом с нашим персонажем с пустым тайлом над ним.

Теперь пойдем в функцию GetContext(), и назначим соответствующие значения переменным mMustGrabRightLedge и mMustGrabLeftLedge. Нам нужно установить их в true, если персонажу в принципе разрешено захватывать уступы (это если mGrabsLedges установлена в true) и если есть уступ, который можно захватить.

1	mMustGrabLeftLedge = mGrabsLedges && !destOnGround && CanGrabLedgeOnLeft(mCurrentNodeId);
2	mMustGrabRightLedge = mGrabsLedges && !destOnGround && CanGrabLedgeOnRight(mCurrentNodeId);

Заметьте, что мы также не хотим захватывать уступы, если узел назначения находится на земле.

Обновим значения прыжка

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

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

Давайте посмотрим на функцию, которая определяет, как долго должна быть нажата клавиша прыжка:

public int GetJumpFramesForNode(int prevNodeId)
{
    int currentNodeId = prevNodeId + 1;

    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
        int jumpHeight = 1;
        for (int i = currentNodeId; i < mPath.Count; ++i)
        {
            if (mPath[i].y - mPath[prevNodeId].y >= jumpHeight)
                jumpHeight = mPath[i].y - mPath[prevNodeId].y;
            if (mPath[i].y - mPath[prevNodeId].y < jumpHeight || mMap.IsGround(mPath[i].x, mPath[i].y - 1))
                return GetJumpFrameCount(jumpHeight);
        }
    }

    return 0;
}

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

1	if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && (mOnGround \|\| mCurrentState == CharacterState.GrabLedge))

Теперь нам нужно добавить еще несколько кадров, если это прыжок для захвата уступа. Сначала мы должны узнать может ли он на самом деле сделать это, поэтому давайте создадим функцию, которая будет сообщать нам, может ли вообще персонаж захватить уступ, будь он справа или слева:

1	public bool CanGrabLedge(int nodeId)
2	{
3	return CanGrabLedgeOnLeft(nodeId) \|\| CanGrabLedgeOnRight(nodeId);
4	}

Теперь давайте добавим несколько кадров к прыжку, когда боту нужно захватить уступ:

if (mPath[i].y - mPath[prevNodeId].y >= jumpHeight)
    jumpHeight = mPath[i].y - mPath[prevNodeId].y;
if (mPath[i].y - mPath[prevNodeId].y < jumpHeight || mMap.IsGround(mPath[i].x, mPath[i].y - 1))
    return (GetJumpFrameCount(jumpHeight));
else if (grabLedges && CanGrabLedge(i))
    return (GetJumpFrameCount(jumpHeight) + 4);

Как видите, мы продлили прыжок на 4 кадра, чего должно хватить в нашем случае.

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

if ((mPath[currentNodeId].y - mPath[prevNodeId].y > 0

        || (mPath[currentNodeId].y - mPath[prevNodeId].y == 0 && !mMap.IsGround(mPath[currentNodeId].x, mPath[currentNodeId].y - 1) && mPath[currentNodeId+1].y - mPath[prevNodeId].y > 0))

    && (mOnGround || mCurrentState == CharacterState.GrabLedge))

Реализация логики движения для захвата уступов и падения с них

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

Давайте начнем с объявления булевой переменной, которая будет показывать, перешли ли мы уже ко второй фазе. Мы назовем ее mCanGrabLedge:

1	public bool mGrabsLedges = false;
2	bool mMustGrabLeftLedge;
3	bool mMustGrabRightLedge;
4	bool mCanGrabLedge = false;

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

Бот уже достиг целевого узла по оси X.
Боту нужно схватиться за левый или правый уступ.
Если бот двинется в направлении уступа, он врежется в стену вместо того, чтобы пройти дальше.

Отлично, первые два условия очень просто теперь проверить, потому что мы уже проделали всю необходимую работу:

1	if (!mCanGrabLedge && mReachedNodeX && (mMustGrabLeftLedge \|\| mMustGrabRightLedge))
2	{
3	}
4	else if (mReachedNodeX && mReachedNodeY)

Теперь, третье условие мы можем разделить на две части. Первая позаботится о ситуации, когда персонаж движется в направлении уступа снизу, и вторая - когда он движется сверху. Условия, которые нам нужны для первого случая:

Текущая позиция бота ниже, чем целевая позиция (он приближается к нему снизу).
Верх бокса границ персонажа выше, чем высота тайла уступа.

1	(pathPosition.y < currentDest.y
2	&& (currentDest.y + Map.cTileSizemHeight) < pathPosition.y + mAABB.HalfSizeY 2)

Если бот приближается сверху, условия будут следующими:

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

1	(pathPosition.y > currentDest.y
2	&& pathPosition.y - currentDest.y < mHeight * Map.cTileSize)

Теперь давайте объединим все это и установим флаг, который сигнализирует, что мы можем безопасно двигаться в направлении уступа:

 else if (!mCanGrabLedge && mReachedNodeX && (mMustGrabLeftLedge || mMustGrabRightLedge) &&
    ((pathPosition.y < currentDest.y && (currentDest.y + Map.cTileSize*mHeight) < pathPosition.y + mAABB.HalfSizeY * 2)
    || (pathPosition.y > currentDest.y && pathPosition.y - currentDest.y < mHeight * Map.cTileSize)))
{
    mCanGrabLedge = true;
}

Есть еще одна вещь, которую нам нужно здесь сделать, это немедленно начать движение в направлении уступа:

if (!mCanGrabLedge && mReachedNodeX && (mMustGrabLeftLedge || mMustGrabRightLedge) &&
    ((pathPosition.y < currentDest.y && (currentDest.y + Map.cTileSize*mHeight) < pathPosition.y + mAABB.HalfSizeY * 2)
    || (pathPosition.y > currentDest.y && pathPosition.y - currentDest.y < mHeight * Map.cTileSize)))
{
    mCanGrabLedge = true;
    
    if (mMustGrabLeftLedge)
        mInputs[(int)KeyInput.GoLeft] = true;
    else if (mMustGrabRightLedge)
        mInputs[(int)KeyInput.GoRight] = true;
}

Отлично, теперь перед гигантским условием давайте создадим более маленькое. Это в основном будет упрощенная версия для движения, когда бот собирается схватиться за уступ:

if (mCanGrabLedge && mCurrentState != CharacterState.GrabLedge)
{
    if (mMustGrabLeftLedge)
        mInputs[(int)KeyInput.GoLeft] = true;
    else if (mMustGrabRightLedge)
        mInputs[(int)KeyInput.GoRight] = true;
}
else if (!mCanGrabLedge && mReachedNodeX && (mMustGrabLeftLedge || mMustGrabRightLedge) &&

Вот главная логика, прячущаяся за захватом уступа, но нужно сделать еще кое-что.

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

1	else if (mReachedNodeX && mReachedNodeY)

Теперь нам нужно также перейти к следующему узлу, если бот был готов схватиться за уступ и затем так и сделать на самом деле:

1	else if ((mReachedNodeX && mReachedNodeY) \|\| (mCanGrabLedge && mCurrentState == CharacterState.GrabLedge))

Управление прыжком и падением с уступа

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

if (mFramesOfJumping > 0 &&
    (mCurrentState == CharacterState.GrabLedge || !mOnGround || (mReachedNodeX && !destOnGround) || (mOnGround && destOnGround)))
{
    mInputs[(int)KeyInput.Jump] = true;
    if (!mOnGround)
        --mFramesOfJumping;
}

Следующая вещь, которую бот должен иметь возможность сделать, это элегантно упасть с уступа. С имеющейся реализацией это очень просто: если мы захватываем уступ и не прыгаем, тогда мы очевидно должны упасть с него!

1	if (mCurrentState == Character.CharacterState.GrabLedge && mFramesOfJumping <= 0)
2	{
3	mInputs[(int)KeyInput.GoDown] = true;
4	}

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

Перестаньте все время захватывать уступы!

В данный момент бот захватывает каждый выступ, который может, независимо от того, имеет ли смысл это делать.

Один вариант решения этой проблемы - назначить большую эвристическую цену для захвата уступов, тогда алгоритм будет предпочитать не использовать их, если в этом нет необходимости - но это потребует от нашего бота владеть немного большей информацией об узлах. Так как все, что мы передаем боту - это список точек, мы не знаем, посчитает ли алгоритм конкретный узел пригодным для захвата уступа, или нет; бот решает, что если за уступ можно ухватиться, то он обязательно должен это сделать!

Мы можем реализовать быстрый способ решения этой проблемы: мы может вызвать функцию поиска пути дважды. Первый раз мы вызовем ее с параметром useLedges, установленным в false, а второй раз, с установленным в true.

Давайте назначим первый путь в качестве найденного пути вообще без использования захватов уступов:

List<Vector2i> path1 = null;
var path = mMap.mPathFinder.FindPath(
                startTile,
                destination,
                Mathf.CeilToInt(mAABB.HalfSizeX / 8.0f),
                Mathf.CeilToInt(mAABB.HalfSizeY / 8.0f),
                (short)mMaxJumpHeight, false);

Теперь, если path не равен null, нам нужно скопировать результаты в список path1, поскольку, когда мы вызовем искателя пути второй раз, результат в списке path будет перезаписан.

if (path != null)
{
    path1 = new List<Vector2i>();
    path1.AddRange(path);
}

Теперь давайте вызовем искателя пути еще раз, на этот раз активировав захваты уступов.

var path2 = mMap.mPathFinder.FindPath(
                startTile,
                destination,
                Mathf.CeilToInt(mAABB.HalfSizeX / 8.0f),
                Mathf.CeilToInt(mAABB.HalfSizeY / 8.0f),
                (short)mMaxJumpHeight, true);

Мы предположим, что наш итоговый путь будет путем с захватом уступов:

1	path = path2;
2	mGrabsLedges = true;

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

if (path1 != null && path1.Count <= path2.Count + 6)
{
    path = path1;
    mGrabsLedges = false;
}

Обратите внимание, что мы измеряем "длину" пути в количестве узлов, которое может быть довольно неточным из-за процесса фильтрации узлов. Было бы намного более точным рассчитать, например, Манхэттэнскую длину пути (|x1 - x2| + |y1 - y2| для каждого узла), но так как весь этот метод больше является хаком, чем реальным решением, приемлемо использовать здесь этот тип эвристики.

Оставшаяся часть функции следует как есть, путь копируется в буфер экземпляра бота и он начинает следовать ему.

Резюме

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

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

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