A * Pathfinding para plataformas 2D basadas en grid: hacer que un bot siga el camino

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

En este tutorial, usaremos el algoritmo de pathfinding de plataformas que hemos estado creando para alimentar un bot que puede seguir el camino por sí mismo; solo haga clic en una ubicación y se ejecutará y saltará para llegar allí. ¡Esto es muy útil para NPC!

Demo

Puede jugar la demostración de Unity, o la versión de WebGL (100MB +), 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 para colocar una plataforma de un solo sentido y haga clic y arrastre los controles deslizantes para cambiar sus valores.

Actualizando el motor

Manejo del estado Bot

El bot tiene dos estados definidos: el primero es para no hacer nada, y el segundo es para manejar el movimiento. Sin embargo, en tu juego probablemente necesitarás muchas más para cambiar el comportamiento del robot de acuerdo con la situación.

public enum BotState
{
  None = 0,
	MoveTo,
}

El ciclo de actualización del bot hará cosas diferentes dependiendo del estado asignado actualmente a mCurrentBotState:

void BotUpdate()
{
    switch (mCurrentBotState)
    {
        case BotState.None:
            /* no need to do anything */
            break;
            
        case BotState.MoveTo:
            /* bot movement update logic */
            break;
    }
    
    CharacterUpdate();
}

La función CharacterUpdate maneja todas las entradas y actualizaciones físicas para el bot.

Para cambiar el estado, usaremos una función ChangeState que simplemente asigna el nuevo valor a mCurrentBotState:

1	public void ChangeState(BotState newState)
2	{
3	mCurrentBotState = newState;
4	}

Controlando el Bot

Controlaremos el robot simulando entradas, que asignaremos a una matriz de Booleanos:

1	protected bool[] mInputs;

Esta matriz está indexada por la enumeración KeyInput enum:

public enum KeyInput
{
    GoLeft = 0,
	GoRight,
	GoDown,
	Jump,
	Count
}

Por ejemplo, si queremos simular presionar el botón izquierdo, lo haremos así:

1	mInputs[(int)KeyInput.GoLeft] = true;

La lógica de caracteres manejará esta entrada artificial de la misma manera que manejaría la entrada real.

También necesitaremos una función de ayuda adicional o una tabla de búsqueda para obtener la cantidad de fotogramas que necesitamos presionar el botón de salto jump para saltar una cantidad determinada de bloques:

int GetJumpFrameCount(int deltaY)
{
    if (deltaY <= 0)
        return 0;
    else
    {
        switch (deltaY)
        {
            case 1:
                return 1;
            case 2:
                return 2;
            case 3:
                return 5;
            case 4:
                return 8;
            case 5:
                return 14;
            case 6:
                return 21;
            default:
                return 30;
        }
    }
}

Tenga en cuenta que esto solo funcionará si nuestro juego se actualiza con una frecuencia fija y la velocidad de salto inicial del personaje es la misma. Lo ideal es que calculemos estos valores por separado para cada personaje dependiendo de la velocidad de salto de ese personaje, pero lo anterior funcionará bien en nuestro caso.

Preparar y obtener el camino para seguir

Restringir la ubicación del objetivo

Antes de que realmente usemos el Pathfinder, sería una buena idea forzar el objetivo de destino en el suelo. Esto se debe a que es bastante probable que el jugador haga clic en un punto que está ligeramente por encima del suelo, en cuyo caso el camino del bot terminaría con un salto incómodo en el aire. Al reducir el punto final para que esté justo en la superficie del suelo, podemos evitarlo fácilmente.

Primero, veamos la función TappedOnTile. Se llama a esta función cuando el jugador hace clic en cualquier parte del juego; el parámetro mapPos es la posición de la ficha en la que el jugador hizo clic:

1	public void TappedOnTile(Vector2i mapPos)
2	{
3	}

Necesitamos bajar la posición de la teja cliqueada hasta que esté en el suelo:

public void TappedOnTile(Vector2i mapPos)
{
    while (!(mMap.IsGround(mapPos.x, mapPos.y)))
        --mapPos.y;
}

Finalmente, una vez que llegamos a un mosaico de tierra, sabemos a dónde queremos mover el personaje:

public void TappedOnTile(Vector2i mapPos)
{
    while (!(mMap.IsGround(mapPos.x, mapPos.y)))
        --mapPos.y;

    MoveTo(new Vector2i(mapPos.x, mapPos.y + 1));
}

