Codierung von zerstörbarem Pixel-Terrain: Wie man alles explodieren lässt

() translation by (you can also view the original English article)

In diesem Tutorial implementieren wir vollständig zerstörbares Pixel-Terrain im Stil von Spielen wie Cortex Command und Worms. Sie lernen, wie Sie die Welt explodieren lassen, wo immer Sie sie abschießen - und wie Sie den "Staub" auf dem Boden niederlassen, um neues Land zu schaffen.

Hinweis: Obwohl dieses Tutorial in Processing geschrieben und mit Java kompiliert wurde, sollten Sie in fast jeder Spieleentwicklungsumgebung dieselben Techniken und Konzepte verwenden können.

Vorschau des Endergebnisses

Sie können die Demo auch selbst spielen. WASD, um sich zu bewegen, Linksklick, um explosive Kugeln abzuschießen, Rechtsklick, um Pixel zu sprühen.

Schritt 1: Das Gelände

In unserem seitlichen Sandkasten wird das Gelände die Kernmechanik unseres Spiels sein. Ähnliche Algorithmen haben oft ein Bild für die Geländetextur und ein anderes als Schwarz-Weiß-Maske, um zu definieren, welche Pixel fest sind. In dieser Demo sind das Gelände und seine Textur alle ein Bild, und die Pixel sind solide, je nachdem, ob sie transparent sind oder nicht. Der Maskenansatz ist besser geeignet, wenn Sie die Eigenschaften jedes Pixels definieren möchten, z. B. wie wahrscheinlich es sich löst oder wie federnd das Pixel ist.

Um das Gelände zu rendern, zeichnet die Sandbox zuerst die statischen Pixel und dann die dynamischen Pixel, wobei alles andere oben liegt.

Das Gelände verfügt auch über Methoden zum Herausfinden, ob ein statisches Pixel an einem Ort fest ist oder nicht, sowie über Methoden zum Entfernen und Hinzufügen von Pixeln. Die wahrscheinlich effektivste Art, das Bild zu speichern, ist ein eindimensionales Array. Das Abrufen eines 1D-Index aus einer 2D-Koordinate ist ziemlich einfach:

1	index = x + y * width

Damit dynamische Pixel abprallen können, müssen wir an jedem Punkt die Oberflächennormale ermitteln können. Durchlaufen Sie einen quadratischen Bereich um den gewünschten Punkt, suchen Sie alle durchgezogenen Pixel in der Nähe und mitteln Sie ihre Position. Nehmen Sie einen Vektor von dieser Position zum gewünschten Punkt, kehren Sie ihn um und normalisieren Sie ihn. Da ist dein normaler!

Die schwarzen Linien repräsentieren die Normalen zum Gelände an verschiedenen Punkten.

So sieht das im Code aus:

normal(x,y) {
    Vector avg
    for x = -3 to 3 // 3 is an arbitrary number
      for y =-3 to 3 // user larger numbers for smoother surfaces
        if pixel is solid at (x + w, y + h) {
          avg -= (x,y)
        }
      }
    }
    length = sqrt(avgX * avgX + avgY * avgY) // distance from avg to the center
    return avg/length // normalize the vector by dividing by that distance
}

Schritt 2: Das dynamische Pixel und die Physik

Das "Terrain" selbst speichert alle nicht bewegten statischen Pixel. Dynamische Pixel sind derzeit in Bewegung befindliche Pixel und werden getrennt von den statischen Pixeln gespeichert. Während das Gelände explodiert und sich einstellt, werden Pixel zwischen statischen und dynamischen Zuständen umgeschaltet, wenn sie sich verschieben und kollidieren. Jedes Pixel wird durch eine Reihe von Eigenschaften definiert:

Position und Geschwindigkeit (erforderlich, damit die Physik funktioniert).
Nicht nur der Ort, sondern auch der vorherige Ort des Pixels. (Wir können zwischen den beiden Punkten scannen, um Kollisionen zu erkennen.)
Andere Eigenschaften umfassen die Farbe, Klebrigkeit und Sprungkraft des Pixels.

