Breakout Clone - Kollision

[muschko]

Hallo FF,

ich bin gerade dabei einen Breakout-Clone zu programmieren. Klappt auch alles wunderbar soweit... Levels werden aus einer XML geladen und auch die Steine werden korrekt platziert. Bewegungen von Ball und Pedal besteht auch schon, jedoch hab ein bisschen Probleme mit der korrekten! Kollision.

Alle meine Steine liegen in einem Array und habe eine X&Y Koordinate. Ich prüfe jetzt im EnterFrame ob der Ball rechts, links, oben oder unten den Stein trifft.

PHP-Code:

// Wenn der Ball einen Stein trifft
if (ballRect.intersects(brickRect)) {

level.getBricks().splice(level.getBricks().indexOf(brick),1);

// Ball abprallen lassen
if (brickRect.contains(ballRect.x ,ballRect.top) || brickRect.contains(ballRect.x, ballRect.bottom)) {
ball.setYspeed(-(ball.getYspeed()));
break;
} else if (brickRect.contains(ballRect.left, ballRect.y) || brickRect.contains(ballRect.right, ballRect.y)){
ball.setXspeed(-(ball.getXspeed()));
} 


Das funktioniert zwar, aber auch nicht wirklich richtig. Mal wird der Ball komisch "abgeleitet" oder springt auch mal durch einen Stein hindurch. Gibt es nicht eine bessere Methodik um zu prüfen wo der Ball aufschlägt und auch korrekt wieder abprallt.

PS: Ist es performanter einen Timer zu benutzen anstatt eines EnterFrames?

lg

[hgseib]

seltsamer weisse passiert das allen ;-)

wenn sich der ball jeweils weiter bewegt, als deine mauer dick ist, dann springt er drüber.
entweder du musst öfters berechnen um kleinere weiter zu erhalten
oder du musst die geschwindigkeit reduzieren
oder du musst den befehl 'intersects' kicken und die schnittpunkte linie (ballbewegung) mit linie (mauer) selbst berechnen.

nur mit intersects ermittelst du auch nicht, wie weit dein ball eindrinnt bzw. ob er die mauersteine seitlich trifft; was dein 'komisch "abgeleitet" ' erklärt.

http://www.seibsprogrammladen.de/fra.../Schnittpunkte
http://www.seibsprogrammladen.de/fra...piel/Kleinkram <-- man muss ja auch mal angeben dürfen ;-)
http://www.seibsprogrammladen.de/fra.../Spiel/Engines <-- PinLines-Engine schnittpunkt berechnen, den reststahl abbrallen, damit wieder schnittpunkt berechnen, bis kein rest mehr da ist.

[muschko]

okay danke für die hinweiße
ich glaub ich werde nicht darum kommen mir die Schnittpunkte selbst zu berechnen, ich glaube das ist die beste Alternative von den 3en

eine Frage noch, wie hast du es in deinem Beispiel "mauer" gelöst?

[muschko]

ich habe mal probiert nun dein Linie-Linie Schnittpunkt Beispiel zu verstehen. Ich hab aber dazu ein paar Fragen.
Wann weiß denn die Methode wenn sich 2 Linien gekreuzt haben ? Und bei unserem Beispiel, woher wüsste er dann ob er links, rechts, oben oder unten getroffen wurde.
Und da ich 4 Punkte habe, müsste ich das 4x berechnen für jede Seitenline 1x oder wie
Ich blick es noch nicht so richtig.

Ich bräuchte mal ein Beispiel anhand eines Arrays von bricks mit einem Ball.

[thomas_E]

für ein klassisches Breakout brauchst du doch "nur" eine Kollisionsberechnung linie-Rechteck, komplexer sind die Formen doch nicht.

hier mal eine zweite Demo (swf && fla (CS4) sind im Anhang)

der Kern des ganzen ist folgende Funktion, und eine Erweiterung hiervon:
winkel zu xy && länge Bildschirmrand

PHP-Code:

var f:Number;

