Wie kann ich eine Kollisionsmaschine optimieren, bei der die Reihenfolge wichtig und die Kollision abhängig von der Objektgruppe ist?

14

Wenn Sie diese Frage zum ersten Mal beantworten, empfehle ich, zuerst den nachstehenden Teil vor dem Update und dann diesen Teil zu lesen. Hier ist eine Zusammenfassung des Problems:

Grundsätzlich habe ich eine Kollisionserkennungs- und -auflösungs-Engine mit einem räumlichen Rasterteilungssystem, bei dem Kollisionsreihenfolge und Kollisionsgruppen eine Rolle spielen. Es muss sich jeweils ein Körper bewegen, dann eine Kollision erkennen und dann die Kollisionen auflösen. Wenn ich alle Körper auf einmal bewege und dann mögliche Kollisionspaare generiere, ist dies offensichtlich schneller, aber die Auflösung bricht ab, weil die Reihenfolge der Kollisionen nicht eingehalten wird. Wenn ich einen Körper nach dem anderen bewege, muss ich dafür sorgen, dass die Körper Kollisionen überprüfen, und das wird zu einem ^ 2-Problem. Fügen Sie Gruppen in die Mischung ein, und Sie können sich vorstellen, warum es mit vielen Körpern sehr langsam und sehr schnell wird.


Update: Ich habe wirklich hart daran gearbeitet, konnte aber nichts optimieren.

Ich habe das von Will beschriebene "Bild" erfolgreich implementiert und Gruppen in Bitsets geändert, aber es ist eine sehr, sehr geringe Beschleunigung.

Ich habe auch ein großes Problem entdeckt: Mein Motor ist abhängig von der Reihenfolge der Kollisionen.

Ich habe versucht, eine einzigartige Kollisionspaargenerierung zu implementieren , die definitiv alles um ein Vielfaches beschleunigt, aber die Kollisionsreihenfolge gebrochen hat .

Lassen Sie mich erklären:

  • In meinem ursprünglichen Design (ohne Paare zu generieren) passiert Folgendes:

    1. ein einzelner Körper bewegt sich
    2. Nachdem es sich bewegt hat, aktualisiert es seine Zellen und holt sich die Körper, gegen die es kollidiert
    3. Wenn es einen Körper überlappt, gegen den es aufgelöst werden muss, beheben Sie die Kollision

    Dies bedeutet, dass, wenn sich ein Körper bewegt und gegen eine Wand (oder einen anderen Körper) stößt, nur der Körper, der sich bewegt hat, seine Kollision löst und der andere Körper davon nicht betroffen ist.

    Das ist das Verhalten, das ich mir wünsche .

    Ich verstehe, dass es für Physik-Engines nicht üblich ist, aber es hat viele Vorteile für Spiele im Retro-Stil .

  • Im üblichen Gitterdesign (Erzeugung eindeutiger Paare) geschieht dies:

    1. Alle Körper bewegen sich
    2. Nachdem sich alle Körper bewegt haben, aktualisieren Sie alle Zellen
    3. erzeugen eindeutige Kollisionspaare
    4. Behandeln Sie für jedes Paar die Kollisionserkennung und -auflösung

    In diesem Fall hätte eine gleichzeitige Bewegung dazu führen können, dass sich zwei Körper überlappen, und sie lösen sich gleichzeitig auf. Dadurch werden die Körper effektiv "gegeneinander gedrückt" und die Kollisionsstabilität mit mehreren Körpern wird aufgehoben

    Dieses Verhalten ist für Physik-Engines üblich, in meinem Fall jedoch nicht akzeptabel .

Ich habe auch ein anderes Problem gefunden, das sehr wichtig ist (auch wenn es in einer realen Situation nicht wahrscheinlich ist):

  • Betrachten Sie Körper der Gruppen A, B und W
  • A kollidiert und löst sich gegen W und A auf
  • B kollidiert und löst sich gegen W und B auf
  • A tut nichts gegen B
  • B macht nichts gegen A