Damit sich das Pixel bewegen kann, muss seine Position mit seiner Geschwindigkeit weitergeleitet werden. Die Euler-Integration ist zwar für komplexe Simulationen ungenau, aber so einfach, dass wir unsere Partikel effizient bewegen können:

1	position = position + velocity * elapsedTime

Die elapsedTime ist die Zeit, die seit dem letzten Update vergangen ist. Die Genauigkeit einer Simulation kann vollständig beeinträchtigt werden, wenn die elapsedTime zu variabel oder zu groß ist. Dies ist bei dynamischen Pixeln weniger ein Problem, aber bei anderen Kollisionserkennungsschemata.

Wir werden Zeitschritte mit fester Größe verwenden, indem wir die verstrichene Zeit in Blöcke konstanter Größe aufteilen. Jeder Block ist ein vollständiges "Update" der Physik, wobei alle verbleibenden Teile in den nächsten Frame gesendet werden.

elapsedTime = lastTime - currentTime
lastTime = currentTime // reset lastTime

// add time that couldn't be used last frame
elapsedTime += leftOverTime

// divide it up in chunks of 16 ms
timesteps = floor(elapsedTime / 16)

// store time we couldn't use for the next frame.
leftOverTime = elapsedTime - timesteps

for (i = 0; i < timesteps; i++) {
     update(16/1000) // update physics
}

Schritt 3: Kollisionserkennung

Das Erkennen von Kollisionen für unsere fliegenden Pixel ist so einfach wie das Zeichnen einiger Linien.

Bresenhams Linienalgorithmus wurde 1962 von einem Gentleman namens Jack E. Bresenham entwickelt. Bis heute wird es verwendet, um einfache Alias-Linien effizient zu zeichnen. Der Algorithmus hält sich streng an ganze Zahlen und verwendet hauptsächlich Addition und Subtraktion, um Linien effektiv zu zeichnen. Heute werden wir es für einen anderen Zweck verwenden: die Kollisionserkennung.

Ich verwende Code, der aus einem Artikel auf gamedev.net entlehnt wurde. Während die meisten Implementierungen des Linienalgorithmus von Bresenham die Zeichnungsreihenfolge neu ordnen, können wir mit dieser speziellen Implementierung immer von Anfang bis Ende scannen. Die Reihenfolge ist wichtig für die Kollisionserkennung. Andernfalls werden Kollisionen am falschen Ende des Pixelpfads erkannt.

Die Steigung ist ein wesentlicher Bestandteil des Linienalgorithmus von Bresenham. Der Algorithmus teilt die Steigung in ihre Komponenten "rise" und "run" auf. Wenn zum Beispiel die Neigung der Linie 1/2 betrug, können wir die Linie zeichnen, indem wir zwei Punkte horizontal platzieren, einen nach oben (und rechts) und dann zwei weitere.

Der hier gezeigte Algorithmus berücksichtigt alle Szenarien, unabhängig davon, ob die Linien eine positive oder negative Steigung aufweisen oder vertikal sind. Der Autor erklärt, wie er es auf gamedev.net ableitet.

rayCast(int startX, int startY, int lastX, int lastY) {
  int deltax = (int) abs(lastX - startX)
  int deltay = (int) abs(lastY - startY)
  int x = (int) startX
  int y = (int) startY
  int xinc1, xinc2, yinc1, yinc2
  // Determine whether x and y is increasing or decreasing 
  if (lastX >= startX) { // The x-values are increasing     
    xinc1 = 1
    xinc2 = 1
  }
  else { // The x-values are decreasing
    xinc1 = -1
    xinc2 = -1
  }
  if (lastY >= startY) { // The y-values are increasing
    yinc1 = 1
    yinc2 = 1
  }
  else { // The y-values are decreasing
    yinc1 = -1
    yinc2 = -1
  }
  int den, num, numadd, numpixels
  if (deltax >= deltay) { // There is at least one x-value for every y-value
    xinc1 = 0 // Don't change the x when numerator >= denominator
    yinc2 = 0 // Don't change the y for every iteration
    den = deltax
    num = deltax / 2
    numadd = deltay
    numpixels = deltax // There are more x-values than y-values
  }
  else { // There is at least one y-value for every x-value
    xinc2 = 0 // Don't change the x for every iteration
    yinc1 = 0 // Don't change the y when numerator >= denominator
    den = deltay
    num = deltay / 2
    numadd = deltax
    numpixels = deltay // There are more y-values than x-values
  }
  int prevX = (int)startX
  int prevY = (int)startY
  for (int curpixel = 0; curpixel <= numpixels; curpixel++) {
  
    if (terrain.isPixelSolid(x, y))
        return (prevX, prevY) and (x, y)
        
    prevX = x
    prevY = y
    
    num += numadd // Increase the numerator by the top of the fraction
    
    if (num >= den) {  // Check if numerator >= denominator
      num -= den // Calculate the new numerator value
      x += xinc1 // Change the x as appropriate
      y += yinc1 // Change the y as appropriate
    }
    
    x += xinc2 // Change the x as appropriate
    y += yinc2 // Change the y as appropriate
  }  
  return null // nothing was found
}