function hitTestRect(p:Point, v:Point, rect:Rectangle):Point
{
    var fx:Number, fy:Number, ox:Boolean, oy:Boolean, tx:Number, ty:Number;
    f = NaN;
    
    //vertical
    if (v.x == 0){
        if (v.y == 0 || p.x <= rect.left || p.x >= rect.right) return null;
        
        if (v.y > 0){
            if(p.y < rect.top){
                f = (rect.top - p.y) / v.y;
                return new Point(rect.top, p.y);
            }else if(p.y < rect.bottom){
                f = (rect.bottom - p.y) / v.y;
                return new Point(rect.bottom, p.y);
            }else{
                return null;
            }
        }else{
            if(p.y > rect.bottom){
                f = (rect.bottom - p.y) / v.y;
                return new Point(rect.bottom, p.y);
            }else if(p.y > rect.top){
                f = (rect.top - p.y) / v.y;
                return new Point(rect.top, p.y);
            }else{
                return null;
            }
        }
    }
    
    //horizontal
    if (v.y == 0){
        if (p.y <= rect.top || p.y >= rect.bottom) return null;
        
        if (v.x > 0){
            if(p.x < rect.left){
                f = (rect.left - p.x) / v.x;
                return new Point(p.x, rect.left);
            }else if(p.x < rect.right){
                f = (rect.right - p.x) / v.x;
                return new Point(p.x, rect.right);
            }else{
                return null;
            }
        }else{
            if(p.x > rect.right){
                f = (rect.right - p.x) / v.x;
                return new Point(p.x, rect.right);
            }else if(p.x > rect.left){
                f = (rect.left - p.x) / v.x;
                return new Point(p.x, rect.left);
            }else{
                return null;
            }
        }
    }
    
    
    //diagonal
    if (v.y > 0){
        if(p.y < rect.bottom){
            ty = (oy = (p.y < rect.top))? rect.top: rect.bottom;
        }else{
            return null;
        }
    }else{
        if(p.y > rect.top){
            ty = (oy = (p.y > rect.bottom))? rect.bottom: rect.top;
        }else{
            return null;
        }
    }
    
    if (v.x > 0){
        if(p.x < rect.right){
            tx = (ox = (p.x < rect.left))? rect.left: rect.right;
        }else{
            return null;
        }
    }else{
        if(p.x > rect.left){
            tx = (ox = (p.x > rect.right))? rect.right: rect.left;
        }else{
            return null;
        }
    }
    
    fx = (tx-p.x) / v.x;
    fy = (ty-p.y) / v.y;

    if( (ox && oy? fx>fy: fx<fy) ){
        f = fx;
        ty = p.y + v.y * fx;
        if(ty < rect.top || ty > rect.bottom) return null;
    }else{
        f = fy;
        tx = p.x + v.x * fy;
        if(tx < rect.left || tx > rect.right) return null;
    }
    
    return new Point(tx, ty);
} 


wirkt erstmal lang, aber wenn du genau hinsiehst besteht der fast nur aus verschachtelten Bedingungen und Funktionsabbrüchen.

die Variable f hab ich extra herausgestellt, da sie ebenfalls die Dauer bis zum treffer ausgibt, in frames (bei gleichem Vektor)

[muschko]

Wow danke! Soviel hätte ich gar nicht erwartet werde ich am Montag mal ausprobieren.

Gruß muschko

[ING]

hätte da auch noch was im angebot

war primär für sichtbarkeitstest entwickelt und ist schon ein tick älter aber seit dem für solche geschichten bei mir im einsatz, ist allerdings schon komplett OO umgesetzt und schlanker als die funktion von thomas_E

die klasse AABB (axis-aligned bounding box / achsen-ausgerichtete bounding box) verwaltet ein rechteck, mit der methode detectCollision() kann ein linienschnitttest mit dem rechteck durchgeführt werden.

die methode detectCollision() erwartet als ersten parameter ein objekt mit den eigenschaften x / y für die position sowie vx / vy für die geschwindigkeit / sichtweite etc, der zweite parameter ist ein array in dem das kollisionsobjekt eingetragen wird falls eine kollision stattfindet.

das kollisionsobjekt (klasse CollisionData) enthält sämtliche informationen wie das getroffene objekt, welche seite getroffen wurde, der genaue schnittpunkt und die distanz. besonders die distanz ist enorm nützlich, damit kann man sortieren, den reststrahl berechnen, die krafteinwirkung bestimmen usw.