Determinar la ubicación de inicio

Antes de que realmente llamemos a la función FindPath, debemos asegurarnos de pasar la celda inicial correcta.

Primero, supongamos que el mosaico inicial es la celda inferior izquierda de un personaje:

1	public void MoveTo(Vector2i destination)
2	{
3	Vector2i startTile = mMap.GetMapTileAtPoint(mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f);
4	}

Este mosaico puede no ser el que queremos pasar al algoritmo como el primer nodo, porque si nuestro personaje está de pie en el borde de la plataforma, el startTile calculado de esta manera puede no tener base, como en la siguiente situación:

En este caso, nos gustaría establecer el nodo inicial en el mosaico que está en el lado izquierdo del personaje, no en el centro.

Comencemos creando una función que nos dirá si el personaje se ajustará a una posición diferente, y si lo hace, si está en el suelo en ese punto:

1	bool IsOnGroundAndFitsPos(Vector2i pos)
2	{
3	}

Primero, veamos si el personaje encaja en el lugar. Si no lo hace, podemos devolverlo de inmediato false:

bool IsOnGroundAndFitsPos(Vector2i pos)
{
    for (int y = pos.y; y < pos.y + mHeight; ++y)
    {
        for (int x = pos.x; x < pos.x + mWidth; ++x)
        {
            if (mMap.IsObstacle(x, y))
                return false;
        }
    }
}

Ahora podemos ver si alguna de las fichas debajo del personaje son mosaicos:

bool IsOnGroundAndFitsPos(Vector2i pos)
{
    for (int y = pos.y; y < pos.y + mHeight; ++y)
    {
        for (int x = pos.x; x < pos.x + mWidth; ++x)
        {
            if (mMap.IsObstacle(x, y))
                return false;
        }
    }

    for (int x = pos.x; x < pos.x + mWidth; ++x)
    {
        if (mMap.IsGround(x, pos.y - 1))
            return true;
    }

    return false;
}

Volvamos a la función MoveTo, y veamos si tenemos que cambiar el mosaico de inicio. Necesitamos hacer eso si el personaje está en el suelo pero la ficha de inicio no es:

Vector2i startTile = mMap.GetMapTileAtPoint(mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f);
        
if (mOnGround && !IsOnGroundAndFitsPos(startTile))
{
}

Sabemos que, en este caso, el personaje se encuentra en el borde izquierdo o derecho de la plataforma.

Primero revisemos el borde derecho; si el personaje encaja allí y el azulejo está en el suelo, entonces tenemos que mover el azulejo de inicio un espacio hacia la derecha. Si no es así, entonces tenemos que moverlo hacia la izquierda.

if (mOnGround && !IsOnGroundAndFitsPos(startTile))
{
    if (IsOnGroundAndFitsPos(new Vector2i(startTile.x + 1, startTile.y)))
        startTile.x += 1;
    else
        startTile.x -= 1;
}

Ahora deberíamos tener todos los datos que necesitamos para llamar al Pathfinder:

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

El primer argumento es el azulejo de inicio.

El segundo es el destino; podemos pasar esto como está.

El tercer y cuarto argumentos son el ancho y la altura que deben aproximarse por el tamaño del mosaico. Tenga en cuenta que aquí queremos usar el techo de la altura en las teselas, así que, por ejemplo, si la altura real del personaje es de 2,3 azulejos, queremos que el algoritmo crea que el personaje tiene 3 tejas de alto. (Es mejor si la altura real del personaje es en realidad un poco menor que su tamaño en mosaicos, para permitir un poco más de espacio para los errores de la ruta después de AI).

Finalmente, el quinto argumento es la altura máxima de salto del personaje.

Copia de seguridad de la lista de nodos

Después de ejecutar el algoritmo, debemos verificar si el resultado es correcto, es decir, si se ha encontrado alguna ruta:

1	if (path != null && path.Count > 1)
2	{
3	}

Si es así, tenemos que copiar los nodos a un búfer separado, porque si algún otro objeto llamara a la función FindPath del Pathfinder en este momento, el viejo resultado se sobrescribirá. Copiar el resultado en una lista separada evitará esto.

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

Como puede ver, estamos copiando el resultado en orden inverso; esto se debe a que el resultado en sí se invierte. Hacer esto significa que los nodos en la lista mPath estarán en orden primordial.

