Cómo adaptar A * Pathfinding a una plataforma 2D basada en grillas: implementación

Ahora que tenemos una buena idea de cómo funcionará nuestro algoritmo de plataformas A *, es hora de realmente codificarlo. En lugar de construirlo desde cero, adaptaremos un sistema de identificación de caminos A * existente para agregar la nueva compatibilidad de plataformas.

La implementación que adaptaremos en este tutorial es el sistema A * pathfinding basado en grid de Gustavo Franco, que está escrito en C #; si no está familiarizado con él, lea su explicación de todas las partes separadas antes de continuar. Si no ha leído el tutorial anterior de esta serie, que ofrece una visión general de cómo funcionará esta adaptación, léalo primero.

Nota: el código fuente completo para este tutorial se puede encontrar en este repositorio GitHub, en la carpeta Implementation.

Demo

Puede jugar la demostración de Unity, o la versión de WebGL (64MB), para ver el resultado final en acción. Use WASD para mover el personaje, haga clic con el botón izquierdo en un punto para encontrar un camino que pueda seguir para llegar allí y haga clic con el botón derecho en una celda para alternar el terreno en ese punto.

Configuración del proyecto del juego

Necesitamos establecer algunas reglas para el proyecto de juego de ejemplo utilizado en este tutorial. ¡Por supuesto, puede cambiar estas reglas cuando implemente este algoritmo en su propio juego!

Configurando la Física

Las reglas de física utilizadas en el proyecto de ejemplo son muy simples.

Cuando se trata de velocidad horizontal, no hay impulso en absoluto. El personaje puede cambiar de dirección de inmediato, e inmediatamente se mueve en esa dirección a toda velocidad. Esto hace que sea mucho más fácil para el algoritmo encontrar una ruta correcta, porque no tenemos que preocuparnos por la velocidad horizontal actual del personaje. También hace que sea más fácil crear una IA que siga el camino, porque no tenemos que hacer que el personaje gane ímpetu antes de realizar un salto.

Usamos cuatro constantes para definir y restringir el movimiento del personaje:

• Gravedad
• Velocidad máxima de caída
• La velocidad al caminar
• Velocidad de salto

Así es como se definen para este proyecto de ejemplo:

1

public const float cGravity = -1030.0f;

2

public const float cMaxFallingSpeed = -900.0f;

3

public const float cWalkSpeed = 160.0f;

4

public const float cJumpSpeed = 410.0f;

La unidad base utilizada en el juego es un píxel, por lo que el personaje se moverá 160 píxeles por segundo horizontalmente (al caminar o saltar); al saltar, la velocidad vertical del personaje se establecerá en 410 píxeles por segundo. En el proyecto de prueba, la velocidad de caída del personaje está limitada a 900, por lo que no hay posibilidad de que caiga a través de las fichas. La gravedad se establece en -1030 píxeles por segundo².

La altura del salto del personaje no es fija: cuanto más tiempo se presiona la tecla de salto, más alto saltará el personaje. Esto se logra al configurar la velocidad del personaje a no más de 200 píxeles por segundo una vez que la tecla de salto ya no se presiona:

1

if (!mInputs[(int)KeyInput.Jump] && mSpeed.y > 0.0f)

2

{

3

    mSpeed.y = Mathf.Min(mSpeed.y, 200.0f);

4

    mFramesFromJumpStart = 100;

5

}

Configurando la Grilla

La cuadrícula es una matriz simple de bytes que representa el costo del movimiento a una celda específica (donde 0 está reservado para bloques que el personaje no puede mover).

No vamos a profundizar en los pesos en este tutorial; en realidad usaremos solo dos valores: 0 para bloques sólidos y 1 para celdas vacías.

El algoritmo utilizado en este tutorial requiere que el ancho y la altura de la cuadrícula tengan una potencia de dos, así que tenlo en cuenta.

Aquí hay un ejemplo de una matriz de cuadrícula y una representación en el juego de la misma.

1

private byte[,] mGrid = {{ 0, 1, 1, 1 }

2

                         { 0, 1, 1, 1 }

3

                         { 0, 1, 0, 0 }

4

                         { 0, 0, 0, 0 }};

Una nota sobre hilos

Normalmente, configuraríamos el proceso de Pathfinder en un hilo separado, para que no haya bloqueos en el juego mientras está funcionando, pero en este tutorial utilizaremos una única versión de subprocesos, debido a las limitaciones de la plataforma WebGL, en que esta demostración se ejecuta.

El algoritmo en sí se puede ejecutar en un hilo separado, por lo que no debería tener problemas para fusionarlo en su código de esa manera si es necesario.

Agregar los valores de salto a los nodos

Recuerde de la teoría general que los nodos se distinguen no solo por las coordenadas x e y, sino también por los valores de salto. En la implementación estándar de A *, las coordenadas x e y son suficientes para definir un nodo, por lo que debemos modificarlo para usar los valores de salto también.

A partir de este momento, modificaremos el archivo fuente principal PathFinderFast.cs de la implementación de Gustavo Franco.

Reestructuración de la lista de nodos

Primero, agregaremos una nueva lista de nodos para cada celda de la grilla; esta lista reemplazará a mCalcGrid del algoritmo original:

1

private List<PathFinderNodeFast>[] nodes;

Tenga en cuenta que PathFinderFast utiliza matrices unidimensionales, en lugar de una matriz 2D, como podríamos esperar al representar una cuadrícula.

Esto no es un problema, porque conocemos el ancho y la altura de la cuadrícula, así que en lugar de acceder a los datos por índices X e Y, accederemos a ella por un único int que se calcula usando location = (y << gridWidthLog2) + x. (Esta es una versión ligeramente más rápida de una clásica location = (y * gridWidth) + x).

Debido a que necesitamos una grilla que sea tridimensional (para incorporar los valores de salto como una tercera "dimensión"), necesitaremos agregar otro entero, que será el índice de un nodo en una lista en una posición particular X e Y.

Debido a que necesitamos una grilla que sea tridimensional (para incorporar los valores de salto como una tercera "dimensión"), necesitaremos agregar otro entero, que será el índice de un nodo en una lista en una posición particular X e Y.Tenga en cuenta que no podemos fusionar las tres coordenadas en un entero porque la tercera dimensión de la cuadrícula no tiene un tamaño constante. Podríamos considerar usar simplemente una grilla tridimensional, que restringiría el número de nodos posible en una posición particular (x, y), pero si el tamaño de la matriz en el "eje z" fuera demasiado pequeño, entonces el algoritmo podría regresar un resultado incorrecto, así que vamos a ir a lo seguro.

