A* Pathfinding für 2D-Grid-based Platformers: Einen Bot dazu bringen, dem Pfad zu folgen

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

In diesem Tutorial verwenden wir den von uns entwickelten Platformer-Pfadfindungsalgorithmus, um einen Bot zu betreiben, der dem Pfad selbst folgen kann. Klicken Sie einfach auf einen Ort und er läuft und springt, um dorthin zu gelangen. Dies ist sehr nützlich für NPCs!

Demo

Sie können die Unity-Demo oder die WebGL-Version (100 MB+) spielen, um das Endergebnis in Aktion zu sehen. Verwenden Sie WASD, um den Charakter zu bewegen, klicken Sie mit der linken Maustaste auf eine Stelle, um einen Weg zu finden, dem Sie folgen können, um dorthin zu gelangen, klicken Sie mit der rechten Maustaste auf eine Zelle, um den Boden an dieser Stelle umzuschalten, klicken Sie mit der mittleren Maustaste, um eine Einwegplattform zu platzieren, und klicken Sie auf -und ziehen Sie die Schieberegler, um ihre Werte zu ändern.

Aktualisieren der Engine

Umgang mit dem Bot-Zustand

Der Bot hat zwei definierte Zustände: Der erste dient dazu, nichts zu tun, und der zweite dient dazu, die Bewegung zu handhaben. In Ihrem Spiel werden Sie jedoch wahrscheinlich viel mehr benötigen, um das Verhalten des Bots der Situation entsprechend zu ändern.

public enum BotState
{
	None = 0,
	MoveTo,
}

Die Update-Schleife des Bots macht verschiedene Dinge, je nachdem, welcher Status derzeit mCurrentBotState zugewiesen ist:

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

Die CharacterUpdate-Funktion verarbeitet alle Eingaben und aktualisiert die Physik für den Bot.

Um den Zustand zu ändern, verwenden wir eine ChangeState-Funktion, die einfach den neuen Wert mCurrentBotState zuweist:

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

Steuerung des Bots

Wir steuern den Bot, indem wir Eingaben simulieren, die wir einem Array von Booleschen Werten zuweisen:

1	protected bool[] mInputs;

Dieses Array wird durch die KeyInput-enum indiziert:

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

Wenn wir zum Beispiel ein Drücken der linken Taste simulieren möchten, machen wir es so:

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

Die Zeichenlogik behandelt dann diese künstliche Eingabe auf dieselbe Weise wie eine echte Eingabe.

Wir benötigen auch eine zusätzliche Hilfsfunktion oder eine Nachschlagetabelle, um die Anzahl der Frames zu erhalten, für die wir die Sprungtaste drücken müssen, um eine bestimmte Anzahl von Blöcken zu überspringen:

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

Beachten Sie, dass dies nur dann konsistent funktioniert, wenn unser Spiel mit einer festen Frequenz aktualisiert wird und die Startsprunggeschwindigkeit des Charakters gleich ist. Idealerweise würden wir diese Werte für jedes Zeichen separat berechnen, abhängig von der Sprunggeschwindigkeit dieses Zeichens, aber das Obige funktioniert in unserem Fall gut.

Vorbereiten und Erhalten des zu befolgenden Pfades

Einschränken der Zielposition

Bevor wir den Pfadfinder tatsächlich verwenden, ist es eine gute Idee, das Ziel auf den Boden zu zwingen. Dies liegt daran, dass der Spieler mit hoher Wahrscheinlichkeit auf eine Stelle klickt, die sich leicht über dem Boden befindet. In diesem Fall würde der Weg des Bots mit einem unangenehmen Sprung in die Luft enden. Indem wir den Endpunkt so absenken, dass er direkt auf der Oberfläche des Bodens liegt, können wir dies leicht vermeiden.

Schauen wir uns zunächst die TappedOnTile-Funktion an. Diese Funktion wird aufgerufen, wenn der Spieler irgendwo im Spiel klickt; Der Parameter mapPos ist die Position des Plättchens, auf das der Spieler geklickt hat:

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

Wir müssen die Position der angeklickten Kachel senken, bis sie auf dem Boden liegt:

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

Wenn wir schließlich bei einem Bodenplättchen ankommen, wissen wir, wohin wir den Charakter bewegen möchten:

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

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

