+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : Prédire un évènement aléatoire (/showthread.php?tid=6986)
Pages :
1
2
Prédire un évènement aléatoire - Maks - 19-06-2013
Salut à tous, j'ai besoin de quelques pistes pour résoudre un problème
Rapidement, un personnage peut effectuer une attaque critique. Imaginons qu'actuellement on utilise un random pour savoir si une attaque est critique (une chance sur 10) côté serveur.
Maintenant imaginons qu'on veuille le prédire côté client. La solution du random tombe à l'eau, car on ,ne pourra garantir qu'il sera le même côté client comme côté serveur. Se baser sur le timestamp apparait également difficile étant donné le temps de latence.
La solution par défaut étant d'estimer qu'il n'y a jamais de coup critique côté client, et de corriger si besoin est par le serveur ensuite.
Des idées ?
RE: Prédire un évènement aléatoire - Xenos - 19-06-2013
Si c'est aléatoire, y'a aucune possibilité de le prévoir...
Se "baser sur le timestamp" ne changera rien, car les algorithmes pseudo aléatoires bien foutus sont capables de changer du tout au tout si on a ne serait-ce que 1ms d'écart. D'autant que certains algorithmes, avec un peu de pirouettes, peuvent avoir des aléatoires différents même si les algorithmes ont été initialisés avec le même timestamp (par exemple, à chaque initialisation, un compteur est incrémenté et toute nouvelle initialisation utilisera non seulement le timestamp comme seed de départ, mais aussi la valeur du compteur donc le même timestamp mais avec un compte différent ne produira pas la même séquence aléatoire).
Donc, non, pas d'idée, car le problème, "prédire un truc aléatoire" me semble tout simplement insolvable
Tout ce qu'on pourrait faire avec l'aléatoire, ce sont des statistiques...
RE: Prédire un évènement aléatoire - Maks - 19-06-2013
Oui voilà l'idée c'est d'avoir un évènement aléatoire mais qui n'est pas basé sur une donnée aléatoire. Par exemple le timestamp de la dernière action certifié par le serveur, faire la somme de ses chiffres et une comparaison qui déterminera si le prochain coup est critique. J'imagines que les MMORPG qui utilisent la prédiction ont un méchanisme du genre ?
RE: Prédire un évènement aléatoire - Xenos - 19-06-2013
D'accord, cela renverse le problème:
il ne s'agit donc plus de prédire un évènement aléatoire mais de donner une apparence aléatoire à un évènement prédictible.
Une première possibilité:
Coté serveur:
Choisir un algorithme pseudo aléatoire répandu (mersenne twister par exemple)
Choisir un seed pour cet algorithme (seed aléatoire si on veut)
Générer N valeurs et les stocker
Ensuite, il suffit d'envoyer au client le seed utilisé, l'algorithme choisi (ca, normalement, c'est "envoyé" au client via le code du javascript lui-même, en d'autres mots, il faut que l'algorithme pseudo aléatoire soit le même coté client et serveur) ainsi que le n° du dernier nombre tiré.
Connaissant ces données, le client peut générer la même liste que le serveur, et sachant quel est le dernier n° tiré, le client est capable de savoir quel sera le prochaine n° tiré.
On peut alléger le coté serveur en ne stockant que le seed et le n° du dernier tirage: ainsi, pour trouver le nombre suivant, il suffit d'initialiser l'algorithme pseudo aléatoire avec le seed stocké, et de faire défiler (n°) tirages aléatoires pour trouver le prochain nombre.
Exemple:
Coté serveur, je décide que d'utiliser mersenne twister. Je choisis le seed 1000 (lui-même aléatoire).
Le n° du dernier tirage est -1, puisque j'ai jamais fait de tirage.
J'envoie au client le couple (1000,-1), pour qu'il sache que le seed est 1000, et le dernier tirage -1.
Le client initialise l'algorithme mt_srand(1000). Il génère ainsi une grille de 100 nombres aléatoires:
Code :
0 753084335
1 1694858333
2 246975523
3 1310787424
4 115944203
5 2115752409
6 1123256280
7 774816128
8 283560872
9 327653942
10 1684423386
11 2130080352
12 87423252
13 1398537922
14 852968622
15 1775019291
16 500647570
17 1829113182
18 1807624438
19 919118209
20 1707760099
21 497724395
22 541247650
23 1947017330
24 1299836476
25 129545465
26 391392911
27 2113765122
28 543668698
29 211595471
30 2007229881
31 1755136974
32 236539833
33 1974903052
34 2045788262
35 305456159
36 1999615310
37 525128298
38 1248272920
39 1414251589
40 2097045177
41 1023438599
42 49866472
43 1753044770
44 729366374
45 516923397
46 624905388
47 911176403
48 777125072
49 358878892
50 2067115247
51 288349692
52 305756667
53 123643954
54 728438645
55 903863614
56 491393804
57 346019037
58 1189893294
59 1715179299
60 1900722616
61 44501693
62 217532971
63 843651190
64 22380431
65 2085033039
66 160109366
67 587035839
68 1612445686
69 554291827
70 1851511841
71 12113357
72 1498782743
73 1510943389
74 855138471
75 1600639048
76 1896490466
77 1988392749
78 1751168120
79 479794419
80 1209522032
81 429079554
82 38962237
83 1185711533
84 1484851500
85 333850514
86 1129654207
87 384589825
88 1864523984
89 66560555
90 224174178
91 189440053
92 181159731
93 682638453
94 1981280807
95 1375821209
96 2056964493
97 1465893082
98 941828119
99 792112746Le serveur exécute le code suivant:
Code PHP :
<?php
//__LAST__ est le n° du dernier tirage effectué, ici, -1.
mt_srand(1000);
for ($i=0;$i<=__LAST__;$i++)
mt_rand();
return (mt_rand());
?>Coté client, le compteur (n° du dernier tirage) est incrémenté, idem coté serveur.
Les deux ont donc exactement les mêmes tirages pseudo-aléatoires.
En revanche, connaissant le seed, le client sera capable, quoiqu'il arrive, de prédire tous les tirages à venir, donc, on pourrait tricher, et abandonner le combat en sachant que les tirages pour ce combat sont un peu "moisis"...
RE: Prédire un évènement aléatoire - Maks - 19-06-2013
J'aime bien l'idée de la liste pré-définie
Tout bêtement on pourrait réduire la liste à chaque coup porté. Cependant l'ordre d'arrivée des packets n'est pas toujours garanti (problème des packets perdus avec le protocole TCP).
Dans mon cas, il n'est pas possible d'"abandonner" réellement un combat (sauf en fuyant et encore)
Merci pour cette piste en tout cas
RE: Prédire un évènement aléatoire - Xenos - 19-06-2013
?
La liste n'est jamais transférée. Seul le couple (seed, n°) est envoyé au début du combat... Voir même, tu n'envoies pas le n° si tu crées un nouveau seed pour chaque combat.
Et si le problème, c'est l'ordre d'arrivée des paques TCP envoyés par le client et disant "je porte un coup", il te suffit de numéroter le paquet avec le n° du coup selon ce que le client demande. Ainsi, le serveur sait quel est le n° de coup et donc le n° aléatoire associé.
RE: Prédire un évènement aléatoire - atra27 - 19-06-2013
Au passage, avec tcp les packets sont toujours reçus, et toujours dans l'ordre
pas de soucis de packets perdus/en retard/dupliqués.
tu confond avec udp (qui ne garanti, ni la réception, ni l'ordre, ni le nombre)
RE: Prédire un évènement aléatoire - niahoo - 19-06-2013
+1 atra27, mais le problème est que en javascript tu peux faire des appels concurents (genre un DoT et en prallèle des coups) tandis que côté serveur tu peux tout traiter dans une file. là l'ordre d'arrivée peut varier (car on est à un bien plus haut niveau que la couche TCP). ça dépend de l'implémentation. Si c'est comme çà, on peut mettre les appels à la file côté JS et c'est réglé. ou numéroter les coups oui.
mais sinon la solution me paraît simple et élégante. Ensuite de savoir si on tire à l'avance X nombres pour le combat ou bien si on les tire un par un ne change pas grand chose.
RE: Prédire un évènement aléatoire - Maks - 20-06-2013
(19-06-2013, 10:10 PM)atra27 a écrit : Au passage, avec tcp les packets sont toujours reçus, et toujours dans l'ordre
pas de soucis de packets perdus/en retard/dupliqués.
J'avais lu un article qui semblait dire le contraire : http://blog.artillery.com/2012/06/websocket-performance.html (à propos des paquets perdus)
RE: Prédire un évènement aléatoire - atra27 - 20-06-2013
Après une lecture rapide Je ne vois pas ou cela est dit mais si ça y est c'est totalement faux
tcp a été conçu pour transmettre un flux, donc ordonné et continu.
tcp fonctionne en mode connexion et est plus long à transmettre car s'il manque un packet, touts les suivant sont discardés et doivent etre retransmis
udp à été conçu pour transmettre des datagrammes, ici chaque packet à sa propre existence, peut arriver ou non, etre dupliqué ou non, et les datagrammes peuvent emprunter des chemins différents (ordre non garanti)
udp ne nécessite pas de connexion entre emetteur et recepteur
pour les jeux d'action, on privilégiera udp pour la simple raison que seuls les données actuelles comptent, et peut importe si une est retardée car la suivante la remplace aussitôt
bon après udp n'est pas supporté par ws donc ça règle la question.
pour la question des requêtes parallèles, cela permet de ne pas attendre la réponse avant d'envoyer la seconde. par contre le navigateur optimise surement en utilisant la meme connexion, donc la réponse arrivera dans le meme ordre que les demandes. mais cela dépend aussi de l'implémentation du navigateur
De plus je doute qu'en js on ai le niveau de controle suffisant pour vérifier le nombre de connexions et prévoir cet ordre à coup sur.
désolé pour les fautes, j'écrit depuis mon telephone dans un aéroport donc c'est pas top ^^
A dans 8heures les gars (et filles)