Verbessern einer O (N ^ 2) -Funktion (alle Entitäten, die über alle anderen Entitäten iterieren)

21

Ein wenig Hintergrund, ich bin Codierung eine Evolution Spiel mit einem Freund in C ++, ENTT für das Entity - System. Kreaturen bewegen sich in einer 2D-Karte, fressen Greens oder andere Kreaturen, vermehren sich und ihre Eigenschaften mutieren.

Darüber hinaus ist die Leistung in Ordnung (60fps kein Problem), wenn das Spiel in Echtzeit ausgeführt wird, aber ich möchte es deutlich beschleunigen können, damit ich nicht 4 Stunden warten muss, um signifikante Änderungen zu sehen. Also möchte ich es so schnell wie möglich bekommen.

Ich kämpfe darum, eine effiziente Methode zu finden, mit der Kreaturen ihre Nahrung finden können. Jede Kreatur soll nach dem besten Futter suchen, das ihnen nahe genug ist.

Beispiel-Screenshot des Spiels

Wenn es essen will, soll sich die in der Mitte abgebildete Kreatur in einem Radius von 149,64 (Blickentfernung) umsehen und beurteilen, welche Nahrung es verfolgen soll, basierend auf Ernährung, Entfernung und Art (Fleisch oder Pflanze). .

Die Funktion, die dafür verantwortlich ist, jedes Lebewesen zu finden, verbraucht ungefähr 70% der Laufzeit. Vereinfacht gesagt, sieht es so aus:

for (creature : all_creatures)
{
  for (food : all_entities_with_food_value)
  {
    // if the food is within the creatures view and it's
    // the best food found yet, it becomes the best food
  }
  // set the best food as the target for creature
  // make the creature chase it (change its state)
}

Diese Funktion wird bei jedem Tick für jede Kreatur ausgeführt, die nach Nahrung sucht, bis die Kreatur Nahrung findet und ihren Zustand ändert. Es wird auch jedes Mal ausgeführt, wenn neue Lebensmittel für Kreaturen auftauchen, die bereits ein bestimmtes Lebensmittel jagen, um sicherzustellen, dass jeder das beste Lebensmittel sucht, das ihm zur Verfügung steht.

Ich bin offen für Ideen, wie dieser Prozess effizienter gestaltet werden kann. Ich würde gerne die Komplexität von O(N2) reduzieren , aber ich weiß nicht, ob das überhaupt möglich ist.

Eine Möglichkeit, die ich bereits verbessert habe, besteht darin, die all_entities_with_food_valueGruppe so zu sortieren , dass eine Kreatur, die über Lebensmittel iteriert, die zu groß sind, um sie zu fressen, dort anhält. Alle anderen Verbesserungen sind mehr als willkommen!

EDIT: Vielen Dank für die Antworten! Ich habe verschiedene Dinge aus verschiedenen Antworten implementiert:

Ich habe es erstens einfach so gemacht, dass die Schuldfunktion nur einmal alle fünf Ticks ausgeführt wird. Dies hat das Spiel um das Vierfache beschleunigt, ohne dass sich etwas an dem Spiel sichtbar verändert hat.

Danach habe ich im Nahrungsmittelsuchsystem ein Array mit der Nahrung gespeichert, die im selben Häkchen erzeugt wurde, wie es ausgeführt wird. Auf diese Weise muss ich nur die Nahrung, die die Kreatur jagt, mit den neuen Nahrungsmitteln vergleichen, die aufgetaucht sind.

Nachdem ich mich mit Raumteilung befasst und BVH und Quadtree in Betracht gezogen hatte, habe ich mich für Letzteres entschieden, da ich der Meinung bin, dass dies viel einfacher und besser für meinen Fall geeignet ist. Ich implementiere es ziemlich schnell und es hat die Leistung erheblich verbessert, die Nahrungssuche dauert kaum irgendwann!

Das Rendern verlangsamt mich, aber das ist ein Problem für einen anderen Tag. Danke euch allen!