Bestimmung des Startorts

Bevor wir die FindPath-Funktion tatsächlich aufrufen, müssen wir sicherstellen, dass wir die richtige Startzelle übergeben.

Nehmen wir zunächst an, dass die Startkachel die untere linke Zelle eines Charakters ist:

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

Diese Kachel ist möglicherweise nicht diejenige, die wir als ersten Knoten an den Algorithmus übergeben möchten, denn wenn unser Charakter am Rand der Plattform steht, hat die so berechnete startTile möglicherweise keinen Boden, wie in der folgenden Situation:

In diesem Fall möchten wir den Startknoten auf die Kachel setzen, die sich auf der linken Seite des Charakters befindet, nicht in seiner Mitte.

Beginnen wir mit der Erstellung einer Funktion, die uns mitteilt, ob der Charakter an eine andere Position passt und ob er sich an dieser Stelle auf dem Boden befindet:

1	bool IsOnGroundAndFitsPos(Vector2i pos)
2	{
3	}

Lassen Sie uns zuerst sehen, ob der Charakter zu der Stelle passt. Wenn dies nicht der Fall ist, können wir sofort false zurückgeben:

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

Jetzt können wir sehen, ob es sich bei den Kacheln unter dem Charakter um Bodenkacheln handelt:

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

Gehen wir zurück zur MoveTo-Funktion und sehen, ob wir die Startkachel ändern müssen. Wir müssen dies tun, wenn der Charakter am Boden liegt, das Startplättchen jedoch nicht:

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

Wir wissen, dass die Figur in diesem Fall entweder am linken oder rechten Rand der Plattform steht.

Lassen Sie uns zuerst die rechte Kante überprüfen; Passt der Charakter dorthin und das Plättchen liegt auf dem Boden, müssen wir das Startplättchen um ein Feld nach rechts verschieben. Wenn dies nicht der Fall ist, müssen wir es nach links verschieben.

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

Jetzt sollten wir alle Daten haben, die wir brauchen, um den Pathfinder aufzurufen:

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

Das erste Argument ist die Startkachel.

Das zweite ist das Ziel; wir können das so weitergeben wie es ist.

Das dritte und vierte Argument sind die Breite und die Höhe, die durch die Kachelgröße angenähert werden müssen. Beachten Sie, dass wir hier die Obergrenze der Höhe in Kacheln verwenden möchten. Wenn also die tatsächliche Höhe des Charakters 2,3 Kacheln beträgt, möchten wir, dass der Algorithmus denkt, dass der Charakter tatsächlich 3 Kacheln hoch ist. (Es ist besser, wenn die tatsächliche Größe des Charakters tatsächlich etwas geringer ist als seine Größe in Kacheln, um etwas mehr Raum für Fehler auf dem Pfad zu lassen, der der KI folgt.)

Das fünfte Argument schließlich ist die maximale Sprunghöhe des Zeichens.

Sichern der Knotenliste

Nachdem wir den Algorithmus ausgeführt haben, sollten wir überprüfen, ob das Ergebnis in Ordnung ist, dh ob ein Pfad gefunden wurde:

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

Wenn ja, müssen wir die Knoten in einen separaten Puffer kopieren, denn wenn ein anderes Objekt jetzt die FindPath-Funktion des Pfadfinders aufrufen würde, würde das alte Ergebnis überschrieben. Das Kopieren des Ergebnisses in eine separate Liste verhindert dies.

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

Wie Sie sehen, kopieren wir das Ergebnis in umgekehrter Reihenfolge; Dies liegt daran, dass das Ergebnis selbst umgekehrt ist. Dies bedeutet, dass die Knoten in der mPath-Liste in der ersten bis letzten Reihenfolge angeordnet sind.

Legen wir nun den aktuellen Zielknoten fest. Da der erste Knoten in der Liste der Ausgangspunkt ist, können wir ihn tatsächlich überspringen und ab dem zweiten Knoten fortfahren:

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

Nachdem wir den aktuellen Zielknoten festgelegt haben, setzen wir den Bot-Status auf MoveTo, sodass ein entsprechender Status aktiviert wird.

Den Kontext erhalten

Bevor wir anfangen, die Regeln für die KI-Bewegung zu schreiben, müssen wir in der Lage sein, herauszufinden, in welcher Situation sich der Charakter zu einem bestimmten Zeitpunkt befindet.

