Wie würde man die Position eines Teilnehmers an einem Rennspiel bestimmen?

9

Im Moment implementiere ich überhaupt kein Rennspiel, aber dieses Problem ist mir gerade in den Sinn gekommen und jetzt bin ich neugierig.

Wie würde man also herausfinden, welcher Teilnehmer eines Rennens derzeit der erste ist? Es kann nicht trivial sein, nur nach Entfernung bis zur Ziellinie zu sortieren, da dies auf den meisten Strecken sehr ungenau wäre. Ich habe darüber nachgedacht, die Route in gerade Segmente zu unterteilen, von denen jedes einen Richtungsvektor hat. Das Spiel prüft dann, ob jemand anderen überholt, indem es seine Positionen auf diesen Vektor projiziert und prüft, welcher vor ihm liegt. Wenn sich die Position geändert hat, würde das Spiel sie entsprechend erhöhen / verringern. Das scheint aber etwas zu kompliziert.

Kennt jemand etablierte Methoden oder hat Erfahrung in der Implementierung einiger?

Marc Müller
quelle

Antworten:

12

Shawn Hargreaves beschreibt, wie die MotoGP ein spezielles spurbezogenes Positionssystem verwendete . Ohne Berücksichtigung der vertikalen y-Position werden die kartesischen x / z-Koordinaten in ein spurbezogenes System übersetzt. Dies hatte viele Vorteile für Berechnungen, die die relativen Positionen der Teilnehmer an einem Rennspiel betreffen (zum Beispiel für die KI):

Eine übliche Vereinfachung besteht darin, 3D in 2D zu reduzieren. Auch wenn Rendering und Physik wirklich 3D sind, muss die Entscheidungslogik nicht alle drei Achsen gleich behandeln. MotoGP-Strecken haben nur wenige Hügel, sodass unsere KI die y-Komponente ignorieren konnte.

Als nächstes wechselten wir von x / z-kartesischen Koordinaten zu einem spurbezogenen System. Die Positionen wurden durch ein Wertepaar dargestellt:

int distance = wie weit um die Spur herum, gespeichert im 16.16-Festkommaformat

  • 0 = Startlinie
  • 0x8000 = auf halbem Weg
  • 0x10000 = zum Start zurückgeschleift
  • 0x1C000 = drei Viertel des Weges durch die zweite Runde

float cross = wie weit seitlich über die Spur 0 = auf der Mittellinie

  • -1 = linker Rand der Rennfläche
  • 1 = rechter Rand der Rennfläche

Um zwischen diesen und den von unserer Physik und unserem Rendering-Code verwendeten kartesischen Koordinaten zu konvertieren, haben wir eine Liste von Segmenten gespeichert, die die Form der Rennfläche definieren: struct TrackSegment {Vector CenterPoint; float DistanceToLeftEdge; float DistanceToRightEdge; }}

Wir haben mehrere hundert dieser Strukturen erstellt, die gleichmäßig um die Spur verteilt sind, indem wir die Bezier-Kurven, aus denen die Spuren ursprünglich erstellt wurden, tesselliert haben. Dies gab uns genügend Informationen, um die erforderlichen Koordinatenkonvertierungsfunktionen zu schreiben.

Mit spurbezogenen Koordinaten werden viele nützliche Berechnungen trivial einfach:

if (abs(cross) > 1)
    // You are off the track and should steer back toward the center line


if (this.distance > other.distance)
    // You are ahead of the other player (even though you may be
    // physically behind in 3D space if you have lapped them)


short difference = (short)(this.distance - other.distance);

if (abs(difference) < threshold)
    // These two bikes are physically close together,
    // so we should run obstacle avoidance checks

Aufgrund des Festpunktdatenformats war das Umsetzen des Abstandszählers von 32 auf 16 Bit eine einfache Möglichkeit, die Rundennummer zu verwerfen, sodass wir auswählen konnten, welche Berechnungen wichtig waren, wenn sich zwei Motorräder auf unterschiedlichen Runden befanden, anstatt zu wissen, ob sie es waren waren nah im physischen Raum. Dank der Magie des Zweierkompliments ergibt die Behandlung des Unterschieds als vorzeichenbehaftetes 16-Bit die kürzeste Entfernung, unabhängig davon, welches Fahrrad sich vorne befindet (denken Sie daran, dass es in einem Modulo-Arithmetiksystem wie einer Rundstrecke zwei mögliche Entfernungen gibt, die Sie messen können in beide Richtungen um die Strecke). Dies funktioniert auch dann, wenn sich die beiden Fahrräder auf gegenüberliegenden Seiten der Startlinie befinden. Dies würde in den meisten anderen Koordinatensystemen eine fehleranfällige Sonderfalllogik erfordern.

Durch das Abflachen und Begradigen dieses virtuellen Spielbereichs war es einfach, über Dinge wie "Bin ich auf der Rennlinie?" oder "Ich komme schnell hinter dieses andere Fahrrad: Habe ich mehr Platz, um sie links oder rechts zu überholen?" Das wäre schwierig gewesen, in einem vollständigen 3D-Weltraum zu implementieren. Sobald wir uns entschieden haben, auf der linken Seite vorbeizukommen, konvertieren wir die resultierende spurbezogene Koordinate zurück in den Weltraum. An diesem Punkt wird die Krümmung der Spur berücksichtigt, um zu zeigen, wie wir steuern sollten, um unser gewähltes Ziel zu erreichen.

Leftium
quelle
Sehr schön! Vielen Dank. Vielen Dank auch für das Hinzufügen entsprechender Tags. Ich konnte dies aufgrund mangelnden Rufs nicht tun. Prost.
Marc Müller
3

Ich denke, ich würde die Tatsache nutzen, dass die Straße im Allgemeinen mit Splines aufgebaut wird, daher hat jede Kante der Straße eine entsprechende Spline-Position, und mit dieser können Sie bestimmen (ungefähr oder feinkörnig, wenn Sie weiter unterteilen), was die Strömung ist Die Spline-Position jedes Autos ist und somit wer an der Spitze liegt. Also mehr oder weniger so, wie Sie es vorschlagen, nur mit dem Spline.

Kaj
quelle
3

Sie haben Ihre eigene Frage mehr oder weniger beantwortet, denke ich. Teilen Sie die Spur in Segmente auf, verfolgen Sie, in welchem ​​Segment sich jedes Auto befindet, und projizieren Sie die Autos auf eine Linie durch die Mitte des entsprechenden Segments (mathematisch gesehen ist es ein einfaches Punktprodukt, also überhaupt nicht kompliziert). Sehr einfach, jedem Auto einen "Abstand" zu geben, den Sie nach Position sortieren können.

Die Segmente bieten Ihnen einen zusätzlichen Vorteil: Sie können sicherstellen, dass Autos keine Kurven fahren (oder generell Abkürzungen nehmen), rückwärts fahren oder andere Cheats durchführen.

JasonD
quelle