Ahora establezcamos el nodo objetivo actual. Como el primer nodo de la lista es el punto de partida, podemos omitirlo y proceder desde el segundo nodo en adelante:

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

Después de establecer el nodo del objetivo actual, establecemos el estado del bot en MoveTo, por lo que se habilitará un estado apropiado.

Obteniendo el contexto

Antes de comenzar a escribir las reglas para el movimiento de IA, debemos ser capaces de encontrar en qué situación se encuentra el personaje en cualquier punto dado.

Necesitamos saber:

las posiciones de los destinos anterior, actual y siguiente
si el destino actual está en el suelo o en el aire
si el personaje ha alcanzado el destino actual en el eje x
si el personaje ha alcanzado el destino actual en el eje y

Nota: los destinos aquí no son necesariamente el destino objetivo final; son los nodos en la lista de la sección anterior.

Esta información nos permitirá determinar con precisión qué debe hacer el robot en cualquier situación.

Comencemos por declarar una función para obtener este contexto:

1	public void GetContext(out Vector2 prevDest, out Vector2 currentDest, out Vector2 nextDest, out bool destOnGround, out bool reachedX, out bool reachedY)
2	{
3	}

Cálculo de posiciones mundiales de nodos de destino

Lo primero que debemos hacer en la función es calcular la posición mundial de los nodos de destino.

Comencemos por calcular esto para el destino anterior. Esta operación depende de cómo esté configurado tu mundo de juego; en mi caso, las coordenadas del mapa no coinciden con las coordenadas del mundo, por lo que debemos traducirlas.

Traducirlos es realmente simple: solo necesitamos multiplicar la posición del nodo por el tamaño de un mosaico, y luego compensar el vector calculado por la posición del mapa:

1	prevDest = new Vector2(mPath[mCurrentNodeId - 1].x * Map.cTileSize + mMap.transform.position.x,
2	mPath[mCurrentNodeId - 1].y * Map.cTileSize + mMap.transform.position.y);

Tenga en cuenta que comenzamos con mCurrentNodeId igual a 1, por lo que no debe preocuparse por intentar accidentalmente acceder a un nodo con un índice de -1.

Calcularemos la posición del destino actual de la misma manera:

1	currentDest = new Vector2(mPath[mCurrentNodeId].x * Map.cTileSize + mMap.transform.position.x,
2	mPath[mCurrentNodeId].y * Map.cTileSize + mMap.transform.position.y);

Y ahora para la posición del próximo destino. Aquí debemos verificar si queda algún nodo después de alcanzar nuestro objetivo actual, así que primero supongamos que el siguiente destino es el mismo que el actual:

1	nextDest = currentDest;

Ahora, si quedan nodos, calcularemos el próximo destino de la misma manera que hicimos con los dos anteriores:

if (mPath.Count > mCurrentNodeId + 1)
{
    nextDest = new Vector2(mPath[mCurrentNodeId + 1].x * Map.cTileSize + mMap.transform.position.x,
                                  mPath[mCurrentNodeId + 1].y * Map.cTileSize + mMap.transform.position.y);
}

Comprobando si el nodo está en el suelo

El siguiente paso es determinar si el destino actual está en el suelo.

Recuerda que no es suficiente solo verificar el azulejo directamente debajo del objetivo; tenemos que considerar los casos donde el personaje tiene más de un bloque de ancho:

Comencemos suponiendo que la posición del destino no está en el suelo:

1	destOnGround = false;

Ahora miraremos a través de las teselas debajo del destino para ver si hay algún bloque sólido allí. Si hay, podemos establecer destOnGround a verdadero true:

for (int x = mPath[mCurrentNodeId].x; x < mPath[mCurrentNodeId].x + mWidth; ++x)
{
    if (mMap.IsGround(x, mPath[mCurrentNodeId].y - 1))
    {
        destOnGround = true;
        break;
    }
}

Comprobando si el nodo ha sido alcanzado en el eje X

Antes de que podamos ver si el personaje ha alcanzado la meta, necesitamos saber su posición en la ruta. Esta posición es básicamente el centro de la celda inferior izquierda de nuestro personaje. Dado que nuestro personaje no está construido en realidad a partir de celdas, simplemente vamos a usar la posición inferior izquierda del recuadro delimitador del personaje más la mitad de una celda:

1	Vector2 pathPosition = mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f;