Wir müssen wissen:

die Positionen des vorherigen, aktuellen und nächsten Ziels
ob das aktuelle Ziel am Boden oder in der Luft liegt
ob das Zeichen das aktuelle Ziel auf der x-Achse erreicht hat
ob das Zeichen das aktuelle Ziel auf der y-Achse erreicht hat

Hinweis: Die Ziele hier sind nicht unbedingt das endgültige Zielziel; Sie sind die Knoten in der Liste aus dem vorherigen Abschnitt.

Anhand dieser Informationen können wir genau bestimmen, was der Bot in jeder Situation tun soll.

Beginnen wir mit der Deklaration einer Funktion, um diesen Kontext zu erhalten:

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

Berechnen der Weltpositionen von Zielknoten

Das erste, was wir in der Funktion tun sollten, ist die Weltposition der Zielknoten zu berechnen.

Beginnen wir damit, dies für das vorherige Ziel zu berechnen. Dieser Vorgang hängt davon ab, wie Ihre Spielwelt eingerichtet ist; In meinem Fall stimmen die Kartenkoordinaten nicht mit den Weltkoordinaten überein, daher müssen wir sie übersetzen.

Sie zu übersetzen ist wirklich einfach: Wir müssen nur die Position des Knotens mit der Größe einer Kachel multiplizieren und dann den berechneten Vektor mit der Kartenposition versetzen:

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

Beachten Sie, dass wir mit mCurrentNodeId gleich 1 beginnen, sodass wir uns keine Sorgen machen müssen, versehentlich auf einen Knoten mit einem Index von -1 zuzugreifen.

Wir berechnen die Position des aktuellen Ziels auf die gleiche Weise:

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

Und nun zur Position des nächsten Ziels. Hier müssen wir überprüfen, ob nach Erreichen unseres aktuellen Ziels noch Knoten zu folgen sind. Nehmen wir also zunächst an, dass das nächste Ziel das gleiche ist wie das aktuelle:

1	nextDest = currentDest;

Wenn nun noch Knoten übrig sind, berechnen wir das nächste Ziel auf die gleiche Weise wie die beiden vorherigen:

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

Prüfen, ob sich der Knoten am Boden befindet

Im nächsten Schritt wird festgestellt, ob sich das aktuelle Ziel am Boden befindet.

Denken Sie daran, dass es nicht ausreicht, nur die Kachel direkt unter dem Tor zu überprüfen; Wir müssen die Fälle berücksichtigen, in denen das Zeichen mehr als einen Block breit ist:

Beginnen wir mit der Annahme, dass sich die Position des Ziels nicht auf dem Boden befindet:

1	destOnGround = false;

Jetzt schauen wir uns die Kacheln unter dem Ziel an, um festzustellen, ob dort feste Blöcke vorhanden sind. Wenn ja, können wir destOnGround auf true setzen:

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

Überprüfen, ob der Knoten auf der X-Achse erreicht wurde

Bevor wir sehen können, ob der Charakter das Ziel erreicht hat, müssen wir seine Position auf dem Weg kennen. Diese Position ist im Grunde das Zentrum der unteren linken Zelle unseres Charakters. Da unser Charakter nicht wirklich aus Zellen besteht, verwenden wir einfach die untere linke Position des Begrenzungsrahmens des Charakters plus eine halbe Zelle:

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

Dies ist die Position, die wir den Zielknoten zuordnen müssen.

Wie können wir feststellen, ob der Charakter das Ziel auf der x-Achse erreicht hat? Es ist sicher anzunehmen, dass das Ziel erreicht wurde, wenn sich der Charakter nach rechts bewegt und eine x-Position größer oder gleich der des Ziels hat.

Um zu sehen, ob sich der Charakter nach rechts bewegt hat, verwenden wir das vorherige Ziel, das in diesem Fall links vom aktuellen Ziel liegen muss:

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

Gleiches gilt für die Gegenseite; Wenn das vorherige Ziel rechts vom aktuellen lag und die x-Position des Charakters kleiner oder gleich der Zielposition ist, können wir sicher sein, dass der Charakter das Ziel auf der x-Achse erreicht hat:

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

Schnapp dir die Position des Charakters