package  
{
    public class AABB
    {
        private var tempData:CollisionData, tempRay:Ray = new Ray(0, 0, 0, 0);
        private var temp1:int, temp2:int, temp3:int, temp4:int;
        private var top:Ray, bottom:Ray, left:Ray, right:Ray;
        private var d:Number, t:Number, s:Number;
        
        public function AABB(x:Number, y:Number, width:int, height:int) {
            width  /= 2;
            height /= 2;
            
            top    = new Ray(x - width, y - height, x + width, y - height);
            bottom = new Ray(x - width, y + height, x + width, y + height);
            left   = new Ray(x - width, y - height, x - width, y + height);
            right  = new Ray(x + width, y - height, x + width, y + height);
        }
        
        public function detectCollision(source:*, resultData:Array) : void {
            tempRay.x1 = source.x;
            tempRay.y1 = source.y;
            tempRay.x2 = source.x + source.vx;
            tempRay.y2 = source.y + source.vy;
            
            if      (source.vx > 0 && intersectRays(tempRay, left))   pushData(resultData, 1);
            else if (source.vx < 0 && intersectRays(tempRay, right))  pushData(resultData, 2);
            
            if      (source.vy > 0 && intersectRays(tempRay, top))    pushData(resultData, 3);
            else if (source.vy < 0 && intersectRays(tempRay, bottom)) pushData(resultData, 4);
        }
        
        private function pushData(data:Array, side:int) : void {
            tempData.distance = Math.sqrt(Math.pow(tempData.x - tempRay.x1, 2) + Math.pow(tempData.y - tempRay.y1, 2));
            tempData.side = side;
            data.push(tempData);
        }
        
        private function intersectRays(r1:Ray, r2:Ray) : Boolean {
            temp1 = r1.x2 - r1.x1; temp2 = r1.y2 - r1.y1;
            temp3 = r2.x2 - r2.x1; temp4 = r2.y2 - r2.y1;
            d =  temp1 * temp4 - temp2 * temp3;
            t = -(r1.x1 * temp4 - r1.y1 * temp3 - r2.x1 * temp4 + r2.y1 * temp3) / d;
            s = -(r1.x1 * temp2 - r1.y1 * temp1 + temp1 * r2.y1 - temp2 * r2.x1) / d;
            if ((t > 0 && s > 0) && (t < 1 && s < 1)) {
                tempData = new CollisionData(this, r1.x1 + temp1 * t, r1.y1 + temp2 * t);
                return true;
            }
            return false;
        }
    }
}
 
// Hilfsklassen ######################################################
 
class CollisionData
{
    public var target:AABB;     // das getroffene objekt
    public var side:int;        // getroffene kante
    public var x:int, y:int;    // schnittpunkt
    public var distance:Number; // zurückgelegte distanz
        
    public function CollisionData(_target:AABB, _x:int, _y:int) {
        target = _target;
        x      = _x;
        y      = _y;
    }
}
    
class Ray
{
    public var x1:int, y1:int, x2:int, y2:int;
    
    public function Ray(_x1:int, _y1:int, _x2:int, _y2:int) {
        x1 = _x1;
        y1 = _y1;
        x2 = _x2;
        y2 = _y2;
    }
} 

verwendung:

// kollisionsDaten und boxes sind beides arrays
// in boxes sind die AABB objekte eingetragen, kollisionsDaten dient zum speichern der kollisionen
 
kollisionsDaten.length = 0; // kollisionsdaten zurücksetzen
for each (box in boxes) box.detectCollision(ball, kollisionsDaten);
            
if (kollisionsDaten.length) {  // kollision vorhanden
   kollisionsDaten.sortOn("distance", Array.NUMERIC); // objekte anhand der entfernung sortieren
   
   // in kollisionsDaten[0] befindet sich nun das kollisionsobjekt des zuerst getroffenen AABB objektes
   infoTXT.text = "Kollision mit " + kollisionsDaten[0].target + " | Getroffene Seite: " + kollisionsDaten[0].side;
} else {
   infoTXT.text = "Keine Kollision";
} 

möchte man die AABB objekte mit den sprites verknüpfen kann man die klasse einfach um eine eigenschaft erweitern, über die kollisionsdaten kommt man dann an das objekt oder man schreibt sich einen manager dafür.

das schöne an der methode ist das man innerhalb eines zyklus gleich alle potenziell getroffenen objekte zurück kriegt und sortieren kann, so kann man den ball zb. erst am zweiten block abprallen lassen und den zuerst getroffenen einfach nur zerstören (für power-ups etc).

demo
maus bewegen, klicken um den linienursprung neu zu setzen

[muschko]

Zitat von ING

