A * Pathfinding para plataformas 2D basadas en grid: agarre de borde

Spanish (Español) translation by Elías Nicolás (you can also view the original English article)

En esta parte de nuestra serie sobre la adaptación del algoritmo de identificación de caminos A * para plataformas, presentaremos una nueva mecánica para el personaje: agarre de salientes. También haremos los cambios apropiados tanto en el algoritmo de identificación de ruta como en la IA de bot, para que puedan hacer uso de la movilidad mejorada.

Demo

Puede jugar la demostración de Unity o la versión de WebGL (16 MB) para ver el resultado final en acción. Utilice WASD para mover el personaje, haga clic con el botón izquierdo en un punto para encontrar un camino que pueda seguir para llegar, haga clic con el botón derecho en una celda para alternar el terreno en ese punto, haga clic del medio para colocar una plataforma de un solo sentido y haga clic y arrastre los controles deslizantes para cambiar sus valores.

Mecanica de agarre de borde

Descripción general de los controles

Primero veamos cómo funciona la mecánica de agarre en la demostración para obtener una idea de cómo debemos cambiar nuestro algoritmo de determinación de ruta para tener en cuenta esta nueva mecánica.

Los controles de agarre son bastante simples: si el personaje está justo al lado de un bordemientras se cae, y el jugador presiona la tecla direccional izquierda o derecha para moverlos hacia ese borde, cuando el personaje está en la posición correcta, agarrará el borde.

Una vez que el personaje agarra un borde, el jugador tiene dos opciones: puede saltar hacia arriba o hacia abajo. Saltar funciona normalmente. el jugador presiona la tecla de salto y la fuerza del salto es idéntica a la fuerza aplicada al saltar del suelo. La caída se realiza presionando el botón hacia abajo (S) o la tecla direccional que apunta hacia afuera del borde.

Implementando los controles

Repasemos cómo funcionan los controles de agarre en el código. Lo primero que hay que hacer aquí es detectar si el borde está a la izquierda o a la derecha del personaje:

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

Podemos usar esa información para determinar si se supone que el personaje debe soltar el borde. Como puede ver, para bajar, el jugador necesita:

presionar el botón hacia abajo,
presionar el botón izquierdo cuando estamos agarrando un borde a la derecha, o
presione el botón derecho cuando estamos agarrando un borde a la izquierda.

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))
{

}

Hay una pequeña advertencia aquí. Considere una situación cuando estamos manteniendo presionado el botón hacia abajo y el botón derecho, cuando el personaje se está sosteniendo en un borde a la derecha. Conseguirá la siguiente situación:

El problema aquí es que el personaje agarra el borde inmediatamente después de soltarlo.

Una solución simple a esto es bloquear el movimiento hacia la repisa para un par de cuadros después de que caímos de la repisa. Eso es lo que hace el siguiente fragmento:

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

Después de esto, cambiamos el estado del personaje a Jump, que manejará la física del salto:

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

Finalmente, si el personaje no se cayó del borde, verificamos si se ha presionado la tecla de salto; si es así, establecemos la velocidad vertical del salto y cambiamos el estado:

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

Detectando un punto de agarre

Veamos cómo determinamos si un borde puede ser agarrado. Usamos algunos puntos de acceso alrededor del borde del personaje:

El contorno amarillo representa los límites del personaje. Los segmentos rojos representan los sensores de pared; estos se usan para manejar la física de los personajes. Los segmentos azules representan dónde nuestro personaje puede agarrarse a una repisa.

Para determinar si el personaje puede tomar una repisa, nuestro código constantemente verifica el lado hacia el que se mueve. Está buscando un mosaico vacío en la parte superior del segmento azul, y luego un mosaico sólido debajo del cual el personaje puede agarrarse.

Nota: el agarre de la repisa está bloqueado si el personaje está saltando. Esto se puede notar fácilmente en la demostración y en la animación en la sección Descripción general de los controles.

El principal problema con este método es que si nuestro personaje cae a gran velocidad, es fácil pasar por alto una ventana en la que puede agarrarse a una repisa. Podemos resolver esto buscando todas las fichas comenzando desde la posición del fotograma anterior hasta el fotograma actual en busca de cualquier ficha vacía por encima de una casilla sólida. Si se encuentra uno de esos mosaicos, puede ser agarrado.

Ahora que hemos aclarado cómo funciona la mecánica de agarre de borde, veamos cómo incorporarlo en nuestro algoritmo de determinación de ruta.

Cambios de buscarutas