Manchmal überschießt er aufgrund der Geschwindigkeit des Charakters das Ziel, was dazu führen kann, dass er nicht auf dem Zielknoten landet. Siehe folgendes Beispiel:

Um dies zu beheben, rasten wir die Position des Charakters ein, damit er auf dem Zielknoten landet.

Die Bedingungen für uns, den Charakter zu schnappen, sind:

Das Ziel wurde auf der x-Achse erreicht.
Der Abstand zwischen der Position des Bots und dem aktuellen Ziel ist größer als cBotMaxPositionError.
Die Entfernung zwischen der Position des Bots und dem aktuellen Ziel ist nicht sehr groß, daher schnappen wir den Charakter nicht aus der Ferne.
Der Charakter hat sich in der letzten Kurve nicht nach links oder rechts bewegt, also schnappen wir den Charakter nur, wenn er gerade nach unten fällt.

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 diesem Tutorial ist gleich 1 Pixel; So weit lassen wir den Charakter vom Ziel entfernt sein, während wir ihm trotzdem erlauben, zum nächsten Ziel zu gelangen.

Prüfen, ob der Knoten auf der Y-Achse erreicht wurde

Lassen Sie uns herausfinden, wann wir sicher sein können, dass der Charakter die Y-Position seines Ziels erreicht hat. Wenn das vorherige Ziel unter dem aktuellen liegt und unser Charakter auf die Höhe des aktuellen Ziels springt, können wir zunächst davon ausgehen, dass das Ziel erreicht wurde.

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

Wenn das aktuelle Ziel unter dem vorherigen liegt und das Zeichen die y-Position des aktuellen Knotens erreicht hat, können wir auch reachedY auf true setzen.

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

Unabhängig davon, ob der Charakter springen oder fallen muss, um die y-Position des Zielknotens zu erreichen, sollten wir reachedY auch auf true setzen, wenn er wirklich nahe ist:

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

Wenn das Ziel auf dem Boden liegt, der Charakter jedoch nicht, können wir davon ausgehen, dass die Y-Position des aktuellen Ziels nicht erreicht wurde:

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

Das ist alles – das sind alle grundlegenden Daten, die wir wissen müssen, um zu überlegen, welche Art von Bewegung die KI ausführen muss.

Umgang mit der Bewegung des Bots

Das erste, was Sie in unserer update-Funktion tun müssen, ist den Kontext abzurufen, den wir gerade implementiert haben:

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

Lassen Sie uns nun die aktuelle Position des Charakters entlang des Pfads ermitteln. Wir berechnen dies auf die gleiche Weise wie in der GetContext-Funktion:

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

Am Anfang des Frames müssen wir die gefälschten Eingaben zurücksetzen und sie nur zuweisen, wenn eine Bedingung dafür eintritt. Wir werden nur vier Eingaben verwenden: zwei für die Bewegung nach links und rechts, eine zum Springen und eine zum Absetzen von einer Einbahnplattform.

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

Die allererste Bedingung für die Bewegung ist folgende: Wenn das aktuelle Ziel niedriger als die Position des Charakters ist und der Charakter auf einer Einwegplattform steht, drücken Sie die Abwärtstaste, was dazu führen sollte, dass der Charakter von der Plattform nach unten springt:

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

Sprünge handhaben

Lassen Sie uns festlegen, wie unsere Sprünge funktionieren sollen. Zunächst einmal möchten wir die Sprungtaste nicht gedrückt halten, wenn mFramesOfJumping 0 ist.

1	if (mFramesOfJumping > 0)
2	{
3	}

Die zweite zu überprüfende Bedingung ist, dass sich der Charakter nicht am Boden befindet.

Bei dieser Implementierung der Platformer-Physik darf der Charakter springen, wenn er gerade die Kante einer Plattform verlassen hat und nicht mehr auf dem Boden liegt. Dies ist eine beliebte Methode, um die Illusion zu mildern, dass der Spieler die Sprungtaste gedrückt hat, der Charakter jedoch nicht gesprungen ist, was möglicherweise aufgrund von Eingabeverzögerungen oder dem Drücken der Sprungtaste direkt nach dem Verlassen der Plattform aufgetreten ist.

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