un resultado incorrecto, así que vamos a ir a lo seguro.Aquí, entonces, está la estructura que usaremos para indexar un nodo particular:

1

public struct Location

2

{

3

    public Location(int xy, int z)

4

    {

5

        this.xy = xy;

6

        this.z = z;

7

    }

8

9

    public int xy;

10

    public int z;

11

}

Lo siguiente que tenemos que modificar es la estructura PathFinderNodeFast. Hay dos cosas que debemos agregar aquí:

• El primero es el índice del padre de un nodo, que es básicamente el nodo anterior desde el cual llegamos al nodo actual. Necesitamos tener ese índice ya que no podemos identificar al padre únicamente por sus coordenadas x e y. Las coordenadas x e y nos señalarán una lista de nodos que se encuentran en esa posición específica, por lo que también necesitamos conocer el índice de nuestro padre en esa lista. Nombraremos ese índice PZ.
• La otra cosa que necesitamos agregar a la estructura es el valor de salto.

Aquí está la vieja estructura:

1

internal struct PathFinderNodeFast

2

{

3

    public int     F;

4

    public int     G;

5

    public ushort  PX;      //parent x

6

    public ushort  PY;      //parent y

7

    public byte    Status;

8

}

Y aquí es a lo que lo modificaremos:

1

internal struct PathFinderNodeFast

2

{

3

    public int     F;

4

    public int     G;

5

    public ushort  PX;          //parent y

6

    public ushort  PY;          //parent x

7

    public byte    Status;

8

    public byte    PZ;          //parent z

9

    public short   JumpLength;  //jump value

10

}

Todavía hay un problema, sin embargo. Cuando usemos el algoritmo una vez, poblará las listas de nodos de las células. Necesitamos borrar esas listas después de cada vez que se ejecuta el Pathfinder, porque si no lo hacemos, esas listas crecerán todo el tiempo con cada uso del algoritmo, y el uso de la memoria aumentará incontrolablemente.

La cuestión es que realmente no queremos borrar cada lista cada vez que se ejecuta el Pathfinder, porque la red puede ser enorme y la ruta probablemente nunca tocará la mayoría de los nodos de la grilla. Causaría una gran sobrecarga, por lo que es mejor borrar solo las listas por las que pasó el algoritmo.

Para eso, necesitamos un contenedor adicional que usaremos para recordar qué células se tocaron:

1

private Stack<int> touchedLocations;

Una pila funcionará bien; solo necesitaremos borrar todas las listas que contiene una por una.

Actualización de la cola de prioridad

Ahora, hagamos que nuestra cola de prioridad mOpen funcione con el nuevo índice.

Lo primero que debemos hacer es cambiar la declaración para usar las ubicaciones en lugar de los enteros, por lo tanto, desde:

1

private PriorityQueueB<int> mOpen = null;

a:

1

private PriorityQueueB<Location> mOpen = null;

A continuación, debemos cambiar el comparador de la cola para que utilice la nueva estructura. En este momento usa solo una matriz de nodos; necesitamos cambiarlo para que use una matriz de listas de nodos. También debemos asegurarnos de que compara los nodos utilizando Location en lugar de solo un número entero.

Aquí está el código anterior:

1

internal class ComparePFNodeMatrix : IComparer<int>

2

{

3

    PathFinderNodeFast[] mMatrix;

4

5

    public ComparePFNodeMatrix(PathFinderNodeFast[] matrix)

6

    {

7

        mMatrix = matrix;

8

    }

9

10

    public int Compare(int a, int b)

11

    {

12

        if (mMatrix[a].F > mMatrix[b].F)

13

            return 1;

14

        else if (mMatrix[a].F < mMatrix[b].F)

15

            return -1;

16

        return 0;

17

    }

18

}

Y aquí está lo nuevo:

1

internal class ComparePFNodeMatrix : IComparer<Location>

2

{

3

    List<PathFinderNodeFast>[] mMatrix;

4

5

    public ComparePFNodeMatrix(List<PathFinderNodeFast>[] matrix)

6

    {

7

        mMatrix = matrix;

8

    }

9

10

    public int Compare(Location a, Location b)

11

    {

12

        if (mMatrix[a.xy][a.z].F > mMatrix[b.xy][b.z].F)

13

            return 1;

14

        else if (mMatrix[a.xy][a.z].F < mMatrix[b.xy][b.z].F)

15

            return -1;

16

        return 0;

17

    }

18

}

Ahora, vamos a inicializar las listas de nodos y la pila de ubicaciones tocadas cuando se cree el Pathfinder. De nuevo, aquí está el código anterior:

1

if (mCalcGrid == null || mCalcGrid.Length != (mGridX * mGridY))

2

{

3

    mCalcGrid = new PathFinderNodeFast[mGridX * mGridY];

4

    mClose = new List<Vector2i>(mGridX * mGridY);

5

}

Y aquí está lo nuevo:

1

if (others == null || others.Length != (mGridX * mGridY))

2

{

3

  nodes = new List<PathFinderNodeFast>[mGridX * mGridY];

4

    touchedLocations = new Stack<int>(mGridX * mGridY);

5

    mClose = new List<Vector2i>(mGridX * mGridY);

6

}

7

8

for (var i = 0; i < others.Length; ++i)

9

{

10

	nodes[i] = new List<PathFinderNodeFast>(1);

11

}

Finalmente, creemos nuestra cola de prioridad usando el nuevo constructor:

1

mOpen = new PriorityQueueB<Location>(new ComparePFNodeMatrix(nodes));

Inicializando el algoritmo

Cuando comenzamos el algoritmo, queremos decir qué tan grande es nuestro personaje (en celdas) y también qué tan alto puede saltar el personaje.

(Tenga en cuenta que, para este tutorial, en realidad no utilizaremos characterWidth ni characterHeight; supondremos que el tamaño del carácter es un bloque de 1x1).

Cambiar esta línea:

1

public List<PathFinderNode> FindPath(Point start, Point end)

A esto:

1

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

Lo primero que debemos hacer es borrar las listas en las ubicaciones previamente tocadas:

1

while (touchedLocations.Count > 0)

2

    others[touchedLocations.Pop()].Clear();

A continuación, debemos asegurarnos de que el personaje pueda caber en la ubicación final. (Si no puede, no tiene sentido ejecutar el algoritmo, porque será imposible encontrar una ruta válida).

1

if (mGrid[end.x, end.y] == 0)

2

	return null;

Ahora podemos crear un nodo de inicio. En lugar de establecer los valores en mCalcGrid, necesitamos agregar un nodo a la lista de nodos en una posición particular.

Primero, calculemos la ubicación del nodo. Por supuesto, para poder hacer esto, también necesitamos cambiar el tipo de mLocation a Location.

