A * Pathfinding per platform 2D basata su griglia: fare un Bot seguire il percorso

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

In questo tutorial, useremo l'algoritmo di path-finding Platform che abbiamo costruito per alimentare un bot che possa seguire il percorso da sè; Basta cliccare su una posizione e potrà correre e saltare per arrivarci. Questo è molto utile per gli NPC!

Demo

Si può giocare la demo di unità, o la versione di WebGL (100 MB +), per vedere il risultato finale in azione. Usa WASD per muovere il personaggio, tasto sinistro del mouse su un punto per trovare un percorso che si possono seguire per arrivarci, destro del mouse su una cella per attivare o disattivare il terreno a quel punto, pulsante centrale del mouse per posizionare una piattaforma unidirezionale e fare clic e trascinare i cursori per modificare i valori.

L'aggiornamento del motore

Gestione dello stato di Bot

Il bot ha due stati definiti: il primo è per non fare nulla, e il secondo è per la gestione del movimento. Nel tuo gioco, però, probabilmente avrai bisogno molti di più per cambiare il comportamento del bot in base alla situazione.

public enum BotState
{
  None = 0,
	MoveTo,
}

Ciclo di aggiornamento del bot farà cose diverse a seconda di quale stato è attualmente assegnato 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 funzione CharacterUpdate gestisce tutti gli ingressi e gli aggiornamenti di fisica per il bot.

Per modificare lo stato, useremo una funzione ChangeState che assegna semplicemente il nuovo valore di mCurrentBotState:

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

Controllare il Bot

Ci potrai controllare il bot simulando ingressi, che ti assegniamo a una matrice di valori booleani:

1	protected bool[] mInputs;

Questa matrice è indicizzata in base KeyInput enum:

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

Ad esempio, se vogliamo simulare una pressa del tasto sinistro, lo faremo come questo:

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

La logica di carattere gestirà quindi questo ingresso artificiale nello stesso modo che esso avrebbe gestito vero e proprio ingresso.

Abbiamo bisogno anche di una funzione di supporto aggiuntive o una tabella di ricerca per ottenere il numero di fotogrammi che abbiamo bisogno di premere il pulsante di salto al fine di saltare un determinato numero di blocchi:

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

Si noti che questo funziona solo costantemente se il nostro gioco aggiorna con una frequenza fissa e la velocità di salto iniziale del personaggio sono lo stesso. Idealmente, ci sarebbe calcolare questi valori separatamente per ogni carattere in base alla velocità di salto di quel personaggio, ma sopra funzionerà bene nel nostro caso.

Preparazione e ottenere il percorso da seguire

Vincolare la posizione di obiettivo

Prima abbiamo effettivamente utilizzare il pathfinder, sarebbe una buona idea per forzare la destinazione obiettivo di essere a terra. Questo è perché il giocatore è abbastanza probabile che a fare clic su un punto che è leggermente sopra la terra, nel qual caso percorso del bot sarebbe finita con un imbarazzante salto in aria. Abbassando il punto di fine di essere proprio sulla superficie del terreno, possiamo facilmente evitare questo.

In primo luogo, diamo un'occhiata alla funzione di TappedOnTile. Questa funzione viene chiamata quando il giocatore fa clic in un punto qualsiasi nel gioco; il parametro mapPos è la posizione della piastrella che il giocatore aveva cliccato su:

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

Abbiamo bisogno di abbassare la posizione della piastrella selezionata fino a quando è a terra:

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

Infine, una volta che arriviamo a una ground piastrella, sappiamo dove vogliamo spostare il personaggio per:

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

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

Determinazione della posizione di partenza

Prima abbiamo realmente chiamare la funzione FindPath, abbiamo bisogno di assicurarsi che si passa alla cella di partenza corretta.

In primo luogo, supponiamo che la piastrella di partenza è la cella inferiore sinistra di un carattere:

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

Questa tegola potrebbe non essere quello che vogliamo passare all'algoritmo come primo nodo, perché se il nostro personaggio è in piedi sul bordo della piattaforma, il startTile calcolato in questo modo non può avere nessuna terra, come la seguente situazione:

In questo caso, vorremmo impostare il nodo iniziale alla piastrella che è sul lato sinistro del personaggio, non il suo centro.

Iniziamo con la creazione di una funzione che ci dirà se il carattere rientra una posizione diversa, e in caso affermativo, se è sulla terra in quel punto:

1	bool IsOnGroundAndFitsPos(Vector2i pos)
2	{
3	}