Alexandre Rodrigues
quelle
2
Haben Sie mit mehreren Threads auf mehreren gleichzeitig laufenden CPU-Kernen experimentiert?
Ed Marty
6
Wie viele Kreaturen hast du im Durchschnitt? Dem Schnappschuss nach zu urteilen, scheint es nicht so hoch zu sein. Wenn dies immer der Fall ist, hilft die Raumaufteilung nicht viel. Haben Sie darüber nachgedacht nicht bei jedem Tick läuft diese Funktion? Sie könnten es alle 10 Ticks ausführen. Die Ergebnisse der Simulation sollten sich qualitativ nicht ändern.
Turms
4
Haben Sie ein detailliertes Profil erstellt, um den kostspieligsten Teil der Lebensmittelbewertung herauszufinden? Anstatt die Gesamtkomplexität zu betrachten, müssen Sie möglicherweise feststellen, ob Sie durch bestimmte Berechnungen oder Speicherstrukturzugriffe beeinträchtigt werden.
Harabeck
Ein naiver Vorschlag: Sie könnten einen Quadtree oder eine verwandte Datenstruktur anstelle des O (N ^ 2) verwenden, wie Sie es jetzt tun.
Seiyria
3
Wie @ Harabeck vorschlug, würde ich tiefer gehen, um zu sehen, wo in der Schleife die ganze Zeit verbracht wird. Wenn es sich beispielsweise um Quadratwurzelberechnungen für die Entfernung handelt, können Sie möglicherweise zuerst die XY-Koordinaten vergleichen, um viele Kandidaten zu eliminieren, bevor Sie die teuren Quadratwurzelberechnungen für die verbleibenden durchführen müssen. Das Hinzufügen if (food.x>creature.x+149.64 or food.x<creature.x-149.64) continue;sollte einfacher sein als das Implementieren einer "komplizierten" Speicherstruktur, WENN sie performant genug ist. (Siehe auch: Es könnte uns helfen, wenn Sie etwas mehr Code in Ihrer inneren Schleife veröffentlichen.)
AC

Antworten:

34

Ich weiß, dass Sie dies nicht als Kollisionen auffassen, aber Sie kollidieren mit allen Nahrungsmitteln mit einem Kreis, der um die Kreatur zentriert ist.

Sie möchten wirklich nicht überprüfen, ob Lebensmittel entfernt sind, sondern nur, was sich in der Nähe befindet. Das ist der allgemeine Rat für die Kollisionsoptimierung. Ich möchte dazu ermutigen, nach Techniken zur Optimierung von Kollisionen zu suchen und mich bei der Suche nicht auf C ++ zu beschränken.


Kreatur, die Nahrung findet

Für Ihr Szenario würde ich vorschlagen, die Welt in ein Raster zu setzen. Stellen Sie die Zellen mindestens auf den Radius der Kreise ein, die Sie kollidieren möchten. Dann kannst du die eine Zelle auswählen, in der sich die Kreatur befindet, sowie die bis zu acht Nachbarn und nur die bis zu neun Zellen durchsuchen.

Hinweis : Sie könnten kleinere Zellen erstellen. Dies würde bedeuten, dass sich der gesuchte Kreis über die unmittelbaren Nachbarn hinaus erstreckt und Sie dort iterieren müssen. Wenn das Problem jedoch darin besteht, dass zu viel Nahrung vorhanden ist, können kleinere Zellen bedeuten, dass insgesamt weniger Nahrungsbestandteile durchlaufen werden, was sich zu Ihren Gunsten auswirkt. Wenn Sie vermuten, dass dies der Fall ist, testen Sie.

Wenn sich das Lebensmittel nicht bewegt, können Sie die Lebensmittelentitäten beim Erstellen zum Raster hinzufügen, sodass Sie nicht nach den Entitäten in der Zelle suchen müssen. Stattdessen fragen Sie die Zelle ab und sie enthält die Liste.

Wenn Sie die Größe der Zellen zu einer Zweierpotenz machen, können Sie die Zelle, in der sich die Kreatur befindet, einfach durch Abschneiden ihrer Koordinaten ermitteln.

Sie können beim Vergleichen mit der quadratischen Distanz arbeiten (auch bekannt als "Nicht ausführen"), um die nächstgelegene zu finden. Weniger sqrt-Vorgänge bedeuten eine schnellere Ausführung.