Cambiar esta línea:

1

mLocation = (start.y << mGridXLog2) + start.x;

A esto:

1

mLocation.xy = (start.y << mGridXLog2) + start.x;

2

mLocation.z = 0;

El mEndLocation se puede dejar tal cual; lo usaremos para verificar si ya hemos alcanzado nuestro objetivo, por lo que solo debemos verificar las posiciones X e Y en ese caso:

1

mEndLocation = (end.y << mGridXLog2) + end.x;

Para la inicialización del nodo de inicio, debemos restablecer el PZ padre a 0 y establecer el valor de salto apropiado.

Cuando el punto de partida está en el suelo, el valor de salto debe ser igual a 0, pero ¿qué sucede si comenzamos en el aire? La solución más simple será establecerlo al valor de caída y no preocuparse demasiado por ello; encontrar un camino cuando comienzas en el aire puede ser bastante problemático, así que tomaremos el camino más fácil.

Aquí está el código anterior:

1

mLocation                      = (start.y << mGridXLog2) + start.x;

2

mEndLocation                   = (end.y << mGridXLog2) + end.x;

3

mCalcGrid[mLocation].G         = 0;

4

mCalcGrid[mLocation].F         = mHEstimate;

5

mCalcGrid[mLocation].PX        = (ushort) start.x;

6

mCalcGrid[mLocation].PY        = (ushort) start.y;

7

mCalcGrid[mLocation].Status    = mOpenNodeValue;

Y el nuevo:

1

mLocation.xy = (start.y << mGridXLog2) + start.x;

2

mLocation.z = 0;

3

mEndLocation = (end.y << mGridXLog2) + end.x;

4

5

PathFinderNodeFast firstNode = new PathFinderNodeFast();

6

firstNode.G = 0;

7

firstNode.F = mHEstimate;

8

firstNode.PX = (ushort)start.x;

9

firstNode.PY = (ushort)start.y;

10

firstNode.PZ = 0;

11

firstNode.Status = mOpenNodeValue;

12

13

if (mMap.IsGround(start.x, start.y - 1))

14

    firstNode.JumpLength = 0;

15

else

16

	firstNode.JumpLength = (short)(maxCharacterJumpHeight * 2);

También debemos agregar el nodo a la lista en la posición de inicio:

1

nodes[mLocation.xy].Add(firstNode);

Y también debemos recordar que la lista de nodos de inicio se borrará en la próxima ejecución:

1

touchedLocations.Push(mLocation.xy);

Finalmente, la ubicación está en cola y podemos comenzar con el algoritmo central. Para resumir, esto es lo que debería ser la inicialización del pathfinder ejecutado:

1

while (touchedLocations.Count > 0)

2

    nodes[touchedLocations.Pop()].Clear();

3

4

if (mGrid[end.x, end.y] == 0)

5

	return null;

6

7

mFound              = false;

8

mStop               = false;

9

mStopped            = false;

10

mCloseNodeCounter   = 0;

11

mOpenNodeValue      += 2;

12

mCloseNodeValue     += 2;

13

mOpen.Clear();

14

15

mLocation.xy = (start.y << mGridXLog2) + start.x;

16

mLocation.z = 0;

17

mEndLocation                   = (end.y << mGridXLog2) + end.x;

18

19

PathFinderNodeFast firstNode = new PathFinderNodeFast();

20

firstNode.G = 0;

21

firstNode.F = mHEstimate;

22

firstNode.PX = (ushort)start.x;

23

firstNode.PY = (ushort)start.y;

24

firstNode.PZ = 0;

25

firstNode.Status = mOpenNodeValue;

26

27

if (mMap.IsGround(start.x, start.y - 1))

28

	firstNode.JumpLength = 0;

29

else

30

	firstNode.JumpLength = (short)(maxCharacterJumpHeight * 2);

31

32

nodes[mLocation.xy].Add(firstNode);

33

touchedLocations.Push(mLocation.xy);

34

35

mOpen.Push(mLocation);

Cálculo de un sucesor

Verificando la posición

No necesitamos modificar mucho en la parte de procesamiento del nodo; solo tenemos que cambiar mLocation a mLocation.xy para poder calcular mLocationX y mLocationY.

Cambia esto:

1

while(mOpen.Count > 0 && !mStop)

2