Schritt 4: Kollisionsbehandlung

Das dynamische Pixel kann während einer Kollision eines von zwei Dingen tun.

Wenn es sich langsam genug bewegt, wird das dynamische Pixel entfernt und dem Gelände, in dem es kollidierte, ein statisches Pixel hinzugefügt. Kleben wäre unsere einfachste Lösung. In Bresenhams Linienalgorithmus ist es am besten, einen vorherigen und einen aktuellen Punkt zu verfolgen. Wenn eine Kollision erkannt wird, ist der "current point" das erste feste Pixel, auf das der Strahl trifft, während der "previous point" der leere Raum unmittelbar davor ist. Der vorherige Punkt ist genau der Ort, an dem wir das Pixel kleben müssen.
Wenn es sich zu schnell bewegt, hüpfen wir vom Gelände ab. Hier kommt unser oberflächennormaler Algorithmus ins Spiel! Reflektieren Sie die Anfangsgeschwindigkeit des Balls über die Normalen, um ihn abzuprallen.

Der Winkel zu beiden Seiten der Normalen ist gleich.

     // Project velocity onto the normal, multiply by 2, and subtract it from velocity
     normal = getNormal(collision.x, collision.y)
     // project velocity onto the normal using dot product
     projection = velocity.x * normal.x + velocity.y * normal.y
     // 
     velocity -= normal * projection * 2

Schritt 5: Kugeln und Explosionen!

Aufzählungszeichen verhalten sich genau wie dynamische Pixel. Bewegung wird auf die gleiche Weise integriert, und die Kollisionserkennung verwendet denselben Algorithmus. Unser einziger Unterschied ist die Kollisionsbehandlung

Nachdem eine Kollision erkannt wurde, explodieren Kugeln, indem alle statischen Pixel innerhalb eines Radius entfernt und dann dynamische Pixel mit nach außen gerichteten Geschwindigkeiten an ihrer Stelle platziert werden. Ich benutze eine Funktion, um einen quadratischen Bereich um den Radius einer Explosion zu scannen, um herauszufinden, welche Pixel verschoben werden sollen. Anschließend wird der Abstand des Pixels von der Mitte verwendet, um eine Geschwindigkeit festzulegen.

explode(x,y, radius) {
     for (xPos = x - radius;  xPos <= x + radius; xPos++) {
          for (yPos = y - radius;  yPos <= y + radius; yPos++) {
               if (sq(xPos - x) + sq(yPos - y) < radius * radius) {
                    if (pixel is solid) {
                         remove static pixel
                         add dynamic pixel
                    }
               }
          }
     }
}

Schritt 6: Der Spieler

Der Spieler ist kein Kernbestandteil der zerstörbaren Geländemechanik, beinhaltet jedoch eine Kollisionserkennung, die definitiv für Probleme relevant sein wird, die in Zukunft auftreten werden. Ich werde erklären, wie Kollisionen in der Demo für den Spieler erkannt und behandelt werden.

Schleifen Sie für jede Kante von einer Ecke zur nächsten und überprüfen Sie jedes Pixel.
Wenn das Pixel fest ist, beginnen Sie in der Mitte des Players und scannen Sie in Richtung dieses Pixels, bis Sie ein festes Pixel treffen.
Bewegen Sie den Player von dem ersten festen Pixel weg, das Sie getroffen haben.

