Bricks Kollision

[Diamondback2007]

Hi!

hab mal ne frage zu nem spiel das ich grade schreibe... es handelt sich um die Kollisionsabfrage zwischen einem ball und kleinen rechtecken.(wers nich kennt, das spiel hat das ziel alle rechtecke abzuschießen um ins nächste level zu kommen) wenn ich aber jetz für jedes rechteck einzeln überprüfe ob das object "ball"(ein quadrat) über meinem rechteck ist, passiert es das der ball zu schnell ist, d. h. das er durch das rechteck durchfliegt bevor das spiel merkt das der ball eig kollidiert. kann ich die kollision irgendwie anders lösen?
hier ein code-Schnipsel:

Delphi-Quellcode:

 //Kollision mit Bricks
  for j := 1 to NumBricks do
  begin
    If Brick_Kollision[j] = true
    Then
    begin
      //linke Seite
      If (Ball.Position.X+Ball.Size.X/2+6>=Brick[j].Obj.Position.X-Brick[j].Obj.Size.X/2) and (Ball.Position.X+Ball.Size.X/2+6<=Brick[j].Obj.Position.X-Brick[j].Obj.Size.X/2)
      Then
        If (Ball.Position.Y-Ball.Size.Y/2 <= Brick[j].Obj.Position.Y-Brick[j].Obj.Size.Y/2+2) and (Ball.Position.Y+Ball.Size.Y/2 >=Brick[j].Obj.Position.Y+Brick[j].Obj.Size.Y/2-2)
        Then
        begin
          DirX_b := -DirX_b;
          Brick_Kollision[j] := false;
          Brick[j].Obj.Visible := false;
        end;

      //rechte Seite
      If (Ball.Position.X-Ball.Size.X/2-6<=Brick[j].Obj.Position.X+Brick[j].Obj.Size.X/2) and (Ball.Position.X-Ball.Size.X/2-6>=Brick[j].Obj.Position.X+Brick[j].Obj.Size.X/2)
      Then
        If (Ball.Position.Y-Ball.Size.Y/2 <= Brick[j].Obj.Position.Y-Brick[j].Obj.Size.Y/2+2) and (Ball.Position.Y+Ball.Size.Y/2 >=Brick[j].Obj.Position.Y+Brick[j].Obj.Size.Y/2-2)
        Then
        begin
          DirX_b := -DirX_b;
          Brick_Kollision[j] := false;
          Brick[j].Obj.Visible := false;
        end;

      //Seite oben
      If (Ball.Position.Y+Ball.Size.Y/2+6>=Brick[j].Obj.Position.Y-Brick[j].Obj.Size.Y/2) and (Ball.Position.Y+Ball.Size.Y/2-6<=Brick[j].Obj.Position.Y-Brick[j].Obj.Size.Y/2)
      Then
        If (Ball.Position.X+Ball.Size.X/2 >= Brick[j].Obj.Position.X-Brick[j].Obj.Size.X/2) and (Ball.Position.X-Ball.Size.X/2 <Brick[j].Obj.Position.X+Brick[j].Obj.Size.X/2)
        Then
        begin
          DirY_b := -DirY_b;
          Brick_Kollision[j] := false;
          Brick[j].Obj.Visible := false;
        end;

      //Seite unten
      If (Ball.Position.Y-Ball.Size.Y/2-6<=Brick[j].Obj.Position.Y+Brick[j].Obj.Size.Y/2) and (Ball.Position.Y-Ball.Size.Y/2-6>=Brick[j].Obj.Position.Y+Brick[j].Obj.Size.Y/2)
      Then
        If (Ball.Position.X+Ball.Size.X/2 > Brick[j].Obj.Position.X-Brick[j].Obj.Size.X/2) and (Ball.Position.X-Ball.Size.X/2 <Brick[j].Obj.Position.X+Brick[j].Obj.Size.X/2)
        Then
        begin
          DirY_b := -DirY_b;
          Brick_Kollision[j] := false;
          Brick[j].Obj.Visible := false;
        end;
    end;

kann sein das ich hier un da ein paar zahlen vertauscht hab, hab nämlich schon ziemlich viel rumprobiert...
vielen dank schonmal!

Fabi

[IngoD7]

--> http://www.delphi-forum.de/viewtopic...asc&highlight=

[Diamondback2007]