In primo luogo, vediamo se il personaggio si inserisce sul posto. Se così non fosse, possiamo immediatamente restituire 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;
        }
    }
}

Ora possiamo vedere se uno qualsiasi delle piastrelle sotto il carattere sono piastrelle di terra:

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

Torniamo alla funzione MoveTo e vedere se dobbiamo cambiare la piastrella di inizio. Abbiamo bisogno di farlo se il personaggio è a terra ma non è la piastrella di inizio:

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

Sappiamo che, in questo caso, il personaggio si trova sul bordo sinistro o il bordo destro della piattaforma.

Controlliamo prima il bordo destro; Se il carattere rientra c'e la piastrella è a terra, quindi abbiamo bisogno di spostare l'inizio delle mattonelle uno spazio a destra. Se così non fosse, allora dobbiamo spostarlo a sinistra.

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

Ora dovremmo avere tutti i dati che abbiamo bisogno di chiamare il pathfinder:

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

Il primo argomento è la piastrella di inizio.

Il secondo è la destinazione; possiamo passare questo come-è.

Il terzo e il quarto argomento è la larghezza e l'altezza che devono essere approssimato con le dimensioni del riquadro. Si noti che qui vogliamo utilizzare il soffitto dell'altezza in piastrelle — così, ad esempio, se l'altezza reale del personaggio è 2,3 piastrelle, vogliamo che l'algoritmo a pensare il personaggio è in realtà 3 piastrelle alte. (È meglio se l'altezza reale del personaggio è in realtà un po' meno rispetto alla sua dimensione in piastrelle, per consentire un po' più spazio per errori dal percorso seguito AI).

Infine, il quinto argomento è la massima altezza del carattere di salto.

L'elenco dei nodi il backup

Dopo l'esecuzione dell'algoritmo dovremmo controllare se il risultato va bene — che è, se qualsiasi percorso è stato trovato:

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

Se così, abbiamo bisogno di copiare i nodi in un buffer distinto, perché se un altro oggetto per chiamare la funzione FindPath di pathfinder in questo momento, il vecchio risultato verrebbero sovrascritti. Copia il risultato in un elenco separato impedirà questo.

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

Come potete vedere, ci stiamo copiando il risultato in ordine inverso; Questo è perché il risultato stesso è invertito. Fare questo significa i nodi nell'elenco mPath sarà in prima per l'ultimo ordine.

Ora creiamo il nodo corrente di obiettivo. Perché il primo nodo nell'elenco è il punto di partenza, in realtà possiamo ignorarlo e procedere dal secondo nodo in poi:

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

Dopo aver impostato il nodo corrente di obiettivo, impostiamo lo stato di bot su MoveTo, così uno stato appropriato verrà attivato.

Recupero del contesto

Prima di iniziare a scrivere le regole per il movimento di AI, dobbiamo essere in grado di trovare quale situazione il personaggio è in un qualsiasi punto.

Abbiamo bisogno di sapere:

le posizioni delle destinazioni precedente, corrente e successiva
Se la destinazione attuale si trova a terra o in aria
Se il personaggio ha raggiunto la destinazione corrente sull'asse x
Se il personaggio ha raggiunto la destinazione corrente sull'asse y

Nota: le destinazioni di qui non sono necessariamente la destinazione finale obiettivo; sono i nodi nell'elenco nella sezione precedente.

Queste informazioni ci determinerà con precisione cosa deve fare il bot in qualsiasi situazione.

Iniziamo con la dichiarazione di una funzione per ottenere questo contesto:

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

Calcolo delle posizioni del mondo dei nodi di destinazione

La prima cosa che dovremmo fare nella funzione è calcolare la posizione del mondo i nodi di destinazione.

Cominciamo da questo calcolo per la destinazione precedente. Questa operazione dipende da come è impostato il tuo mondo di gioco; nel mio caso, le coordinate di mappa non corrispondono le coordinate del mondo, quindi abbiamo bisogno di tradurli.

Traducendoli è davvero semplice: abbiamo solo bisogno di moltiplicare la posizione del nodo per la dimensione di una piastrella e quindi compensare il vettore calcolato con la posizione sulla mappa:

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

Si noti che iniziamo con mCurrentNodeId uguale a 1, quindi non abbiamo bisogno di preoccuparsi accidentalmente cercando di accedere a un nodo con un indice di -1.

Calcoliamo la posizione della destinazione corrente nello stesso modo:

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

Ed ora per la posizione di destinazione successiva. Qui abbiamo bisogno di controllare se ci sono eventuali nodi lasciati per seguire dopo raggiungiamo il nostro obiettivo attuale, quindi per prima cosa diciamo si supponga che la prossima destinazione è la stessa di quella attuale:

1	nextDest = currentDest;

Ora, se ci sono eventuali nodi lasciati, calcoliamo la prossima destinazione nello stesso modo che abbiamo fatto i precedenti due:

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

Verifica se il nodo è a terra

Il passo successivo è quello di determinare se la destinazione attuale è a terra.

Ricordate che non è abbastanza per controllare solo la piastrella direttamente sotto l'obiettivo; Dobbiamo considerare i casi in cui il personaggio è più di un blocco largo:

Iniziamo da supponendo che la posizione della destinazione non è a terra:

1	destOnGround = false;

Ora daremo un'occhiata attraverso le tegole sotto la destinazione per vedere se ci sono eventuali blocchi solidi lì. Se ci sono, è possibile impostare destOnGround su true:

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

Verifica se il nodo è stata raggiunta sull'asse x

Prima che possiamo vedere se il carattere ha raggiunto l'obiettivo, abbiamo bisogno di conoscere la sua posizione sul percorso. Questa posizione è fondamentalmente il centro della cella inferiore sinistra del nostro carattere. Dal momento che il nostro personaggio non è in realtà costruito da cellule, stiamo andando semplicemente utilizzare il basso a sinistra posizione del riquadro di delimitazione del carattere più una cellula mezza:

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

Questa è la posizione che abbiamo bisogno di corrispondere ai nodi obiettivo.

Come possiamo determinare se il carattere ha raggiunto l'obiettivo sull'asse x? Sarebbe lecito ritenere che, se il personaggio è lo spostamento a destra e ha una posizione x maggiore o uguale a quello di destinazione, quindi l'obiettivo è stato raggiunto.

Per vedere se il carattere è stato commovente destra useremo la destinazione precedente, che in questo caso deve essere stato a sinistra di quella corrente:

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

Lo stesso vale per il lato opposto; Se la destinazione precedente era a destra di quello attuale e il carattere posizione x è minore o uguale a quello della posizione obiettivo, allora possiamo essere sicuri che il personaggio ha raggiunto l'obiettivo sull'asse x:

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

Posizione del carattere a scatto

A volte, a causa della velocità del personaggio, superamento la destinazione, che può comportare l'atterraggio non il nodo di destinazione. Vedere l'esempio riportato di seguito:

Per risolvere questo problema, ci avrai snap posizione del carattere in modo che atterri sul nodo di obiettivo.

Sono le condizioni per noi scattare il carattere:

L'obiettivo è stato raggiunto sull'asse x.
La distanza tra la posizione attuale destinazione e il bot è maggiore di cBotMaxPositionError.
La distanza tra la posizione del bot e la destinazione attuale non è molto lontano, così abbiamo non blocca il carattere da lontano.
Il carattere non spostare a sinistra o destra ultimo girare, così abbiamo scattare il carattere solo se sta cadendo verso il basso.

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 in questo tutorial è uguale a 1 pixel; Questo è quanto siamo fuori lasciamo il carattere sia dalla destinazione consentendo comunque di andare per il prossimo obiettivo.

Verifica se il nodo è stata raggiunta sull'asse y

Cerchiamo di capire quando possiamo essere sicuri che il personaggio ha raggiunto la posizione Y del suo bersaglio. Prima di tutto, se la destinazione precedente è inferiore a quella attuale, e il nostro personaggio salta all'altezza dell'attuale obiettivo, quindi possiamo supporre che l'obiettivo è stato raggiunto.

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

Allo stesso modo, se la destinazione corrente è inferiore a quella precedente e il personaggio ha raggiunto la posizione y del nodo corrente, possiamo impostare reachedY su true come bene.

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

Indipendentemente dal fatto se il carattere deve essere saltando o cadendo per raggiungere la posizione y del nodo di destinazione, se è davvero vicino, quindi dovremmo impostare reachedY su true anche:

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

Se la destinazione è sul terreno, ma non è il carattere, quindi possiamo supporre che la posizione Y dell'obiettivo attuale non è stato raggiunto:

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

Questo è tutto — ecco tutti i dati di base abbiamo bisogno di sapere da considerare che tipo di movimento AI deve fare.

Gestire il movimento del Bot

La prima cosa da fare nella nostra funzione di aggiornamento è ottenere il contesto che abbiamo appena implementato:

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

Ora prendiamo la posizione corrente del carattere lungo il percorso. Questo calcoliamo allo stesso modo che abbiamo fatto nella funzione GetContext:

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

All'inizio del telaio abbiamo bisogno di reimpostare gli ingressi falsi e assegnare loro solo se si pone una condizione di farlo. Useremo solo quattro ingressi: due per movimento destro e sinistro, uno per il salto e uno per far cadere una piattaforma di one-way.

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 prima condizione per il movimento sarà questo: se la destinazione attuale è più bassa rispetto alla posizione del carattere e il carattere è in piedi su una piattaforma sola andata, quindi premere il pulsante giù, che dovrebbe provocare il personaggio che salta fuori la piattaforma verso il basso:

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

Gestione salti

Finiamo il fuori come dovrebbero funzionare il nostro salti. In primo luogo fuori, non vogliamo tenere premuto se mFramesOfJumping è 0 il pulsante di salto.

1	if (mFramesOfJumping > 0)
2	{
3	}

La seconda condizione da verificare è che il personaggio non è a terra.

In questa implementazione della fisica di platforming, il carattere è consentito saltare se solo ha fatto un passo fuori dal bordo di una piattaforma e non è più sulla terra. Si tratta di un metodo popolare per attenuare un'illusione che il giocatore ha premuto il pulsante di salto, ma non salta il carattere, che potrebbe comparire a causa di ritardo di ingresso o il lettore premendo il tasto di salto giusto dopo il carattere ha spostato fuori dalla piattaforma.

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

Questa condizione funzionerà se il carattere ha bisogno di saltare da una sporgenza, perché le cornici di salto verranno impostate un importo appropriato, il carattere naturalmente camminerà sulla sporgenza e a quel punto si inizierà anche il salto.

Questo non funzionerà se il salto deve essere eseguita da terra; per gestire questi che abbiamo bisogno di controllare queste condizioni:

Il personaggio ha raggiunto la posizione x del nodo di destinazione, dove sta per iniziare a saltare.
Il nodo di destinazione non è sul terreno; Se si vuole saltare, abbiamo bisogno di passare attraverso un nodo che è nell'aria prima.

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

Il personaggio dovrebbe saltare anche se è sulla terra e la destinazione è su terreno pure. Generalmente ciò accade se il carattere ha bisogno di saltare una piastrella alto e di lato per raggiungere una piattaforma che è solo un blocco superiore.

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

Ora facciamo attivare il salto e decrementare i fotogrammi di salto, affinché il carattere detiene il salto per il corretto numero di fotogrammi:

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

Si noti che abbiamo decrementare la mFramesOfJumping solo se il carattere non è a terra. Si tratta di evitare accidentalmente diminuendo la lunghezza del salto prima di iniziare il salto.

Procedere con il successivo nodo di destinazione

Pensiamo a che cosa deve accadere quando raggiungiamo il nodo — vale a dire, quando sono vere entrambe reachedX e reachedY.

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

In primo luogo, avrai incrementiamo l'ID del nodo corrente:

1	mCurrentNodeId++;

Ora abbiamo bisogno di verificare se questo ID è maggiore del numero di nodi nel nostro percorso. Se è, significa che il personaggio ha raggiunto l'obiettivo:

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

La prossima cosa che dobbiamo fare è calcolare il salto per il nodo successivo. Poiché abbiamo bisogno di utilizzare questo in più di un luogo, facciamo una funzione per esso:

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

Vogliamo solo saltare se il nuovo nodo è superiore a quella precedente e il personaggio è a terra:

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

Per scoprire quante piastrelle che avremo bisogno di saltare, stiamo andando per scorrere i nodi per come finché essi andare più in alti e più in alto. Quando si arriva a un nodo che si trova ad un'altezza inferiore, o un nodo che è terreno sotto di essa, possiamo fermare, dal momento che sappiamo che non ci sarà alcun bisogno di andare più elevato di quello.

In primo luogo, cerchiamo di dichiarare e impostare la variabile che conterrà il valore del salto:

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

Ora facciamo scorrere i nodi, a partire dal nodo corrente:

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

Se il nodo successivo non è superiore alla jumpHeight ed è a terra, quindi consente di impostare la nuova altezza di 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;
        }
    }
}