{

3

    mLocation    = mOpen.Pop();

4

5

    //Is it in closed list? means this node was already processed

6

    if (mCalcGrid[mLocation].Status == mCloseNodeValue)

7

        continue;

8

9

    mLocationX   = (ushort) (mLocation & mGridXMinus1);

10

    mLocationY   = (ushort) (mLocation >> mGridXLog2);

11

12

    if (mLocation == mEndLocation)

13

    {

14

        mCalcGrid[mLocation].Status = mCloseNodeValue;

15

        mFound = true;

16

        break;

17

    }

18

19

    if (mCloseNodeCounter > mSearchLimit)

20

    {

21

        mStopped = true;

22

        return null;

23

    }

A esto:

1

while(mOpen.Count > 0 && !mStop)

2

{

3

    mLocation = mOpen.Pop();

4

5

    //Is it in closed list? means this node was already processed

6

    if (nodes[mLocation.xy][mLocation.z].Status == mCloseNodeValue)

7

        continue;

8

9

    mLocationX = (ushort) (mLocation.xy & mGridXMinus1);

10

    mLocationY = (ushort) (mLocation.xy >> mGridXLog2);

11

12

    if (mLocation.xy == mEndLocation)

13

    {

14

        nodes[mLocation.xy][mLocation.z] = nodes[mLocation.xy][mLocation.z].UpdateStatus(mCloseNodeValue);

15

        mFound = true;

16

        break;

17

    }

18

19

    if (mCloseNodeCounter > mSearchLimit)

20

    {

21

        mStopped = true;

22

        return null;

23

    }

Tenga en cuenta que, cuando cambiamos el estado de un nodo dentro de la lista de nodos, utilizamos la función UpdateStatus(byte newStatus). Realmente no podemos cambiar ninguno de los miembros de la estructura dentro de la lista, ya que la lista devuelve una copia del nodo; necesitamos reemplazar todo el nodo. La función simplemente devuelve un nodo copiado con Status cambiado a newStatus:

1

public PathFinderNodeFast UpdateStatus(byte newStatus)

2

{

3

    PathFinderNodeFast newNode = this;

4

    newNode.Status = newStatus;

5

    return newNode;

6

}

También necesitamos modificar la forma en que se calculan los sucesores:

1

for (var i=0; i<(mDiagonals ? 8 : 4); i++)

2

{

3

    mNewLocationX = (ushort) (mLocationX + mDirection[i,0]);

4

    mNewLocationY = (ushort) (mLocationY + mDirection[i,1]);

5

    mNewLocation  = (mNewLocationY << mGridXLog2) + mNewLocationX;

Aquí solo calculamos la ubicación de uno de los sucesores; necesitamos esto para que podamos encontrar la posición relativa del nodo sucesor.

Determinar el tipo de posición

Lo siguiente que debemos saber es qué tipo de posición representa un sucesor.

Estamos interesados ​​en cuatro variantes aquí:

1. El personaje no encaja en la posición. Suponemos que la posición de la celda responde a la "celda" inferior izquierda de un personaje. Si este es el caso, entonces podemos descartar el sucesor, ya que no hay forma de mover al personaje a través de él.
2. El personaje se ajusta a la posición y está en el suelo. Esto significa que el valor de salto del sucesor debe cambiarse a 0.
3. El personaje encaja en la posición, y está justo debajo del techo. Esto significa que incluso si el personaje tiene la velocidad suficiente para saltar más alto, no puede, por lo que debemos cambiar el valor de salto de forma adecuada.
4. El personaje simplemente cabe en el lugar y no está ni en el suelo ni en el techo.

Primero, supongamos que el personaje no está ni en el suelo ni en el techo:

1

var onGround = false;

2

var atCeiling = false;

Comprobemos si el personaje se ajusta al nuevo lugar. De lo contrario, podemos omitir el sucesor de forma segura y verificar el siguiente.

1

if (mGrid[mNewLocationX, mNewLocationY] == 0)

2

    continue;

Para verificar si el personaje estaría en el suelo cuando está en la nueva ubicación, solo necesitamos ver si hay un bloque sólido debajo del sucesor:

1

if (mGrid[mNewLocationX, mNewLocationY - 1] == 0)

2

    onGround = true;

Del mismo modo, verificamos si el personaje estaría en el techo:

1

if (mGrid[mNewLocationX, mNewLocationY + 1] == 0)

2

    atCeiling = true;    

Cálculo del valor de salto

Lo siguiente que debemos hacer es ver si este sucesor es válido o no, y si es así, calcule un JumpLength apropiado para él.

Primero, obtengamos el JumpLength del nodo padre:

1

var jumpLength = nodes[mLocation.xy][mLocation.z].JumpLength;

También declararemos el nuevo JumpLength para el sucesor procesado actualmente:

1

short newJumpLength = jumpLength;

Ahora podemos calcular el nuevo JumpLength. (Cómo hacemos esto se explica al principio de la descripción general de la teoría).

Si el nodo sucesor está en el suelo, entonces newJumpValue es igual a 0:

1

if (onGround)

2

    newJumpLength = 0;

Nada de qué preocuparse aquí. Es importante verificar si el personaje está en el suelo primero, porque si el personaje está tanto en el suelo como en el techo, entonces queremos establecer el valor de salto en 0.

Si la posición está en el techo, entonces debemos considerar dos casos:

1. el personaje debe caer hacia abajo, o
2. el personaje todavía puede mover una celda a cada lado.

En el primer caso, necesitamos establecer el nuevo JumpLength para que sea al menos maxCharacterJumpHeight * 2 + 1, porque este valor significa que estamos cayendo y nuestro siguiente movimiento debe hacerse verticalmente.

En el segundo caso, el valor debe ser al menos maxCharacterJumpHeight * 2. Dado que el valor es par, el nodo sucesor aún podrá moverse hacia la izquierda o hacia la derecha.

1

else if (atCeiling)

2

{

3

    if (mNewLocationX != mLocationX)

4

        newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2 + 1, jumpLength + 1);

5

    else

6

        newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 2);

7

}

Los casos "en el suelo" y "en el techo" están resueltos; ahora podemos llegar a calcular el valor del salto mientras está en el aire.

Cálculo del valor de salto en medio del aire

Primero, manejemos el caso en el cual el nodo sucesor está sobre el nodo padre.

Si la longitud del salto es pareja, la incrementamos en dos; de lo contrario, lo incrementamos en uno. Esto dará como resultado un valor par para newJumpLength:

1

else if (mNewLocationY > mLocationY)

2

{

3

	if (jumpLength % 2 == 0)

4

		newJumpLength = (short)(jumpLength + 2);

5

	else

6

		newJumpLength = (short)(jumpLength + 1);

7

}

Dado que, en un salto promedio, la velocidad del personaje tiene su valor más alto al inicio y al final del salto, debemos representar este hecho en el algoritmo.

Arreglaremos el inicio de salto obligando al algoritmo a mover dos celdas si acabamos de despegar. Esto se puede lograr fácilmente intercambiando el valor de salto de 2 a 3 en el momento del salto, porque en el valor de salto de 3, el algoritmo sabe que el personaje no puede ir hacia un lado (ya que 3 es un número impar).

La curva de salto cambiará a lo siguiente.

Vamos también a acomodarnos a este cambio en el código:

1

else if (mNewLocationY > mLocationY)

2

{

3

    if (jumpHeight < 2) //first jump is always two block up instead of one up and optionally one to either right or left

4

        newJumpHeight = 3;

5

	else if (jumpHeight % 2 == 0)

6

		newJumpHeight = (short)Mathf.Max(jumpHeight + 2, 2);

7

	else

8

		newJumpHeight = (short)Mathf.Max(jumpHeight + 1, 2);

9

}

(Arreglaremos la curva cuando la velocidad del personaje sea demasiado alta para ir hacia los lados cuando validemos el nodo más adelante).

Ahora manejemos el caso en el que el nuevo nodo está debajo del anterior.

Si la nueva coordenada y es más baja que la de los padres, eso significa que estamos cayendo. Calculamos el valor del salto de la misma manera que lo hacemos al saltar hacia arriba, pero el mínimo debe establecerse en maxCharacterJumpHeight * 2. (Esto se debe a que el personaje no necesita hacer un salto completo para comenzar a caer; por ejemplo, simplemente puede alejarse una repisa.) En ese caso, el valor de salto debe cambiarse de 1 a 6 inmediatamente (en el caso en que la altura máxima de salto del personaje sea 3):

1

else if (mNewLocationY < mLocationY)

2

{

3

	if (jumpLength % 2 == 0)

4

		newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 2);

5

	else

6

		newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 1);

7

}

Validar al sucesor

Ahora tenemos todos los datos que necesitamos para validar un sucesor, así que vamos a hacerlo.

Primero, descartemos un nodo si su valor de salto es impar y el padre está a la izquierda o a la derecha. Esto se debe a que si el valor de salto es impar, significa que el personaje ya se fue al costado una vez y ahora tiene que moverse un bloque hacia arriba o hacia abajo:

1

if (jumpLength % 2 != 0 && mLocationX != mNewLocationX)

2

    continue;

Si el carácter está disminuyendo y el nodo secundario está por encima del elemento principal, entonces debemos omitirlo. Así es como evitamos saltar ad infinitum; una vez que el valor de salto alcanza el umbral, solo podemos descender.

1

if (jumpLength >= maxCharacterJumpHeight * 2 && mNewLocationY > mLocationY)

2

    continue;

Si el valor de salto del nodo es mayor que (seis más el valor del umbral de caída), entonces debemos dejar de permitir el cambio de dirección en cada valor de salto par. Esto evitará que el algoritmo proporcione valores incorrectos cuando el personaje esté cayendo muy rápido, porque en ese caso en lugar de 1 bloque hacia un lado y 1 bloque hacia abajo, necesitaría mover 1 bloque hacia un lado y 2 o más bloques hacia abajo. (En este momento, el personaje puede moverse 3 bloques hacia un lado después de que comienza a caer, y luego le permitimos que se mueva hacia los lados cada 4 bloques atravesados verticalmente).

1

if (newJumpLength >= maxCharacterJumpHeight * 2 + 6 && mNewLocationX != mLocationX && (newJumpLength - (maxCharacterJumpHeight * 2 + 6)) % 8 != 3)

2

    continue;

Si hay una necesidad de un control de salto más preciso, entonces, en lugar de descartar el nodo de la manera que se muestra arriba, podríamos crear una tabla de búsqueda con datos que determinen a qué longitud de salto el personaje podría moverse hacia un lado.

Cálculo del costo

Al calcular el costo del nodo, debemos tener en cuenta el valor de salto.

Haciendo que el personaje se mueva con sensatez

Es bueno hacer que el personaje se adhiera al suelo tanto como sea posible, ya que hará que su movimiento sea menos nervioso cuando se mueve en terreno llano, y también lo alentará a utilizar caminos "más seguros", que no requieren largas caídas.

Podemos hacer que el personaje haga esto fácilmente aumentando el costo del nodo de acuerdo con su valor de salto. Aquí está el código anterior:

1

mNewG = mCalcGrid[mLocation].G + mGrid[mNewLocationX, mNewLocationY];

Y aquí está lo nuevo:

1

mNewG = nodes[mLocation.xy][mLocation.z].G + mGrid[mNewLocationX, mNewLocationY] + newJumpLength / 4;

El newJumpLength / 4 funciona bien para la mayoría de los casos; no queremos que el personaje se pegue demasiado al suelo, después de todo.

Revisando nodos con diferentes valores de salto

Normalmente, cuando procesamos el nodo una vez, establecemos su estado como closed y nunca nos molestamos en volver a hacerlo; sin embargo, como ya hemos discutido, es posible que necesitemos visitar una posición particular en la cuadrícula más de una vez.

Primero, antes de que decidamos omitir el nodo actualmente verificado, necesitamos ver si hay algún nodo en la posición actual (x, y). Si todavía no hay nodos, entonces seguramente no podemos omitir el actual:

1

if (nodes[mNewLocation].Count > 0)

2

{

3

}

La única condición que nos permite omitir el nodo es esta: el nodo no permite ningún movimiento nuevo en comparación con los otros nodos en la misma posición.

El nuevo movimiento puede suceder si:

• El valor de salto del nodo procesado actualmente es menor que cualquiera de los otros nodos en la misma posición (x, y); en este caso, el nodo actual promete permitir que el personaje salte más alto usando este camino que cualquier otro.
•      El valor de salto del nodo procesado actualmente es par, y los valores de salto de todos los nodos en la posición no lo son. Esto básicamente significa que este nodo particular permite el movimiento lateral en esta posición, mientras que otros nos obligan a mover hacia arriba o hacia abajo.

El primer caso es simple: queremos mirar a través de los nodos con valores de salto más bajos ya que estos nos permiten saltar más alto. El segundo caso aparece en situaciones más peculiares, como esta:

Aquí, no podemos movernos hacia un lado cuando saltamos porque queríamos forzar al algoritmo a subir dos veces después de comenzar un salto. El problema es que, incluso cuando se cae, el algoritmo simplemente ignoraría el nodo con el valor de salto de 8, porque ya hemos visitado esa posición y el nodo anterior tenía un valor de salto inferior de 3. Es por eso que en este caso es importante para no omitir el nodo con un valor de salto par (y razonablemente bajo).

Primero, declaremos nuestras variables que nos permitirán saber cuál es el valor de salto más bajo en la posición actual (x, y), y si alguno de los nodos permite el movimiento lateral:

1

int lowestJump = short.MaxValue;

2

bool couldMoveSideways = false;

A continuación, debemos iterar sobre todos los nodos y establecer las variables declaradas a los valores adecuados:

1

for (int j = 0; j < nodes[mNewLocation].Count; ++j)

2

{

3

    if (nodes[mNewLocation][j].JumpLength < lowestJump)

4

        lowestJump = nodes[mNewLocation][j].JumpLength;

5

6

    if (nodes[mNewLocation][j].JumpLength % 2 == 0 && nodes[mNewLocation][j].JumpLength < maxCharacterJumpHeight * 2 + 6)

7

        couldMoveSideways = true;

8

}

Como puede ver, no solo verificamos si el valor de salto del nodo es par, sino también si el valor de salto no es demasiado alto para moverlo hacia los lados.

Finalmente, lleguemos a la condición que decidirá si podemos omitir el nodo o no:

1

if (lowestJump <= newJumpLength && (newJumpLength % 2 != 0 || newJumpLength >= maxCharacterJumpHeight * 2 + 6 || couldMoveSideways))

2

    continue;

Como puede ver, el nodo se omite si lowestJump es menor o igual que el valor de salto del nodo procesado y cualquiera de los otros nodos en la lista permite el movimiento lateral.

Podemos abandonar la fórmula heurística tal como está; no necesitamos cambiar nada aquí:

1

switch(mFormula)

2

