Demoscene.fr BBS

Articles et discussions techniques => Code => Topic started by: ponce on 30 June 2010 à 23:34:44

Title: Passer d'un timestep fixe a un timestep variable
Post by: ponce 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 ?
Title: Re : [code] Passer d'un timestep fixe a un timestep variable
Post by: MooZ 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 (http://arxiv.org/abs/hep-ph/0006269) :)
Title: Re : Re : [code] Passer d'un timestep fixe a un timestep variable
Post by: ponce 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.
Title: Re : [code] Passer d'un timestep fixe a un timestep variable
Post by: MooZ 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.
Title: Re : Passer d'un timestep fixe a un timestep variable
Post by: Patapom on 12 January 2011 à 13:45:03
Comprends rien... ;D
Title: Re : Passer d'un timestep fixe a un timestep variable
Post by: yrizoud 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).
Title: Re : Passer d'un timestep fixe a un timestep variable
Post by: nystep 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);
}
Title: Re : Passer d'un timestep fixe a un timestep variable
Post by: nystep 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...
Title: Re : Passer d'un timestep fixe a un timestep variable
Post by: eva03sp 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).
Title: Re : Passer d'un timestep fixe a un timestep variable
Post by: maracuja 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 ?
Title: Re : Passer d'un timestep fixe a un timestep variable
Post by: xoofx 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.
Title: Re : Passer d'un timestep fixe a un timestep variable
Post by: krabob 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)
Title: Re : Passer d'un timestep fixe a un timestep variable
Post by: xoofx 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 (http://www.iquilezles.org/apps/shadertoy/presets/slisesix.txt).
Title: Re : Re : Passer d'un timestep fixe a un timestep variable
Post by: Elrick on 12 January 2011 à 18:09:27
Comprends rien... ;D

HUHU !!! quoted !!! pour une fois que c'est pas l'inverse !!!
Title: Re : Re : Passer d'un timestep fixe a un timestep variable
Post by: nystep 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/ (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..
Title: Re : Passer d'un timestep fixe a un timestep variable
Post by: maracuja on 12 January 2011 à 21:03:49
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.

Ok, merci @lex. :)
Title: Re : Passer d'un timestep fixe a un timestep variable
Post by: ponce on 12 January 2011 à 22:20:48
Oulà merci pour vos réponses dans ce vieux thread :)

@yrizoud: En fait c'est ça sauf que le N est pas un entier.

@nystep: j'ai pas tout compris mais à mon avis un noise 1d déterministe ça résoud pas vraiment mon problème qui est plus un problème d'intégrale d'une fonction aléatoire sur le timestep (la fonction uniforme => peut-être que ce que je cherche c'est la loi de Poisson ?)

@eva03sp: effectivement ca marcherait pour ce que je voulais faire, je suppose qu'on peut obtenir à peu près la même fréquence d'évenement mais au niveau variance on sait pas trop en effet. Bon comme en pratique le FPS va pas varier dans des proportions folles ca peut le faire.