Es kann eine Situation geben, in der viele A-Körper und B-Körper dieselbe Zelle belegen. In diesem Fall gibt es eine Menge unnötiger Iterationen zwischen Körpern, die nicht aufeinander reagieren dürfen (oder Kollisionen nur erkennen, aber nicht auflösen). .

Für 100 Körper, die dieselbe Zelle belegen, sind es 100 ^ 100 Iterationen! Dies geschieht, weil keine eindeutigen Paare generiert werden - aber ich kann keine eindeutigen Paare generieren , da ich sonst ein Verhalten bekomme, das ich nicht wünsche.

Gibt es eine Möglichkeit, diese Art von Kollisionsmotor zu optimieren?

Dies sind die Richtlinien, die eingehalten werden müssen:

  • Reihenfolge der Kollision ist extrem wichtig!

    • Körper bewegen muss einen nach dem anderen , dann überprüfen Sie auf Kollisionen einen nach dem anderen , und Entschlossenheit nach der Bewegung eines nach dem anderen .
  • Körper müssen 3 Gruppenbitsätze haben

    • Gruppen : Gruppen, zu denen der Körper gehört
    • GroupsToCheck : Gruppen, die der Körper erkennen muss Kollision
    • GroupsNoResolve : Gruppen, die der Body nicht auflösen darf Kollision
    • Es kann Situationen geben, in denen ich nur möchte, dass eine Kollision erkannt, aber nicht behoben wird



Pre-Update:

Vorwort : Ich bin mir bewusst, dass die Optimierung dieses Engpasses keine Notwendigkeit ist - der Motor ist bereits sehr schnell. Ich würde jedoch aus Spaß- und Bildungsgründen gerne einen Weg finden, den Motor noch schneller zu machen.


Ich erstelle eine universelle C ++ 2D-Kollisionserkennungs- / Antwort-Engine mit Schwerpunkt auf Flexibilität und Geschwindigkeit.

Hier ist ein sehr einfaches Diagramm seiner Architektur:

Grundlegende Motorarchitektur

Grundsätzlich ist die Hauptklasse World, die den Speicher von a ResolverBase*, a SpatialBase*und a besitzt (verwaltet) vector<Body*>.

SpatialBase ist eine rein virtuelle Klasse, die sich mit der Erkennung von Kollisionen in weiten Phasen befasst.

ResolverBase ist eine rein virtuelle Klasse, die sich mit Kollisionsauflösung befasst.

Die Körper kommunizieren World::SpatialBase*mit SpatialInfoObjekten, die den Körpern selbst gehören.


Derzeit gibt es eine räumliche Klasse: Dies ist ein Grid : SpatialBasefestes 2D-Grundraster. Es hat eine eigene Info-Klasse,GridInfo : SpatialInfo .

So sieht die Architektur aus:

Motorarchitektur mit räumlichem Raster

Die GridKlasse besitzt ein 2D-Array von Cell*. Die CellKlasse enthält eine Sammlung von (nicht im Besitz) Body*: a, vector<Body*>die alle Körper enthält, die sich in der Zelle befinden.

GridInfo Objekte enthalten auch nicht-besitzende Zeiger auf die Zellen, in denen sich der Körper befindet.


Wie ich bereits sagte, basiert die Engine auf Gruppen.

  • Body::getGroups() gibt a zurück std::bitset der Gruppen zurück, zu denen der Körper gehört.
  • Body::getGroupsToCheck()Gibt eine std::bitsetder Gruppen zurück, gegen die der Körper die Kollision überprüfen muss.

Körper können mehr als eine einzelne Zelle einnehmen. GridInfo speichert immer nicht im Besitz von Zeigern auf die belegten Zellen.


Nachdem sich ein einzelner Körper bewegt hat, findet eine Kollisionserkennung statt. Ich gehe davon aus, dass alle Körper achsenausgerichtete Begrenzungsrahmen sind.

So funktioniert die breitphasige Kollisionserkennung:

Teil 1: Geodaten-Update

Für jeden Body body:

    • Die Zellen, die ganz oben links belegt sind, und die Zellen, die ganz unten rechts belegt sind, werden berechnet.
    • Wenn sie sich von den vorherigen Zellen unterscheiden, body.gridInfo.cellswerden sie gelöscht und mit allen Zellen gefüllt, die der Körper einnimmt (2D für Schleife von der Zelle ganz oben links zur Zelle ganz unten rechts).
  1. body Jetzt wissen Sie garantiert, welche Zellen es belegt.

Teil 2: Aktuelle Kollisionsprüfungen

Für jeden Body body:

  • body.gridInfo.handleCollisions wird genannt:

void GridInfo::handleCollisions(float mFrameTime)
{
    static int paint{-1};
    ++paint;

    for(const auto& c : cells)
        for(const auto& b : c->getBodies())
        {
            if(b->paint == paint) continue;
            base.handleCollision(mFrameTime, b);
            b->paint = paint;
        }
}

void Body::handleCollision(float mFrameTime, Body* mBody)
    {
        if(mBody == this || !mustCheck(*mBody) || !shape.isOverlapping(mBody->getShape())) return;

        auto intersection(getMinIntersection(shape, mBody->getShape()));

        onDetection({*mBody, mFrameTime, mBody->getUserData(), intersection});
        mBody->onDetection({*this, mFrameTime, userData, -intersection});

        if(!resolve || mustIgnoreResolution(*mBody)) return;
        bodiesToResolve.push_back(mBody);
    }

  • Die Kollision wird dann für jeden Körper in aufgelöst bodiesToResolve.

  • Das ist es.


Deshalb versuche ich schon seit einiger Zeit, diese breitphasige Kollisionserkennung zu optimieren. Jedes Mal, wenn ich etwas anderes als die aktuelle Architektur / das aktuelle Setup ausprobiere, läuft etwas nicht wie geplant oder ich gehe von einer Simulation aus, die sich später als falsch herausstellt.

Meine Frage ist: Wie kann ich die breite Phase meines Kollisionsmotors optimieren ?

Gibt es eine Art magische C ++ - Optimierung, die hier angewendet werden kann?

Kann die Architektur umgestaltet werden, um mehr Leistung zu ermöglichen?


Callgrind-Ausgabe für die neueste Version: http://txtup.co/rLJgz

Vittorio Romeo
quelle
Profilieren und Erkennen von Engpässen. Lassen Sie uns wissen, wo sie sind, dann haben wir etwas zu arbeiten.
Maik Semder
@MaikSemder: Das habe ich gemacht und in der Post geschrieben. Es ist das einzige Code-Snippet, das den Engpass darstellt. Es tut mir leid, wenn es lang und detailliert ist, aber das ist ein Teil der Frage, da ich mir sicher bin, dass dieser Engpass nur durch eine Änderung des Designs des Motors behoben werden kann.
Vittorio Romeo
Sorry, war schwer zu finden. Können Sie uns Zahlen nennen? Die Funktionszeit und die Anzahl der Objekte, die in dieser Funktion verarbeitet wurden?
Maik Semder
@MaikSemder: mit Callgrind getestet, auf einem binären mit Clang 3.4 SVN - O3 zusammengestellt: 10000 dynamische Körper - die Funktion getBodiesToCheck()5.462.334 Mal aufgerufen wurde, und nahm 35,1% der gesamten Profilierungs Zeit (Instruction Lesezugriffszeit)
Vittorio Romeo
2
@Quonux: keine Beleidigung. Ich liebe es einfach, das Rad neu zu erfinden. Ich könnte Bullet oder Box2D nehmen und mit diesen Bibliotheken ein Spiel machen, aber das ist nicht wirklich mein Ziel. Ich fühle mich viel erfüllter und lerne viel mehr, indem ich Dinge von Grund auf neu erschaffe und versuche, die auftretenden Hindernisse zu überwinden - auch wenn das bedeutet, frustriert zu sein und um Hilfe zu bitten. Abgesehen von meiner Überzeugung, dass das Codieren von Grund auf für Lernzwecke von unschätzbarem Wert ist, finde ich es auch sehr unterhaltsam und eine große Freude, meine Freizeit damit zu verbringen.
Vittorio Romeo