{

3

    default:

4

    case HeuristicFormula.Manhattan:

5

        mH = mHEstimate * (Mathf.Abs(mNewLocationX - end.x) + Mathf.Abs(mNewLocationY - end.y));

6

        break;

7

    case HeuristicFormula.MaxDXDY:

8

        mH = mHEstimate * (Math.Max(Math.Abs(mNewLocationX - end.x), Math.Abs(mNewLocationY - end.y)));

9

        break;

10

    case HeuristicFormula.DiagonalShortCut:

11

        var h_diagonal  = Math.Min(Math.Abs(mNewLocationX - end.x), Math.Abs(mNewLocationY - end.y));

12

        var h_straight  = (Math.Abs(mNewLocationX - end.x) + Math.Abs(mNewLocationY - end.y));

13

        mH = (mHEstimate * 2) * h_diagonal + mHEstimate * (h_straight - 2 * h_diagonal);

14

        break;

15

    case HeuristicFormula.Euclidean:

16

        mH = (int) (mHEstimate * Math.Sqrt(Math.Pow((mNewLocationY - end.x) , 2) + Math.Pow((mNewLocationY - end.y), 2)));

17

        break;

18

    case HeuristicFormula.EuclideanNoSQR:

19

        mH = (int) (mHEstimate * (Math.Pow((mNewLocationX - end.x) , 2) + Math.Pow((mNewLocationY - end.y), 2)));

20

        break;

21

    case HeuristicFormula.Custom1:

22

        var dxy       = new Vector2i(Math.Abs(end.x - mNewLocationX), Math.Abs(end.y - mNewLocationY));

23

        var Orthogonal  = Math.Abs(dxy.x - dxy.y);

24

        var Diagonal    = Math.Abs(((dxy.x + dxy.y) - Orthogonal) / 2);

25

        mH = mHEstimate * (Diagonal + Orthogonal + dxy.x + dxy.y);

26

        break;

27

}

Poner en orden

Ahora, finalmente, dado que el nodo ha pasado todas las comprobaciones, podemos crear una instancia PathFinderNodeFast apropiada para ello.

1

PathFinderNodeFast newNode = new PathFinderNodeFast();

2

newNode.JumpLength = newJumpLength;

3

newNode.PX = mLocationX;

4

newNode.PY = mLocationY;

5

newNode.PZ = (byte)mIdentifier.y;

6

newNode.G = mNewG;

7

newNode.F = mNewG + mH;

8

newNode.Status = mOpenNodeValue;

Y también podemos finalmente agregar el nodo a la lista de nodos en mNewLocation.

Sin embargo, antes de hacer eso, agreguemos la ubicación a la pila de ubicaciones tocadas si la lista está vacía. Sabremos que tenemos que borrar la lista de esta ubicación cuando ejecutemos el Pathfinder nuevamente:

1

if (nodes[mNewLocation].Count == 0)

2

    touchedLocations.Push(mNewLocation);

3

4

nodes[mNewLocation].Add(newNode);

5

mOpen.Push(new Location(mNewLocation, nodes[mNewLocation].Count - 1));

Después de que todos los hijos hayan sido procesados, podemos cambiar el estado del padre a closed e incrementar el mCloseNodeCounter:

1

mCloseNodeCounter++;

2

nodes[mLocation.xy][mLocation.z] = nodes[mLocation.xy][mLocation.z].UpdateStatus(mCloseNodeValue);

Al final, el ciclo de los niños debería verse así.

1

//Lets calculate each successors

2

for (var i=0; i<(mDiagonals ? 8 : 4); i++)

3

{

4

    mNewLocationX = (ushort) (mLocationX + mDirection[i,0]);

5

    mNewLocationY = (ushort) (mLocationY + mDirection[i,1]);

6

    mNewLocation  = (mNewLocationY << mGridXLog2) + mNewLocationX;

7

8

	var onGround = false;

9

	var atCeiling = false;

10

11

    if (mGrid[mNewLocationX, mNewLocationY] == 0)

12

        goto CHILDREN_LOOP_END;

13

14

    if (mMap.IsGround(mNewLocationX, mNewLocationY - 1))

15

        onGround = true;

16

    else if (mGrid[mNewLocationX, mNewLocationY + characterHeight] == 0)

17

        atCeiling = true;	

18

19

	//calculate a proper jumplength value for the successor

20

21

    var jumpLength = nodes[mLocation.xy][mLocation.z].JumpLength;

22

    short newJumpLength = jumpLength;

23

24

	if (atCeiling)

25

    {

26

        if (mNewLocationX != mLocationX)

27

            newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2 + 1, jumpLength + 1);

28

        else

29

            newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 2);

30

    }

31

    else if (onGround)

32

		newJumpLength = 0;

33

	else if (mNewLocationY > mLocationY)

34

	{

35

        if (jumpLength < 2) //first jump is always two block up instead of one up and optionally one to either right or left

36

            newJumpLength = 3;

37

        else  if (jumpLength % 2 == 0)

38

            newJumpLength = (short)(jumpLength + 2);

39

        else

40

            newJumpLength = (short)(jumpLength + 1);

41

	}

42

	else if (mNewLocationY < mLocationY)

43

	{

44

		if (jumpLength % 2 == 0)

45

			newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 2);

46

		else

47

			newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 1);

48

	}

49

	else if (!onGround && mNewLocationX != mLocationX)

50

		newJumpLength = (short)(jumpLength + 1);

51

52

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

53

		continue;

54

55

	//if we're falling and succeor's height is bigger than ours, skip that successor

56

	if (jumpLength >= maxCharacterJumpHeight * 2 && mNewLocationY > mLocationY)

57

		continue;

58

59

    if (newJumpLength >= maxCharacterJumpHeight * 2 + 6 && mNewLocationX != mLocationX && (newJumpLength - (maxCharacterJumpHeight * 2 + 6)) % 8 != 3)

60

		continue;

61

62

63

    mNewG = nodes[mLocation.xy][mLocation.z].G + mGrid[mNewLocationX, mNewLocationY] + newJumpLength / 4;

64

65

    if (nodes[mNewLocation].Count > 0)

66

    {

67

        int lowestJump = short.MaxValue;

68

        bool couldMoveSideways = false;

69

        for (int j = 0; j < nodes[mNewLocation].Count; ++j)

70

        {

71

            if (nodes[mNewLocation][j].JumpLength < lowestJump)

72

                lowestJump = nodes[mNewLocation][j].JumpLength;

73

74

            if (nodes[mNewLocation][j].JumpLength % 2 == 0 && nodes[mNewLocation][j].JumpLength < maxCharacterJumpHeight * 2 + 6)

75

                couldMoveSideways = true;

76

        }

77

78

        if (lowestJump <= newJumpLength && (newJumpLength % 2 != 0 || newJumpLength >= maxCharacterJumpHeight * 2 + 6 || couldMoveSideways))

79

            continue;

80

    }

81

82

    switch(mFormula)

