[Alg] advanced collision detection (uitvoer in flashMX) *

[Verwijderd]

Ik ben bezig met een collision detection voor een spel wat ik aan 't schrijven ben. Omdat het om sprites gaat is het dus moeilijk bepalen wanneer er nou precies een collision optreed. Daarom bedacht ik eerst de volgende manier: Hij kijkt eerst met een hitTest of 2 objecten colliden, zo ja, dan gaat hij naar het volgende stadium van de detectie.

Detectie 2 gaat als volgt : een sprite is ook nog eens in 4 vlakken ingedeeld genummer 0 t/m 4. De twee objecten kijken in welke vlakken de collision plaatsvind, bv objectA heeft hem in vlak 3, en objectB in vlak 2. Wanneer dit bekeken is springt de functie naar een nog dieper stadium.

Detectie 3 is het zogenaamde advanced deel. Ik had eerst bedacht om langs randen van de sprites kleine vierkantjes te tekenen en opdezelfde manier als detectie 2 te kijken of er weer een collision plaatsvind. Op zich werkte deze methode al behoorlijk aardig; alleen ben ik bang dat er bij meerdere objecten snelheidsproblemen optreden.

Daarom bedacht ik een nieuwe manier, die als volgt gaat:
Elke sprite heeft op zijn hoekpunten een lege MC staan. Wanneer detectie-fase 3 ingaat gaat flash tussen elke punten de zogenaamde lijn-formule noteren (Y = M*X + B, hierbij worden M en B verkregen door de X en Y waardes in te vullen); door de formule Ma*Xa+Ba = Mb*Xb+Bb op te lossen zou er een mogelijke X coordinaat uit moeten rollen waarbij de lijnen van de twee objecten elkaar snijden (en dus een botsing plaatsvind) ... er moet dus nog wel controleert worden deze gevonden X binnen de waardes van de lijnen past.

De code voor het geheel staat hieronder:

code:

function collisionDetection (objA, objB, repeater, nrA, nrB) {
    output = "";
    // stage 1
    if ((repeater == 1) && (objA.hitTest(objB))) {
        collisionDetection (objA, objB, 2);
    }
    // stage 2
    else if (repeater == 2) {
        for (i=0;i<4;i++) {
            for (j=0;j<4;j++) {
                if (objA["bigHit" + i].hitTest(objB["bigHit" + j]))
                    collisionDetection (objA, objB, 3, i, j);
            }
        }
    }
    // stage 3
    else if (repeater == 3) {
        hitsA = objA.lines.length / 4; hitsB = objB.lines.length / 4;
        minA = Math.floor (hitsA * nrA); maxA = Math.round (hitsA * (nrA + 1));
        minB = Math.floor (hitsB * nrB); maxB = Math.round (hitsB * (nrB + 1));

        aRadA = ((objA._rotation) * Math.PI) / 180;
        aRadB = ((objB._rotation) * Math.PI) / 180;

        for (i=minA;i<maxA;i++) {
            Ax1 = (objA.lines[i][0] * Math.cos(aRadA) - objA.lines[i][2] * Math.sin(aRadA)) + objA._x
            Ax2 = (objA.lines[i][1] * Math.cos(aRadA) - objA.lines[i][3] * Math.sin(aRadA)) + objA._x;
            Ay1 = (objA.lines[i][0] * Math.sin(aRadA) + objA.lines[i][2] * Math.cos(aRadA)) + objA._y;
            Ay2 = (objA.lines[i][1] * Math.sin(aRadA) + objA.lines[i][3] * Math.cos(aRadA)) + objA._y;
            Am = (Ay1 - Ay2) / (Ax1 - Ax2);
            Ab = Ay1 - (m * Ax1);

            for (j=minB;j<maxB;j++) {
                Bx1 = (objB.lines[j][0] * Math.cos(aRadB) - objB.lines[j][2] * Math.sin(aRadB)) + objB._x;
                Bx2 = (objB.lines[j][1] * Math.cos(aRadB) - objB.lines[j][3] * Math.sin(aRadB)) + objB._x;
                By1 = (objB.lines[j][0] * Math.sin(aRadB) + objB.lines[j][2] * Math.cos(aRadB)) + objB._y;
                By2 = (objB.lines[j][1] * Math.sin(aRadB) + objB.lines[j][3] * Math.cos(aRadB)) + objB._y;
                Bm = (By1 - By2) / (Bx1 - Bx2);
                Bb = By1 - (m * Bx1);

                myB = Ab - Bb;
                myM = Am - Bm;
                X = (-myB) / myM;

                if ((Ax1 > Ax2) && (Ax1 > X) && (Ax2 < X)) {
                    if ((Bx1 > Bx2) && (Bx1 > X) && (Bx2 < X)) {
                        output="collision";
                    }
                    else if ((Bx1 < Bx2) && (Bx1 < X) && (Bx2 > X)) {
                        output="collision";
                    }               
                }
                else if ((Ax1 < Ax2) && (Ax1 < X) && (Ax2 > X)) {
                    if ((Bx1 > Bx2) && (Bx1 > X) && (Bx2 < X)) {
                        output="collision";
                    }
                    else if ((Bx1 < Bx2) && (Bx1 < X) && (Bx2 > X)) {
                        output="collision";
                    }                                   
                }
            }
        }
    }
}