Antworten:

14

getBodiesToCheck()

Bei der getBodiesToCheck()Funktion können zwei Probleme auftreten . zuerst:

if(!contains(bodiesToCheck, b)) bodiesToCheck.push_back(b);

Dieser Teil ist O (n 2 ), nicht wahr?

Anstatt zu überprüfen, ob der Körper bereits in der Liste enthalten ist, sollten Sie stattdessen malen .

loop_count++;
if(!loop_count) { // if loop_count can wrap,
    // you just need to iterate all bodies to reset it here
}
bodiesToCheck.clear();
for(const auto& q : queries)
    for(const auto& b : *q)
        if(b->paint != loop_count) {
            bodiesToCheck.push_back(b);
            b->paint = loop_count;
        }
return bodiesToCheck;

Sie dereferenzieren den Zeiger in der Erfassungsphase, aber Sie würden ihn trotzdem in der Testphase dereferenzieren. Wenn Sie also genug L1 haben, ist das keine große Sache. Sie können die Leistung verbessern, indem Sie dem Compiler auch Pre-Fetch-Hinweise hinzufügen __builtin_prefetch, obwohl dies mit klassischen for(int i=q->length; i-->0; )Schleifen und dergleichen einfacher ist .

Das ist eine einfache Änderung, aber mein zweiter Gedanke ist, dass es einen schnelleren Weg geben könnte, dies zu organisieren:

Sie können jedoch stattdessen Bitmaps verwenden und das Ganze vermeidenbodiesToCheck Vektor . Hier ist ein Ansatz:

Sie verwenden bereits ganzzahlige Schlüssel für Körper, suchen sie dann aber in Karten und Dingen nach und führen Listen mit ihnen. Sie können zu einem Slot-Allokator wechseln, bei dem es sich im Grunde nur um ein Array oder einen Vektor handelt. Z.B:

class TBodyImpl {
   public:
       virtual ~TBodyImpl() {}
       virtual void onHit(int other) {}
       virtual ....
       const int slot;
   protected:
      TBodyImpl(int slot): slot(slot_) {}
};

struct TBodyBase {
    enum ... type;
    ...
    rect_t rect;
    TQuadTreeNode *quadTreeNode; // see below
    TBodyImpl* imp; // often null
};

std::vector<TBodyBase> bodies; // not pointers to them

Dies bedeutet, dass alles, was für die eigentlichen Kollisionen benötigt wird, im linearen Cache-freundlichen Speicher abgelegt ist. Sie wechseln nur dann zum implementierungsspezifischen Bit und ordnen es einem dieser Slots zu, wenn dies erforderlich ist.

Um die Zuordnungen in diesem Vektor von Körpern zu verfolgen, können Sie ein Array von Ganzzahlen als Bitmap und Bit-Twiddling oder verwenden__builtin_ffs ähnliches verwenden. Dies ist besonders effizient, wenn Sie zu aktuell belegten Slots wechseln oder einen nicht belegten Slot im Array suchen. Sie können das Array manchmal sogar komprimieren, wenn es unangemessen groß wird und dann Lose als gelöscht markiert werden, indem Sie diese am Ende verschieben, um die Lücken zu füllen.

überprüfe nur einmal für jede Kollision

Wenn Sie geprüft haben, ob a mit b kollidiert , müssen Sie nicht prüfen, ob b mit b kollidiert a zu.

Aus der Verwendung von Integer-IDs folgt, dass Sie diese Überprüfungen mit einer einfachen if-Anweisung vermeiden. Wenn die ID einer möglichen Kollision kleiner oder gleich der aktuellen ID ist, auf die geprüft wird, kann sie übersprungen werden! Auf diese Weise überprüfen Sie jedes mögliche Pairing immer nur einmal. das ist mehr als die Hälfte der Kollisionsprüfungen.

