Tiny Ore Diver

[TomasRiker]

Ich sehe das größere Problem ehrlich gesagt in den Normalen / Tangenten. Die Bitmap ist ja nicht die Geometrie, sondern ein niedrigaufgelöstes Sampling der Geometrie. Betrachtet man die Bitmap als echte Geometrie aus Blöcken dann gibt es nur perfekt senkrechte und perfekt waagerechte Linien, keine Schrägen. Natürlich kann man diese Treppen mit Kugeln kollidieren lassen, aber das Verhalten wird vermutlich nicht das sein, was man erwartet.

Da könnte man eine 2D-Version von "Marching Cubes" implementieren. Marching Squares?

[Schrompf]

Ja, heißt Marching Squares, und jetzt klingt ihr mit Euren Bedenken exakt wie der Box2D-Discord, der meine Fragen gar nicht erst zur Kenntnis genommen hat, sondern gleich meinte, ich solle es sein lassen.

Was die Kontaktnormalen angeht, wollte ich das wie bei meinem Survival-Voxel-Spiel damals machen: die 5x5-Umgebung zu ner Normale verwursten. Ich mach aber erstmal Kugel vs. Bitmap, und da hast Du ganz bequem die Kugel-Richtung als Normale. Für Kugeln >> 1px Radius wird das schon ordentlich funktionieren. Kritisch wird's später bei Bitmap vs. Bitmap - da kann man sich Grenzfälle ausdenken, wo jede Heuristik scheitert. Aber erstmal soweit sein und dann sehen wir weiter.

[Jonathan]

Da könnte man eine 2D-Version von "Marching Cubes" implementieren. Marching Squares?

Aber Marching Cubes hat doch als Eingabe ein Signed Distance Field, und das gibts hier doch nicht, oder?

Ich mach aber erstmal Kugel vs. Bitmap, und da hast Du ganz bequem die Kugel-Richtung als Normale. Für Kugeln >> 1px Radius wird das schon ordentlich funktionieren.

Ich bin da skeptisch. Habs mal eben aufgemalt:

Nicht exakt gezeichnet, aber die selbe Kugel triff immer die selbe Ecke von dem mittleren 2-er Steinchen zuerst. Ich nehme an, das meintest du - Kugel mit exakten Quadraten kollidieren lassen und dann annehmen, dass die Berührungsebene tangential zur Kugel liegt.
Für den selben Kontaktpunkt kannst du jetzt aber sehr unterschiedliche Richtungen rausbekommen, nämlich alles zwischen den zwei roten Linien. Das ist dann doch arg ungenau. In "Wirklichkeit" approximieren die grünen Quadrate aber die blau Linie, wie man sieht ist die korrekte Normale also ungefähr zwischen den zwei maximalen.

Hier wird es jetzt philosophisch, ob die grüne oder die blaue Geometrie die wahre ist. Die meisten Spieler werden aber intuitiv von der blauen ausgehen, nicht von der grünen. Wenn du hundert Bälle gegen diese grüne Wand prallen lässt, springt jeder in eine andere Richtung, auch wenn die Wand "glatt" ist.

Was die Kontaktnormalen angeht, wollte ich das wie bei meinem Survival-Voxel-Spiel damals machen: die 5x5-Umgebung zu ner Normale verwursten.

Das ist, denke ich, die richtige Lösung. Lokal an die Geometrie eine kontinuierliche Funktion fitten, deren Normale man dann an der Kontaktstelle exakt berechnen kann. So kannst du auch für Runde Objekte sehr glatte (im Sinne von differenzierbare) Normalen bekommen, und nicht nur Stückweis-Lineare Funktionen, bei denen die Normalen dann plötzlich springen, wenn man ein kleines bisschen anders aufkommt.

[TomasRiker]

Da könnte man eine 2D-Version von "Marching Cubes" implementieren. Marching Squares?

Aber Marching Cubes hat doch als Eingabe ein Signed Distance Field, und das gibts hier doch nicht, oder?