Diese Bedingung funktioniert, wenn der Charakter von einem Sims springen muss, da die Sprungrahmen auf einen angemessenen Wert eingestellt sind, der Charakter natürlich von dem Sims abläuft und an diesem Punkt auch den Sprung startet.

Dies funktioniert nicht, wenn der Sprung vom Boden aus ausgeführt werden muss; Um diese zu handhaben, müssen wir diese Bedingungen überprüfen:

Der Charakter hat die x-Position des Zielknotens erreicht, wo er zu springen beginnt.
Der Zielknoten befindet sich nicht am Boden; Wenn wir hochspringen wollen, müssen wir zuerst einen Knoten durchlaufen, der in der Luft liegt.

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

Der Charakter sollte auch springen, wenn er sich auf dem Boden befindet und das Ziel ebenfalls auf dem Boden liegt. Dies geschieht im Allgemeinen, wenn der Charakter eine Kachel nach oben und zur Seite springen muss, um eine Plattform zu erreichen, die nur einen Block höher ist.

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

Lassen Sie uns nun den Sprung aktivieren und die Sprungrahmen dekrementieren, damit der Charakter den Sprung für die richtige Anzahl von Frames hält:

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

Beachten Sie, dass wir mFramesOfJumping nur dekrementieren, wenn sich der Charakter nicht am Boden befindet. Dies soll verhindern, dass die Sprunglänge versehentlich verringert wird, bevor der Sprung gestartet wird.

Weiter zum nächsten Zielknoten

Lassen Sie uns darüber nachdenken, was passieren muss, wenn wir den Knoten erreichen – das heißt, wenn beides, reachedX und reachedY, true sind.

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

Zuerst erhöhen wir die aktuelle Knoten-ID:

1	mCurrentNodeId++;

Jetzt müssen wir prüfen, ob diese ID größer ist als die Anzahl der Knoten in unserem Pfad. Wenn ja, hat der Charakter das Ziel erreicht:

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

Als nächstes müssen wir den Sprung für den nächsten Knoten berechnen. Da wir dies an mehr als einer Stelle verwenden müssen, erstellen wir eine Funktion dafür:

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

Wir wollen nur springen, wenn der neue Knoten höher ist als der vorherige und der Charakter am Boden liegt:

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

Um herauszufinden, wie viele Kacheln wir springen müssen, durchlaufen wir die Knoten, solange sie höher und höher werden. Wenn wir einen Knoten mit niedrigerer Höhe erreichen oder einen Knoten mit Boden darunter haben, können wir anhalten, da wir wissen, dass wir nicht höher gehen müssen.

Zuerst deklarieren und setzen wir die Variable, die den Wert des Sprungs enthält:

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

Lassen Sie uns nun die Knoten durchlaufen, beginnend beim aktuellen Knoten:

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

Wenn der nächste Knoten höher als die jumpHeight ist und sich nicht auf dem Boden befindet, legen wir die neue Sprunghöhe fest:

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

Wenn die neue Knotenhöhe niedriger als die vorherige ist oder sich auf dem Boden befindet, geben wir die Anzahl der Sprungrahmen zurück, die für die gefundene Höhe erforderlich sind. (Und wenn kein Sprung nötig ist, geben wir einfach 0 zurück.)

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

Wir müssen diese Funktion an zwei Stellen aufrufen.

Die erste ist, wenn das Zeichen die x- und y-Positionen des Knotens erreicht hat:

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

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

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

Beachten Sie, dass wir die Sprungrahmen für den gesamten Sprung festlegen. Wenn wir also einen In-Air-Knoten erreichen, möchten wir die Anzahl der Sprungrahmen, die vor dem Sprung festgelegt wurden, nicht ändern.

Nachdem wir das Ziel aktualisiert haben, müssen wir alles erneut verarbeiten, damit der nächste Bewegungsrahmen sofort berechnet wird. Dazu verwenden wir einen goto-Befehl:

1	goto case BotState.MoveTo;

Die zweite Stelle, für die wir den Sprung berechnen müssen, ist die Funktion MoveTo, da es sein könnte, dass der erste Knoten des Pfads ein Sprungknoten ist:

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

Handhabung der Bewegung, um die X-Position des Knotens zu erreichen

Behandeln wir nun die Bewegung für den Fall, dass der Charakter die x-Position des Zielknotens noch nicht erreicht hat.

