physics & tijdspannes

[Verwijderd]

hallo menschen, ik heb een probleem bij het bedenken van de physics engine van mn fantastische voetbalspel

stel ik heb een object (bal? ) dat met 10 km/u een kant op gaat en ik heb in mijn spel een process() functie die dat fixed, met als parameter de tijd die er is verstreken sinds de laatste keer dat de process() functie werd aangeroepen.

stel nu, mijn spel is enorm traag, en er is een uur verstreken als de process() functie wordt aangeroepen.. de bal zou dan 10 km verderop moeten worden gezet (even uitgaande van een perpetuum mobile bal )

echter, stel dat er op 5 km van het beginpunt een muurtje zit. dat zou hij dan alleen kunnen constateren als mn spel vloeit, als de process() functie elke $weinig ms wordt aangeroepen. kortom, op trage computers zou de collision detection ed nogal kunnen falen, en dat kan natuurlijk niet de bedoeling zijn.

ik zou elke ms van dat uur langs kunnen gaan in de process() functie, maar dat zou zo traag worden dat er dan intussen alweer een uur is verstreken.. dan krijg ik een infinite bereken loop
bovendien moeten dan alle andere objecten tegelijkertijd elke keer een millisec verder worden berekend, en dat wordt qua opzet van de code weer lastig.

iemand enig idee hoe zoiets normaliter wordt geprogrammeerd?

[Verwijderd]

Wellicht kun je om de zoveel (milli)seconden het pad van het object doorrekenen en testen of er collisions plaatsvinden en het gedrag dan daarop afstemmen. De afgelegde afstand kun je overigens nauwkeuriger bepalen door (ipv de snelheids-vector te vermenigvuldigen met een bepaalde tijdspanne) de integraal te nemen over de snelheid als functie van de tijd (lijkt me).

[Verwijderd]

ik moet toegeven dat ik niet weet wat integralen zijn, zal ik eens even induiken..

maar het gevaar met elke x ms de boel doorrekenen is dat als het doorrekenen te lang duurt, de volgende update nog meer doorrekeningen vraagt (er is dan immers weer meer tijd verstreken) en dat het spel uiteinelijk 'grind to a halt' als je cpu niet rap genoeg is..

[Adion]

Het lijkt me dat je collision detection functie gewoon steeds het volledige pad tussen de eerste positie van de bal en de nieuwe positie moet bekijken, of er nu een klein stukje of een groot stuk afstand tussen zit.

[.oisyn]

Wat Adion zegt is een oplossing (en een vrij simpele in deze, lineaire sphere sweeps zijn niet zo complex). Echter, je probeert een symptoom van een ernstig probleem weg te moffelen. Doorgaans werken echte physics engines het beste met een redelijk vaste stapgrootte. Als de tijd tussen twee frames veel groter is dan deze stapgrootte (door andere processen zoals rendering, AI, etc.), dan wordt de frame opgedeeld in kleinere stapgrootte waarin puur de physics loop plaatsvindt. Als het voorkomt dat je physics engine het systeem is dat de boel zoveel ophoudt dan ben je sowieso verkeerd bezig, en kun je beter stellen dat je computer niet geschikt is om de berekeningen te doen

[marcieking]

.oisyn schreef op woensdag 27 juni 2007 @ 23:28:
Wat Adion zegt is een oplossing (en een vrij simpele in deze, lineaire sphere sweeps zijn niet zo complex). Echter, je probeert een symptoom van een ernstig probleem weg te moffelen. Doorgaans werken echte physics engines het beste met een redelijk vaste stapgrootte. Als de tijd tussen twee frames veel groter is dan deze stapgrootte (door andere processen zoals rendering, AI, etc.), dan wordt de frame opgedeeld in kleinere stapgrootte waarin puur de physics loop plaatsvindt. Als het voorkomt dat je physics engine het systeem is dat de boel zoveel ophoudt dan ben je sowieso verkeerd bezig, en kun je beter stellen dat je computer niet geschikt is om de berekeningen te doen

Ik meen laatst gelezen te hebben dat veel engines juist precies één keer per frame uitrekenen hoever een object verschoven is en wat dat voor invloed heeft op de omgeving, en niet bij een te lange frametime tussendoor gaan rekenen. Dat is ook de reden dat er volgens sommigen "magische framerates (125 of 333fps)" zijn waarop je verder kunt springen e.d.: als zo vaak per seconden een berekening wordt gedaan worden getallen naar boven afgerond en spring je verder.