83

    {

84

        default:

85

        case HeuristicFormula.Manhattan:

86

            mH = mHEstimate * (Mathf.Abs(mNewLocationX - end.x) + Mathf.Abs(mNewLocationY - end.y));

87

            break;

88

        case HeuristicFormula.MaxDXDY:

89

            mH = mHEstimate * (Math.Max(Math.Abs(mNewLocationX - end.x), Math.Abs(mNewLocationY - end.y)));

90

            break;

91

        case HeuristicFormula.DiagonalShortCut:

92

            var h_diagonal  = Math.Min(Math.Abs(mNewLocationX - end.x), Math.Abs(mNewLocationY - end.y));

93

            var h_straight  = (Math.Abs(mNewLocationX - end.x) + Math.Abs(mNewLocationY - end.y));

94

            mH = (mHEstimate * 2) * h_diagonal + mHEstimate * (h_straight - 2 * h_diagonal);

95

            break;

96

        case HeuristicFormula.Euclidean:

97

            mH = (int) (mHEstimate * Math.Sqrt(Math.Pow((mNewLocationY - end.x) , 2) + Math.Pow((mNewLocationY - end.y), 2)));

98

            break;

99

        case HeuristicFormula.EuclideanNoSQR:

100

            mH = (int) (mHEstimate * (Math.Pow((mNewLocationX - end.x) , 2) + Math.Pow((mNewLocationY - end.y), 2)));

101

            break;

102

        case HeuristicFormula.Custom1:

103

            var dxy       = new Vector2i(Math.Abs(end.x - mNewLocationX), Math.Abs(end.y - mNewLocationY));

104

            var Orthogonal  = Math.Abs(dxy.x - dxy.y);

105

            var Diagonal    = Math.Abs(((dxy.x + dxy.y) - Orthogonal) / 2);

106

            mH = mHEstimate * (Diagonal + Orthogonal + dxy.x + dxy.y);

107

            break;

108

    }

109

110

    PathFinderNodeFast newNode = new PathFinderNodeFast();

111

    newNode.JumpLength = newJumpLength;

112

    newNode.PX = mLocationX;

113

    newNode.PY = mLocationY;

114

    newNode.PZ = (byte)mLocation.z;

115

    newNode.G = mNewG;

116

    newNode.F = mNewG + mH;

117

    newNode.Status = mOpenNodeValue;

118

119

    if (nodes[mNewLocation].Count == 0)

120

        touchedLocations.Push(mNewLocation);

121

122

    nodes[mNewLocation].Add(newNode);

123

    mOpen.Push(new Location(mNewLocation, nodes[mNewLocation].Count - 1));

124

125

CHILDREN_LOOP_END:

126

	continue;

127

}

Filtrando los Nodos

Realmente no necesitamos todos los nodos que obtendremos del algoritmo. De hecho, será mucho más fácil para nosotros escribir una IA que siga el camino si filtramos los nodos a un conjunto más pequeño con el que podamos trabajar más fácilmente.

El proceso de filtrado de nodos en realidad no es parte del algoritmo, sino más bien una operación para preparar la salida para su posterior procesamiento. No es necesario que se ejecute en la clase PathFinderFast en sí, pero ese será el lugar más conveniente para hacerlo a los fines de este tutorial.

El filtrado de nodos se puede hacer junto con el siguiente código de ruta; es bastante improbable que filtremos el conjunto de nodos perfectamente para satisfacer nuestras necesidades con nuestras suposiciones iniciales, por lo que, a menudo, se necesitarán muchos ajustes. En este tutorial avanzaremos y reduciremos el conjunto a su forma final en este momento, para luego poder enfocarnos en la IA sin tener que modificar la clase pathfinder otra vez.

Queremos que nuestro filtro pase por cualquier nodo que cumpla con alguno de los siguientes requisitos:

1. Es el nodo de inicio.
2. Es el nodo final.
3. Es un nodo de salto.
4. Es un primer nodo en el aire en un salto lateral (un nodo con valor de salto igual a 3).
5. Es el nodo de aterrizaje (un nodo que tenía un valor de salto distinto de cero se convierte en 0).
6. Es el punto más alto del salto (el nodo entre moverse hacia arriba y hacia abajo).
7. Es un nodo que rodea un obstáculo.

Aquí hay un par de ilustraciones que muestran qué nodos queremos mantener. Los números rojos muestran cuál de las reglas anteriores hizo que el filtro dejara el nodo en la ruta:

Configurando los valores

Filtramos los nodos a medida que se empujan a la lista mClose, por lo que significa que iremos desde el nodo final al nodo de inicio.

1

if (mFound)

2