een toelichting; de punten staan in de MC van de sprite. Om daarom geldige lijnformules te krijgen moet er gekeken worden of de sprite is geroteerd (en hierop nieuwe lokale X en Y coordinaten berekenen), deze vervolgens omrekenen naar globaal toe door de sprite zijn X en Y erbij op te tellen. Verder zijn er twee arrays welke bepaalde standaard waarden hebben waar vanuit gerekend moet gaan worden.

Helaas werkt dit hele boekwerk nog niet! Weet iemand de oplossing of dit wel ene goede manier van collision detection is, of het beter of anders kan, of het sneller kan etc. Please help!! B-top? Seraph?

[oh,when?]

dus als ik het goed begrijp, moet je ook nog weten vanaf welke kant het vierkant word geraakt? is heteen evenzijdige vierhoek?

Want dan zou ik het volgende doen

ieder object weet zijn x en y positie, en zijn hoogte en breedte. nu kan je op verschillende manieren collision detection uitvoeren, maar het gevaar zit natuurlijk dat je (n2--n)/2 checks gaat uitvoeren. als je nu gaat sorteren op een as, bijvoorbeeld de x of y as, kun je heel makkelijk de sprites sorteren als een lijst op zijn y waarden, en dan alleen te checken op zijn buren in die lijst, maal zijn hoogte of breedte. Deze methode is ook wel bekend als axis sorting. Een andere methode heet de sector method, wat toepasselijker is in dit verhaal. Deze methode gaat uit dat je een object verdeeld in een grid van sectoren ( of het scherm / playfield dat kan ook ) en alleen in die sector doe je een standard collisie detectie ( dus sprite1 checked sprite2 en sprite3, sprite 2 checked sprite3 ) moeilijkheid zit hem natuurlijk in dat een sprite bijvoorbeeld in meerdere sectoren zou kunnen vallen. lees eens wat oude geometry wiskunde door, daarin worden zulke dingen tot in de treure behandeld.

goed terug naar de praktijk. wat ik zou aanraden is om de hoek te berekenen tussen de 2 objecten, want ieder gelijkhoekig vierkant is makkelijk te verdelen in 4 delen, 0-90 | 90-180 | 180-270 | 270-360

stel de hoek tussen de 2 punten VOORDAT ze elkaar raken is 0.97 radianen, convert dat naar graden:

JavaScript:

var d = .97 * 180 / Math.PI;

geeft 56 terug. 56 graden, dat valt in 0-90 vlak. Voor de andere sprite is dat precies het tegenover gestelde, namelijk 236, dat valt dus in het tegenovergestelde vlak

code:

     ---
    |   |
    |   |
     ---
 ---
|   |
|   |
 ---