Hacerlo posible para activar y desactivar el agarre de repisa

Antes que nada, agreguemos un nuevo parámetro a nuestra función FindPath que indica si el Pathfinder debería considerar agarrar cornisas. Lo llamaremos useLedges:

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

Detectar nodos de agarre de repisa

Condiciones

Ahora tenemos que modificar la función para detectar si un nodo en particular puede ser utilizado para agarrar rebordes. Podemos hacer eso luego de verificar si el nodo es un nodo "en el suelo" o un nodo "en el techo", porque en cualquier caso no puede usarse para agarrar el borde.

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)
{

De acuerdo: ahora necesitamos averiguar cuándo un nodo debe considerarse un nodo de apropiación de rebordes. Para cliarity, aquí hay un diagrama que muestra algunos ejemplos de posiciones de agarre de repisa:

... y así es como se ven en el juego:

Los sprites de los personajes principales se estiran para mostrar cómo se ve con los personajes de diferentes tamaños.

Los glóbulos rojos representan los nodos marcados; junto con las celdas verdes, representan el personaje en nuestro algoritmo. Las dos situaciones superiores muestran un borde de agarre de 2x2 caracteres a la izquierda y a la derecha, respectivamente. Los dos de abajo muestran lo mismo, pero el tamaño del personaje aquí es de 1x3 en lugar de 2x2.

Como puede ver, debería ser bastante fácil detectar estos casos en el algoritmo. Las condiciones para el nodo de agarre de la repisa serán las siguientes:

Hay un mosaico sólido junto al recuadro de caracteres superior derecho / superior izquierdo.
Hay un mosaico vacío encima del mosaico sólido encontrado.
No hay ningún mosaico sólido debajo del personaje (no es necesario agarrar las repisas si está en el suelo).

Tenga en cuenta que la tercera condición ya se ha solucionado, ya que buscamos el nodo de agarre de la cornisa solo si el personaje no está en tierra.

En primer lugar, compruebe si realmente queremos detectar las agarres de bordes:

1	else if (useLedges)

Ahora veamos si hay un mosaico a la derecha del nodo de caracteres superior derecho:

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

Y luego, si está arriba de ese mosaico, hay un espacio vacío:

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

Ahora tenemos que hacer lo mismo para el lado izquierdo:

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)))

Hay una cosa más que podemos hacer opcionalmente, que es desactivar encontrar los nodos de agarre de la repisa si la velocidad de caída es demasiado alta, por lo que la ruta no devuelve algunas posiciones extremas de agarre de borde que serían difíciles de seguir por el robot:

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)))
{
}

Después de todo esto, podemos estar seguros de que el nodo encontrado es un nodo de agarre de repisa.

Agregar un nodo especial

¿Qué hacemos cuando encontramos un gancho de agarre? Necesitamos establecer su valor de salto.

Recuerde, el valor de salto es el número que representa qué fase del salto sería el personaje, si llegó a esta celda. Si necesita una recapitulación sobre cómo funciona el algoritmo, eche otro vistazo al artículo de teoría.

Parece que todo lo que tendríamos que hacer es establecer el valor de salto del nodo en 0, ya que desde el punto de agarre de la repisa el personaje puede restablecer un salto de manera efectiva, como si estuviera en el suelo, pero hay un par de puntos para considerar aquí.

En primer lugar, sería bueno si pudiéramos ver a simple vista si el nodo es o no un gancho de seguridad: esto será inmensamente útil al crear un comportamiento de bot y también al filtrar los nodos.
En segundo lugar, normalmente saltar desde el suelo se puede ejecutar desde el punto que sea más adecuado en una ficha concreta, pero al saltar desde una agarradera, el personaje está atascado en una posición particular e incapaz de hacer nada más que empezar a caer o saltar hacia arriba.

Teniendo en cuenta esas advertencias, agregaremos un valor de salto especial para los nodos de agarre de la repisa. Realmente no importa cuál sea este valor, pero es una buena idea hacerlo negativo, ya que eso reducirá nuestras posibilidades de malinterpretar el nodo.

1	const short cLedgeGrabJumpValue = -9;

Ahora, asignemos este valor cuando detectemos un nodo de agarre en el borde:

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

Hacer que cLedgeGrabJumpValue sea negativo tendrá un efecto en el cálculo del costo del nodo; hará que el algoritmo prefiera usar repisas en lugar de omitirlas. Hay dos cosas para notar aquí:

Los puntos de agarre de la cornisa ofrecen una mayor posibilidad de movimiento que cualquier otro nodo en el aire, porque el personaje puede saltar de nuevo al usarlos; desde este punto de vista, es bueno que estos nodos sean más baratos que otros.
Agarrar demasiadas repisas a menudo conduce a movimientos antinaturales, porque generalmente los jugadores no usan agarres de repisa a menos que sean necesarios para llegar a alguna parte.

En la animación anterior, puede ver la diferencia entre avanzar cuando las repisas son preferidas y cuando no lo son.

Por ahora, dejaremos el cálculo del costo tal como está, pero es bastante fácil modificarlo, para hacer que los nodos de borde sean más caros.

Modificar el valor de salto al saltar o caer desde una cornisa

Ahora tenemos que ajustar los valores de salto para los nodos que comienzan desde el punto de agarre de la cornisa. Necesitamos hacer esto porque saltar desde una posición de agarre en el borde es bastante diferente de saltar de un piso. Hay muy poca libertad al saltar de una repisa, porque el personaje está fijo en un punto en particular.

Cuando está en el suelo, el personaje puede moverse libremente hacia la izquierda o hacia la derecha y saltar en el momento más adecuado.

Primero, establezcamos el caso cuando el personaje desciende desde una toma de borde:

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

Como puede ver, la nueva longitud del salto es un poco más grande si el personaje se cae de una repisa: de esta manera compensamos la falta de maniobrabilidad al agarrar una repisa, lo que dará como resultado una velocidad vertical más alta antes de que el jugador pueda alcanzar otros nodos .

El siguiente es el caso donde el personaje cae a un lado de agarrar una repisa:

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

Todo lo que tenemos que hacer es establecer el valor de salto al valor de caída.

Ignorar más nodos

Necesitamos agregar un par de condiciones adicionales para cuando necesitamos ignorar los nodos.

En primer lugar, cuando estamos saltando desde una posición de agarre de reborde, tenemos que ir hacia arriba, no hacia un lado. Esto funciona de manera similar a simplemente saltar desde el suelo. La velocidad vertical es mucho más alta que la velocidad horizontal posible en este punto, y necesitamos modelar este hecho en el algoritmo:

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

Si queremos permitir caer del borde al lado opuesto de esta manera:

Entonces necesitamos editar la condición que no permite el movimiento horizontal cuando el valor de salto es impar. Esto se debe a que, actualmente, nuestro valor especial de agarre de rebordes es igual a -9, por lo que solo es apropiado excluir todos los números negativos de esta condición.

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

Actualice el filtro de nodo

Finalmente, pasemos al filtrado de nodos. Todo lo que tenemos que hacer aquí es agregar una condición para los nodos de agarre de saliente, para que no los filtremos. Simplemente necesitamos verificar si el valor de salto del nodo es igual a cLedgeGrabJumpValue:

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

Todo el filtrado se ve así ahora:

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

Eso es todo, estos son todos los cambios que necesitamos hacer para actualizar el algoritmo de buscarutas.

Cambios de Bot

Ahora que nuestro camino muestra los puntos en los que un personaje puede atrapar una repisa, modifiquemos el comportamiento del bot para que haga uso de estos datos.

Deje de volver a calcular llegar reachedX y reachedY

Antes que nada, para aclarar las cosas en el bot, actualicemos la función GetContext(). El problema actual es que los valores reachedX y reachedY se recalculan constantemente, lo que elimina parte de la información sobre el contexto. Estos valores se usan para ver si el bot ya ha alcanzado el nodo objetivo en sus ejes x e y, respectivamente. (Si necesita una actualización sobre cómo funciona esto, consulte mi tutorial sobre cómo codificar el bot).

Simplemente cambiemos esto para que, si un personaje llega al nodo en el eje x o y, estos valores se mantengan verdaderos siempre que no pasemos al siguiente nodo.

Para que esto sea posible, debemos declarar que se ha reachedX y reachedY como miembros de la clase:

1	public bool mReachedNodeX;
2	public bool mReachedNodeY;

Esto significa que ya no es necesario pasarlos a la función GetContext():

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

Con estos cambios, también debemos restablecer las variables manualmente cada vez que comenzamos a avanzar hacia el siguiente nodo. La primera vez que aparece es cuando acabamos de encontrar la ruta y vamos a movernos hacia el primer nodo:

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;

El segundo es cuando alcanzamos el nodo objetivo actual y queremos avanzar hacia el siguiente:

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

Para dejar de recalcular las variables, debemos reemplazar las siguientes líneas:

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