Se la nuova altezza di nodo è inferiore rispetto al precedente, o è a terra, poi torniamo al numero di fotogrammi di salto necessario per l'altezza trovato. (E se non c'è nessun bisogno di saltare, appena torniamo 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;
}

Abbiamo bisogno di chiamare questa funzione in due punti.

Il primo è nel caso in cui il personaggio ha raggiunto x - e y-posizioni del nodo:

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

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

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

Si noti che abbiamo impostato i fotogrammi di salto per il salto tutto, così quando raggiungiamo un nodo nell'aria non vogliamo cambiare il numero di fotogrammi di salto che è stato determinato prima del salto avvenuto.

Dopo abbiamo aggiornato l'obiettivo, abbiamo bisogno di elaborare tutto nuovo, così il fotogramma successivo movimento ottiene calcolato immediatamente. Per questo, useremo un comando goto:

1	goto case BotState.MoveTo;

Il secondo posto per che abbiamo bisogno di calcolare il salto è la funzione MoveTo, perché potrebbe essere il caso che il primo nodo del percorso è un nodo di 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);
}

Gestione movimento per raggiungere la posizione del nodo X-

Ora cerchiamo di gestire il movimento per il caso in cui il personaggio non ha ancora raggiunto posizione del nodo di destinazione x.