Nichts Kompliziertes hier; Wenn das Ziel rechts liegt, müssen wir den richtigen Tastendruck simulieren. Wenn das Ziel links liegt, müssen wir das Drücken der linken Taste simulieren. Wir müssen das Zeichen nur verschieben, wenn der Positionsunterschied größer als die Konstante cBotMaxPositionError ist:

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

Handhabung der Bewegung zum Erreichen der Y-Position des Knotens

Wenn der Charakter die Ziel-X-Position erreicht hat, wir aber trotzdem höher springen können, können wir den Charakter immer noch nach links oder rechts bewegen, je nachdem, wo das nächste Ziel ist. Dies bedeutet nur, dass der Charakter nicht so starr am gefundenen Pfad haftet. Dadurch wird es viel einfacher sein, zum nächsten Ziel zu gelangen, denn anstatt einfach nur darauf zu warten, die Ziel-y-Position zu erreichen, bewegt sich der Charakter dabei auf natürliche Weise in Richtung der x-Position des nächsten Knotens.

Wir werden den Charakter nur dann zum nächsten Ziel bewegen, wenn er überhaupt existiert und sich nicht am Boden befindet. (Wenn es auf dem Boden liegt, können wir es nicht überspringen, da es ein wichtiger Kontrollpunkt ist – es setzt die vertikale Geschwindigkeit des Charakters zurück und ermöglicht es ihm, den Sprung erneut zu verwenden.)

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

Bevor wir uns jedoch dem nächsten Ziel nähern, müssen wir sicherstellen, dass wir damit nicht den Weg brechen.

Vermeiden, einen Sturz vorzeitig zu brechen

Betrachten Sie das folgende Szenario:

Hier erreichte die Figur, sobald sie die Kante, an der sie begann, verließ, die x-Position des zweiten Knotens und fiel, um die y-Position zu erreichen. Da sich der dritte Knoten rechts vom Charakter befand, bewegte er sich nach rechts – und endete in einem Tunnel über dem, in den er hineingehen sollte.

Um dies zu beheben, müssen wir prüfen, ob sich zwischen dem Charakter und dem nächsten Ziel Hindernisse befinden; wenn nicht, können wir den Charakter darauf hin bewegen; wenn ja, dann müssen wir warten.

Sehen wir uns zunächst an, welche Kacheln wir überprüfen müssen. Wenn sich das nächste Ziel rechts vom aktuellen befindet, müssen wir die Kacheln rechts überprüfen. Wenn es links ist, müssen wir die Kacheln links überprüfen. Wenn sie sich an derselben x-Position befinden, gibt es keinen Grund, Präventivbewegungen durchzuführen.

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

Wie Sie sehen, hängt die x-Koordinate des Knotens rechts von der Breite des Zeichens ab.

Jetzt können wir überprüfen, ob sich zwischen dem Zeichen und der Position des nächsten Knotens auf der y-Achse Kacheln befinden:

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

Die Funktion AnySolidBlockInStripe überprüft, ob zwischen zwei bestimmten Punkten auf der Karte feste Kacheln vorhanden sind. Die Punkte müssen die gleiche x-Koordinate haben. Die x-Koordinate, die wir überprüfen, ist die Kachel, in die sich der Charakter bewegen soll, aber wir sind uns nicht sicher, ob wir das können, wie oben erklärt.

Hier ist die Implementierung der Funktion.

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

Wie Sie sehen, ist die Funktion wirklich einfach; es iteriert einfach durch die Kacheln in einer Spalte, beginnend mit der unteren.

Jetzt, da wir wissen, dass wir uns dem nächsten Ziel nähern können, tun wir dies:

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

Zulassen, dass der Bot Knoten überspringt

Das war's fast schon – aber es gibt noch einen Fall zu lösen. Hier ist ein Beispiel:

Wie Sie sehen, stieß der Charakter, bevor er die y-Position des zweiten Knotens erreichte, mit dem Kopf gegen die schwebende Kachel, weil wir ihn zum nächsten Ziel nach rechts bewegten. Als Ergebnis erreicht das Zeichen nie die y-Position des zweiten Knotens; stattdessen ging es direkt zum dritten Knoten. Da reachedY in diesem Fall false ist, kann es nicht mit dem Pfad fortfahren.