... con estos, que detectarán si hemos llegado a un nodo en un eje solo si aún no lo hemos alcanzado:

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

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

Por supuesto, también necesitamos reemplazar cualquier otra ocurrencia de reachedX y reachedY con las nuevas versiones declaradas mReachedNodeX y mReachedNodeY.

Ver si el personaje necesita agarrar una cornisa

Vamos a declarar un par de variables que usaremos para determinar si el bot necesita tomar una repisa y, de ser así, cuál:

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

mGrabsLedges es una bandera que le pasamos al algoritmo para que sepa si debe encontrar una ruta que incluya los agarres de la repisa. mMustGrabLeftLedge y mMustGrabRightLedge se usarán para determinar si el siguiente nodo es un gancho de agarre, y si el bot debe agarrar el borde hacia la izquierda o hacia la derecha.

Lo que queremos hacer ahora es crear una función que, dado un nodo, pueda detectar si el personaje en ese nodo será capaz de agarrar una repisa.

Necesitaremos dos funciones para esto: una comprobará si el personaje puede agarrar una repisa a la izquierda, y la otra comprobará si el personaje puede agarrar una repisa a la derecha. Estas funciones funcionarán de la misma manera que nuestro código de ruta de acceso para detectar repisas:

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

Como puede ver, comprobamos si hay un mosaico sólido al lado de nuestro personaje con un mosaico vacío encima.

Ahora vamos a la función GetContext() y asignamos los valores apropiados a mMustGrabRightLedge y mMustGrabLeftLedge. Necesitamos establecerlos en true si se supone que el personaje agarra repisas (es decir, si mGrabsLedges es true) y si hay un borde al que agarrarse.

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

Tenga en cuenta que tampoco queremos agarrar repisas si el nodo de destino está en el suelo.

Actualiza los valores de salto

Como habrás notado, la posición del personaje cuando agarras una repisa es ligeramente diferente a su posición cuando estás justo debajo de ella:

La posición de agarre de la repisa es un poco más alta que la posición de pie, a pesar de que estos caracteres ocupan el mismo nodo. Esto significa que agarrar un borde requerirá un salto ligeramente más alto que simplemente saltar sobre una plataforma, y debemos tener esto en cuenta.

Veamos la función que determina cuánto tiempo debe presionarse el botón de salto:

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

Antes que nada, cambiaremos la condición inicial. El robot debería poder saltar, no solo desde el suelo, sino también cuando está agarrando una repisa:

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

Ahora tenemos que agregar algunos marcos más si está saltando para agarrar una repisa. En primer lugar, necesitamos saber si realmente puede hacer eso, así que creemos una función que nos dirá si el personaje puede tomar una repisa a la izquierda o a la derecha:

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

Ahora agreguemos un par de cuadros al salto cuando el robot necesite agarrarse a una repisa:

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

Como puede ver, prolongamos el salto en 4 cuadros, lo que debería hacer bien el trabajo en nuestro caso.

Pero hay una cosa más que tenemos que cambiar aquí, que en realidad no tiene mucho que ver con el agarre de bordes. Corrige un caso cuando el siguiente nodo tiene la misma altura que el actual, pero no está en el suelo, y el nodo después de eso está en una posición más alta, lo que significa que es necesario un salto:

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))

Implemente la lógica de movimiento para agarrar y soltar las repisas

Queremos dividir la lógica de agarre de repisa en dos fases: una para cuando el robot aún no está lo suficientemente cerca de la repisa para comenzar a agarrar, así que simplemente queremos continuar el movimiento como de costumbre, y uno para cuando el niño pueda comenzar con seguridad avanzando hacia él para agarrarlo.

Comencemos por declarar un booleano que indicará si ya hemos pasado a la segunda fase. Lo llamaremos mCanGrabLedge:

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

Ahora necesitamos definir las condiciones que permitirán al personaje pasar a la segunda fase. Estos son bastante simples:

El bot ya ha alcanzado el nodo objetivo en el eje X.
El bot necesita agarrarse a la repisa izquierda o derecha.
Si el bot se mueve hacia la cornisa, chocará contra una pared en lugar de ir más allá.

Está bien, las dos primeras condiciones son muy fáciles de verificar ahora porque ya hemos hecho todo el trabajo necesario:

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

Ahora, la tercera condición podemos separar en dos partes. El primero se encargará de la situación en la que el personaje se mueve hacia el borde desde la parte inferior y el segundo desde la parte superior. Las condiciones que queremos establecer para el primer caso son:

La posición actual del robot es menor que la posición objetivo (se acerca desde la parte inferior).
La parte superior del cuadro delimitador del personaje es más alta que la altura del borde de la repisa.

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

Si el bot se acerca desde la parte superior, las condiciones son las siguientes:

La posición actual del robot es más alta que la posición objetivo (se acerca desde la parte superior).
La diferencia entre la posición del personaje y la posición del objetivo es menor que la altura del personaje.

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

Ahora combinemos todos estos elementos y establezcamos la bandera que indica que podemos avanzar con seguridad hacia una repisa:

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

Hay una cosa más que queremos hacer aquí, y es comenzar inmediatamente a avanzar hacia la repisa:

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

Bien, ahora, antes de esta gran condición, creemos una más pequeña. Esta será básicamente una versión simplificada para el movimiento cuando el bot está a punto de agarrar una repisa:

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) &&

Esa es la lógica principal detrás del agarre de la repisa, pero todavía hay un par de cosas que hacer.

Necesitamos editar la condición en la que verificamos si está bien moverse al siguiente nodo. Actualmente, la condición se ve así:

1	else if (mReachedNodeX && mReachedNodeY)

Ahora también tenemos que movernos al siguiente nodo si el bot estaba listo para agarrar el borde y luego realmente lo hizo:

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

Manejar saltar y caer desde la cornisa

Una vez que el bot está en la repisa, debería poder saltar de forma normal, así que agreguemos una condición adicional a la rutina de salto:

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

Lo siguiente que el robot necesita para poder hacer es dejar caer gentilmente la repisa. Con la implementación actual es muy simple: si tomamos una repisa y no saltamos, ¡obviamente tenemos que abandonarla!

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

¡Eso es! Ahora el personaje puede salir sin problemas de la posición de agarre de la cornisa, sin importar si necesita saltar o simplemente desplegarse.

Deja de agarrar repisas todo el tiempo!

Por el momento, el bot agarra cada repisa que puede, independientemente de si tiene sentido hacerlo.

Una solución para esto es asignar un gran costo heurístico a los agarres de repisa, por lo que el algoritmo prioriza en contra de usarlos si no es necesario, pero esto requeriría que nuestro robot tenga un poco más de información sobre los nodos. Como todo lo que pasamos al bot es una lista de puntos, no sabemos si el algoritmo significaba que un nodo particular debía ser agarrado o no; el bot supone que si se puede agarrar una repisa, seguramente debería.

Podemos implementar una solución rápida para este comportamiento: llamaremos a la función buscarutas dos veces. La primera vez que lo llamaremos con el parámetro useLedges establecido en false, y la segunda vez con set en true.

Asignemos la primera ruta como la ruta encontrada sin usar ninguna captura de repisa:

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

Ahora, si esta path no es nula, debemos copiar los resultados en nuestra lista path1, porque cuando llamamos al Pathfinder por segunda vez, el resultado en path se sobrescribirá.

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

Ahora llamemos al Pathfinder de nuevo, esta vez habilitando los agarres de repisa:

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

Asumiremos que nuestra ruta final va a ser la ruta con agarres de repisa:

1	path = path2;
2	mGrabsLedges = true;

Y justo después de esto, verifiquemos nuestra suposición. Si encontramos un camino sin agarres de repisa, y ese camino no es mucho más largo que el camino que los usa, entonces haremos que el bot deshabilite los agarres de repisa.

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

Tenga en cuenta que medimos la "longitud" de la ruta en el recuento de nodos, que puede ser bastante inexacta debido al proceso de filtrado de nodos. Sería mucho más exacto calcular, por ejemplo, la longitud Manhattan de la ruta (|x1 - x2| + |y1 - y2| de cada nodo), pero dado que este método es más un hack que una solución real , está bien usar este tipo de heurística aquí.

El resto de la función sigue como estaba; la ruta se copia al búfer de la instancia del bot y comienza a seguirla.

Resumen

¡Eso es todo por el tutorial! Como puede ver, no es tan difícil extender el algoritmo para agregar posibilidades de movimiento adicionales, pero hacerlo definitivamente aumenta la complejidad y agrega algunos problemas problemáticos.

De nuevo, la falta de precisión puede mordernos aquí más de una vez, especialmente cuando se trata del movimiento de caída: esta es el área que necesita más mejora, pero he tratado de hacer que el algoritmo coincida con la física lo mejor posible. con el conjunto actual de valores.

Con todo, el robot puede atravesar un nivel de una manera que rivalizaría con muchos jugadores, ¡y estoy muy satisfecho con ese resultado!