( mocht je waardes krijgen boven de 360 en onder de 0 dan kun je de volgende one-liner gebruiken

JavaScript:

var a = ((a %= 360 ) ? a + 360 : a;

waar a natuurlijk de angle is. )

iig...zo kun je zonder de vier kanten te checken weten vanaf welke kant een sprite word geraakt. hoop dat ik een beetje duidelijk ben geweest..zo niet..dan leg ik het op een andere manier uit.

HTH

[Verwijderd]

Het probleem is dat ik met sprites zitten die vreemde hoeken hebben en niet vierkant zijn ... ik probeer dus met lijn-formules aan elkaar gelijk te zetten te kijken of er een collision plaatsvind, dit is erg nauwkeurig, weinig CPU-power, en minder werk voor de developers.

Ik heb de code in de eerst post aangepast; er zaten wat klleine foutjes in en wat zaken wat sneller kon ... de lines array worden gezet in de MC van de sprites en hebben de volgende inhoud : lines[i] = {x1, x2, y1, y2} ... ik kan de a en m nog niet setten omdat deze bij elke rotatie veranderen, en daarom berekent die hem nu elke keer opnieuw in de derde fase van de detectie. Ik maak de waardes globaal door de X en Y van de sprite bij deze waarden op te tellen, zo krijg je naar mijn gevoel een geldige vergelijking.

op http://www2.hku.nl/~patrick staat de SWF

Als ouput krijg je de 2 lijnformules en de mogelijke waarde van X van een botsing ... als deze waarde binnen de Xgrenzen van beide lijnen zit is er een collision. Tot het berekenen van de lijnformules gaat het goed. Ik heb beide getest en ze gaven goede formules ... ook wanneer je handmatig de X in beide formules in de output stopt krijg je dezelfde Y-waardes; dus ook tot hier gaat het goed!

Later kan ik met de gevonden X kijken waar elk object word geraakt, en zo een realistische botsing berekenen (moment, impuls) ... Maar ja, dan moet de collision detection eerst wel werken ... Weet iemand misschien ook hoe het sneller kan?

P.S. druk ook eens op de <q> en <w>

[oh,when?]

Volgens mij pak je het allemaal wat moeilijk aan dan het in feite is Je moet meer aan objecten denken, een tank is een object, een loop van een tank is een object, en de kogel die hij schiet is een object. Ieder object weet zijn hoogte en breedte ( dat mag ik hopen iig ) en bevat bepaalde methodes en eigenschappen ( kanbewegen, kanontploffen, heeftkanon ) etc etc

Bind nu sommige methodes aan zogenaamde events, bijvoorbeeld keyevents of mouseevents en zo is het hele zaakje te besturen. Wat je nu ziet is dat je een hele lap code hebt, die helemaal niet overzichtelijk is, en om het woord maar ff in de groep te gooien, niet object georienteerd genoeg. Dat zie je ook in het voorbeeld, want ik kan nu maar 1 tank tegelijk besturen.

Ik zal pogen van het weekend een simpel en werkend voorbeeld te sturen van bovenstaande verhaal, verder raad ik je aan om op internet te zoeken over event handling ( in Flash MX ) of het boek van branden en samuel te lezen.

[Pelle]

moved.to/anderekantvandeschutting

(voor meer info over het waarom: Niveau /13 )

[Verwijderd]

Ik heb gebruik gemaakt van Listeners op de toetsen. Dat je de tweede tank niet kan besturen komt heel simpel omdat ik hieruit de Listeners heb verwijderd. Ook bestaat de tank uit verschillende eigenschappen; zwaarte, snelheid, rotatie etc. welke in de MC van tank staan. Ik kan je best de .FLA toesturen zodat je precies kan zien wat er gebeurt, en ja dan zie je ook het wel degelijk OO genoeg is.

[.oisyn]

ok, eerst even inventariseren wat je nu eigenlijk wilt, om je probleem gebied af te bakenen

Wat voor collision detection wil je? Puur gebaseerd op een bepaald tijdstip (dus object bewegen, en dan kijken of ie een ander object snijdt), of continuous tussen intervallen (een object heeft een positie en een richting, en dan wordt gekeken hoever ie kan bewegen zonder te botsen)

Welke vorm hebben je sprites? Zijn ze rechthoekig, zijn het convex polygonen (ronde vormen zeg maar), of zijn het concave polygonen (vormen met 'gaten' erin)

[Verwijderd]

Ik maak gebruik van sprites; deze word constant gecontroleerd of de bounding box van de een de ander overlapt. Zo ja, dan gaat een nauwekeurige detectie in zijn werk. Deze maakt gebruik van de line equations. Op elke hoek van de sprite staat een lege movieclip, deze worden gebruikt om denkbeeldige lijnen te creeeren, en om zo de lijnformules te maken.

Tot zover gaat het aardig goed, de lijnformules kloppen als ik deze bekijk via een output; en er komen ook geldige X waardes uit.

De X waarde die word gegenreert is de waarde waar de twee formules van mogelijk snijdende lijnen gelijk zijn. Als deze X dan ook nog binnen de X waarden van beide lijnen valt dan snijden de lijnen en is er een collision.

[.oisyn]

ik wil niet weten hoe je het doet, ik wil weten wat je wilt bereiken (zie mijn vorige post)

[Verwijderd]

ik wil dat er collision detection tussen mijn sprites is (zie mijn URL);

[.oisyn]

ah ok, collision detection op 2 convex polygonen
Dat is het best op te lossen met het separating axis theorem. Dit is gebaseerd op het feit dat als 2 convexe objecten elkaar niet snijden, er dan een vlak (lijn in dit geval, het is 2d) te vinden is die die 2 objecten scheiden. Deze lijn loopt evenwijdig aan
1) een edge van A
2) een edge van B
3) een edge gemaakt uit een hoekpunt van A en een hoekpunt van B