unsigned * bitmap;
int bitmap_len;
...

for(int i=0; i<bitmap_len; i++) {
  unsigned mask = bitmap[i];
  while(mask) {
      const int j = __builtin_ffs(mask);
      const int slot = i*sizeof(unsigned)*8+j;
      for(int neighbour: get_neighbours(slot))
          if(neighbour > slot)
              check_for_collision(slot,neighbour);
      mask >>= j;
  }

respektieren Sie die Reihenfolge der Kollisionen

Anstatt eine Kollision zu bewerten, sobald ein Paar gefunden wurde, berechnen Sie die Entfernung, um sie zu treffen, und speichern Sie sie in einem binären Haufen . Bei diesen Heaps handelt es sich normalerweise um Prioritätswarteschlangen bei der Pfadfindung. Dies ist also ein sehr nützlicher Dienstprogrammcode.

Markieren Sie jeden Knoten mit einer Sequenznummer, damit Sie sagen können:

  • A 10 trifft B 12 um 6
  • A 10 trifft C 12 bei 3

Nachdem Sie alle Kollisionen gesammelt haben, werden sie offensichtlich aus der Prioritätswarteschlange entfernt, und zwar so bald wie möglich. Das erste, was Sie erhalten, ist A 10 Treffer C 12 bei 3. Sie erhöhen die Folgenummer jedes Objekts (das 10- Bit), bewerten die Kollision, berechnen ihre neuen Pfade und speichern ihre neuen Kollisionen in derselben Warteschlange. Die neue Kollision ist A 11 Treffer B 12 bei 7. Die Warteschlange hat jetzt:

  • A 10 Treffer B 12 um 6
  • A 11 trifft B 12 um 7

Dann knallen Sie aus der Prioritätswarteschlange und die A 10 Treffer B 12 auf 6. Aber Sie sehen , dass A 10 ist abgestanden ; A ist derzeit bei 11. Sie können diese Kollision also verwerfen.

Es ist wichtig, sich nicht die Mühe zu machen, alle veralteten Kollisionen aus dem Baum zu löschen. das Entfernen von einem Haufen ist teuer. Werfen Sie sie einfach weg, wenn Sie sie knallen lassen.

das Gitter

Sie sollten stattdessen einen Quadtree verwenden. Es ist eine sehr einfach zu implementierende Datenstruktur. Oft sieht man Implementierungen, die Punkte speichern, aber ich bevorzuge es, Rects zu speichern und das Element in dem Knoten zu speichern, der es enthält. Dies bedeutet, dass Sie zur Überprüfung von Kollisionen nur alle Körper durchlaufen müssen und diese für jeden Körper im selben Quad-Tree-Knoten (mit dem oben beschriebenen Sortiertrick) und alle in übergeordneten Quad-Tree-Knoten überprüfen müssen. Der Quad-Tree ist selbst die Liste der möglichen Kollisionen.

Hier ist ein einfacher Quadtree:

struct Object {
    Rect bounds;
    Point pos;
    Object * prev, * next;
    QuadTreeNode * parent;
};

struct QuadTreeNode {
    Rect bounds;
    Point centre;
    Object * staticObjects;
    Object * movableObjects;
    QuadTreeNode * parent; // null if root
    QuadTreeNode * children[4]; // null for unallocated children
};

Wir speichern die beweglichen Objekte separat, da wir nicht prüfen müssen, ob die statischen Objekte mit irgendetwas kollidieren.

Wir modellieren alle Objekte als achsenausgerichtete Begrenzungsrahmen (AABB) und fügen sie in den kleinsten QuadTreeNode ein, der sie enthält. Wenn ein QuadTreeNode viele Kinder hat, können Sie ihn weiter unterteilen (wenn sich diese Objekte gut auf die Kinder verteilen).

Bei jedem Spiel-Tick müssen Sie in den Quadtree zurückkehren und die Bewegung - und Kollisionen - jedes beweglichen Objekts berechnen. Es ist auf Kollisionen zu prüfen mit:

  • jedes statische Objekt in seinem Knoten
  • Jedes bewegliche Objekt in seinem Knoten, das sich in der Liste "bewegliche Objekte" vor ihm befindet (oder hinter ihm; wählen Sie einfach eine Richtung aus)
  • jedes bewegliche und statische Objekt in allen übergeordneten Knoten

Dies erzeugt alle möglichen ungeordneten Kollisionen. Dann machst du die Züge. Sie müssen diese Bewegungen nach Entfernung und "Wer bewegt sich zuerst" (was Ihre spezielle Anforderung ist) priorisieren und sie in dieser Reihenfolge ausführen. Verwenden Sie dazu einen Haufen.

Sie können diese Quadtree-Vorlage optimieren. Sie müssen die Grenzen und den Mittelpunkt nicht wirklich speichern. Das ist völlig ableitbar, wenn Sie den Baum gehen. Sie müssen nicht prüfen, ob sich ein Modell innerhalb der Grenzen befindet, sondern nur, auf welcher Seite es sich im Mittelpunkt befindet (ein "Achse der Trennung" -Test).

Um schnell fliegende Objekte wie Projektile zu modellieren, anstatt sie bei jedem Schritt zu bewegen oder eine separate Liste mit Kugeln zu haben, die Sie immer überprüfen, legen Sie sie einfach mit dem Flugstreifen für einige Spielschritte in den Quadtree. Das bedeutet, dass sie sich viel seltener im Quadtree bewegen, aber Sie überprüfen keine Kugeln gegen weit entfernte Wände, also ist es ein guter Kompromiss.

Große statische Objekte sollten in Einzelteile aufgeteilt werden. Bei einem großen Würfel sollte beispielsweise jedes Gesicht separat gespeichert werden.

Wille
quelle
"Malen" klingt gut, ich werde es versuchen und die Ergebnisse so schnell wie möglich melden. Ich verstehe den zweiten Teil Ihrer Antwort jedoch nicht - ich werde versuchen, etwas über das Vorabholen zu lesen.
Vittorio Romeo
Ich würde QuadTree nicht empfehlen, es ist komplizierter als das Erstellen eines Rasters. Wenn es nicht richtig ausgeführt wird, funktioniert es nicht richtig und es werden zu oft Knoten erstellt / entfernt.
ClickerMonkey
Über Ihren Haufen: Wird die Reihenfolge der Bewegung eingehalten? Betrachten Körper A und Körper B . A bewegt sich nach rechts in Richtung B und B und bewegt sich nach rechts in Richtung A. Nun - wenn sie gleichzeitig kollidieren, derjenige, der zuerst bewegt bekommen sollte zuerst gelöst , und der andere würde nicht betroffen.
Vittorio Romeo
@VittorioRomeo Wenn A sich in Richtung B bewegt und B sich in derselben Linie und mit derselben Geschwindigkeit in Richtung A bewegt, treffen sie sich dann in der Mitte? Oder trifft A, der sich zuerst bewegt, auf B, wo B beginnt?
Wird
1
@ Will youtube.com/watch?v=EExHVi8NMzA
Vittorio Romeo
3

Ich wette, Sie haben nur eine Menge Cache-Fehler, wenn Sie über die Körper iterieren. Bündeln Sie alle Ihre Körper mithilfe eines datenorientierten Entwurfsschemas? Mit einer N ^ 2-Breitphase kann ich Hunderte und Hunderte von Körpern ohne Framerate in den unteren Regionen (unter 60) simulieren , während ich mit Fraps aufnehme, und das alles ohne einen benutzerdefinierten Zuweiser. Stellen Sie sich vor, was mit der richtigen Cache-Nutzung erreicht werden kann.

Der Hinweis ist hier:

const std::vector<Body *>

Dies löst sofort eine große rote Fahne aus. Weisen Sie diesen Stellen neue Anrufe zu? Wird ein benutzerdefinierter Allokator verwendet? Es ist am wichtigsten, dass Sie alle Ihre Körper in einem riesigen Array haben, in dem Sie linear verlaufen . Wenn Sie den Speicher nicht linear durchlaufen möchten, sollten Sie stattdessen eine intrusiv verknüpfte Liste verwenden.

Außerdem scheinen Sie std :: map zu verwenden. Wissen Sie, wie der Speicher in std :: map belegt ist? Sie haben eine O (lg (N)) -Komplexität für jede Kartenabfrage, und diese kann mit einer Hash-Tabelle wahrscheinlich auf O (1) erhöht werden. Darüber hinaus wird der von std :: map zugewiesene Speicher auch Ihren Cache schrecklich überlasten.

Meine Lösung besteht darin, eine aufdringliche Hash-Tabelle anstelle von std :: map zu verwenden. Ein gutes Beispiel für sowohl aufdringlich verknüpfte Listen als auch aufdringliche Hash-Tabellen findet sich in Patrick Wyatts Basis innerhalb seines Coho-Projekts: https://github.com/webcoyote/coho

Kurz gesagt, Sie müssen wahrscheinlich einige benutzerdefinierte Tools für sich selbst erstellen, nämlich einen Allokator und einige aufdringliche Container. Dies ist das Beste, was ich tun kann, ohne den Code selbst zu profilieren.

RandyGaul
quelle
"Weisen Sie diesen Körpern rohe neue Anrufe zu?" Ich rufe nicht explizit an, newwenn ich Körper auf den getBodiesToCheckVektor drücke. Meinst du, das passiert intern? Gibt es eine Möglichkeit, dies zu verhindern, obwohl es immer noch eine dynamisch große Sammlung von Körpern gibt?
Vittorio Romeo
std::mapist kein Flaschenhals - ich erinnere mich auch daran, dass ich versucht habe dense_hash_set, keine Leistung zu erbringen.
Vittorio Romeo
@Vittorio, welcher Teil von getBodiesToCheck ist dann der Engpass? Wir brauchen Informationen, um zu helfen.
Maik Semder
@MaikSemder: Der Profiler geht nicht tiefer als die Funktion selbst. Die ganze Funktion ist der Engpass, weil sie einmal pro Frame und Body aufgerufen wird. 10000 Teilnehmer = 10000 getBodiesToCheckAnrufe pro Frame. Ich vermute, dass das ständige Reinigen / Einschieben des Vektors der Engpass der Funktion selbst ist. Die containsMethode ist auch Teil der Verlangsamung, aber da bodiesToChecknie mehr als 8-10 Körper darin sind, sollte es so langsam sein
Vittorio Romeo
@Vittorio wäre schön, wenn du diese Info in die Fragen steckst, das ist ein Game-Changer;) Insbesondere meine ich den Teil, den getBodiesToCheck für alle Körper aufruft , also 10000 mal jeden Frame. Ich frage mich, Sie sagten, sie seien in Gruppen, warum sollten Sie sie dann in das bodyToCheck-Array einfügen, wenn Sie bereits über die Gruppeninformationen verfügen? Sie könnten auf diesen Teil näher eingehen, scheint mir ein sehr guter Optimierungskandidat zu sein.
Maik Semder
1