Esta es la posición que necesitamos para que coincida con los nodos objetivo.

¿Cómo podemos determinar si el personaje ha alcanzado la meta en el eje x? Sería seguro asumir que, si el personaje se mueve hacia la derecha y tiene una posición x mayor o igual a la del destino, entonces se ha alcanzado el objetivo.

Para ver si el personaje se movía correctamente, usaremos el destino anterior, que en este caso debe haber estado a la izquierda del actual:

1	reachedX = (prevDest.x <= currentDest.x && pathPosition.x >= currentDest.x);

Lo mismo se aplica al lado opuesto; si el destino anterior estaba a la derecha del actual y la posición x del personaje es menor o igual que la posición del objetivo, entonces podemos estar seguros de que el personaje ha alcanzado el objetivo en el eje x:

1	reachedX = (prevDest.x <= currentDest.x && pathPosition.x >= currentDest.x)
2	\|\| (prevDest.x >= currentDest.x && pathPosition.x <= currentDest.x);

Ajustar la posición del personaje

A veces, debido a la velocidad del personaje, excede el destino, lo que puede hacer que no aterrice en el nodo objetivo. Vea el siguiente ejemplo:

Para arreglar esto, ajustaremos la posición del personaje para que aterrice en el nodo objetivo.

Las condiciones para que podamos ajustar el personaje son:

El objetivo se ha alcanzado en el eje x.
La distancia entre la posición del bot y el destino actual es mayor que cBotMaxPositionError.
La distancia entre la posición del bot y el destino actual no es muy grande, por lo que no capturamos al personaje desde lejos.
El personaje no se movió ni a la izquierda ni a la derecha en el último turno, por lo que restamos al personaje solo si cae directamente hacia abajo.

if (reachedX && Mathf.Abs(pathPosition.x - currentDest.x) > Constants.cBotMaxPositionError && Mathf.Abs(pathPosition.x - currentDest.x) < Constants.cBotMaxPositionError*3.0f && !mPrevInputs[(int)KeyInput.GoRight] && !mPrevInputs[(int)KeyInput.GoLeft])
{
    pathPosition.x = currentDest.x;
    mPosition.x = pathPosition.x - Map.cTileSize * 0.5f + mAABB.HalfSizeX + mAABBOffset.x;
}

cBotMaxPositionError en este tutorial es igual a 1 píxel; esto es lo lejos que dejamos que el personaje sea desde el destino mientras le permitimos ir al siguiente objetivo.

Comprobando si el nodo ha sido alcanzado en el eje Y

Vamos a averiguar cuándo podemos estar seguros de que el personaje ha alcanzado la posición Y de su objetivo. Antes que nada, si el destino anterior está por debajo del actual, y nuestro personaje salta a la altura del objetivo actual, entonces podemos suponer que se ha alcanzado el objetivo.

1	reachedY = (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.y);

De manera similar, si el destino actual está por debajo del anterior y el personaje ha alcanzado la posición y del nodo actual, también podemos establecer que reachedY a verdadero true .

1	reachedY = (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.)
2	\|\| (prevDest.y >= currentDest.y && pathPosition.y <= currentDest.y);

Independientemente de si el personaje necesita saltar o caer para llegar a la posición y del nodo de destino, si está muy cerca, entonces debemos establecer que reachedY también sea verdadero true :

reachedY = (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.y)

    || (prevDest.y >= currentDest.y && pathPosition.y <= currentDest.y)

    || (Mathf.Abs(pathPosition.y - currentDest.y) <= Constants.cBotMaxPositionError);

Si el destino está en el suelo pero el personaje no, podemos suponer que no se ha alcanzado la posición Y del objetivo actual:

1	if (destOnGround && !mOnGround)
2	reachedY = false;

Eso es todo, esos son todos los datos básicos que necesitamos saber para considerar qué tipo de movimiento necesita hacer la IA.

Manejando el movimiento del Bot

Lo primero que debe hacer en nuestra función de actualización update es obtener el contexto que acabamos de implementar:

1	Vector2 prevDest, currentDest, nextDest;
2	bool destOnGround, reachedY, reachedX;
3	GetContext(out prevDest, out currentDest, out nextDest, out destOnGround, out reachedX, out reachedY);

Ahora vamos a obtener la posición actual del personaje a lo largo del camino. Calculamos esto de la misma manera que lo hicimos en la función GetContext:

