Wie kann ich eine 2D-Bitmap (für Gelände verwendet) zur Kollision in ein 2D-Polygonnetz konvertieren?

7

Also mache ich ein Artillerie-Spiel, ähnlich wie Worms, mit all den üblichen Dingen wie zerstörbarem Gelände usw. ... und während ich eine Kollision pro Pixel verwenden könnte, die mir keine Kollisionsnormalen oder ähnliches gibt. Das Konvertieren in ein Netz würde auch bedeuten, dass ich eine vorhandene Physikbibliothek verwenden könnte, die besser wäre als alles, was ich selbst machen kann.

Ich habe Leute gesehen, die dies erwähnt haben, indem sie Marching Squares verwendet haben, um Konturen in der Bitmap zu erhalten, aber ich kann nichts finden, das erwähnt, wie diese in ein Netz umgewandelt werden können (es sei denn, es bezieht sich auf ein 3D-Netz mit Konturlinien, die unterschiedliche Höhen definieren). das ist NICHT was ich will). Im Moment kann ich eine grundlegende Kontur für Marschquadrate erhalten, die ungefähr so ​​aussieht (wobei die gitterartigen Linien im Hintergrund die Zellen der Marschquadrate wären):

Marching Squares Ergebnis

Das muss interpoliert werden, um ein glatteres und genaueres Ergebnis zu erzielen, aber das ist die allgemeine Idee. Ich hatte ein paar Ideen, wie ich daraus ein Netz machen könnte, aber viele davon würden in bestimmten Fällen nicht funktionieren, und die, von der ich dachte, dass sie perfekt funktionieren würde, hat sich als sehr langsam herausgestellt und ich habe sie noch nicht einmal fertiggestellt noch! Idealerweise möchte ich, dass alles, was ich am Ende benutze, schnell genug ist, um jeden Frame für Fälle wie schnell schießende Waffen oder Grabwerkzeuge zu erstellen.

Ich denke, es muss eine Art Algorithmus / Technik geben, um so etwas in ein Netz zu verwandeln, aber ich kann anscheinend nichts finden. Ich habe mir einige Dinge wie die Delaunay-Triangulation angesehen, aber soweit ich das beurteilen kann, werden konkave Formen wie im obigen Beispiel nicht richtig behandelt und auch keine Löcher im Gelände berücksichtigt.

Ich werde die Technik, die ich mir zum Vergleich ausgedacht habe, durchgehen und ich werde sehen, ob jemand eine bessere Idee hat. Interpolieren Sie zunächst die Konturlinien der Marching Squares, erstellen Sie Scheitelpunkte an den Linienenden und erhalten Sie Scheitelpunkte, an denen Linien die Zellkanten kreuzen (wichtig). Erstellen Sie dann für jede Zelle, die Scheitelpunkte enthält, Polygone, indem Sie 2 Scheitelpunkte und eine Zellecke als 3. Scheitelpunkt verwenden (wahrscheinlich die nächstgelegene Ecke).

Geben Sie hier die Bildbeschreibung ein

Tun Sie dies für jede Zelle und ich denke, Sie sollten ein Netz haben, das die ursprüngliche Bitmap genau darstellt (obwohl es nur Polygone an den Rändern der Bitmap gibt und große ausgefüllte Bereiche dazwischen leer sind). Das einzige Problem dabei ist, dass jedes Pixel für die ersten Marschquadrate einmal durchlaufen wird und dann mindestens zweimal jede Zelle (Bildhöhe + 1 x Bildbreite + 1) durchlaufen wird, was für jede anständige Größe sehr langsam ist Bild...

Megadanxzero
quelle
1
"Das gibt mir keine Kollisionsnormalen oder ähnliches." Sagt wer? Sie können die Pixel in der Nähe überprüfen und eine normale Kollision erzeugen. Tatsächlich können Sie bei Bedarf Marschwürfel verwenden, um genau dies zu tun. Keine Notwendigkeit für ein Netz; du brauchst nur einen normalen, oder?
Nicol Bolas
Oh ja, ich habe schon etwas Ähnliches gemacht, aber es ist nicht großartig. Ich meine, es funktioniert ziemlich gut, aber definitiv nicht perfekt. Die Verwendung von Marching Squares auf einem kleinen Bereich um den Kollisionspunkt wäre wahrscheinlich eine etwas bessere Lösung als meine vorherige, aber ich kann immer noch Probleme damit sehen. Zum Beispiel führt ein zu kleiner Probenbereich zu einer ungenauen Normalen, weil Sie Details vermissen, während ein zu großer Bereich bedeutet, dass Sie wahrscheinlich den Winkel der Kanten mitteln müssen, die Sie erhalten (was wiederum ungenau sein könnte).
Megadanxzero
Und das ignoriert natürlich die Tatsache, dass ich dann immer noch meine eigene Physik erstellen müsste, was wahrscheinlich nicht sehr gut werden würde, anstatt nur eine vorhandene robuste Physik-Engine zu verwenden. Ich kenne keine Physik-Engines, mit denen Sie die Kollisionserkennung mit Ihrem eigenen Pro-Pixel-Material überschreiben und dann einfach eine normale Kollision geben können, auf die Sie reagieren können. Könnte aber sein, dass so etwas existiert.
Megadanxzero
Wie genau brauchen Sie einen Normalen? Du machst ein Spiel im Stil von Scorched Earth / Worms. Ich denke, deine Spieler werden dir vergeben, wenn der Sprung nicht perfekt ist. Ich meine, denkst du, dass die alte DOS Scorched Earth hochpräzise Netze gebaut hat und so weiter? Denken Sie, dass selbst moderne Worms-Spiele große Anstrengungen unternehmen, um dieses Zeug zu berechnen?
Nicol Bolas
1
Der "Physik" -Teil eines Physiksystems ( insbesondere in 2D) ist der einfachste Teil. Es ist der Teil "Kollision", der schwierig ist.
Nicol Bolas

Antworten:

2

Ich habe noch nie mit 2D-Physik-Engines gearbeitet, ich bin mir nicht sicher, wie das Kollisionsnetz genau aussehen soll.

Wenn es sich lediglich um eine Reihe von 2D-Dreiecken handelt, sollten Sie sich mit Triangulationsmethoden befassen. Zum Beispiel eingeschränkte Delauney-Triangulation .

Delaunay-Triangulationen maximieren den minimalen Winkel aller Winkel der Dreiecke in der Triangulation. Sie neigen dazu, dünne Dreiecke zu vermeiden.

Das ist eine gute Sache, wenn es darum geht, diese Dreiecke zumindest zu rendern, und kann auch für die Kollisionserkennung gut sein oder auch nicht.

Eine eingeschränkte Delauny-Triangulation enthält feste Kanten, die Ihre erkannten Kanten wären. Diese Bibliothek bietet möglicherweise das, was Sie benötigen


quelle
Aha, ich hatte noch nie von Constrained Delaunay Triangulation gehört, das scheint genau das zu sein, was ich brauche. Ich muss mich auf jeden Fall darum kümmern. Vielen Dank!
Megadanxzero