Niente di complicato qui; Se la destinazione è sulla destra, abbiamo bisogno di simulare la pressione del pulsante destro. Se la destinazione è a sinistra, quindi abbiamo bisogno di simulare la pressione del pulsante sinistro. Abbiamo solo bisogno di muovere il personaggio, se la differenza di posizione è più che la costante di 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;
}

Gestione movimento per raggiungere la posizione del nodo Y-

Se il personaggio ha raggiunto l'obiettivo x-posizione, ma siamo ancora a saltare più in alto, possiamo ancora passare il carattere a sinistra o destra a seconda di dove si trova il prossimo obiettivo. Ciò significa solo che il personaggio non si attacca così rigidamente al percorso trovato. Grazie a ciò, sarà molto più facile raggiungere la prossima destinazione, perché invece di semplicemente in attesa di raggiungere la destinazione y-posizione, il carattere sarà naturalmente muovendo verso x-posizione del nodo successivo mentre lo fa.

Solo ci sposteremo il personaggio verso la prossima destinazione se esiste affatto e non è a terra. (Se è a terra, quindi abbiamo non possiamo ignorare perché è un importante punto di controllo — Reimposta la velocità verticale del personaggio e permette di utilizzare il salto nuovamente.)

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

Ma prima ci muoviamo in realtà verso il prossimo obiettivo, dobbiamo controllare che non rompiamo il percorso in questo modo.