{

3

    mClose.Clear();

4

    var posX = end.x;

5

    var posY = end.y;

Antes de comenzar el proceso de filtrado, tenemos que configurar algunas variables para realizar un seguimiento del contexto del nodo filtrado:

1

var fPrevNodeTmp = new PathFinderNodeFast();

2

var fNodeTmp = nodes[mEndLocation][0];

3

4

var fNode = end;

5

var fPrevNode = end;

fNode y fPrevNode son Vector2s simples, mientras que fNodeTmp y fPrevNodeTmp son los nodos PathFinderNodeFast. Necesitamos ambos; Usaremos Vector2 para obtener la posición de los nodos y los objetos PathFinderNodeFast para obtener la ubicación principal, el valor de salto y todo lo demás que necesitaremos.

1

 var loc = (fNodeTmp.PY << mGridXLog2) + fNodeTmp.PX;

loc apunta a la posición XY en la cuadrícula del nodo que se procesará la próxima iteración.

Definiendo el Loop

Ahora podemos comenzar nuestro ciclo. Seguiremos bucles siempre que no lleguemos al nodo de inicio (en ese punto, la posición del padre es igual a la posición del nodo):

1

while(fNode.x != fNodeTmp.PX || fNode.y != fNodeTmp.PY)

2

{

Necesitaremos acceder al siguiente nodo además del anterior, así que vamos a obtenerlo:

1

var fNextNodeTmp = nodes[loc][fNodeTmp.PZ];

Agregar el nodo final

Ahora comencemos el proceso de filtrado. El nodo de inicio se agregará a la lista al final, después de que se hayan tratado todos los demás elementos. Como vamos desde el nodo final, asegurémonos de incluirlo en nuestra ruta final:

1

if ((mClose.Count == 0))

2

    mClose.Add(fNode);

Si mClose está vacío, eso significa que aún no hemos insertado ningún nodo, lo que significa que el nodo procesado actualmente es el nodo final, y como queremos incluirlo en la lista final, lo agregamos a mClose.

Agregar nodos de salto

Para los nodos de salto, querremos usar dos condiciones.

La primera condición es que el valor de salto del nodo procesado actualmente sea 0, y el valor de salto del nodo anterior no sea 0:

1

if ((mClose.Count == 0)

2

    || (fNodeTmp.JumpLength == 0 && fPrevNodeTmp.JumpLength != 0))

3

    mClose.Add(fNode);

La segunda condición es que el valor de salto sea igual a 3. Este es básicamente el primer punto de cambio de dirección en el primer salto o en el aire en un salto en particular:

1

if ((mClose.Count == 0)

2

    || (fNodeTmp.JumpLength == 0 && fPrevNodeTmp.JumpLength != 0)

3

    || (fNodeTmp.JumpLength == 3))

4

    mClose.Add(fNode);

Agregar nodos de aterrizaje

Ahora para los nodos de aterrizaje:

1

if ((mClose.Count == 0)

2

    || (fNodeTmp.JumpLength == 0 && fPrevNodeTmp.JumpLength != 0)

3

    || (fNodeTmp.JumpLength == 3)

4

    || (fNextNodeTmp.JumpLength != 0 && fNodeTmp.JumpLength == 0)   )

5

    mClose.Add(fNode);

Detectamos el nodo de aterrizaje al ver que el siguiente nodo está en el suelo y el nodo actual no. Recuerde que estamos procesando los nodos en orden inverso, de modo que el aterrizaje se detecta cuando el nodo anterior está en el suelo y la current no.

Agregar nodos de punto más altos

Ahora agreguemos los puntos altos de salto. Detectamos estos al ver si los nodos anterior y siguiente son más bajos que el nodo actual:

1

if ((mClose.Count == 0)

2

    || (fNodeTmp.JumpLength == 0 && fPrevNodeTmp.JumpLength != 0)

3

    || (fNodeTmp.JumpLength == 3)

4

    || (fNextNodeTmp.JumpLength != 0 && fNodeTmp.JumpLength == 0)

5

    || (fNode.y > mClose[mClose.Count - 1].y && fNode.y > fNodeTmp.PY))

6

    mClose.Add(fNode);

Tenga en cuenta que, en el último caso, no comparamos la coordenada y del nodo actual con fPrevNode.y, sino con la coordenada y del nodo empujado anterior. Esto se debe a que puede ser que el nodo anterior esté a la misma altura que el actual, si el personaje se movió hacia un lado para alcanzarlo.

Agregar nodos que rodean obstáculos

Finalmente, cuidemos los nodos que nos permiten maniobrar alrededor de los obstáculos. Si estamos al lado de un obstáculo y el nodo anterior empujado no está alineado con el actual, ya sea horizontal o verticalmente, entonces suponemos que este nodo nos alineará con el obstáculo y nos permitirá movernos limpiamente sobre él si es necesario:

1

if ((mClose.Count == 0)

2

    || (fNextNodeTmp.JumpLength != 0 && fNodeTmp.JumpLength == 0)

3

    || (fNodeTmp.JumpLength == 3 && fPrevNodeTmp.JumpLength != 0)

4

    || (fNodeTmp.JumpLength == 0 && fPrevNodeTmp.JumpLength != 0)

5

    || (fNode.y > mClose[mClose.Count - 1].y && fNode.y > fNodeTmp.PY)

6

    || ((mMap.IsGround(fNode.x - 1, fNode.y) || mMap.IsGround(fNode.x + 1, fNode.y)) 

7

        && fNode.y != mClose[mClose.Count - 1].y && fNode.x != mClose[mClose.Count - 1].x))

8

    mClose.Add(fNode);

Preparación para el siguiente bucle

Después de agregar un nodo a la lista mClose o ignorarlo, debemos preparar las variables para la siguiente iteración:

1

    fPrevNode = fNode;

2

    posX = fNodeTmp.PX;

3

    posY = fNodeTmp.PY;

4

    fPrevNodeTmp = fNodeTmp;

5

    fNodeTmp = fNextNodeTmp;

6

    loc = (fNodeTmp.PY << mGridXLog2) + fNodeTmp.PX;

7

    fNode = new Vector2i(posX, posY);

8

} 

Como puede ver, calculamos todo de la misma manera que preparamos el ciclo para la primera iteración.

Agregar el nodo de inicio

Después de que todos los nodos hayan sido procesados (y el ciclo haya finalizado), podemos agregar el punto de inicio a la lista y finalizar el trabajo:

1

    mClose.Add(fNode);

2

3

    mStopped = true;

4

5

    return mClose;

6

}

Todo junto

El procedimiento completo de filtrado de ruta debería verse así.

1

if (mFound)

2

{

3

    mClose.Clear();

4

    var posX = end.x;

5

    var posY = end.y;

6

7

    var fPrevNodeTmp = new PathFinderNodeFast();

8

    var fNodeTmp = nodes[mEndLocation][0];

9

10

    var fNode = end;

11

    var fPrevNode = end;

12

13

    var loc = (fNodeTmp.PY << mGridXLog2) + fNodeTmp.PX;

14

15

    while (fNode.x != fNodeTmp.PX || fNode.y != fNodeTmp.PY)

16

    {

17

        var fNextNodeTmp = nodes[loc][fNodeTmp.PZ];

18

19

        if ((mClose.Count == 0)

20

    		|| (fNextNodeTmp.JumpLength != 0 && fNodeTmp.JumpLength == 0)

21

    		|| (fNodeTmp.JumpLength == 3 && fPrevNodeTmp.JumpLength != 0)

22

    		|| (fNodeTmp.JumpLength == 0 && fPrevNodeTmp.JumpLength != 0)

23

    		|| (fNode.y > mClose[mClose.Count - 1].y && fNode.y > fNodeTmp.PY)

24

    		|| ((mMap.IsGround(fNode.x - 1, fNode.y) || mMap.IsGround(fNode.x + 1, fNode.y)) 

25

    			&& fNode.y != mClose[mClose.Count - 1].y && fNode.x != mClose[mClose.Count - 1].x))

26

	    	mClose.Add(fNode);

27

28

        fPrevNode = fNode;

29

        posX = fNodeTmp.PX;

30

        posY = fNodeTmp.PY;

31

        fPrevNodeTmp = fNodeTmp;

32

        fNodeTmp = fNextNodeTmp;

33

        loc = (fNodeTmp.PY << mGridXLog2) + fNodeTmp.PX;

34

        fNode = new Vector2i(posX, posY);

35

    }

36

37

    mClose.Add(fNode);

38

39

    mStopped = true;

40

41

    return mClose;

42

}

Conclusión

El producto final del algoritmo es una ruta encontrada para un personaje que tiene un bloque de ancho y un bloque de alto con una altura de salto máxima definida.

Podemos mejorar esto: podríamos permitir que el tamaño del personaje sea variado, podríamos agregar soporte para plataformas de un solo sentido, y podríamos codificar un bot de IA para seguir el camino. ¡Hablaremos de todas estas cosas en las próximas partes del tutorial!