Reduzieren Sie die Anzahl der Körper, um jeden Frame zu überprüfen:

Überprüfen Sie nur Körper, die sich tatsächlich bewegen können. Statische Objekte müssen nach der Erstellung nur einmal Ihren Kollisionszellen zugewiesen werden. Überprüfen Sie nun Kollisionen nur für Gruppen, die mindestens ein dynamisches Objekt enthalten. Dies sollte die Anzahl der Überprüfungen pro Frame verringern.

Verwenden Sie einen Quadtree. Siehe meine ausführliche Antwort hier

Entfernen Sie alle Zuordnungen aus Ihrem Physikcode. Möglicherweise möchten Sie hierfür einen Profiler verwenden. Aber ich habe nur die Speicherzuordnung in C # analysiert, daher kann ich nicht mit C ++ helfen.

Viel Glück!

Stephen
quelle
0

Ich sehe zwei Problemkandidaten in Ihrer Engpassfunktion:

Erstens ist "enthält" Teil - dies ist wahrscheinlich der Hauptgrund für den Engpass. Es durchläuft bereits gefundene Körper für jeden Körper. Vielleicht solltest du lieber eine Art hash_table / hash_map anstelle von vector verwenden. Dann sollte das Einfügen schneller sein (mit der Suche nach Dubletten). Aber ich kenne keine spezifischen Zahlen - ich habe keine Ahnung, wie viele Körper hier wiederholt werden.