Ja, stimmt. Ist nicht genau das gleiche. Die Idee dahinter wäre ähnlich. Man guckt sich an, welche der 4 Eckpunkte eines Quadrats 1 bzw. 0 sind, und erzeugt dann entsprechend Kanten.

[Schrompf]

Marching Cubes war auch der Vorschlag der Box2D-Community, und nach meinem Wissen macht z.B. Noita das so. Anekdote am Rande: xq hatte mir erzählt, dass die jetzt ihr "FallingEverything"-Engine zur Lizenzierung anbieten. Ich hatte lange mit mir gerungen, ob ich das überhaupt will, aber bevor ich dann überhaupt mit Box2D und dem Kollisionsthema anfing, sendete ich ihnen doch erstmal ne Mail. Immerhin haben die ja all diese Probleme schon gelöst, nämlich mit Marching Squares und Konvex-Zerlegung, wie in dem dort verlinkten Video auch erklärt.

Leider haben sie nie geantwortet. Ist jetzt drei Wochen her oder so, da kommt also wohl nix mehr. Also hab ich selbst angefangen. Und bevor ich 64x pro Sekunde Marching Squares und Konkavkrieg betreibe, wollte ich doch erstmal gucken, ob ich nicht auch Pixel-Kollision in Box2D reingepatcht kriege. Würde ja reichen, wenn ich nur die bewegten Trümmerteile marchen und konvex zerlegen müsste.

[Chromanoid]

Clonk hat das ganze glaube ich mit wenigen "Testpixeln" gelöst. Die sind dann die Eckpunkte der Gefährte. Das spielt vor allem bei den Loren eine Rolle. Es kann dabei natürlich passieren, dass man den Loren auf einen "Erdspieß" schiebt und die Testpixel links und rechts vom Erdspieß hängen. Dadurch dass Clonk von einem frickeligen Spielgefühl lebt, hat mich das nie gestört. Ich glaube bei den Ubooten in Clonk gibt es mindestens drei Testpunkte. Vielleicht reicht das ja? Ich bin mir allerdings nicht sicher, wie die auf der Basis eine Normale zum schieben der Objekte berechnen. Vermutlich einfach ein paar Lookups entlang der Bewegungsrichtung oder so.

[antisteo]

Clonk hat das ganze glaube ich mit wenigen "Testpixeln" gelöst. Die sind dann die Eckpunkte der Gefährte. Das spielt vor allem bei den Loren eine Rolle. Es kann dabei natürlich passieren, dass man den Loren auf einen "Erdspieß" schiebt und die Testpixel links und rechts vom Erdspieß hängen. Dadurch dass Clonk von einem frickeligen Spielgefühl lebt, hat mich das nie gestört. Ich glaube bei den Ubooten in Clonk gibt es mindestens drei Testpunkte. Vielleicht reicht das ja? Ich bin mir allerdings nicht sicher, wie die auf der Basis eine Normale zum schieben der Objekte berechnen. Vermutlich einfach ein paar Lookups entlang der Bewegungsrichtung oder so.