Neues Essen hinzugefügt

Wenn neues Futter hinzugefügt wird, müssen nur Kreaturen in der Nähe geweckt werden. Es ist die gleiche Idee, außer dass Sie jetzt stattdessen die Liste der Kreaturen in den Zellen abrufen müssen.

Umso interessanter ist es, wenn Sie in der Kreatur vermerken, wie weit es von dem Essen entfernt ist, das sie jagt ... Sie können direkt anhand dieser Entfernung prüfen.

Eine andere Sache, die Ihnen helfen wird, ist, dem Essen bewusst zu machen, welche Kreaturen es jagen. Auf diese Weise können Sie den Code für die Suche nach Nahrung für alle Kreaturen ausführen, die ein Stück Lebensmittel jagen, das gerade gegessen wurde.

Starten Sie die Simulation in der Tat ohne Futter, und alle Kreaturen haben eine annotierte Entfernung von unendlich. Beginnen Sie dann mit dem Hinzufügen von Lebensmitteln. Aktualisiere die Entfernungen, während sich die Kreaturen bewegen ... Wenn Essen gegessen wird, nimm die Liste der Kreaturen, die es gejagt haben, und finde dann ein neues Ziel. Abgesehen von diesem Fall werden alle anderen Aktualisierungen behandelt, wenn Lebensmittel hinzugefügt werden.


Simulation überspringen

Wenn du die Geschwindigkeit einer Kreatur kennst, weißt du, wie viel es ist, bis es sein Ziel erreicht. Wenn alle Kreaturen die gleiche Geschwindigkeit haben, ist diejenige mit der geringsten kommentierten Entfernung diejenige, die zuerst erreicht wird.

Wenn Sie auch die Zeit kennen, bis Sie mehr Nahrung hinzufügen ... Und hoffentlich haben Sie eine ähnliche Vorhersehbarkeit für Fortpflanzung und Tod, dann kennen Sie die Zeit bis zum nächsten Ereignis (entweder wenn Sie Nahrung hinzugefügt haben oder wenn eine Kreatur frisst).

Springe zu diesem Moment. Sie müssen keine Kreaturen simulieren, die sich bewegen.

Theraot
quelle
1
"und nur dort suchen." und die Zellen in unmittelbarer Nachbarschaft - dh insgesamt 9 Zellen. Warum 9? Denn was ist, wenn sich die Kreatur genau in der Ecke einer Zelle befindet?
UKMonkey
1
@UKMonkey "Mache die Zellen mindestens zum Radius der Kreise, die du kollidieren möchtest", wenn die Zellenseite der Radius ist und die Kreatur in der Ecke ist ... naja, ich nehme an, du musst in diesem Fall nur vier suchen. Natürlich können wir die Zellen verkleinern, was nützlich sein könnte, wenn zu viel Futter und zu wenig Lebewesen vorhanden sind. Bearbeiten: Ich werde klären.
Theraot
2
Sicher - wenn Sie herausfinden möchten, ob Sie in zusätzlichen Zellen suchen müssen ... aber angesichts der Tatsache, dass die meisten Zellen kein Essen haben (nach dem angegebenen Bild); Es ist schneller, nur 9 Zellen zu durchsuchen, als herauszufinden, welche 4 Sie durchsuchen müssen.
UKMonkey
@ UKMonkey weshalb ich das anfangs nicht erwähnt habe.
Theraot
16

Sie sollten einen Space-Partitioning-Algorithmus wie BVH verwenden , um die Komplexität zu verringern. Um für Ihren Fall spezifisch zu sein, müssen Sie einen Baum erstellen, der aus achsengerichteten Begrenzungsrahmen besteht, die Lebensmittelstücke enthalten.

Um eine Hierarchie zu erstellen, platzieren Sie Lebensmittelstücke in AABBs nahe beieinander, und platzieren Sie diese AABBs dann in größeren AABBs, wiederum um den Abstand zwischen ihnen. Tun Sie dies, bis Sie einen Wurzelknoten haben.