Schritt 7: Optimieren

Tausende von Pixeln werden gleichzeitig verarbeitet, was die Physik-Engine erheblich belastet. Um dies schnell zu machen, würde ich wie alles andere empfehlen, eine Sprache zu verwenden, die relativ schnell ist. Die Demo ist in Java kompiliert.

Sie können auch auf Algorithmenebene Optimierungsmaßnahmen ergreifen. Zum Beispiel kann die Anzahl der Partikel aus Explosionen durch Verringern der Zerstörungsauflösung verringert werden. Normalerweise finden wir jedes Pixel und verwandeln es in ein dynamisches 1x1-Pixel. Scannen Sie stattdessen alle 2x2 Pixel oder 3x3 und starten Sie ein dynamisches Pixel dieser Größe. In der Demo verwenden wir 2x2 Pixel.

Wenn Sie Java verwenden, ist die Speicherbereinigung ein Problem. Die JVM findet regelmäßig Objekte im Speicher, die nicht mehr verwendet werden, wie z. B. die dynamischen Pixel, die im Austausch gegen statische Pixel verworfen werden, und versucht, diese zu entfernen, um Platz für mehr Objekte zu schaffen. Das Löschen von Objekten, Tonnen von Objekten, nimmt jedoch Zeit in Anspruch, und jedes Mal, wenn die JVM eine Bereinigung durchführt, friert unser Spiel kurz ein.

Eine mögliche Lösung ist die Verwendung eines Caches. Anstatt ständig Objekte zu erstellen/zu zerstören, können Sie einfach tote Objekte (wie dynamische Pixel) halten, um sie später wiederzuverwenden.

Verwenden Sie nach Möglichkeit Grundelemente. Die Verwendung von Objekten für Positionen und Geschwindigkeiten wird beispielsweise die Speicherbereinigung etwas erschweren. Es wäre sogar noch besser, wenn Sie alles als Grundelemente in eindimensionalen Arrays speichern könnten.

Schritt 8: Machen Sie es sich selbst

Es gibt viele verschiedene Richtungen, die Sie mit dieser Spielmechanik einschlagen können. Funktionen können hinzugefügt und an jeden gewünschten Spielstil angepasst werden.

Beispielsweise können Kollisionen zwischen dynamischen und statischen Pixeln unterschiedlich behandelt werden. Eine Kollisionsmaske unter dem Gelände kann verwendet werden, um die Klebrigkeit, Sprungkraft und Stärke jedes statischen Pixels oder die Wahrscheinlichkeit zu definieren, durch eine Explosion verschoben zu werden.

Es gibt eine Vielzahl verschiedener Dinge, die Sie auch mit Waffen tun können. Aufzählungszeichen können eine "Eindringtiefe" erhalten, damit sie sich vor der Explosion durch so viele Pixel bewegen können. Traditionelle Waffenmechaniken können ebenfalls angewendet werden, wie eine unterschiedliche Feuerrate, oder wie eine Schrotflinte können mehrere Kugeln gleichzeitig abgefeuert werden. Sie können sogar, wie bei den Sprungpartikeln, Kugeln von Metallpixeln abprallen lassen.

Abschluss

2D-Geländezerstörung ist nicht ganz einzigartig. Zum Beispiel entfernen die Klassiker Würmer und Panzer bei Explosionen Teile des Geländes. Cortex Command verwendet ähnliche Bouncy-Partikel, die wir hier verwenden. Andere Spiele könnten genauso gut, aber ich habe noch nichts davon gehört. Ich freue mich darauf zu sehen, was andere Entwickler mit dieser Mechanik machen werden.

Das meiste, was ich hier erklärt habe, ist vollständig in der Demo implementiert. Bitte werfen Sie einen Blick auf die Quelle, wenn etwas mehrdeutig oder verwirrend erscheint. Ich habe der Quelle Kommentare hinzugefügt, um sie so klar wie möglich zu machen. Danke fürs Lesen!