Author Topic: Passer d'un timestep fixe a un timestep variable  (Read 5487 times)

0 Members and 1 Guest are viewing this topic.

Offline ponce

Passer d'un timestep fixe a un timestep variable
« on: 30 June 2010 à 23:34:44 »
Ca serait pas mal de partager les petits trucs qu'on connaît. Des fois j'ai du utiliser ces transformations pour qu'un mouvement pas précalculé dépende plus du framerate (en reprenant du vieux code).

Imaginons qu'à chaque frame il se passe ca, et que vous êtes bloqué sur 75 FPS:

Code: [Select]
machin = machin * 0.74;

ça devient

Code: [Select]
machin = machin * exp(dt * 75 * log(0.74));

De même, pour des mouvements à la Newton genre :

Code: [Select]
a.acc = forces;
a.vel = a.vel + a.acc;
a.pos = a.pos + a.vel;
a.vel *= friction;

ça devient  :

Code: [Select]
a.acc = forces;
a.vel = a.vel + a.acc * dt * 75;
a.pos = a.pos + a.vel * dt * 75;
a.vel *= exp(dt * 75 * log(friction));

Ca donnera pas exactement le même résultat (l'intégration d'Euler est pas exacte) mais ca ressemblera bien.


Du coup je me pose une question, comment faire pour un code qui ressemble à ca ?
Code: [Select]
if (randomFloatEntre0et1() < 0.36) {
  quelquechose();
}

C'est à dire pour qu'il se passe environ 0.36 * 75 fois quelquechose() dans une seconde.
On veut garder ce comportement mais transformer ça en

Code: [Select]
int n = fonction(dt);
pour i de 1 à n {
  quelquechose();
}

A votre avis ?
« Last Edit: 14 July 2010 à 19:22:35 by wullon »

Offline MooZ

  • Base
    • Pouet.net
    • View Profile
    • Lair of the procrastinators
  • Groupe: BlockoS
  • Rôle: Dieu vivant du code sans fin
Re : [code] Passer d'un timestep fixe a un timestep variable
« Reply #1 on: 01 July 2010 à 14:00:50 »
En gros ton problème reviens à générer N valeurs ( ici N=E(0,36*75) ) sur l'intervalle [0,1]et à compter le nombre de valeurs comprises dans l'intervalle [t, t+dt].

En attendant que je trouve un truc : http://arxiv.org/abs/hep-ph/0006269 :)
La scène est marne en 77.

Offline ponce

Re : Re : [code] Passer d'un timestep fixe a un timestep variable
« Reply #2 on: 01 July 2010 à 15:06:39 »
En gros ton problème reviens à générer N valeurs ( ici N=E(0,36*75) ) sur l'intervalle [0,1]et à compter le nombre de valeurs comprises dans l'intervalle [t, t+dt].

Y'a la technique qui est de dire "tu a passé dt secondes, donc il s'est passé dt * 0.36 fois quelque chose".
Le problème c'est que par exemple il peut se passer rien du tout pendant une seconde (avec beaucoup de chance), alors que si on fait comme ca on aura pas les cas extrème. C'est pas la même variance quoi.

Offline MooZ

  • Base
    • Pouet.net
    • View Profile
    • Lair of the procrastinators
  • Groupe: BlockoS
  • Rôle: Dieu vivant du code sans fin
Re : [code] Passer d'un timestep fixe a un timestep variable
« Reply #3 on: 01 July 2010 à 16:05:55 »
Donc la répartition sera tout sauf uniforme.
Ben tu peux déjà calculer le nombre d'occurrences (n=dt*0.36*75) et après tu prends un nombre aléatoire entre 0 et 1. Si cette valeur est supérieure ou égale à un seuil à la con tu fais n fois ton bidule. Sinon tu ne fais rien.
La scène est marne en 77.

Offline Patapom

  • Base
    • View Profile
    • www.patapom.com
  • Ancienneté: 1988
  • Groupe: Bomb!
  • Rôle: Coder
  • Ville: Lyon