1	Vector2 pathPosition = mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f;

Al comienzo del cuadro, necesitamos restablecer las entradas falsas y asignarlas solo si surge una condición para hacerlo. Utilizaremos solo cuatro entradas: dos para el movimiento hacia la izquierda y hacia la derecha, una para saltar, y una para dejar caer una plataforma de una vía.

1	mInputs[(int)KeyInput.GoRight] = false;
2	mInputs[(int)KeyInput.GoLeft] = false;
3	mInputs[(int)KeyInput.Jump] = false;
4	mInputs[(int)KeyInput.GoDown] = false;

La primera condición para el movimiento será esta: si el destino actual es más bajo que la posición del personaje y el personaje está de pie sobre una plataforma unidireccional, entonces presione el botón hacia abajo down, lo que debería provocar que el personaje salte de la plataforma hacia abajo :

1	if (pathPosition.y - currentDest.y > Constants.cBotMaxPositionError && mOnOneWayPlatform)
2	mInputs[(int)KeyInput.GoDown] = true;

Manejo de saltos

Vamos a explicar cómo deberían funcionar nuestros saltos. En primer lugar, no queremos mantener presionado el botón de salto si mFramesOfJumping es 0.

1	if (mFramesOfJumping > 0)
2	{
3	}

La segunda condición para verificar es que el personaje no está en el suelo.

En esta implementación de la física de plataformas, el personaje puede saltar si simplemente se salió del borde de una plataforma y ya no está en el suelo. Este es un método popular para mitigar la ilusión de que el jugador ha presionado el botón de salto pero el personaje no saltó, lo que podría haber aparecido debido al retraso de entrada o al jugador presionando el botón de salto justo después de que el personaje se movió fuera de la plataforma.

1	if (mFramesOfJumping > 0 && !mOnGround)
2	{
3	}

Esta condición funcionará si el personaje necesita saltar de una repisa, porque los marcos de salto se establecerán en una cantidad apropiada, el personaje saldrá naturalmente de la cornisa, y en ese punto también comenzará el salto.

Esto no funcionará si el salto debe realizarse desde el suelo; Para manejar estos debemos verificar estas condiciones: El personaje ha llegado a la posición x del nodo de destino, donde comenzará a saltar.

El nodo de destino no está en el suelo; si vamos a saltar, primero tenemos que atravesar un nodo que está en el aire.
El nodo de destino no está en el suelo; si vamos a saltar, primero tenemos que atravesar un nodo que está en el aire.

1	if (mFramesOfJumping > 0 &&
2	(!mOnGround \|\| (reachedX && !destOnGround)))
3	{
4	}

El personaje también debería saltar si está en el suelo y el destino también está en el suelo. Esto generalmente sucederá si el personaje necesita saltar un azulejo hacia arriba y hacia un lado para alcanzar una plataforma que está a solo un bloque más arriba.

1	if (mFramesOfJumping > 0 &&
2	(!mOnGround \|\| (reachedX && !destOnGround) \|\| (mOnGround && destOnGround)))
3	{
4	}

Ahora activemos el salto y disminuyamos los marcos de salto, de modo que el personaje tenga el salto para la cantidad correcta de cuadros:

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

Tenga en cuenta que disminuimos los mFramesOfJumping solo si el personaje no está en el suelo. Esto es para evitar disminuir accidentalmente la longitud del salto antes de comenzar el salto.

Procediendo al siguiente nodo de destino

Pensemos en lo que debe suceder cuando lleguemos al nodo, es decir, cuando ambos reachedX y reachedY sean verdaderos true.

1	if (reachedX && reachedY)
2	{
3	}

Primero, incrementaremos la ID del nodo actual:

1	mCurrentNodeId++;

Ahora necesitamos verificar si esta ID es mayor que la cantidad de nodos en nuestra ruta. Si lo es, eso significa que el personaje ha alcanzado el objetivo:

if (mCurrentNodeId >= mPath.Count)
{
    mCurrentNodeId = -1;
    ChangeState(BotState.None);
    break;
}

Lo siguiente que debemos hacer es calcular el salto para el siguiente nodo. Ya que necesitaremos usar esto en más de un lugar, hagamos una función para ello:

1	public int GetJumpFramesForNode(int prevNodeId)
2	{
3	}

Solo queremos saltar si el nuevo nodo es más alto que el anterior y el personaje está en el suelo:

public int GetJumpFramesForNode(int prevNodeId)
{
    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
    }
}

Para saber cuántos mosaicos tendremos que saltar, vamos a iterar a través de los nodos mientras vayan subiendo más y más. Cuando llegamos a un nodo que está a una altura más baja, o un nodo que tiene tierra debajo de él, podemos detenernos, ya que sabemos que no habrá necesidad de ir más allá de eso.

Primero, declaremos y establezcamos la variable que contendrá el valor del salto:

public int GetJumpFramesForNode(int prevNodeId)
{
    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
        int jumpHeight = 1;
    }
}

Ahora iteremos a través de los nodos, comenzando en el nodo actual:

public int GetJumpFramesForNode(int prevNodeId)
{
    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
        int jumpHeight = 1;
        
        for (int i = currentNodeId; i < mPath.Count; ++i)
        {
        }
    }
}

Si el siguiente nodo es más alto que el jumpHeight, y no está en el suelo, establezcamos la nueva altura del salto:

public int GetJumpFramesForNode(int prevNodeId)
{
    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 && !mMap.IsGround(mPath[i].x, mPath[i].y - 1))
                    jumpHeight = mPath[i].y - mPath[prevNodeId].y;
        }
    }
}

Si la altura del nuevo nodo es más baja que la anterior, o está en el suelo, entonces devolvemos el número de cuadros de salto necesarios para la altura encontrada. (Y si no hay necesidad de saltar, devolvamos 0.)

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

Necesitamos llamar a esta función en dos lugares.

El primero es en el caso donde el personaje ha alcanzado las posiciones x e y del nodo:

if (reachedX && reachedY)
{
    int prevNodeId = mCurrentNodeId;
    mCurrentNodeId++;

    if (mCurrentNodeId >= mPath.Count)
    {
        mCurrentNodeId = -1;
        ChangeState(BotState.None);
        break;
    }

    if (mOnGround)
        mFramesOfJumping = GetJumpFramesForNode(prevNodeId);
}

Tenga en cuenta que establecemos los fotogramas de salto para todo el salto, por lo que cuando lleguemos a un nodo en el aire no queremos cambiar el número de fotogramas de salto que se determinaron antes de que se produjera el salto.

Después de actualizar el objetivo, tenemos que procesar todo de nuevo, por lo que el siguiente marco de movimiento se calcula de inmediato. Para esto, usaremos un comando goto:

1	goto case BotState.MoveTo;

El segundo lugar para el que debemos calcular el salto es la función MoveTo, porque podría ser el caso de que el primer nodo de la ruta sea un nodo de salto:

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

    mCurrentNodeId = 1;

    ChangeState(BotState.MoveTo);

    mFramesOfJumping = GetJumpFramesForNode(0);
}

Manejo del movimiento para alcanzar la posición X del nodo

Ahora manejemos el movimiento para el caso donde el personaje aún no ha alcanzado la posición x del nodo objetivo.

Nada complicado aquí; si el destino está a la derecha, debemos simular el botón derecho presionar. Si el destino está a la izquierda, entonces tenemos que simular el botón izquierdo presionar. Solo tenemos que mover el carácter si la diferencia de posición es mayor que la constante cBotMaxPositionError:

else if (!reachedX)
{
    if (currentDest.x - pathPosition.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoRight] = true;
    else if (pathPosition.x - currentDest.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoLeft] = true;
}

Manejo del movimiento para alcanzar la posición Y del nodo

Si el personaje ha alcanzado la posición x de destino, pero aún así lo hacemos para saltar más alto, aún podemos mover el personaje hacia la izquierda o hacia la derecha dependiendo de dónde esté el próximo objetivo. Esto solo significará que el personaje no se pegará tan rígidamente al camino encontrado. Gracias a eso, será mucho más fácil llegar al siguiente destino, porque en lugar de simplemente esperar para alcanzar la posición y de destino, el personaje se moverá naturalmente hacia la posición x del siguiente nodo mientras lo hace.

Solo moveremos al personaje hacia el próximo destino si existe y no está en el suelo. (Si está en el suelo, no podemos omitirlo porque es un punto de control importante; restablece la velocidad vertical del personaje y le permite volver a usar el salto).

1	else if (!reachedY && mPath.Count > mCurrentNodeId + 1 && !destOnGround)
2	{
3
4	}