Um den Baum zu nutzen, führen Sie zuerst einen Kreis-AABB-Schnittpunkttest gegen einen Wurzelknoten durch. Wenn eine Kollision auftritt, testen Sie gegen Kinder jedes aufeinanderfolgenden Knotens. Am Ende solltest du eine Gruppe von Essensstücken haben.

Sie können auch die Bibliothek AABB.cc verwenden.

Ozelot
quelle
1
Dies würde zwar die Komplexität auf N log N reduzieren, aber es wäre auch kostspielig, die Partitionierung durchzuführen. Da ich jeden Tick partitionieren müsste (da die Kreaturen jeden Tick verschieben), wäre es das trotzdem wert? Gibt es Lösungen, mit denen Sie seltener partitionieren können?
Alexandre Rodrigues
3
@AlexandreRodrigues Sie müssen nicht jeden Tick den gesamten Baum neu erstellen, sondern nur Teile aktualisieren, die sich bewegen, und nur dann, wenn sich etwas außerhalb eines bestimmten AABB-Containers befindet. Um die Leistung weiter zu verbessern, möchten Sie möglicherweise Knoten reduzieren (wobei ein gewisser Abstand zwischen den untergeordneten Knoten verbleibt), damit Sie bei einer Blattaktualisierung nicht den gesamten Zweig neu erstellen müssen.
Ocelot
6
Ich denke, ein BVH könnte hier zu komplex sein - ein einheitliches Raster, das als Hash-Tabelle implementiert ist, ist gut genug.
Steven
1
@Steven Durch die Implementierung von BVH können Sie den Maßstab der Simulation in Zukunft problemlos erweitern. Und Sie verlieren nichts wirklich, wenn Sie es für eine kleine Simulation auch tun.
Ocelot
2

Während die beschriebenen Raumpartitionsmethoden tatsächlich die Zeit reduzieren können, besteht Ihr Hauptproblem nicht nur in der Suche. Es ist die Menge an Suchanfragen, die Sie durchführen und die Ihre Aufgabe verlangsamt. Sie optimieren also die innere Schleife, können aber auch die äußere Schleife optimieren.

Ihr Problem ist, dass Sie weiterhin Daten abrufen. Es ist ein bisschen so, als würden Kinder zum tausendsten Mal auf dem Rücksitz nachfragen "Sind wir schon da?". Sie müssen also nicht tun, dass der Fahrer Sie benachrichtigt, wenn Sie dort sind.

Stattdessen sollten Sie sich bemühen, wenn möglich, jede Aktion bis zu ihrem Abschluss zu lösen, sie in eine Warteschlange zu stellen und diese Blasenereignisse herauszulassen. Dies kann Änderungen an der Warteschlange vornehmen, aber das ist in Ordnung. Dies wird als diskrete Ereignissimulation bezeichnet. Wenn Sie Ihre Simulation auf diese Weise implementieren können, suchen Sie nach einer beträchtlichen Geschwindigkeitssteigerung, die die Geschwindigkeitssteigerung, die Sie durch die bessere Suche nach Raumpartitionen erzielen können, bei weitem übertrifft.

Um den Punkt in einer früheren Karriere zu unterstreichen, habe ich Fabriksimulatoren gemacht. Mit dieser Methode simulierten wir wochenlang große Fabriken / Flughäfen mit einem gesamten Materialfluss auf jeder Artikelebene in weniger als einer Stunde. Während die zeitschrittbasierte Simulation nur 4-5 mal schneller als in Echtzeit simulieren konnte.

Auch als sehr niedrig hängende Frucht sollten Sie erwägen, Ihre Zeichenroutinen von Ihrer Simulation zu entkoppeln. Auch wenn Ihre Simulation einfach ist, ist der Aufwand für das Zeichnen immer noch gering. Schlimmer noch, der Bildschirmtreiber beschränkt Sie möglicherweise auf x Aktualisierungen pro Sekunde, während Ihre Prozessoren in Wirklichkeit die Dinge hundertmal schneller erledigen könnten. Dies unterstreicht die Notwendigkeit einer Profilerstellung.

joojaa
quelle
@Theraot wissen wir nicht, wie die Zeichnung Dinge strukturiert sind. Aber ja, Drawcalls werden zu Engpässen, wenn Sie sowieso schnell genug sind
joojaa
1