Um solche Fälle zu vermeiden, prüfen wir einfach, ob der Charakter das nächste Ziel erreicht hat, bevor er das aktuelle erreicht hat.

Der erste Schritt in diese Richtung besteht darin, unsere bisherigen Berechnungen von reachedX und reachedY in ihre eigenen Funktionen aufzuteilen:

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

Ersetzen Sie als Nächstes die Berechnungen durch den Funktionsaufruf in der GetContext-Funktion:

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

Jetzt können wir überprüfen, ob das nächste Ziel erreicht wurde. Wenn dies der Fall ist, können wir mCurrentNode einfach inkrementieren und die Zustandsaktualisierung sofort wiederholen. Dadurch wird das nächste Ziel zum aktuellen und da der Charakter es bereits erreicht hat, können wir weitermachen:

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

Das ist alles für die Charakterbewegung!

Umgang mit Neustartbedingungen

Es ist gut, einen Backup-Plan für eine Situation zu haben, in der sich der Bot nicht wie vorgesehen durch den Pfad bewegt. Dies kann beispielsweise passieren, wenn die Karte geändert wird – das Hinzufügen eines Hindernisses zu einem bereits berechneten Pfad kann dazu führen, dass der Pfad ungültig wird. Was wir tun, ist den Pfad zurückzusetzen, wenn der Charakter länger als eine bestimmte Anzahl von Frames feststeckt.

Lassen Sie uns also Variablen deklarieren, die zählen, wie viele Frames der Charakter hängengeblieben ist und wie viele Frames er höchstens hängen bleiben darf:

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

Wir müssen dies zurücksetzen, wenn wir die MoveTo-Funktion aufrufen:

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

Und schließlich, am Ende von BotState.MoveTo, überprüfen wir, ob das Zeichen feststeckt. Hier müssen wir nur überprüfen, ob seine aktuelle Position mit der alten übereinstimmt; In diesem Fall müssen wir auch die mStuckFrames erhöhen und prüfen, ob das Zeichen für mehr Frames als cMaxStuckFrames feststeckt. Wenn dies der Fall ist, müssen wir die MoveTo-Funktion mit dem letzten Knoten des aktuellen Pfads als Parameter aufrufen. Wenn die Position anders ist, müssen wir die mStuckFrames natürlich auf 0 zurücksetzen:

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;

Jetzt sollte der Charakter einen alternativen Pfad finden, wenn er den ursprünglichen nicht beenden konnte.

Abschluss

Das ist das ganze Tutorial! Es war viel Arbeit, aber ich hoffe, Sie finden diese Methode nützlich. Es ist keineswegs die perfekte Lösung für die Pfadfindung im Plattformer; Die Approximation der Sprungkurve für das Zeichen, die der Algorithmus erstellen muss, ist oft ziemlich schwierig und kann zu falschem Verhalten führen. Der Algorithmus kann noch erweitert werden – es ist nicht sehr schwer, Ledge-Grabs und andere Arten erweiterter Bewegungsflexibilität hinzuzufügen – aber wir haben die grundlegenden Plattformer-Mechaniken behandelt. Es ist auch möglich, den Code zu optimieren, um ihn schneller zu machen und weniger Speicher zu verbrauchen; Diese Iteration des Algorithmus ist in Bezug auf diese Aspekte überhaupt nicht perfekt. Es leidet auch unter einer ziemlich schlechten Annäherung der Kurve, wenn es mit großen Geschwindigkeiten fällt.

Der Algorithmus kann auf viele Arten verwendet werden, insbesondere zur Verbesserung der feindlichen KI oder der KI-Gefährten. Es kann auch als Steuerungsschema für Touch-Geräte verwendet werden – dies würde im Wesentlichen genauso funktionieren wie in der Tutorial-Demo, wobei der Spieler dort tippt, wo sich der Charakter bewegen soll. Dies beseitigt die Ausführungsherausforderung, auf der viele Plattformer basieren, sodass das Spiel anders gestaltet werden müsste, um viel mehr darauf zu achten, Ihren Charakter an der richtigen Stelle zu positionieren, als zu lernen, den Charakter genau zu steuern.

Danke fürs Lesen! Hinterlassen Sie unbedingt ein Feedback zur Methode und lassen Sie mich wissen, wenn Sie Verbesserungen daran vorgenommen haben!