Pero antes de avanzar hacia el siguiente objetivo, debemos verificar que no rompamos el camino al hacerlo.

Evitar romper una caída prematuramente

Considere la siguiente situación:

Aquí, tan pronto como el personaje salió de la repisa donde comenzó, alcanzó la posición x del segundo nodo, y estaba cayendo para alcanzar la posición y. Como el tercer nodo estaba a la derecha del personaje, se movió a la derecha y terminó en un túnel por encima del que queríamos que entrara.

Para solucionar esto, debemos verificar si existen obstáculos entre el personaje y el próximo destino; si no hay, entonces somos libres de mover al personaje hacia él; si hay, entonces tenemos que esperar.

Primero, veamos qué fichas necesitaremos verificar. Si el próximo objetivo está a la derecha del actual, entonces necesitaremos revisar los cuadros a la derecha; si está a la izquierda, entonces necesitaremos revisar las fichas a la izquierda. Si se encuentran en la misma posición x, no hay ninguna razón para realizar ningún movimiento preventivo.

int checkedX = 0;

int tileX, tileY;
mMap.GetMapTileAtPoint(pathPosition, out tileX, out tileY);

if (mPath[mCurrentNodeId + 1].x != mPath[mCurrentNodeId].x)
{
    if (mPath[mCurrentNodeId + 1].x > mPath[mCurrentNodeId].x)
        checkedX = tileX + mWidth;
    else
        checkedX = tileX - 1;
}

Como puede ver, la coordenada x del nodo a la derecha depende del ancho del carácter.

Ahora podemos verificar si hay alguna tesela entre el personaje y la posición del próximo nodo en el eje y:

1	if (checkedX != 0 && !mMap.AnySolidBlockInStripe(checkedX, tileY, mPath[mCurrentNodeId + 1].y))
2	{
3	}

La función AnySolidBlockInStripe comprueba si hay alguna tesela sólida entre dos puntos determinados en el mapa. Los puntos deben tener la misma coordenada x. La coordenada x que estamos verificando es a la que nos gustaría que se mueva el personaje, pero no estamos seguros si podemos, como se explicó anteriormente.

Aquí está la implementación de la función.

public bool AnySolidBlockInStripe(int x, int y0, int y1)
{
    int startY, endY;

    if (y0 <= y1)
    {
        startY = y0;
        endY = y1;
    }
    else
    {
        startY = y1;
        endY = y0;
    }

    for (int y = startY; y <= endY; ++y)
    {
        if (GetTile(x, y) == TileType.Block)
            return true;
    }

    return false;
}

Como puede ver, la función es realmente simple; simplemente itera a través de las teselas en una columna, empezando por la inferior.

Ahora que sabemos que podemos avanzar hacia el próximo destino, hagámoslo:

if (checkedX != 0 && !mMap.AnySolidBlockInStripe(checkedX, tileY, mPath[mCurrentNodeId + 1].y))
{
    if (nextDest.x - pathPosition.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoRight] = true;
    else if (pathPosition.x - nextDest.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoLeft] = true;
}

Permitir que el Bot salte los nodos

Eso es casi todo, pero aún hay un caso por resolver. Aquí hay un ejemplo:

Como puede ver, antes de que el personaje alcanzara la posición y del segundo nodo, se golpeó la cabeza contra el mosaico flotante, porque lo hicimos avanzar hacia el siguiente destino a la derecha. Como resultado, el personaje nunca llega a la posición y del segundo nodo; en su lugar, se movió directamente al tercer nodo. Como reachY es falso false en este caso, no puede continuar con la ruta.

Para evitar estos casos, simplemente comprobaremos si el personaje alcanzó el siguiente objetivo antes de alcanzar el actual.

El primer paso hacia esto será separar nuestros cálculos previos de reachX y reachedY en sus propias funciones:

public bool ReachedNodeOnXAxis(Vector2 pathPosition, Vector2 prevDest, Vector2 currentDest)
{
    return (prevDest.x <= currentDest.x && pathPosition.x >= currentDest.x)
        || (prevDest.x >= currentDest.x && pathPosition.x <= currentDest.x)
        || Mathf.Abs(pathPosition.x - currentDest.x) <= Constants.cBotMaxPositionError;
}