[.oisyn]

Je kunt de physics code van Quake die floats afrondt naar ints om bandbreedte te besparen waardoor je dat soort effecten krijgt nauwelijks een physics engine noemen . Veel games gebruiken helemaal geen full blown physics engine die daadwerkelijke mechanica nabootst, maar gewoon een erg versimpelde modellering van de werkelijkheid omdat dat sneller en doeltreffender is, zonder dat je het verschil echt ziet. In Quake hebben objecten geen massa en zijn ze gemodelleerd met een simpele bounding box. De enige "physics" die erin zit is zwaartekracht (een versnelling omlaag, niet echt bepaald rocketscience) en het stuiteren van granaten tegen statische geometrie. Dat werkt prima voor die game, maar om dat physics te noemen vind ik erg ver gaan.

Waar echte physics engines last van hebben zijn numeric instability, wegens de gelimiteerde precisie van floats en de gebruikte integratiemethoden. Als de stapgrootte bij dit soort berekeningen te klein (hoewel dit meestal niet zo'n heel erg groot probleem is), of te groot (meestal wél een groot probleem) worden krijg je rare resultaten. Denk aan een raceauto die bij een kleine hobbel ineens keihard de lucht in schiet.

Dit artikel bevat een hoop nuttige info over (het kiezen van 3rd party) physics engines. Er is ook een paragraaf geweidt aan time management: http://www.gamasutra.com/features/20020816/maclaurin_01.htm (je moet wel registreren om te kunnen lezen)

[Verwijderd]

bedankt voor de reacties luitjes

nu sta ik voor de keuze of ik een 'quake-like' simpele physics-emulatie inbouw, of voor het 'echie' ga..

een probleem heb ik wel bij beide methoden, hoe implementeer ik dit in mijn scenegraph?

ik heb nu bijv deze boomstructuur ->

world
|-- ball
|-- player

alleen als ik de bal ga 'terugrekenen' moet hij de player ook (tegelijk) terugrekenen, alleen de bal weet natuurlijk niet van het bestaan van de player af (alleen de player krijgt een pointer naar de ball mee om te weten of hij em kan controlleren etc). hoe wordt dit opgelost in andere spellen? ik neem aan dat die toch ook met een boomstructuur werken.

eerst pizza iig, en dan dat artikel eens doorlezen, gamasutra rules tnx oisyn

[.oisyn]

Op zich heeft de scenegraph weinig met physics te maken. De physics engine moet sowieso op de hoogte zijn van alle objecten in world space. De scenegraph is alleen handig om hierarchische transformaties te doen.

[Verwijderd]

hm ja eigenlijk wel.. ik doe via de scenegraph ook sommige recursieve functies (dus naast render die transforms en tekenen doet ook de update voor die physics)..

kan ik beter in de root node de physics engine duwen?

[Woy]

Naast je scene graph kun je toch ook nog een andere data structuur bij houden die je voor je physics gebruikt.

Je scene graph bouw je op aan de hand van transformaties.

Voor je physics engine is het handiger om dat aan de hand van locatie te doen, kan ik me voorstellen.

[Verwijderd]

hmja ik denk het.. snap nog niet helemaal hoe ik zoiets implementeer
handig artikel trouwens oisyn, ik snap alleen nog iets niet;
stel je wil een 60fps physics timestep. als ik het goed begrijp moet de gfx fps daar dan netjes 'inpassen' maar dat zou je fps beperken tot 120, 60, 30 of 15 fps.. of begrijp ik dat verkeerd?

[Janoz]

Je hoeft ze niet exact synchroon te hebben lopen (zolang je je concurrency op orde hebt). De uitkomst van de physics engine zijn als het ware roosterpunten op vaste tijden. Voor het daadwerkelijke renderen kun je die vervolgens interpoleren.

[.oisyn]

Je moet een vrij vaste timestep interpreteren als een factor 0.5 tot 4 oid aan speling. Als je dus uitgaat van een ideale situatie van 30 fps, dan kun je ook makkelijk timesteps van 15 tot 120 fps gebruiken. Onder de 15 zou ik je physics engine dan meerdere stappen laten doen per frame, en boven de 120 fps is eigenlijk sowieso onzin.

@Janoz: dat is een optie, maar dan introduceer je wel een extra frame delay, want je kunt pas interpoleren als je de volgende stap weet. Aangezien er ook weer 1 of 2 frames aan delay tussen de actuele user input en het resultaat daarvan zit kan dat als heel erg irritant ervaren worden.

(Ik zou het sowieso niet in een aparte thread doen aangezien beide threads continu op dezelfde data werken - voor multicore optimalisaties is het verspreiden van subtaken over verschillende cores meestal handiger dan het verspreiden van de globale taken (physics, rendering, AI, etc.) zelf)

[ Voor 18% gewijzigd door .oisyn op 01-07-2007 03:22 ]

[Janoz]

Je kunt ook extrapoleren ipv interpoleren. Dan hoef je niet op het volgende 'physics-frame' te wachten

[.oisyn]

Da's ook een optie idd, maar dan moet je wel zorgen dat je physics timestep klein genoeg is anders krijg je al snel jerky movement.

[Janoz]

Klopt, hij moet wel klein genoeg zijn. Daarnaast hoef je niet lineair te extrapoleren. Natuurlijk is niet lineair extrapoleren duurder, maar aan de andere kant heb je veel minder deling operatoren omdat je bij je physics altijd van dezelfde tijdstap uit kan gaan.

Ik praat trouwens puur theoretisch nu. Geen idee of het daadwerkelijk tegen elkaar weg te strepen is, maar het lijkt me wel een ideale oplossing tegen de magic framerate gebeurens.

[.oisyn]

Ik zou ook niet lineair interpoleren nee (als in, basic dingen als zwaartekracht en versnelling gewoon meenemen in de berekening). Letten op het aantal delingen is niet helemaal meer van deze tijd

[Verwijderd]

kheb et voor elkaar, tnx a lot (heeft ff geduurd ivm drukte maar beter laat dan nooit)

als ik mn spel nu even forceer te pauzeren en daarna weer verder ga heeft de bal netjes gestuiterd en is op de goede positie met ingebakken timestep correction mocht de fps in de soep of juist wat al te hard lopen.

wat me wel opvalt; omdat ik het aantal physics-stappen baseer op de elapsed time van het vorige frame lijkt het soms een beetje 'hakkelig' (tenminste ik denk dat het daar door komt). misschien als ik wat interpoleer dat dat de boel oplost, maar ben nu beetje te moe om daar nog over na te denken. nogmaals bedankt iig oisyn en janoz

[Verwijderd]

ik stuit nog wel op een mogelijk probleempje (tenminste theoretisch), wat als 1 physics-step (qua berekenen) langer duurt dan de x ms die er voor 'gereserveerd' is?

en nog iets, hoe synchroniseer ik zoiets in een server-client multiplayer game? moet de server dan alle physics doen?

[Woy]

voor een client-server game zul je idd moeten zorgen dat de server leidend is met de berekeningen, je kan natuurlijk de client de berekeningen ook lokaal laten doen om het er vloeiend uit te laten zien, alleen moet je corrigeren op het moment dat de berekening afwijkt van die van de server.

[Deviruchi]

rwb schreef op donderdag 12 juli 2007 @ 08:07:
voor een client-server game zul je idd moeten zorgen dat de server leidend is met de berekeningen, je kan natuurlijk de client de berekeningen ook lokaal laten doen om het er vloeiend uit te laten zien, alleen moet je corrigeren op het moment dat de berekening afwijkt van die van de server.

Krijg je dan niet een gigantische server-load, als de server voor elke client de volledige physics gaat berekenen? Ik ben een totale leek op dit gebied, maar dit lijkt mij toch wel een groot minpunt van het systeem dat jij voorstelt.

[stimpie79]

kan je in een dergelijke situatie geen gebruik maken van predictive collision?
-> de bal vertrekt in een bepaalde richting, als er een muurtje staat in die richting weet je precies op welk tijdstip de bal zal botsen (x),
als de eerstvolgende oproep voorbij dat tijdstip zit, weet je toch dat de bal al een bepaalde tijd geleden in de andere richting aan het gaan is ?

[Woy]

Deviruchi schreef op donderdag 12 juli 2007 @ 08:46:
[...]

Krijg je dan niet een gigantische server-load, als de server voor elke client de volledige physics gaat berekenen? Ik ben een totale leek op dit gebied, maar dit lijkt mij toch wel een groot minpunt van het systeem dat jij voorstelt.

Je hoeft op de server ook niet perse de physics op de hoogste resulotie uit te rekenen lijkt me. Maar als je de client zelf de berekening laat doen dan gaan er op een gegeven moment gewoon verschillen onstaan tussen de verschillende clients. Daar krijg je dan hele rare situaties mee.

[Janoz]

Deviruchi schreef op donderdag 12 juli 2007 @ 08:46:
[...]

Krijg je dan niet een gigantische server-load, als de server voor elke client de volledige physics gaat berekenen? Ik ben een totale leek op dit gebied, maar dit lijkt mij toch wel een groot minpunt van het systeem dat jij voorstelt.

Er zit natuurlijk behoorlijk wat overlap in de physics van de verschillende clients. Als speler A iets opblaast dan moet speler B dat ook zien, maar het is gewoon 1 explosie die doorgerekend moet worden (schade, wereldverandering enz).

op de server ben je dus eigenlijk gewoon 1x de physics van de hele spelwereld aan het doorrekenen. Aangezien dat het enige is dat de server hoeft te doen (hij hoeft geen beeld te renderen en hoeft ook geen eigen player input door te rekenen) valt het qua load nog best wel mee.

Waar je trouwens wel rekening mee moet houden op de server (of bij de client) is dat je ook een vertraging hebt tussen client en server. Zeker als het van de ene client via de server naar een andere client gaat.

[Woy]

Janoz schreef op donderdag 12 juli 2007 @ 09:46:
[...]
Waar je trouwens wel rekening mee moet houden op de server (of bij de client) is dat je ook een vertraging hebt tussen client en server. Zeker als het van de ene client via de server naar een andere client gaat.

Idd, daarom zou je de client ook nog gewoon de client zelf de physics kunnen laten door rekenen en alleen corrigeren aan de hand van de server berekening.

[.oisyn]

Verwijderd schreef op woensdag 11 juli 2007 @ 19:28:
ik stuit nog wel op een mogelijk probleempje (tenminste theoretisch), wat als 1 physics-step (qua berekenen) langer duurt dan de x ms die er voor 'gereserveerd' is?

Dan moet je je physics code optimaliseren om te zorgen dat dit niet gebeurt

[roy-t]

.oisyn schreef op donderdag 12 juli 2007 @ 12:13:
[...]

Dan moet je je physics code optimaliseren om te zorgen dat dit niet gebeurt

maar kun je het zover optimalizeren dat het op mijn celeron 300 niet gebeurt? Of op mijn super-spyware infected X2-4800?

[Verwijderd]

interessante kwestie.. vraag me af hoe ze dit doen bij bijv. fifa of pes. valt me nooit op dat er bij de client een vertraging in zit tov de (non-dedicated) server (alsin; het voelt 'eerlijk' aan, winkansen lijken redelijk gelijk), dus of die lag is gewoon heel klein of ze hebben het heel slim gecode.

het idee om de client gewoon zelf de boel te laten berekenen en nu en dan braaf geupdate te worden door de server lijkt me wel het handigst. beste van 2 werelden..

[.oisyn]

therat10430 schreef op donderdag 12 juli 2007 @ 12:36:
[...]


maar kun je het zover optimalizeren dat het op mijn celeron 300 niet gebeurt? Of op mijn super-spyware infected X2-4800?

Dan bail je eruit met het bericht: "Buy a faster PC, dickhead!". Seriously, je hebt zoiets als minimum systeemeisen, en als je PC te langzaam is waardoor een physics timestep langer duurt om uit te rekenen dan die timestep zelf dan is die PC gewoon niet geschikt om de boel te draaien. En dat mag je als game best enforcen

[Verwijderd]

niet helemaal mee eens.. stel dat je een dynamische wereld hebt in je spel, dan kan het voorkomen dat er op een gegeven moment onwaarschijnlijk veel objecten rondstuiteren, en als dan net toevallig je virusscanner aan het updaten gaat oid bail je ineens uit je game.. zou behoorlijk lullig zijn (en ook nog nooit meegemaakt in commerciele spellen dus die zullen er toch ook iets op hebben gevonden )

tenzij je er natuurlijk van uit gaat dat je physics timestep bijv 10ms is en het daadwerkelijke berekenen <3ms oid duurt, maw dikke buffer.. maar ik vraag me af of dat mogelijk is met een ingewikkelde wereld

(ik zal dat probleem iig niet hebben bij mn voetbalspelletje)

[.oisyn]

Maar dan is de tijd om je physics te berekenen niet daadwerkelijk langer dan je timestep, aangezien je CPU niet al die tijd met je physics bezig is geweest. Het punt is namelijk dat je physics thread stallt tot hij weer een timeslice krijgt van het OS, en dus is het prima mogelijk weer bij te komen.