[RMXP] Kollisionsabfrage => Denkfehler

[Kagurame]

Hoi, ich werkele immer noch am dir8-Script, und habe wohl den einen oder anderen Denkfehler.


Ich möchte ein Pixel-Movement und arbeite gerade in ersten Zügen an der Kollisions-Abfrage zweier Charaktere. Dabei geht es derzeit vorrangig davon, ob sich das Rect zweier Figuren (Ob NPC-Spieler, NPC-NPC oder Spieler-Spieler) irgendwo überschneidet.


In der beigefügten Demo kann man sich durch druck der ESC-Taste die derzeitig kollidierenden Charaktere ausgeben lassen (Anhand eines zufällig generierten Schlüssels. Dieser sollte Unique sein, die Chance zwei mal den selben Schlüssel zu generieren ist sehr gering (Da 999999 verschiedene Werte generiert werden können und nicht annähernd so viele Figuren auf eine Map können... rein technisch gesehen [performance]))

Das funktioniert soweit, aber wenn sich zwei Figuren auf der X- oder Y-Achse genau überschneiden, wird keine Kollision mehr erkannt.

Kollisionsabfrage bisher:
http://img651.imageshack.us/img651/6771/skizzekollision.png

Oberste Linke Ecke des Spielers. Besteht aus my_min_x sowie my_min_y
Untere Rechte Ecke des Spielers. Besteht aus my_max_x sowie my_max_y
Oberste Linke Ecke eines NPC. Besteht aus figure_min_x sowie figure_min_y
Untere Rechte Ecke eines NPC. Besteht aus figure_max_x sowie figure_max_y
Oben Links befindet sich außerhalb des NPC und kollidiert nicht.
Unten Rechts befindet sich zwischen figure_min_x und figure_max_x und außerdem zwischen figure_min_y sowie figure_max_y. => Kollision
Wird für Vergleiche genutzt. Befindet sich ein Eckpunkt zwischen 7 und 8, findet eine Kollision statt.
Wird für Vergleiche genutzt. Befindet sich ein Eckpunkt zwischen 7 und 8, findet eine Kollision statt.



Im zweiten Spoiler ist eine Skizze beigefügt. Begrifflichkeiten sollten dort drin sein.

Überprüfung ob einer der Eckpunkte der Ausgangsfigur sich innerhalb einer anderen Figur befindet. Dafür wurden der obere linke und der untere Rechte Punkt ermittelt.



my_min_x = X-Position der Ausgangsfigur
my_max_x = X-Position + Länge der Ausgangsfigur

my_min_y = Y-Position der Ausgangsfigur
my_max_y = Y-Position + Höhe der Ausgangsfigur

# Äquivalent figure_min_x / y / max / ... für die Figure, welche derzeit auf Kollision geprüft wird

if (my_min_x >= figure_min_x) && (my_min_x <= figure_max_x) && (my_min_y >= figure_min_y) && (my_min_y <= figure_max_y) ||
(my_max_x <= figure_max_x) && (my_max_x >= figure_min_x) && (my_max_y <= figure_max_y) && (my_max_y >= figure_min_y) #...

Um das ganze zu vereinfachen, wird nun geprüft, ob sich ein Eckpunkt zwischen zwei anderen befindet (between?), siehe dazu Code-Ausschnitte oder Demo.


Derzeitige Überprüfung:


def self.get_range_characters(self_key)
in_range = []
self_char = @@characters[self_key]

my_min_x = self_char.x
my_max_x = my_min_x + self_char.src_x

my_min_y = self_char.y
my_max_y = my_min_y + self_char.src_y

factor = 3
factor *= 2 if self_char.running
factor /= 2 if self_char.slow

my_min_x -= factor
my_min_y -= factor

my_max_x += factor
my_max_y += factor

@@characters.each_pair { |key, char|
next if key == self_key
figure_min_x = char.x
figure_max_x = char.x + char.src_x

figure_min_y = char.y
figure_max_y = char.y + char.src_y

if my_max_x.between?(figure_min_x, figure_max_x) &&
my_max_y.between?(figure_min_y, figure_max_y) ||
my_min_x.between?(figure_min_x, figure_max_x) &&
my_min_y.between?(figure_min_y, figure_max_y) ||
my_max_y.between?(figure_min_y, figure_max_y) &&
my_min_x.between?(figure_min_x, figure_max_x) ||
my_max_x.between?(figure_min_x, figure_max_x) &&
my_min_y.between?(figure_min_y, figure_max_y) then

in_range.push key
end
}

in_range
end
Die Condition am Ende der Methode ist hier relevant.


Ein ganz anderer Gedanke war, jede Figur mit jedem Pixel in einem Array zu halten, um dann einfach zu überprüfen ob sich einer der Pixel der Figur, welche gerade geprüft wird, in dem Array befindet (include?).
Allerdings kann man sich denken, dass dies sehr unperformant werden könnte und dem entgegen wird erwartet, dass das Mapping-System, welches zum Schluss raus kommt (mit dir8, Pixelmovement und so weiter), mit geschätzten 200 Events klar kommen muss. Da ist es verständlich, dass ich schnelle und speicher sparende Wege suche.


Der Code darin ist frisch und nicht refaktorisiert, entsprechend können also Redundanzen vorhanden sein oder unkommentierte Stellen enthalten sein.