public bool ReachedNodeOnYAxis(Vector2 pathPosition, Vector2 prevDest, Vector2 currentDest)
{
    return (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.y)
        || (prevDest.y >= currentDest.y && pathPosition.y <= currentDest.y)
        || (Mathf.Abs(pathPosition.y - currentDest.y) <= Constants.cBotMaxPositionError);
}

A continuación, reemplace los cálculos con la llamada de función en la función GetContext:

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

Ahora podemos verificar si se ha alcanzado el siguiente destino. Si es así, simplemente podemos incrementar mCurrentNode e inmediatamente volver a hacer la actualización de estado. Esto hará que el siguiente destino se convierta en el actual, y como el personaje ya lo alcanzó, podremos continuar:

if (checkedX != 0 && !mMap.AnySolidBlockInStripe(checkedX, tileY, mPath[mCurrentNodeId + 1].y))
{
    if (nextDest.x - pathPosition.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoRight] = true;
    else if (pathPosition.x - nextDest.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoLeft] = true;

    if (ReachedNodeOnXAxis(pathPosition, currentDest, nextDest) && ReachedNodeOnYAxis(pathPosition, currentDest, nextDest))
    {
        mCurrentNodeId += 1;
        goto case BotState.MoveTo;
    }
}

¡Eso es todo por el movimiento del personaje!

Manejo de condiciones de reinicio

Es bueno tener un plan de respaldo para una situación en la que el robot no se está moviendo por el camino como debería. Esto puede suceder si, por ejemplo, se cambia el mapa, agregar un obstáculo a una ruta ya calculada puede hacer que la ruta se vuelva inválida. Lo que haremos es restablecer la ruta si el personaje está atrapado por más tiempo que una cantidad determinada de cuadros.

Entonces, declaremos las variables que contarán cuántos marcos ha estado atrapado el personaje y cuántos marcos puede estar atascado como máximo:

1	public int mStuckFrames = 0;
2	public const int cMaxStuckFrames = 20;

Necesitamos restablecer esto cuando llamamos a la función MoveTo:

public void MoveTo(Vector2i destination)
{
    mStuckFrames = 0;
    /*
    ...
    */
}

Y finalmente, al final de BotState.MoveTo, vamos a verificar si el personaje está atascado. Aquí, simplemente necesitamos verificar si su posición actual es igual a la anterior; si es así, también necesitamos incrementar los mStuckFrames y verificar si el personaje ha estado atascado para más cuadros que cMaxStuckFrames, y si lo fue, entonces necesitamos llamar a la función MoveTo con el último nodo de la ruta actual como parámetro. Por supuesto, si la posición es diferente, entonces debemos restablecer mStuckFrames a 0:

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

if (mPosition == mOldPosition)
{
    ++mStuckFrames;
    if (mStuckFrames > cMaxStuckFrames)
        MoveTo(mPath[mPath.Count - 1]);
}
else
    mStuckFrames = 0;

Ahora el personaje debería encontrar una ruta alternativa si no pudo terminar la ruta inicial.

Conclusión

¡Ese es todo el tutorial! Ha sido mucho trabajo, pero espero que encuentres útil este método. No es de ninguna manera una solución perfecta para el pathfinding de plataformas; la aproximación de la curva de salto para el personaje que el algoritmo necesita hacer es a menudo bastante difícil de hacer y puede conducir a un comportamiento incorrecto. El algoritmo aún se puede ampliar, no es muy difícil agregar rebordes y otros tipos de flexibilidad de movimiento extendido, pero hemos cubierto la mecánica básica de plataformas. También es posible optimizar el código para hacerlo más rápido y utilizar menos memoria; esta iteración del algoritmo no es perfecta cuando se trata de esos aspectos. También sufre una aproximación bastante pobre de la curva cuando cae a gran velocidad.

El algoritmo se puede utilizar de muchas maneras, sobre todo para mejorar a los compañeros AI o AI enemigos. También se puede usar como un esquema de control para dispositivos táctiles; esto funcionaría básicamente de la misma manera que en la demostración tutorial, con el jugador tocando donde quiera que se mueva el personaje. Esto elimina el desafío de ejecución sobre el que se han construido muchas plataformas, por lo que el juego tendría que diseñarse de forma diferente, para ser mucho más sobre posicionar a tu personaje en el lugar correcto en lugar de aprender a controlar el personaje con precisión.

¡Gracias por leer! ¡Asegúrese de dejar un comentario sobre el método y también hágame saber si lo ha mejorado!