Aber bei den U-Booten von Clonk ist man auch ständig in der Landschaft hängen geblieben. Ich hätte mir ein paar mehr Kollisionspunkte gewünscht (mindestens noch einen zweiten an der Unterseite

Ich bin da eher ein Freund von Kollisionsvolumen. Konkave Objekte werden einfach durch mehrere konvexe Hüllen beschrieben

[Jonathan]

Ich hab nochmal darüber nachgedacht, das Thema ist kompliziert und interessiert mich dann doch schon irgendwie:

These: Physiksimulation sollte so passieren, als ob die rote Linie hier die wahre Geometrie wäre:

Wie gesagt: Intuitiv denkt niemand, dass die Welt aus Blöcken besteht. Intuitiv denkt jeder, die Blöcke sind nur eine "schlechte" Annäherung an die Realität. Weil über mehrere Dekaden Computerspiele halt pixelig waren, aber immer schon kontinuierliche Flächen dargestellt haben. Vergleichbar mit schwarzen Linien um Comic-Charaktere: Die sind ein Artefakt der Darstellung (man braucht die um Flächen sauber abzugrenzen), kein Mensch denkt, dass alle Charaktere von einer Art schwarzen Öl-Films umgeben sind. Die Linien sind nicht Teil der Realität. Und die Inseln im Bild sind nicht eckig, sondern haben weiche Kurven, nämlich die roten Linien.

Das Bild oben ist aus Inkscape, aus der Bitmap wurde ein Pfadobjekt berechnet. Nicht überall perfekt, aber auch nicht so schlecht. Wie man sieht, hat man schöne, weiche Kanten an denen Kugelobjekte sehr schön und reibungsarm entlang gleiten könnten. Die Idee wäre also, eine solche kontinuierliche Linie aus den Pixel zu schätzen (eine handvoll Pixel samplen und darein nach einer festen Formel die Parameter für eine glatte Funktion (Spline, Polynom, etc.) zu fitten) und dann die Kollision damit zu machen. Nicht ganz billig, aber es gibt ja auch keine 1000 Objekte, selbst wenn man die Schnittteste numerisch macht und da 5-10 Schritte fürs Root-Finding in einem iterativen Solver braucht, ist das Performance-technisch kein Problem (solange man das für Spielobjekte benutzt und nicht für einzelne Sandpartikel).

Für eine Heightmap wäre das einfach und würde sicher gut funktionieren. Wie bei Splines mit stückweise lokalem Support braucht man nur ein paar Pixel anschauen, kann da (für jeden Test neu) sein Teil der Funktion dran fitten und den Schnitttest machen / die Normale berechnen. Aber hier hat man keine Heightmap sondern komplexe Geometrie. Im linken Block hat man an der rechten Hälfte etwa eine sehr steile, aber nicht senkrechte Kante. Was ich eigentlich nett finde. Aber: Dafür braucht man ja ein 10 Pixel Fenster.
Andererseits hat man in der Mitte zwischen den zwei Inseln nur 2 oder 3 Pixel freien Raum. Wenn man darauf besteht sich ein paar Nachbarpixel anzuschauen und dann eine Linie durchzulegen, wird man an dieser Stelle sehr schnell scheitern, und Spezialfälle wie diesen wird es dutzende geben. Bei derartiger Geometrie kann man die Normale dann also nicht wirklich lokal berechnen, sondern man müsste global die Form ausrechnen (z.B. ein Floodfill um alle Pixel der Außenkanten zu finden) und zwischenspeichern. Damit sollte man dann die meisten Sonderfälle recht gut und robust abdecken können.

Effektiv macht man dann also keine Kollision auf Pixelbasis mehr, sondern man rechnet sich seine Collisionshape vorher aus und speichert sie. Ähnlich zu der Idee, die Bitmap in konvexe Polygone zu zerlegen. Das schöne am lokalen Fit war aber, dass er sehr schnell geht und man ihn für jeden Test neu machen kann, aber wenn man es global macht, muss man in jedem Frame das ganze Level neu tracen (weil sich die Geometrie ja ständig ändern kann, soweit ich das verstanden habe).

Hoffe das war halbwegs verständlich, ich hatte jetzt keine Lust 5 mal so viel Text zu schreiben um alles detailliert zu erklären. Insgesamt ist das Problem aber wohl schwieriger als ich zunächst dachte :D

[Schrompf]

Tja, was soll ich sagen. Da gibt's viele Ansätze, und Du hast schon echt schön dargelegt, was dieser Ansatz gut kann und was Probleme machen wird. Ich bin bisher weiter stumpf auf Bitmasken fokussiert, und der Ansatz liefert dank moderner Speicherbandbreiten jetzt Ergebnisse in Nanosekunden:

Dabei habe ich nochmal so richtig unter die Nase gerieben bekommen, dass mein Debug-Linien-Renderer genau einen Pixel vertikal daneben liegt. Dieser Pixelshiejt bringt mich noch um meine grauen Haare.