Kollisionen
Wir müssen gegen Wände laufen
Was sich bewegt, stößt zusammen
Jetzt, wo es bewegliche Entities gibt, ist ein ‘Problem’ entstanden. Sie laufen nämlich einfach durcheinander hindurch wie ein Geist 👻.
Dafür gibt es verschiedene Möglichkeiten, und vielleicht habe ich hier eine falsche Abwägung getroffen, nämlich ‘Geschwindigkeit’. Jede Berechnung kostet Zeit, und die will man so gering wie möglich halten. Die erste Entscheidung war, ob ich Polygon-Berechnungen oder einfache Rechteck-Berechnungen (rect) verwende.
Update 2025: Mit der Erfahrung, die ich jetzt habe, würde ich nur Polygone verwenden.
Ich habe mich für rect entschieden, da ich nur einfache Formen habe. Wenn ich ein transparentes Bild einer Figur habe, hat es eine maximale Höhe und Breite, und das ist das gesamte Rechteck, durch das man nicht hindurchlaufen darf.
engine3 wurde um folgende Grundfunktionen erweitert
---Check if a point is inside the rect.
-- This function will include the border
---@param x integer
---@param y integer
---@param rect Rect The you want to use for the collision check
local function pointInRect(x, y, rect)
return x >= rect.x1 and x <= rect.x2 and y >= rect.y1 and y <= rect.y2
end
---@param x integer
---@param y integer
---@param rects table<Rect> The (collidable)Rects you want to use for the collision check
local function pointInRects(x, y, rects)
for _, rect in pairs(rects) do
if pointInRect(x, y, rect) then
return true
end
end
return false
end
--- Check if a point is inside the rect
-- https://2dengine.com/?p=intersections
---@param x integer X point coordinate
---@param y integer Y point coordinate
---@param l integer X left corner coordinate
---@param t integer Y top corner coordinate
---@param r integer X right corner coordinate
---@param b integer Y bottom corner coordinate
local function pointInAABB(x, y, l, t, r, b)
if x < l or x > r then
return false
end
if y < t or y > b then
return false
end
return true
end
---Check if two boxes overlap
-- https://love2d.org/wiki/BoundingBox.lua
---@param x1 integer X left corner coordinate box 1
---@param y1 integer Y top corner coordinate box 1
---@param w1 integer Width box 1
---@param h1 integer Height box 1
---@param x2 integer X left corner coordinate box 2
---@param y2 integer Y top corner coordinate box 2
---@param w2 integer Width box 2
---@param h2 integer Height box 2
local function rectsOverlap(x1, y1, w1, h1, x2, y2, w2, h2)
return x1 < x2 + w2 and x2 < x1 + w1 and y1 < y2 + h2 and y2 < y1 + h1
end
---Check if two boxes overlap using AABB
---@param x1a integer X left corner coordinate box 1
---@param y1a integer Y top corner coordinate box 1
---@param x2a integer X right corner coordinate box 1
---@param y2a integer Y bottom corner coordinate box 1
---@param x1b integer X left corner coordinate box 2
---@param y1b integer Y top corner coordinate box 2
---@param x2b integer X right corner coordinate box 2
---@param y2b integer Y bottom corner coordinate box 2
local function AABBVsAABB(x1a, y1a, x2a, y2a, x1b, y1b, x2b, y2b)
if x1a > x2b or x1b > x2a then
return false
end
if y1a > y2b or y1b > y2a then
return false
end
return true
end
---Check if two boxes overlap using AABB using width and height
---@param o1x integer
---@param o1y integer
---@param o1w integer
---@param o1h integer
---@param o2x integer
---@param o2y integer
---@param o2w integer
---@param o2h integer
local function AABBWHVsAABBWH(o1x, o1y, o1w, o1h, o2x, o2y, o2w, o2h)
return not ((o2x > o1x + o1w) or (o2x + o2w < o1x) or (o2y > o1y + o1h) or (o2y + o2h < o1y))
end
Danach bekommt eine Entity Informationen darüber, wie sie mit anderen Entities umgehen soll.
Das Lustige ist, dass ich schnell gemerkt habe, dass das zwar tatsächlich sehr schnell ist, aber auch zu eingeschränkt. Man kann ja auch eine Kreisform oder andere ‘seltsame’ Formen haben. Wenn man dann zum Beispiel mit dem Mauszeiger über so ein Objekt fährt, zeigt es schon außerhalb des Kreises (um den das unsichtbare rect liegt) an, was es ist.
Deshalb verwendet eine Entity jetzt für die Kollision mit dem Cursor ein Polygon und für die Bewegung ein rect.
local Collision = require "lib.engine3.src.framework.helper.math.collision"
---@field collidableA? table {1[opt](left),2([opt]right),3([opt]top),4([opt]bottom)}
---@field collidableB? table {1[opt](left),2([opt]right),3([opt]top),4([opt]bottom)}
---@field collidableRects? table Collidable rects [{x1,y1,x2,y2}]
function Frameset:new(data)
Folge dem Pfad
Jetzt, wo alle Entities die nötigen Daten haben, können wir mit aStar bestimmen, wo die Entity laufen darf.
function PathFinding:isPointInCollision(collisionRectsTable, x, y)
for _, collisionRectList in pairs(collisionRectsTable) do
for _, rect in pairs(collisionRectList) do
if Collision.pointInRect(x, y, rect) then
return true
end
end
end
return false
end
Wenn du irgendwo auf den Bildschirm klickst, wird anhand der Karte geprüft, wo der Spieler laufen darf. Die Karte nutzt die Funktion oben und liegt teilweise im Cache.
local path = aStar()
if path then
path = self:optimizePath(path)
path = self:smoothPath(path, map)
return {targetX = targetX, targetY = targetY, path = path}
end
Da ich nicht alle x,y-Koordinaten will, sondern nur die Momente, in denen die Entity eine andere Position bekommen muss, nutze ich auch optimizePath und smoothPath, wie du unten sehen kannst.
path {
x = 1, y = 1
x = 2, y = 1
x = 3, y = 1
x = 4, y = 1
x = 5, y = 1
x = 6, y = 1
}
path {
x = 1, y = 1
x = 6, y = 1
}
Zum Schluss
Ein Fehler, den ich gemacht hatte, war, dass ich das in Love2d über einen Hintergrund-Thread abwickeln wollte. Meine Idee war, dass es dann schneller geht. Das Ergebnis war, dass es zwar schneller war, aber nicht mehr zu dem passte, was man auf dem Bildschirm sah. Man sah dann gerade eine ‘Verzögerung’.
Update 2025 Auch wenn es oben einfach aussieht, wird dieses System noch mehrere Refactorings bekommen, und ich steige teilweise auf eine Walkmap um. Das ist eine einfache Ebene in Photoshop in Schwarz und Weiß, wobei Schwarz begehbar ist und Weiß nicht.