Re : Passer d'un timestep fixe a un timestep variable
« Reply #4 on: 12 January 2011 à 13:45:03 »
Comprends rien... ;D
.  Pom  .

yrizoud

  • Guest
Re : Passer d'un timestep fixe a un timestep variable
« Reply #5 on: 12 January 2011 à 15:31:28 »
Si je comprends bien, tu veux en un seul tirage au sort déterminer "combien de fois" le traitement du milieu doit être simulé.

Par exemple pour N=2 :
0 fois : 0.64*0.64 (41%)
1 fois : 0.36*0.64 + 0.64*0.36 (46%)
2 fois : 0.36*0.36 (13%)

Pour N=3
0 fois : 0.64*0.64*0.64 (26%)
1 fois : 0.36*0.64*0.64 + 0.64*0.36*0.64 + 0.64*0.64*0.36 (44%)
2 fois : 0.64*0.36*0.36 + 0.36*0.64*0.36 + 0.36*0.36*0.64 (25%)
3 fois : 0.36*0.36*0.36 (5%)

Ca je sais le faire à la main mais pas le coder avec un bon O(n).

nystep

  • Guest
Re : Passer d'un timestep fixe a un timestep variable
« Reply #6 on: 12 January 2011 à 15:33:35 »
Quote
if (randomFloatEntre0et1() < 0.36) {
  quelquechose();
}

Code: [Select]
int n=int(t*100.0f) % quelqueChoseSiTuVeux;
if (randomFloatEntre0et1(n) < 0.36) {
  quelquechose();
}

en s'assurant que randomFloatEntre0et1 est déterministe...
c'est juste perso, mais je n'aime pas du tout ce qui n'est pas déterministe.. :)

par exemple:

Code: [Select]
static float randomFloatEntre0et1( int x )
{
    int n = x;
n = (n * (n * n * 75731 + 189221) + 1371312589);
return (float) (n & 0x7FFFFFFF) * (1.f / 2147483648.f);
}

nystep

  • Guest
Re : Passer d'un timestep fixe a un timestep variable
« Reply #7 on: 12 January 2011 à 15:35:58 »
Bon après si tu veux un "comportement gaussien" il suffit de modifier le générateur de nombres aléatoires pour qu'il renvoie une répartition gaussienne...

Offline eva03sp

  • Base
    • View Profile
  • Ville: Aix-en-Provence
Re : Passer d'un timestep fixe a un timestep variable
« Reply #8 on: 12 January 2011 à 15:47:25 »
Ce que tu peux faire, c'est utiliser un générateur de nombres aléatoires uniforme pour calculer à l'avance l'échéance T_ech de ton prochain évènement. A chaque frame, tu passes dans une boucle WHILE qui se répète tant que T_ech est inférieur ou égal à T_courant, et qui se charge 1) d'exécuter ton évènement, 2) calculer une nouvelle valeur de T_ech.

Je sais pas quelle est la variance de la fréquence d'exécution avec ça (ça fait trop longtemps que j'ai pas fait de proba :(). Ce que je sais néanmoins, c'est que dans un aspect purement pratique c'est plus flexible que de tirer un nombre au hasard (tu peux imposer des bornes mini et maxi à T_ech), et que ça me suffisait amplement dans des jeux (pour faire cligner les persos des yeux par exemple ;D).

Offline maracuja

  • Base
    • View Profile
Re : Passer d'un timestep fixe a un timestep variable
« Reply #9 on: 12 January 2011 à 16:27:23 »
Code: [Select]
static float randomFloatEntre0et1( int x )
{
    int n = x;
n = (n * (n * n * 75731 + 189221) + 1371312589);
return (float) (n & 0x7FFFFFFF) * (1.f / 2147483648.f);
}


Dis moi, j'ai souvent vu cette algo pour generer un nombre aleatoire, d'ou est il issu ?

