Share
In dit deel van mijn serie over het maken van een aangepaste 2D-physics-engine voor je games, voegen we meer functies toe aan de impulsresolutie die we in het eerste deel hebben gebruikt. We zullen in het bijzonder kijken naar integratie, timestepping, een modulair ontwerp voor onze code en detectie van brede fasebotsing.
In de laatste post in deze serie behandelde ik het onderwerp impulsresolutie. Lees dat eerst, als je dat nog niet hebt gedaan!
Laten we direct naar de onderwerpen gaan die in dit artikel worden behandeld. Deze onderwerpen zijn alle benodigdheden voor elke half-fatsoenlijke physics-engine, dus het is nu een geschikt moment om meer functies te bouwen bovenop de kernresolutie uit het vorige artikel..
Integratie is heel eenvoudig te implementeren en er zijn heel veel gebieden op het internet die goede informatie bieden voor iteratieve integratie. Dit gedeelte laat meestal zien hoe een goede integratiefunctie geïmplementeerd kan worden, en wijst naar een aantal andere locaties voor verder lezen, indien gewenst.
Eerst moet bekend zijn wat versnelling eigenlijk is. De tweede wet van Newton bepaalt:
\ [Vergelijking 1: \\
F = ma \]
Dit stelt dat de som van alle krachten die op een object inwerken gelijk is aan de massa van dat object m vermenigvuldigd met zijn versnelling een. m is in kilogrammen, een is in meter / seconde, en F is in Newtons.
Deze vergelijking een beetje herschikken om op te lossen een opbrengsten:
\ [Vergelijking 2: \\
a = \ frac F m \\
\ \\ derhalve
a = F * \ frac 1 m \]
De volgende stap omvat het gebruik van versnelling om een object van de ene naar de andere locatie te verplaatsen. Omdat een game in afzonderlijke frames in een illusie-achtige animatie wordt weergegeven, moeten de locaties van elke positie bij deze discrete stappen worden berekend. Zie voor meer informatie over deze vergelijkingen: Erin Catto's Integration Demo van GDC 2009 en Hannu's aanvulling op Symplectic Euler voor meer stabiliteit in FPS-omgevingen.
Expliciete Euler (uitgesproken als "oiler") integratie wordt getoond in het volgende fragment, waar X is positie en v is snelheid. Houd er rekening mee dat 1 / m * F is versnelling, zoals hierboven uitgelegd:
// Expliciete Euler x + = v * dt v + = (1 / m * F) * dt
Accentsconagua
dt hier verwijst naar delta tijd. Δ is het symbool voor delta en kan letterlijk worden gelezen als "verandering in", of geschreven als Δt. Dus wanneer je het ziet dt het kan worden gelezen als "verandering in tijd". dv zou "verandering in snelheid" zijn. Dit zal werken, en wordt vaak gebruikt als een startpunt. Het heeft echter numerieke onnauwkeurigheden die we kunnen verwijderen zonder extra inspanningen. Dit is wat bekend staat als Symplectic Euler:
// Symplectische Euler v + = (1 / m * F) * dt x + = v * dt
Merk op dat alles wat ik deed de volgorde van de twee regels code herschikte - zie "> het bovengenoemde artikel van Hannu.
In dit bericht worden de numerieke onnauwkeurigheden van Explicit Euler uitgelegd, maar wees gewaarschuwd dat hij RK4 gaat behandelen, wat ik niet persoonlijk aanbeveel: gafferongames.com: Euler Onnauwkeurigheid.
Deze eenvoudige vergelijkingen zijn alles wat we nodig hebben om alle objecten te verplaatsen met lineaire snelheid en versnelling.
Omdat games met discrete tijdsintervallen worden weergegeven, moet er een manier zijn om de tijd tussen deze stappen op een gecontroleerde manier te manipuleren. Heb je ooit een game gezien die op verschillende snelheden werkt, afhankelijk van op welke computer het wordt gespeeld? Dat is een voorbeeld van een game met een snelheid die afhangt van het vermogen van de computer om het spel uit te voeren.
We hebben een manier nodig om ervoor te zorgen dat onze engine voor fysica alleen wordt uitgevoerd als een bepaalde hoeveelheid tijd is verstreken. Op deze manier, de dt dat wordt gebruikt binnen berekeningen is altijd exact hetzelfde aantal. Met exact hetzelfde dt waarde in uw code overal zal uw physics-engine daadwerkelijk worden deterministische, en staat bekend als a vaste tijdspanne. Dit is iets goeds.
Een deterministische fysica-engine is er één die altijd precies hetzelfde zal doen elke keer dat het wordt uitgevoerd, ervan uitgaande dat dezelfde ingangen worden gegeven. Dit is essentieel voor veel soorten games waarbij het spelen van games heel goed moet zijn afgestemd op het gedrag van de physics-engine. Dit is ook essentieel voor het debuggen van je physics engine, want om bugs te lokaliseren moet het gedrag van je motor consistent zijn.
Laten we eerst een eenvoudige versie van een vaste tijdspanne bekijken. Hier is een voorbeeld:
const float fps = 100 const float dt = 1 / fps float accumulator = 0 // in eenheden van seconden float frameStart = GetCurrentTime () // hoofdlus while (true) const float currentTime = GetCurrentTime () // Bewaar de verstreken tijd sinds het laatste frame begon met accumulator + = currentTime - frameStart () // Neem het begin van dit frame op StartStart = currentTime while (accumulator> dt) UpdateFhysics (dt) accumulator - = dt RenderGame ()
Dit wacht rond, waardoor het spel wordt weergegeven, totdat er genoeg tijd is verstreken om de fysica bij te werken. De verstreken tijd wordt vastgelegd en is discreet dt-grote brokken tijd worden uit de accumulator gehaald en verwerkt door de natuurkunde. Dit zorgt ervoor dat exact dezelfde waarde wordt doorgegeven aan de natuurkunde, wat er ook gebeurt, en dat de waarde die wordt doorgegeven aan de natuurkunde een nauwkeurige weergave is van de werkelijke tijd die in het echte leven voorbijgaat. Stukjes dt worden verwijderd uit de accumulator tot de accumulator is kleiner dan a dt brok.
Er zijn een aantal problemen die hier kunnen worden opgelost. De eerste betreft hoe lang het duurt om de fysica-update daadwerkelijk uit te voeren: wat als de natuurkundige update te lang duurt en de accumulator gaat elke gamerus hoger en hoger? Dit wordt de spiraal van de dood genoemd. Als dit niet is opgelost, zal uw motor snel tot stilstand komen als uw fysica niet snel genoeg kan worden uitgevoerd.
Om dit op te lossen, moet de motor eigenlijk gewoon minder natuurkundige updates uitvoeren als de accumulator wordt te hoog. Een eenvoudige manier om dit te doen zou zijn om de accumulator onder een willekeurige waarde.
const float fps = 100 const float dt = 1 / fps float accumulator = 0 // in eenheden seconden float frameStart = GetCurrentTime () // hoofdlus while (true) const float currentTime = GetCurrentTime () // Bewaar de verstreken tijd sinds de laatste frame begon accumulator + = currentTime - frameStart () // Neem het begin van dit frame op StartStart = currentTime // Vermijd de spiraal van dood en klem dt, dus klemmend // hoe vaak de UpdateFysics kunnen worden aangeroepen // een enkel spel lus. if (accumulator> 0.2f) accumulator = 0.2f terwijl (accumulator> dt) UpdatePhysics (dt) accumulator - = dt RenderGame ()
Nu, als een spel dat deze loop uitvoert ooit een soort van blokkering tegenkomt om welke reden dan ook, zal de fysica zichzelf niet verdrinken in een spiraal van dood. De game zal gewoon wat langzamer draaien, indien van toepassing.
Het volgende ding om op te lossen is vrij gering in vergelijking met de spiraal van de dood. Deze lus neemt dt brokken van de accumulator tot de accumulator is kleiner dan dt. Dit is leuk, maar er is nog steeds een beetje resterende tijd over in de accumulator. Dit vormt een probleem.
Neem aan dat accumulator blijft achter met 1/5 van a dt stuk elk frame. Op het zesde frame de accumulator zal genoeg resterende tijd hebben om nog een natuurkundige update uit te voeren dan alle andere frames. Dit zal resulteren in een frame per seconde of zo een iets grotere discrete sprong in de tijd uitvoeren, en kan erg opvallen in je spel.
Om dit op te lossen, is het gebruik van lineaire interpolatie Is benodigd. Als dit eng klinkt, maak je geen zorgen - de implementatie wordt getoond. Als u de implementatie wilt begrijpen, zijn er veel bronnen online voor lineaire interpolatie.
// lineaire interpolatie voor a van 0 tot 1 // van t1 tot t2 t1 * a + t2 (1.0f - a)
Hiermee kunnen we interpoleren (bij benadering) waar we ons bevinden tussen twee verschillende tijdsintervallen. Dit kan worden gebruikt om de status van een spel tussen twee verschillende fysica-updates te maken.
Met lineaire interpolatie kan de weergave van een motor in een ander tempo verlopen dan de engine voor fysica. Dit maakt een sierlijke omgang met de overgeblevenen mogelijk accumulator van de updates van de natuurkunde.
Hier is een volledig voorbeeld:
const float fps = 100 const float dt = 1 / fps float accumulator = 0 // in eenheden seconden float frameStart = GetCurrentTime () // hoofdlus while (true) const float currentTime = GetCurrentTime () // Bewaar de verstreken tijd sinds de laatste frame begon accumulator + = currentTime - frameStart () // Neem het begin van dit frame op StartStart = currentTime // Vermijd de spiraal van dood en klem dt, dus klemmend // hoe vaak de UpdateFysics kunnen worden aangeroepen // een enkel spel lus. if (accumulator> 0.2f) accumulator = 0.2f terwijl (accumulator> dt) UpdateFhysics (dt) accumulator - = dt const float alpha = accumulator / dt; RenderGame (alpha) void RenderGame (float alpha) voor shape in game do // bereken een geïnterpoleerde transformatie voor rendering Transform i = shape.previous * alpha + shape.current * (1.0f - alpha) shape.previous = shape.current shape .Render (i)
Hier kunnen alle objecten in het spel worden getekend op variabele momenten tussen discrete physics timesteps. Dit zal op elegante wijze alle fouten- en resttijdaccumulatie aan. Dit is feitelijk nog steeds een beetje achterliggend aan wat de fysica op dit moment heeft opgelost, maar bij het kijken naar de game run is alle beweging perfect geëffend door de interpolatie..
De speler zal nooit weten dat de weergave enigszins achter de natuurkunde zit, omdat de speler alleen weet wat hij ziet, en wat hij zal zien is perfect vloeiende overgangen van het ene frame naar het andere.
Je vraagt je misschien af: "waarom interpoleren we niet van de huidige positie naar de volgende?". Ik probeerde dit en het vereist de weergave om te "raden" waar objecten in de toekomst zullen zijn. Objecten in een fysica-engine maken vaak plotselinge veranderingen in beweging, zoals tijdens een botsing, en wanneer een dergelijke plotselinge verplaatsingsverandering wordt aangebracht, zullen objecten teleporteren als gevolg van onnauwkeurige interpolaties naar de toekomst.
Er zijn een paar dingen die elk object van de natuur nodig heeft. De specifieke dingen die elk object van de natuurkunde nodig heeft, kunnen echter enigszins van object tot object veranderen. Een slimme manier om al deze gegevens te organiseren is vereist, en er wordt van uitgegaan dat de geringere hoeveelheid code om te schrijven om een dergelijke organisatie te bereiken, gewenst is. In dit geval zou een modulair ontwerp goed van pas kunnen komen.
Modulair ontwerp klinkt waarschijnlijk een beetje pretentieus of te gecompliceerd, maar het is logisch en vrij eenvoudig. In deze context betekent 'modulair ontwerp' alleen dat we een natuurkundevoorwerp in afzonderlijke stukken willen splitsen, zodat we ze kunnen verbinden of loskoppelen, maar we vinden dat goed.
Een fysica-instantie is een object dat alle informatie bevat over een bepaald fysica-object. Het slaat de vorm (en) op waarop het object wordt weergegeven, massagegevens, transformatie (positie, rotatie), snelheid, koppel, enzovoort. Dit is wat onze lichaam zou moeten lijken op:
struct body Vorm * vorm; Transformeer tx; Materieel materiaal; MassData mass_data; Vec2 snelheid; Vec2 kracht; echte zwaartekrachtScale; ;
Dit is een goed startpunt voor het ontwerp van een fysica-lichaamsstructuur. Er zijn hier enkele intelligente beslissingen genomen die neigen naar een sterke code-organisatie.
Het eerste dat opvalt, is dat een vorm in het lichaam is opgenomen door middel van een wijzer. Dit vertegenwoordigt een losse relatie tussen het lichaam en zijn vorm. Een lichaam kan elke vorm bevatten en de vorm van een lichaam kan naar believen worden geruild. In feite kan een lichaam worden gerepresenteerd door meerdere vormen, en een dergelijk lichaam zou bekend staan als een "samengesteld", omdat het uit meerdere vormen zou bestaan. (Ik ga geen composieten behandelen in deze zelfstudie.)
Lichaams- en vorminterface. De vorm zelf is verantwoordelijk voor het berekenen van grensvormen, het berekenen van de massa op basis van dichtheid en rendering.
De mass_data is een kleine gegevensstructuur om massagerelateerde informatie te bevatten:
struct MassData float-massa; zweven inv_mass; // Voor rotaties (niet inbegrepen in dit artikel) zweeftraagheid; zweven inverse_inertia; ;
Het is prettig om alle massa- en intertia-gerelateerde waarden in één structuur op te slaan. De massa mag nooit met de hand worden geplaatst - massa moet altijd worden berekend door de vorm zelf. Massa is een nogal onintuïtief type waarde, en het handmatig instellen ervan kost veel tijd. Het is gedefinieerd als:
\ [Vergelijking 3: \\ Massa = dichtheid * volume \]
Wanneer een ontwerper een vorm meer "massief" of "zwaar" wil, moeten ze de dichtheid van een vorm wijzigen. Deze dichtheid kan worden gebruikt om de massa van een vorm te berekenen op basis van het volume. Dit is de juiste manier om de situatie aan te pakken, omdat de dichtheid niet wordt beïnvloed door het volume en nooit zal veranderen tijdens de looptijd van het spel (tenzij specifiek ondersteund met speciale code).
Enkele voorbeelden van vormen zoals AABB's en cirkels zijn te vinden in de vorige tutorial in deze serie.
Al dit gepraat over massa en dichtheid leidt tot de vraag: waar ligt de dichtheidswaarde? Het bevindt zich in de Materiaal structuur:
struct Materiaal float density; vlotter restitutie; ;
Zodra de waarden van het materiaal zijn ingesteld, kan dit materiaal worden doorgegeven aan de vorm van een lichaam, zodat het lichaam de massa kan berekenen.
Het laatste dat vermeldenswaard is, is het gravity_scale. Zwaartekracht voor verschillende objecten schalen is zo vaak nodig voor het tweaken van de gameplay dat het het beste is om gewoon een waarde in elk lichaam op te nemen, specifiek voor deze taak.
Sommige nuttige materiaalinstellingen voor algemene materiaalsoorten kunnen worden gebruikt om een te construeren Materiaal object van een opsommingswaarde:
Rock Density: 0.6 Restitutie: 0.1 Wood Density: 0.3 Restitutie: 0.2 Metal Density: 1.2 Restitutie: 0.05 BouncyBall Density: 0.3 Restitutie: 0.8 SuperBall Density: 0.3 Restitutie: 0.95 Pillow Density: 0.1 Restitutie: 0.2 Static Density: 0.0 Restitutie: 0.4
Er is nog iets om over te praten in de lichaam structuur. Er is een data-lid gebeld dwingen. Deze waarde begint bij nul aan het begin van elke natuurkundige update. Andere invloeden in de physics engine (zoals zwaartekracht) zullen toevoegen Vec2 vectoren hierin dwingen data lid. Vlak voor integratie zal al deze kracht worden gebruikt om de versnelling van het lichaam te berekenen en tijdens de integratie worden gebruikt. Na integratie dit dwingen gegevenslid wordt op nul gezet.
Dit staat toe dat elk aantal krachten op een object inwerkt wanneer zij dat nodig achten, en er hoeft geen extra code te worden geschreven wanneer nieuwe soorten krachten op objecten moeten worden toegepast.
Laten we een voorbeeld nemen. Stel dat we een kleine cirkel hebben die een heel zwaar object vertegenwoordigt. Deze kleine cirkel vliegt rond in het spel, en het is zo zwaar dat het er nog iets naar toe trekt. Hier is een ruwe pseudocode om dit aan te tonen:
HeavyObject-object voor body in game do if (object.CloseEnoughTo (body) -object.ApplyForcePullOn (body)
De functie ApplyForcePullOn () zou misschien een kleine kracht kunnen gebruiken om de lichaam richting de HeavyObject, alleen als het lichaam is dichtbij genoeg.
Het maakt niet uit hoeveel krachten worden toegevoegd aan de dwingen van een lichaam, omdat ze allemaal optellen tot een enkele gesommeerde krachtvector voor dat lichaam. Dit betekent dat twee krachten die op hetzelfde lichaam inwerken elkaar potentieel kunnen opheffen.
In het vorige artikel in deze serie werden collision detection routines geïntroduceerd. Deze routines lagen eigenlijk los van wat bekend staat als de "smalle fase". De verschillen tussen brede fase en smalle fase kunnen vrij eenvoudig worden onderzocht met een Google-zoekopdracht.
(In het kort: we gebruiken detectie van brede fasebotsing om uit te vissen welke paren objecten macht botsen, en vervolgens de detectie van de fase-botsing om te controleren of ze daadwerkelijk zijn botsen.)
Ik zou graag een voorbeeldcode willen geven, samen met een uitleg over hoe een brede fase van \ (O (n ^ 2) \) tijd-complexiteitspaarberekeningen te implementeren.
\ (O (n ^ 2) \) betekent in feite dat de tijd die nodig is om elk paar potentiële botsingen te controleren, afhangt van het kwadraat van het aantal objecten. Het maakt gebruik van Big-O-notatie.Omdat we met paren objecten werken, is het handig om een structuur te maken zoals:
struct Pair body * A; lichaam * B; ;
Een brede fase moet een aantal mogelijke botsingen verzamelen en allemaal opslaan Paar structuren. Deze paren kunnen vervolgens worden doorgegeven aan een ander deel van de motor (de smalle fase) en vervolgens worden opgelost.
Voorbeeld brede fase:
// Genereert de paarlijst. // Alle vorige paren worden gewist wanneer deze functie wordt aangeroepen. void BroadPhase :: GeneratePairs (void) paren.help () // Cacheruimte voor AABB's die worden gebruikt bij de berekening // van het begrenzingsvak van elke vorm AABB A_aabb AABB B_aabb voor (i = bodies.begin (); i! = bodies .end (); i = i-> volgende) for (j = bodies.begin (); j! = bodies.end (); j = j-> volgende) Body * A = & i-> GetData () Hoofdtekst * B = & j-> GetData () // Skip overslaan met zelf als (A == B) doorgaan A-> ComputeAABB (& A_aabb) B-> ComputeAABB (& B_aabb) if (AABBtoAABB (A_aabb, B_aabb)) paren.push_back (A, B)
De bovenstaande code is vrij eenvoudig: controleer elk lichaam tegen elk lichaam en sla zelfcontroles over.
Er is één probleem uit de laatste sectie: veel duplicaatparen worden geretourneerd! Deze duplicaten moeten uit de resultaten worden gehaald. Er is enige bekendheid met sorteeralgoritmen vereist als u geen sorteerbibliotheek beschikbaar hebt. Als je C ++ gebruikt, heb je geluk:
// Sorteer paren om dubbele sortering te tonen (pairs, pairs.end (), SortPairs); // Wachtrij-manifolds voor het oplossen van int i = 0; terwijl ik < pairs.size( )) Pair *pair = pairs.begin( ) + i; uniquePairs.push_front( pair ); ++i; // Skip duplicate pairs by iterating i until we find a unique pair while(i < pairs.size( )) Pair *potential_dup = pairs + i; if(pair->A! = Potential_dup-> B || paar-> B! = potential_dup-> A) pauze; I ++;
Na het sorteren van alle paren in een specifieke volgorde kan worden aangenomen dat alle paren in de paren container bevat alle duplicaten naast elkaar. Plaats alle unieke paren in een nieuwe container genaamd uniquePairs, en het klaren van duplicaten is voltooid.
Het laatste ding om te vermelden is het predicaat SortPairs (). Deze SortPairs () functie is wat feitelijk wordt gebruikt om het sorteren uit te voeren, en het kan er als volgt uitzien:
bool SortPairs (Pair lhs, Pair rhs) if (lhs.A < rhs.A) return true; if(lhs.A == rhs.A) return lhs.B < rhs.B; return false;De voorwaarden
lhs en rhs kan worden gelezen als "linkerzijde" en "rechterzijde". Deze termen worden vaak gebruikt om te verwijzen naar parameters van functies waar dingen logisch gezien kunnen worden als de linker- en rechterkant van een of andere vergelijking of algoritme. gelaagdheid verwijst naar de handeling waarbij verschillende objecten nooit met elkaar botsen. Dit is essentieel omdat kogels die door bepaalde objecten worden afgevuurd geen invloed hebben op bepaalde andere objecten. Spelers in het ene team willen bijvoorbeeld dat hun raketten de vijanden beschadigen, maar niet elkaar.
Gelaagdheid kan het beste worden geïmplementeerd met bitmasks - zie Een Quick Bitmask-instructie voor programmeurs en de Wikipedia-pagina voor een snelle introductie, en het gedeelte Filtering van de Box2D-handleiding om te zien hoe die engine bitmaskers gebruikt.
Lagen moet in de brede fase worden gedaan. Hier zal ik gewoon een voorbeeld van een voltooide brede fase plakken:
// Genereert de paarlijst. // Alle vorige paren worden gewist wanneer deze functie wordt aangeroepen. void BroadPhase :: GeneratePairs (void) paren.help () // Cacheruimte voor AABB's die worden gebruikt bij de berekening // van het begrenzingsvak van elke vorm AABB A_aabb AABB B_aabb voor (i = bodies.begin (); i! = bodies .end (); i = i-> volgende) for (j = bodies.begin (); j! = bodies.end (); j = j-> volgende) Body * A = & i-> GetData () Hoofdtekst * B = & j-> GetData () // Skip overslaan met zelf als (A == B) doorgaan // Alleen overeenkomende lagen worden overwogen als (! (A-> lagen & B-> lagen)) worden voortgezet; A-> ComputeAABB (& A_aabb) B-> ComputeAABB (& B_aabb) if (AABBtoAABB (A_aabb, B_aabb)) paren.push_back (A, B)
Gelaagdheid blijkt zowel zeer efficiënt als heel eenvoudig te zijn.
EEN halve ruimte kan als één kant van een regel in 2D worden bekeken. Het detecteren of een punt zich aan de ene of de andere kant van een lijn bevindt, is een vrij algemene taak en moet grondig worden begrepen door iemand die zijn eigen physics-engine maakt. Het is jammer dat dit onderwerp nergens op het internet echt op een zinvolle manier wordt behandeld, althans van wat ik heb gezien - tot nu toe natuurlijk!
De algemene vergelijking van een regel in 2D is:
\ [Vergelijking 4: \\
Algemeen \: vorm: ax + by + c = 0 \\
Normaal \: tot \: regel: \ begin bmatrix
een \\
b \\
\ End bmatrix \]
Merk op dat, ondanks zijn naam, de normale vector niet noodzakelijkerwijs genormaliseerd is (dat wil zeggen dat hij niet noodzakelijkerwijs een lengte van 1 heeft).
Om te zien of een punt zich aan een bepaalde kant van deze lijn bevindt, hoeft u alleen maar het punt in het X en Y variabelen in de vergelijking en controleer het teken van het resultaat. Een resultaat van 0 betekent dat het punt op de lijn ligt, en positief / negatief betekent verschillende kanten van de lijn.
Dat is alles wat er is! Dit wetende dat de afstand van een punt tot de lijn eigenlijk het resultaat is van de vorige test. Als de normale vector niet genormaliseerd is, wordt het resultaat geschaald door de grootte van de normale vector.
Inmiddels kan een complete, zij het eenvoudige, fysica-engine volledig vanaf nul worden opgebouwd. Geavanceerdere onderwerpen zoals wrijving, oriëntatie en dynamische AABB-structuur kunnen worden behandeld in toekomstige zelfstudies. Stel vragen of geef hieronder commentaar, ik geniet ervan ze te lezen en te beantwoorden!