Evitare una caduta di rottura prematuramente

Si consideri il seguente scenario:

Qui, appena il personaggio entrato sulla sporgenza dove è iniziato, ha raggiunto la posizione x del secondo nodo e cadeva per raggiungere la posizione y. Poiché il terzo nodo era a destra del carattere, spostato a destra — e finito in un tunnel sopra a quello che volevamo per andare in.

Per risolvere questo problema, abbiamo bisogno di verificare se ci sono eventuali ostacoli tra il carattere e la destinazione successiva; Se non ci sono, allora siamo liberi muovere il personaggio verso di esso; Se ci sono, quindi dobbiamo aspettare.

In primo luogo, vediamo quali piastrelle avremo bisogno di controllare. Se il prossimo obiettivo è a destra di quello corrente, quindi abbiamo bisogno di controllare le piastrelle sulla destra; Se è a sinistra, ci sarà necessario controllare le tessere a sinistra. Se sono nella stessa posizione di x, non c'è alcun motivo di fare eventuali movimenti pre-emptive.

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

Come potete vedere, la coordinata x del nodo a destra dipende dalla larghezza del carattere.

Ora possiamo verificare se esistono eventuali piastrelle tra il personaggio e posizione del successivo nodo sull'asse y:

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

La funzione AnySolidBlockInStripe controlla se vi sono eventuali piastrelle tinta tra due punti indicati sulla mappa. I punti devono avere la stessa coordinata x. La coordinata x del punto in che stiamo verificando è la piastrella che vorremmo che il personaggio di muoversi in, ma non siamo sicuri se siamo in grado, come spiegato sopra.

Qui è l'implementazione della funzione.

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

Come potete vedere, la funzione è davvero semplice; scorre solo le piastrelle in una colonna, a partire da quella inferiore.

Ora che sappiamo che possiamo spostare verso la prossima destinazione, facciamo così:

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