Das zweite Problem könnte vector :: clear und push_back sein. Clear kann eine Neuzuweisung hervorrufen oder nicht. Aber vielleicht möchten Sie es vermeiden. Lösung könnte ein Flags-Array sein. Möglicherweise haben Sie jedoch viele Objekte. Daher ist es ineffektiv, eine Liste aller Objekte für jedes Objekt zu haben. Ein anderer Ansatz könnte nett sein, aber ich weiß nicht, welchen Ansatz: /

Zacharmarz
quelle
Zum ersten Problem: Ich habe versucht, anstelle des Vektors + contain ein dense_hash_set zu verwenden, und es war langsamer. Ich habe versucht, den Vektor zu füllen und dann alle Duplikate zu entfernen, und es war langsamer.
Vittorio Romeo
0

Hinweis: Ich kenne nichts von C ++, nur Java, aber Sie sollten in der Lage sein, den Code herauszufinden. Physik ist universelle Sprache, oder? Mir ist auch klar, dass dieser Beitrag ein Jahr alt ist, aber ich wollte ihn nur mit allen teilen.

Ich habe ein Beobachtermuster, das im Grunde genommen nach dem Verschieben des Objekts das Objekt zurückgibt, mit dem es kollidiert hat, einschließlich eines NULL-Objekts. Einfach gesagt:

( Ich mache Minecraft neu )

public Block collided(){
   return World.getBlock(getLocation());
}

Nehmen wir an, Sie irren in Ihrer Welt herum. wann immer du anrufst, rufst move(1)du ancollided() . Wenn Sie den gewünschten Block erhalten, fliegen möglicherweise Partikel und Sie können sich nach links, rechts und hinten bewegen, aber nicht nach vorne.

Verwenden Sie dies allgemeiner als nur Minecraft als Beispiel:

public Object collided(){
   return threeDarray[3][2][3];
}

Stellen Sie einfach ein Array bereit, um die Koordinaten zu kennzeichnen, die, wie Java es tut, Zeiger verwenden.

Die Verwendung dieser Methode erfordert immer noch etwas anderes als a priori Kollisionserkennungsmethode. Sie könnten dies als Schleife ausführen, aber das macht den Zweck zunichte. Sie können dies auf Broad-, Mid- und Narrow-Collision-Techniken anwenden, aber alleine ist es ein Biest, besonders wenn es für 3D- und 2D-Spiele recht gut funktioniert.

Wenn ich jetzt noch einen Blick darauf wirft, bedeutet dies, dass ich gemäß meiner minecraft collide () -Methode im Block lande und den Spieler daher außerhalb des Blocks bewegen muss. Anstatt den Player zu überprüfen, muss ein Begrenzungsrahmen hinzugefügt werden, der überprüft, welcher Block auf jede Seite des Rahmens trifft. Problem gelöst.

Der obige Absatz ist mit Polygonen möglicherweise nicht so einfach, wenn Sie Genauigkeit wünschen. Aus Gründen der Genauigkeit würde ich vorschlagen, einen Polygon-Begrenzungsrahmen zu definieren, der kein Quadrat, aber kein Tesselat ist. Wenn nicht, ist ein Rechteck in Ordnung.

AMDG
quelle