möchte man die AABB objekte mit den sprites verknüpfen kann man die klasse einfach um eine eigenschaft erweitern, über die kollisionsdaten kommt man dann an das objekt oder man schreibt sich einen manager dafür.

das schöne an der methode ist das man innerhalb eines zyklus gleich alle potenziell getroffenen objekte zurück kriegt und sortieren kann, so kann man den ball zb. erst am zweiten block abprallen lassen und den zuerst getroffenen einfach nur zerstören (für power-ups etc).

demo
maus bewegen, klicken um den linienursprung neu zu setzen

Hallo ING,

erstmal ein riesen "Danke" an deine Klasse. Echt super, so kann ich das nämlich gleich öfters mal benutzen.

Jedoch habe ich noch ein Problem. Und zwar hab ich nun eine Liste mit AABB Objects ( Meine Steine ) und teste diese auf Kollisionen mit meinem Ball ( ganz normaler MovieClip ).
Oben und Links funktioniert die Kollision super, aber Rechts und Unten geht der Ball mindestens zuf Hälfte in den Stein hinein und prallt dann ab.
Ich denke du kannst mir helfen woran das liegen könnte.

Danke nochmal an alle
muschko

[ING]

Zitat von muschko

Oben und Links funktioniert die Kollision super, aber Rechts und Unten geht der Ball mindestens zuf Hälfte in den Stein hinein und prallt dann ab.
Ich denke du kannst mir helfen woran das liegen könnte.

das liegt vermutlich daran das bei der kollision nicht die breite des balls berücksichtigt wird, ab dem punkt wirds dann langsam wirklich kompliziert was die kollisionabfrage bewegter objekte angeht.

simpler workaround: einfach die bounding box entsprechend vergrößerst, ein ball.width dazu addieren reicht meistens schon.

du solltest auch berücksichtigen das die x und y werte die der klasse übergeben werden den mittelpunkt darstellen und nicht die linke obere ecke

[muschko]

Also die Steine erstelle ich nun so:

var brickAABB:AABB = new AABB(brick.x + brick.width/2 ,brick.y + brick.height/2, 30 , 20 ); 

Jetzt müsste ich es quasi so ändern, dass die Breite des Balls berücksichtigt wird:

var brickAABB:AABB = new AABB(brick.x + brick.width/2 ,brick.y + brick.height/2, 30 + ball.width , 20 ); 

Leider funktioniert das nicht so wie ich möchte. Denn manchmal werden in einer kompletten Steinreihe, nur von links und rechts "treffbar". Alle anderen funktionieren dann tabellos

Muss der Ball eigentlich auch ein AABB Object sein oder reicht da ein normaler MC?

Danke nochmal für deine Hilfe.

[ING]

also der ankerpunkt der objekte spielt auch eine rolle, wenn der überall zentriert ist sollte das aber eigentlich klappen

bin grad dabei die breakout spielmechanik nachzubauen und hab dabei auch bemerkt das es vorkommen kann das manchmal eine reihe aus einer bestimmten richtung ignoriert wird. problem ist wenn die "bewegungslinie" des balls pixelgenau auf die andere linie trifft, dabei kann eine kollision übersehen werden, umso langsamer die bewegung umso höher die wahrscheinlichkeit.

wie eingangs erwähnt, war das für sichtbarkeitstest entwickelt, da fiel mir das nie auf. hab das problem aber schon behoben, infolge dessen model ich das ganze grad aber nochmal etwas um und kann dir in den nächsten tagen bestimmt eine überarbeitete version anbieten wo das problem behoben ist

[muschko]

Zitat von ING

also der ankerpunkt der objekte spielt auch eine rolle, wenn der überall zentriert ist sollte das aber eigentlich klappen

bin grad dabei die breakout spielmechanik nachzubauen und hab dabei auch bemerkt das es vorkommen kann das manchmal eine reihe aus einer bestimmten richtung ignoriert wird. problem ist wenn die "bewegungslinie" des balls pixelgenau auf die andere linie trifft, dabei kann eine kollision übersehen werden, umso langsamer die bewegung umso höher die wahrscheinlichkeit.

wie eingangs erwähnt, war das für sichtbarkeitstest entwickelt, da fiel mir das nie auf. hab das problem aber schon behoben, infolge dessen model ich das ganze grad aber nochmal etwas um und kann dir in den nächsten tagen bestimmt eine überarbeitete version anbieten wo das problem behoben ist

