2D-Kollisionsdetektion
Algorithmen zur Kollisionsdetektion in 2D-Spielen hängen von der Art der Formen ab, die kollidieren können (z. B. Rechteck zu Rechteck, Rechteck zu Kreis, Kreis zu Kreis). Im Allgemeinen haben Sie eine einfache generische Form, die die Entität als "Hitbox" abdeckt. Auch wenn die Kollisionsabfrage dadurch nicht pixelgenau ist, sieht sie gut genug aus und ist leistungsfähig über mehrere Entitäten hinweg. Dieser Artikel bietet einen Überblick über die am häufigsten verwendeten Techniken zur Kollisionsdetektion in 2D-Spielen.
Engine-Code
Die Demos auf dieser Seite basieren nicht auf einer externen Bibliothek, daher implementieren wir die gesamte Orchestrierung selbst, einschließlich Rendering, Handhabung der Benutzereingaben und Aufruf von Verhaltensweisen jeder Entität. Der Code wird unten gezeigt (er wird nicht für jedes Beispiel wiederholt):
<div id="container"></div>
.entity {
display: inline-block;
position: absolute;
height: 20px;
width: 20px;
background-color: blue;
}
.movable {
left: 50px;
top: 50px;
background-color: red;
}
.collision-state {
background-color: green !important;
}
const collider = {
moveableEntity: null,
staticEntities: [],
checkCollision() {
// Important: the isCollidingWith method is what we are implementing
const isColliding = this.staticEntities.some((staticEntity) =>
this.moveableEntity.isCollidingWith(staticEntity),
);
this.moveableEntity.setCollisionState(isColliding);
},
};
const container = document.getElementById("container");
class BaseEntity {
ref;
position;
constructor(position) {
this.position = position;
this.ref = document.createElement("div");
this.ref.classList.add("entity");
this.ref.style.left = `${this.position.x}px`;
this.ref.style.top = `${this.position.y}px`;
container.appendChild(this.ref);
}
shiftPosition(dx, dy) {
this.position.x += dx;
this.position.y += dy;
this.redraw();
}
redraw() {
this.ref.style.left = `${this.position.x}px`;
this.ref.style.top = `${this.position.y}px`;
}
setCollisionState(isColliding) {
if (isColliding && !this.ref.classList.contains("collision-state")) {
this.ref.classList.add("collision-state");
} else if (!isColliding) {
this.ref.classList.remove("collision-state");
}
}
isCollidingWith(other) {
throw new Error("isCollidingWith must be implemented in subclasses");
}
}
document.addEventListener("keydown", (e) => {
e.preventDefault();
switch (e.key) {
case "ArrowLeft":
collider.moveableEntity.shiftPosition(-5, 0);
break;
case "ArrowUp":
collider.moveableEntity.shiftPosition(0, -5);
break;
case "ArrowRight":
collider.moveableEntity.shiftPosition(5, 0);
break;
case "ArrowDown":
collider.moveableEntity.shiftPosition(0, 5);
break;
}
collider.checkCollision();
});
Achsenparalleles Begrenzungsrechteck
Eine der einfacheren Formen der Kollisionsdetektion findet zwischen zwei rechteckigen, achsenparallelen Begrenzungen ohne Rotation statt. Der Algorithmus funktioniert, indem sichergestellt wird, dass keine Lücke zwischen den 4 Seiten der Rechtecke besteht. Jede Lücke bedeutet, dass keine Kollision existiert.
class BoxEntity extends BaseEntity {
width = 20;
height = 20;
isCollidingWith(other) {
return (
this.position.x < other.position.x + other.width &&
this.position.x + this.width > other.position.x &&
this.position.y < other.position.y + other.height &&
this.position.y + this.height > other.position.y
);
}
}
Kreis-Kollision
Eine andere einfache Form für die Kollisionsdetektion ist zwischen zwei Kreisen. Dieser Algorithmus funktioniert, indem die Mittelpunkte der beiden Kreise genommen werden und sichergestellt wird, dass der Abstand zwischen den Mittelpunkten kleiner ist als die Summe der beiden Radien.
.entity {
border-radius: 50%;
}
class CircleEntity extends BaseEntity {
radius = 10;
isCollidingWith(other) {
const dx =
this.position.x + this.radius - (other.position.x + other.radius);
const dy =
this.position.y + this.radius - (other.position.y + other.radius);
const distance = Math.sqrt(dx * dx + dy * dy);
return distance < this.radius + other.radius;
}
}
Hinweis:
Die x- und y-Koordinaten der Kreise beziehen sich auf ihre oberen linken Ecken, deshalb müssen wir den Radius hinzufügen, um ihre Mittelpunkte zu vergleichen.
Trennung der Achsensätze
Dies ist ein Kollisionsalgorithmus, der eine Kollision zwischen zwei konvexen Polygonen erkennen kann. Er ist komplizierter zu implementieren als die oben genannten Methoden, bietet aber mehr Möglichkeiten. Die Komplexität eines solchen Algorithmus erfordert, dass wir Leistungsoptimierungen in Betracht ziehen, die im nächsten Abschnitt behandelt werden.
Die Implementierung von SAT liegt außerhalb des Umfangs dieser Seite, sehen Sie sich daher die empfohlenen Tutorials unten an:
Kollisionsleistung
Während einige dieser Algorithmen zur Kollisionsdetektion einfach genug zu berechnen sind, kann es eine Verschwendung von Zyklen sein, jede Entität mit jeder anderen Entität zu testen. Normalerweise teilen Spiele die Kollision in zwei Phasen auf: grob und eng.
Grobphase
Die Grobphase sollte Ihnen eine Liste von Entitäten geben, die möglicherweise kollidieren. Dies kann mit einer räumlichen Datenstruktur implementiert werden, die Ihnen eine grobe Vorstellung davon gibt, wo sich die Entität befindet und was sich um sie herum befindet. Einige Beispiele für räumliche Datenstrukturen sind Quad Bäume, R-Bäume oder eine räumliche Hashmap.
Engphase
Wenn Sie eine kleine Liste von zu überprüfenden Entitäten haben, möchten Sie einen Engphasen-Algorithmus verwenden (wie die oben genannten), um eine sichere Antwort darauf zu geben, ob eine Kollision besteht oder nicht.