Sie können einen Sweep-Line-Algorithmus verwenden, um die Komplexität auf Nlog (N) zu reduzieren. Die Theorie ist die von Voronoi-Diagrammen, bei denen die Umgebung einer Kreatur in Regionen unterteilt wird, die aus allen Punkten bestehen, die dieser Kreatur näher sind als alle anderen.

Der sogenannte Fortune-Algorithmus erledigt das für Sie in Nlog (N), und die Wiki-Seite darauf enthält Pseudocode, um es zu implementieren. Ich bin sicher, dass es auch Bibliotheksimplementierungen gibt. https://en.wikipedia.org/wiki/Fortune%27s_algorithm

Nabla
quelle
Willkommen bei GDSE und vielen Dank für Ihre Antwort. Wie genau würden Sie dies auf die Situation von OP anwenden? Die Problembeschreibung besagt, dass ein Unternehmen alle Lebensmittel innerhalb seiner Sichtweite berücksichtigen und das beste auswählen sollte. Ein traditioneller Voronoi würde Lebensmittel ausschließen, die näher an einer anderen Entität waren. Ich sage nicht, dass ein Voronoi nicht funktionieren würde, aber es ist aus Ihrer Beschreibung nicht ersichtlich, wie OP einen für das beschriebene Problem verwenden sollte.
Pikalek
Mir gefällt diese Idee, ich würde sie gerne erweitert sehen. Wie stellen Sie das Voronoi-Diagramm dar (wie in der Speicherdatenstruktur)? Wie fragen Sie es ab?
Theraot
@Theraot Sie brauchen nicht das Voronoi-Diagramm nur die gleiche Sweepline-Idee.
Joojaa
-2

Die einfachste Lösung wäre, eine Physik-Engine zu integrieren und nur den Kollisionserkennungsalgorithmus zu verwenden. Bauen Sie einfach einen Kreis / eine Kugel um jedes Objekt und lassen Sie die Physik-Engine die Kollisionen berechnen. Für 2D würde ich Box2D oder Chipmunk und Bullet für 3D vorschlagen .

Wenn Sie der Meinung sind, dass die Integration einer ganzen Physik-Engine zu viel ist, würde ich vorschlagen, die spezifischen Kollisionsalgorithmen zu untersuchen. Die meisten Kollisionserkennungsbibliotheken arbeiten in zwei Schritten:

  • Breite Phasendetektion: Das Ziel dieser Phase ist es, die Liste der möglichen Objektpaare, die kollidieren können, so schnell wie möglich zu erhalten. Zwei gebräuchliche Optionen sind:
    • Sweepen und Beschneiden : Sortieren Sie die Begrenzungsrahmen entlang der X-Achse und markieren Sie das Objektpaar, das sich schneidet. Wiederholen Sie dies für jede andere Achse. Wenn ein Kandidatenpaar alle Tests besteht, geht es zur nächsten Stufe. Dieser Algorithmus kann die zeitliche Kohärenz sehr gut ausnutzen: Sie können die Listen der sortierten Entitäten behalten und sie bei jedem Frame aktualisieren, aber da sie fast sortiert sind, ist dies sehr schnell. Außerdem wird die räumliche Kohärenz ausgenutzt: Da Objekte in aufsteigender räumlicher Reihenfolge sortiert sind, können Sie beim Überprüfen auf Kollisionen anhalten, sobald ein Objekt nicht kollidiert, da alle nächsten Objekte weiter entfernt sind.
    • Räumliche Partitionierung von Datenstrukturen wie Quadtrees, Octrees und Grids. Gitter sind einfach zu implementieren, können jedoch sehr verschwenderisch sein, wenn die Entitätsdichte niedrig und für unbegrenzten Raum sehr schwierig zu implementieren ist. Statische räumliche Bäume sind ebenfalls einfach zu implementieren, aber schwierig zu balancieren oder zu aktualisieren, sodass Sie sie für jeden Frame neu erstellen müssten.
  • Enge Phase: Kandidatenpaare, die in der breiten Phase gefunden wurden, werden mit genaueren Algorithmen weiter getestet.
José Franco Campos
quelle