Permettendo il Bot di saltare i nodi

Questo è quasi tutto — ma c'è ancora un caso da risolvere. Ecco un esempio:

Come si può vedere, prima che il personaggio ha raggiunto la seconda posizione del nodo y-, sbattuto la testa sul riquadro galleggiante, perché ce l'abbiamo fatta spostare verso la destinazione successiva a destra. Di conseguenza, il carattere finisce mai raggiungendo la seconda posizione del nodo y; invece si è mosso dritto il terzo nodo. Poiché reachedY è false in questo caso, esso non può procedere con il percorso.

Per evitare questi casi, semplicemente controlleremo se il personaggio ha raggiunto il prossimo obiettivo prima di raggiungere quella corrente.

La prima mossa in questa direzione sarà essere che separa i nostri calcoli precedenti di reachedX e reachedY nelle proprie funzioni:

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

Avanti, è possibile sostituire i calcoli con la chiamata di funzione nella funzione GetContext:

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

Ora possiamo controllare se è stata raggiunta la destinazione successiva. Se ha, possiamo semplicemente incrementare mCurrentNode e immediatamente rifare lo stato aggiornamento. Questo renderà la prossima destinazione diventa quello corrente, e poiché il personaggio ha raggiunto già, saremo in grado di andare avanti:

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

Questo è tutto per il movimento di carattere!

Condizioni di riavvio di manipolazione

È bene avere un piano di backup per una situazione in cui il bot non si muove attraverso il percorso come dovrebbe. Questo problema può verificarsi se, ad esempio, la mappa viene cambiata — aggiungendo un ostacolo a un percorso già calcolato può causare il percorso per diventare non valido. Quello che faremo è reimpostare il percorso se il personaggio è bloccato per più di un determinato numero di fotogrammi.

Quindi, cerchiamo di dichiarare variabili che conteranno quanti fotogrammi è stato bloccato il carattere e il numero di fotogrammi può essere bloccati al massimo:

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

Abbiamo bisogno di reimpostare questo quando chiamiamo MoveTo funzione:

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

E infine, alla fine della BotState.MoveTo, controlliamo se il personaggio è bloccato. Qui, abbiamo semplicemente bisogno di controllare se la posizione corrente è uguale a quello vecchio; Se così, quindi abbiamo anche bisogno di incrementare la mStuckFrames e verifica se il carattere è stato bloccato per più fotogrammi di cMaxStuckFrames — e se fosse, allora abbiamo bisogno di chiamare la funzione MoveTo con l'ultimo nodo del percorso corrente come parametro. Naturalmente, se la situazione è diversa, quindi dobbiamo reimpostare la mStuckFrames su 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;

Ora il personaggio deve trovare un percorso alternativo se non fosse stato in grado di finire quella iniziale.

Conclusione

Che è tutto il tutorial! È stato un sacco di lavoro, ma spero che troverete utile questo metodo. Mezzo non è una soluzione perfetta per pathfinding Platform; l'approssimazione della curva del salto per il carattere che l'algoritmo ha bisogno di fare spesso è abbastanza difficile da fare e può portare a comportamenti scorretti. L'algoritmo può essere ancora esteso — non è molto difficile aggiungere sporgenza-benne e altri tipi di flessibilità di movimento esteso — ma abbiamo coperto la meccanica di base Platform. È anche possibile ottimizzare il codice per renderlo più veloce, nonché di utilizzare meno memoria; Questa iterazione dell'algoritmo non è affatto perfetta quando si tratta di quegli aspetti. Si soffre anche piuttosto scarsa approssimazione della curva quando cadendo a grande velocità.

L'algoritmo può essere utilizzato in molti modi, in particolare per migliorare il nemico AI o AI compagni. Può anche essere utilizzato come un sistema di controllo per i dispositivi touch — questo funzionerebbe fondamentalmente allo stesso modo lo fa nella demo tutorial, con il giocatore toccando dovunque vogliono il personaggio di muoversi. Questa operazione rimuove la sfida di esecuzione su cui sono stati costruiti molti Platform, così il gioco avrebbe dovuto essere progettato in modo diverso, per essere molto più circa il tuo personaggio di posizionamento nel punto giusto, piuttosto che imparare a controllare il personaggio con precisione.

Grazie per la lettura! Assicuratevi di lasciare un feedback sul metodo e inoltre vorrei sapere se hai fatto eventuali miglioramenti ad esso!