Wow das wäre perfekt. Bin dir sehr dankbar
Genau was du beschrieben hast ist bei mir aufgetreten, das manche Steine nur von bestimmten Seiten getroffen werden konnten.

Sobald ich das dann fertig habe, kann ich dir ja mal meine Version von Breakout zeigen ... "Breax"

Grüße
muschko

[ING]

so, das ganze wurde nun einem ordentlichen refactoring unterzogen es sollte aber alles wie bisher funktionieren...

• es ist die klasse Bounds hinzugekommen auf der nun alles basiert, damit sind auch kollisionstest mit polygonen möglich. die klasse AABB erbt von ihr, erstellt auto. die rechteck-kanten und überschreibt die detectCollision methode da bei aabb's nur 2 linienschnitttests nötig sind.
• die detectCollision methode gibt jetzt zusätzlich ein bool zurück ob eine kollision stattgefunden hat (nützlich bei einzelnen tests), so ist auch der 2. parameter (das array was die kollisionsdaten aufnimmt) optional geworden. man kann aber ggf. auch hier über aabbObject.collision auf die kollisionsdaten zugreifen.
• AABB objekte können invertiert werden, so werden anstatt kollisionen von außen nur welche von innen erkannt, so können objekte in AABB objekten "gefangen" werden (stage begrenzung etc).
• performance macht auch einen guten eindruck, selbst bei 100 bricks, 2 bällen und 60 fps (= 12000 kollisionstests pro sekunde) ist auf meinem alten webrechner kein perfomanceverbrauch messbar

--------------------------------------------------

ich hab die breakout demo nur auf die schnelle umgesetzt, besonders das kollisionshandling (klasse: Ball, methode: projectCollision) hab ich nur hingeschlampt, die "engine" übernimmt zwar die kollisionserkennung aber das handling bleibt einem selbst überlassen. normalerweise kommen hier die geschichten wie ausfallswinkel & reststrahl berechnen, reststrahl auf weitere kollisionen testen usw. zum einsatz, das ist umso wichtiger umso kleiner der abstand zwischen den objekten wird.

das gute ist das das CollisionData objekt alle nötigen daten verfügbar macht, auch auf die daten der getroffenen seite (Ray objekt) kann man zugreifen, über kollisionsDaten.target.rays[kollisionsDaten.side].angle erhält man zb. den winkel der getroffenen seite. über die Ray klasse (vergleichbar mit einem Vector2D objekt) kann man das recht unkompliziert lösen, denk ich. werd das bei nächster gelegenheit auch nochmal in angriff nehmen, bis dahin überlasse ich jedem diesen spaß, bin aber für lösungen immer offen

Breakout Demo (3kb, breakout endlosschleife)
Download (3kb, demo code und kollisionerkennung (im package ing.bounds))

--------------------------------------------------

Zitat von muschko

Genau was du beschrieben hast ist bei mir aufgetreten, das manche Steine nur von bestimmten Seiten getroffen werden konnten.

habs ja erst aufgrund deines hinweises entdeckt, hätt die wahrscheinlichkeit für dieses ereignis aber niemals als so groß eingeschätzt als das ich sie hätte berücksichtigen müssen denn die "bewegungslinie" des balls muss sich innerhalb eines zyklus genau mit dem anfang und dem ende pixelgenau auf der linie befinden

lösung war denkbar einfach, die linie einfach um 1 pixel verlängern, dadurch entsteht zwar die möglichkeit auf bis zu einem pixel ungenauigkeit aber ich denke die ist verschnmerzbar

Zitat von muschko

Sobald ich das dann fertig habe, kann ich dir ja mal meine Version von Breakout zeigen ... "Breax"

unbedingt!

[milchreis]

Warum eigentlich nicht auf sowas wie box2d zurück greifen?

[muschko]

Zitat von milchreis

Warum eigentlich nicht auf sowas wie box2d zurück greifen?

Hat den ganz einfachen Hintergrund, dass ich das erst selber schreiben wollte und gar nicht gesehen habe, dass es doch relativ umfangreich ist. Auch den ganzen Overhead von einem großeren Framework wollte ich mir sparen.

Ich wäre dann als nächstes aber warscheinlich zu Box2D oder FlashPunk gegangen, wenn mir hier keiner geholfen hätte.

Danke nochmal an alle