Testen of een edge een mogelijke scheidingslijn vormt doe je als volgt:
Je berekente eerst de normaal van de edge (een lijn die daar loodrecht op staat dus). Dan projecteer je de 2 objecten op deze lijn. Dat doe je door voor elk punt van elk object het inwendig produkt (dotproduct) te nemen van dat punt en de normaal. Als je de lus langs gaat voor object A hoef je alleen de minimale en maximale waarde bij te houden. Object A geprojecteerd op de normaal loopt dan van min naar max. Ditzelfde doe je met object B. Dan kun je testen of [A^min, A^max] overlapt met [B^min, B^max]. Zo niet, dan heb je een edge gevonden die de 2 objecten scheidt en is er dus geen collision. Overlappen de waarden wel, dan moet je de andere edges nog testen. Zijn alle edges getest en er zijn alleen maar overlappingen gevonden dan is er een collision.

Deze methode is natuurlijk te optimaliseren door eerst een bounding volume te testen, zoals een box als je al deed, of een cirkel (een cirkel is vrij makkelijk, gewoon kijken of de afstand van het middelpunt van A tot het middelpunt van B groter is dan de stralen van de 2 objecten bij elkaar opgeteld)

[.oisyn]

tekeningetje erbij om het duidelijk te maken:

[Genoil]

wow dit is de shit .oisyn, maar ik snap er geen hol van. meeste tutorails wat dit betreft gaan ook gelijk over 3D, dus nog complexer. zit er evt. in dat je dit voor de wiskundig ietsje minder begaafden uitwerkt en in de FAQ stopt? ik weet zeker dat ik dit nog een keer nodig ga hebben . En nu wil ik het wel es echt snappen ipv van sourcecode rippen

[.oisyn]

Het is ook eigenlijk een 3d iets, maar het is voor meerdere dimensies toe te passen

Ik wilde sowieso nog een algemene collision detection tutorial schrijven, met de nadruk op 3d dan weliswaar. Maar goed, dit soort dingen vereisen nou eenmaal een bepaalde wiskundige kennis (vector en matrix algebra vooral). Maar als ik vanavond nog tijd heb post ik hier wel even een uitleg in leken-taal