Offline xoofx

  • Base
    • Pouet.net
    • View Profile
    • xoofx
  • Ancienneté: 1989
  • Groupe: FRequency
  • Rôle: code (+musique), web
  • Ville: Grenoble
Re : Passer d'un timestep fixe a un timestep variable
« Reply #10 on: 12 January 2011 à 17:08:12 »
Dis moi, j'ai souvent vu cette algo pour generer un nombre aleatoire, d'ou est il issu ?
Je crois qu'il vient d'iq, mais je ne retrouve plus son article original. Elle est surtout utilisée sur le GPU car elle n'a pas besoin de stocker en statique un seed ou un état intermédiaire.

Offline krabob

  • Base
    • Pouet.net
    • View Profile
    • www.m4nkind.com
  • Ancienneté: 1994
  • Groupe: Mankind
  • Rôle: code amiga / linux / OpenGL
  • Ville: Toulouse
Re : Passer d'un timestep fixe a un timestep variable
« Reply #11 on: 12 January 2011 à 17:29:56 »
ouaou  :o... intéressant le random en shader: ça s'exploite les textures procédurales avec précision infinies quelle que soit l'échelle avec ce genre de truc ?

 ... sinon, là je force des doStep() de calculs physiques 30 fois par secondes, dans un draw(),quelque soit la fréquence du draw() , avec un petit algo qui itère doStep():

Code: [Select]
int mssince = ((context.m_MillisecTime-m_LastStepDate)*30)/1000;
if(mssince<0) mssince=0;
else if(mssince>4) mssince=4;
int ii;
for(ii=0 ; ii<mssince ; ii++) doStep();
if(mssince>0) m_LastStepDate = context.m_MillisecTime;
Comme ça, si ordi rapide, certaines frame auront pas de doStep(), et si plus lent, certaines frames feront plusieurs doStep(), mais dans l'absolu la moyenne tendra forcément vers les 30 per/sec souhaité.

( edit) Ah oui c'est vrai que noise3d() vaut peut etre le coup maintenant... (il y a 5 ans quand je testouillais les shaders c'était pas la peine.) !!! 8)
« Last Edit: 12 January 2011 à 17:39:00 by krabob »
Votez comme ça Mélenchon ... ou Clément Wittman, ... ou Eva ! Oo

Offline xoofx

  • Base
    • Pouet.net
    • View Profile
    • xoofx
  • Ancienneté: 1989
  • Groupe: FRequency
  • Rôle: code (+musique), web
  • Ville: Grenoble
Re : Passer d'un timestep fixe a un timestep variable
« Reply #12 on: 12 January 2011 à 17:34:39 »
ouaou  :o... intéressant le random en shader: ça s'exploite les textures procédurales avec précision infinies quelle que soit l'échelle avec ce genre de truc ?
Tout à fait! ;) Si tu regardes les exemples de code dans shadertoy, tu verras que ce code d'iq est utilisé notamment par lunaquatic. Dans slicesix, on peut le voir à l'oeuvre avec une fonction noise3D.

Offline Elrick

  • Base
    • View Profile
  • Groupe: SFX
  • Rôle: Code / GFX
  • Ville: Lyon
Re : Re : Passer d'un timestep fixe a un timestep variable
« Reply #13 on: 12 January 2011 à 18:09:27 »
Comprends rien... ;D

HUHU !!! quoted !!! pour une fois que c'est pas l'inverse !!!

nystep

  • Guest
Re : Re : Passer d'un timestep fixe a un timestep variable
« Reply #14 on: 12 January 2011 à 19:20:59 »
Dis moi, j'ai souvent vu cette algo pour generer un nombre aleatoire, d'ou est il issu ?

http://www.nrbook.com/c/ à partir de la page 274

Les générateurs de nombres pseudos aléatoires sont souvent codés comme des dépassements de capacité de multiplication tronqués modulo 32 bits... Mais cette implé précise vient de sislesix je pense.. D'ailleurs il doit y avoir moyen de l'optimiser..
« Last Edit: 12 January 2011 à 20:03:59 by nystep »