Die Klasse Character_Cache ist hier die relevante, welche die Kollisions-Abfragen derzeit zugeschustert bekommt.
Ich suche also eine Alternative für self.get_range_characters(self_key), wo derzeit alle Charaktere gefunden werden sollen, welche genauestens geprüft werden müssen (da hier dann real einzelne Pixel geprüft werden müssen, ich das aber nur bei den Figuren mache, mit denen ich theoretisch kollidieren könnte).

Movement: Numpad (1-9 ohne 5), Pfeiltasten
Running: B (nicht B-7, funktioniert nicht.)
Beenden: Enter
Kollidierende Figuren ausgeben lassen: ESC


Kann dort jemand helfen und mir vielleicht sagen, wo ich was falsch mache?

Zusatzfrage: Wie kann ich mir die Speicheradresse einer Instanz von einem Objekt besorgen? (vgl. Pointer C++)

EDIT:

Bis auf die Zusatzfrage hat sich die Anfrage erledigt (:




def self.get_range_characters(my_key)
in_range = []
my_char = @@characters[my_key]

my_x = my_char.x
my_y = my_char.y

my_length = my_char.src_x
my_height = my_char.src_y

@@characters.each_pair { |key, figure_char|
next if key == my_key

diff_x = my_x - figure_char.x
diff_y = my_y - figure_char.y

if (diff_x.betrag <= my_length) && (diff_y.betrag <= my_height)
in_range.push key
end
}

in_range
end

# Zusätzlich:

class Integer

def betrag
return (self >= 0) ? self : (self * (-1))
end

end


15912

[DNKpp]

wenn du eine kollission zweier gleichgroßer rechtecke abfragen möchtest, brauchst du eigentlich nur 2 abfragen.
also praktisch:


if (x1begin >= x2begin && y1begin >= y2begin && x1begin <= x2end && y1begin <= y2end)

damit schaust du, ob sich die obere linke ecke des ersten rechtecks innerhalb des 2. rechtecks befindet. wenn ja, findet logischerweise eine kollission statt.
wenn das nicht zutrifft


if (x1end >= x2begin && y1end >= y2begin && x1end <= x2end && y1end <= y2end)
das betrifft die untere rechte ecke.
sollte diese auch nicht innerhalb des rechtecks sein, findet keine kollission statt.

alternativ kannst du auch einfach:

if (x1end < x2begin)
das würde zum beispiel heißen, das der x endpunkt des 1. rechtecks kleiner als der x startpunkt des 2. rechtecks ist, und somit gar keine kollission stattfinden kann.
entsprechend das ganze noch für die anderen seiten.


if (x1end < x2begin || x1begin > x2end || y1end < y2begin || y1begin > y2end)
wenn eine der bedingungen zutrifft ist eine kollission ausgeschlossen. da ich leider auch nicht mehr ganz konfirm darin bin, und es ein wenig her ist, das ich das bei mir eingebaut habe, und ich jetzt wenig zeit habe, darüber nachzudenken kann ich gerade leider nur die paar fetzen schreiben. ich hoffe, ich konnte weiter helfen ;)

mfg

[Cornix]

wenn du eine kollission zweier gleichgroßer rechtecke abfragen möchtest, brauchst du eigentlich nur 2 abfragen.
also praktisch:

Code:
if (x1begin >= x2begin && y1begin >= y2begin && x1begin <= x2end && y1begin <= y2end) damit schaust du, ob sich die obere linke ecke des ersten rechtecks innerhalb des 2. rechtecks befindet. wenn ja, findet logischerweise eine kollission statt.
wenn das nicht zutrifft

Code:
if (x1end >= x2begin && y1end >= y2begin && x1end <= x2end && y1end <= y2end) das betrifft die untere rechte ecke.
sollte diese auch nicht innerhalb des rechtecks sein, findet keine kollission statt.
Was du sagst stimmt leider so nicht, schaue auf das Bild im Anhang.

Die korrekte Lösung ist folgende:
Ein Rechteck liegt teilweise innerhalb eines anderen genau dann wenn die beiden nicht vollständig disjunkt sind.
Das wäre als Code:

public boolean overlap(Rechteck r1, Rechteck r2)
return !(r1.startX > r2.endX || r1.startY > r2.endY || r1.endX < r2.startX || r1.endY < r2.startY)

Denn falls eine der folgenden Bedingungen erfüllt ist:
r1.startX > r2.endX
r1.startY > r2.endY
r1.endX < r2.startX
r1.endY < r2.startY
berühren sich die beiden Rechtecke überhaupt nicht, und die Negation der Aussage ist dann die Bedingung falls beide Rechtecke einander überschneiden.

[DNKpp]

stimmt, du hast recht. wie gesagt war nur kurz auf der arbeit drüber nachgedacht ;)
aber bei dem letzten punkt sind wir uns ja einig.

[-KD-]

Zusatzfrage: Wie kann ich mir die Speicheradresse einer Instanz von einem Objekt besorgen? (vgl. Pointer C++)
Mit Object#object_id kommst du an die Objekt-ID eines Objekts. Per ObjectSpace._id2ref kannst du eine Objekt-ID wieder in ein Objekt umwandeln. Auf diese Weise kannst du z.B. weak Pointer umsetzen. Aus der Objekt-ID kannst du auch die reale Speicheradresse ausrechnen, in dem du sie um ein Bit shiftest:

objekt = "Foo"
memory_adress = objekt.object_id << 1