verlinkt...ja un?

[IngoD7]

Zitat von Diamondback2007:

verlinkt...ja un?

(Zeitgleiches) Crossposting nennt man das, was du da tust.

Es sprechen sehr viele Gründe dagegen, sich mit Anfragen, die zeitgleich auch woanders behandelt werden, zu beschäftigen.
Somit tust du dir (und den jeweiligen Communities) keinen Gefallen damit.

[Der_Unwissende]

Zitat von Diamondback2007:

wenn ich aber jetz für jedes rechteck einzeln überprüfe ob das object "ball"(ein quadrat) über meinem rechteck ist, passiert es das der ball zu schnell ist, d. h. das er durch das rechteck durchfliegt bevor das spiel merkt das der ball eig kollidiert. kann ich die kollision irgendwie anders lösen?

Hi,
und erstmal Herzlich Willkommen in der DP

Zwar hast Du schon ein wenig zu deinem Problem geäussert, aber es fehlt auch noch eine wichtige Information, wie bewegt sich eigentlich Dein Ball? Wann genau berechnest Du die Bewegung/fragst Du Kollisionen ab/...?
Im einfachsten Fall würdest Du einfach die Kollision vor jeder Bewegung berechnen und somit wäre zwar ein langsamer Ball, aber eben nicht ein "Durchfliegen" möglich.
An sich solltest Du aber einfach schauen, was genau Du hast. Du hast eine Menge von Steinen (die eine feste Position und Ausdehnung haben) und einen Ball (der ebenfalls eine Position und eine Ausdehnung hat). Wichtig ist, dass sich nur der Ball frei bewegt. Die Steine werden immer in einem Raster platziert. Das ist in der Regel ein vielfaches ihrer Dimension (häufig z.B. eine ganze oder halbe Breite vom Stein).
Da das Überprüfen aller Steine auf eine mögliche Kollision zu langsam ist kannst Du einfach mal schauen, wie Du die Menge der zu überprüfenden Steine reduzierst. Hier kommt das Raster ins Spiel. Da sich die Steine immer in einem festen Raster bewegen kannst Du für jede Position des Balls einen großen Teil der Steine ausser Acht lassen. Der Ball kann nur solche Steine treffen, die im Raster in der selben Spalte sind, wie der Ball (X-Position). Bei einem max. gefüllten Feld kannst Du also (#Spalten - 1) * #Zeilen Steine unbetrachtet lassen, da diese unmöglich mit dem Ball kollidieren können. Andersherum wirst Du nie mehr als #Zeilen Steine prüfen müssen. Die Anzahl der Zeilen ist dabei wirklich der Worst-Case, es gibt wohl wenig Felder bei denen sich in jeder Zelle einer Spalte ein Stein befindet.
Ja, für die Zeilen sieht es aber eigentlich völlig analog aus. Hier kann der Ball natürlich (abhängig von der Y-Position) nur mit den Steinen kollidieren, die auf der selben Höhe sind wie der Ball.
Du siehst bestimmt schon worauf es hinaus läuft, hast Du die Spalte schon eingeschränkt und schränkst nun die Reihe ein, so hast Du eine eindeutige Koordinate (im Raster), die Du direkt überprüfen kannst. Solange Du die Steine also nur diskret (auf endlich vielen Positionen/in einem festen Raster) platzieren kannst (sollte üblich für ein Bricks-Clone sein), kommst Du mit einer Anfrage aus. Dazu musst Du das Raster nur geeignet speichern. Du benötigst eine Struktur, die Dir einen wahlfreien Zugriff erlaubt. Ein Array wäre genau so eine Struktur (Du kannst über den Index direkt auf eine Zelle zugreifen). Für ein Raster kannst Du einfach ein Array von Arrays verwenden. Abhängig von der Ball-Position musst Du dann nur noch eine Zelle abfragen (und das sollte sehr schnell gehen).
Natürlich hat ein Array einen gewissen Overhead (liegt daran, dass einige Felder nie gefüllt sein werden), aber der Speicherplatzbedarf dürfte sich in Grenzen halten. Alternativ kannst Du auch ein Array für die Spalten oder Zeilen anlegen und in jeder Zelle eine Liste (mit dyn. Größe) speichern. Dann kannst Du hier den Suchbereich auf eine Spalte/Zeile eingrenzen, musst aber über alle Elemente der Liste iterieren.

Ich denke allerdings, dass Dein Problem nicht im zu langsamen Suchen liegt als vielmehr in der Prüfung der Kollision bzw. dem Aufrufzeitpunkt dieser Überprüfung.

Ach ja, deinen Code hab ich mir ehrlich gesagt nicht angeschaut. Hoffe es hilft Dir weiter,

Gruß Der Unwissende

[Edit]
Wo war der rote Kasten?! (wie so oft in letzter Zeit)
[/Edit]

[Diamondback2007]

wow! thx! schonma! also das mit dem begrenzen hat ich schon mal versucht aber auf andere weise...der ball kann ja nicht die inneren steine treffen...
aber die berechnung der zu treffenden steine war dann doch komplizierter und aufwändiger als alle zuprüfen.
deine idee ist schon mal ganz,aber wie du ja auch geschrieben hast liegt das eher an der kollisionsabfrage un dem zeitpunkt. die abfrage wird im OnIdle der form ausgeführt.
da ich aber doch relativ kleine steine habe(-->mehr davon) fliegt der ball leider mancmal hindurch. dies passiert am häufigste´n bei schrägem einflug, sprich über die ecke eines steines.
im delphi-forum wurde vorgeschlagen, die nächste bewegung zu berechnen und dann zwischen den beiden positionen zu prüfen ob eine kollision stattgefunden hat.
leider weiß ich noch nicht so recht wie ich die realisieren soll. vor allem weiß ich auch nicht wie sich das performance-technisch äußert, da ich selbst einen ziemlich schnellen rechner besitze...
Aber vielen dank schon mal!

Fabi

[Der_Unwissende]

Zitat von Diamondback2007:

deine idee ist schon mal ganz,aber wie du ja auch geschrieben hast liegt das eher an der kollisionsabfrage un dem zeitpunkt. die abfrage wird im OnIdle der form ausgeführt.

Und das wäre imho ein ziemlich schlechter Zeitpunkt. Besser ist es hier, wenn Du die Kollisionsabfrage dort machst, wo Du auch den Ball bewegst. Ich weiß nicht in welcher Geschwindigkeit dein Ball bewegt wird bzw. wie hoch ein Stein bei Dir ist, aber Du musst die Überprüfung natürlich auch nur dann durchführen, wenn die Reihe / Spalte gewechselt wird.
Die Frage ist halt (irgendwie immer noch unbeantwortet) wann wird der Ball bewegt, wann die Kollision abgefragt. Wie gesagt, dass sollte immer mit der gleichen Priorität geschehen. Die Performance sollte auch jeder Rechner haben. Hast Du ein festes Raster, lässt sich sehr einfach (und schnell) die Position des Balls im Raster berechnen und der Zugriff auf eine Zelle eines 2D-Arrays ist auch sehr sehr schnell möglich (alles andere als ein Flaschenhals!). Liegt daran, dass ein Array immer am Stück im Speicher liegt. Du hast hier dann einerseits den Vorteil, dass Du die Adresse jeder Zelle direkt berechnen kannst (macht Dein Programm natürlich aut.). Und da ein Array am Stück im Speicher liegt greifen hier auch Caching-Mechanismen besonders gut (da lokale Speicherbereiche immer mit geladen werden). Da kostet das Zeichnen des Balls schon deutlich mehr Leistung.
Die Größe des Rasters entscheidet beim Array über dessen Speicher Bedarf, es würden hier nur Referenzen abgespeichert werden, pro Zelle Fallen also 4 Byte an, dann nochmal für die gespeicherte Länge 4 Byte pro Array. Bei einem Raster von 200 x 200 wären dass also 1600 Byte für die Längenangaben + 160000 Byte für die gespeicherten Referenzen, also stolze 158 KByte (so viel Speicher dürfte wohl auch jeder Rechner noch frei haben).

Ich sehe hier also eigentlich keine Probleme. Ich denke mal einfach, dass der Ball nicht mit vollem CPU-Takt wandert, dass dürfte sonst etwas nervige Unterschiede zwischen den Systemen mit sich bringen und auf kaum einem Rechner noch spielbar sein. Die Zeit die zwischen zwei Bewegungen des Balls vergeht sollte mehr als locker reichen um die hier beschriebene Kollisionsabfrage durchzuführen.