Mise à jour du makefile et ajoute dans le dossier doc du mail d'explication envoyé à Dams

git-svn-id: file:///var/svn/2010-netlemmings/trunk@4 077b3477-7977-48bd-8428-443f22f7bfda

1 files changed, 94 insertions, 0 deletions

diff --git a/doc/archi.txt b/doc/archi.txt
new file mode 100644
index 0000000..d14bf63
--- /dev/null
+++ b/doc/archi.txt
@@ -0,0 +1,94 @@
+########################
+# ARCHITECTURE GLOBALE #
+########################
+
+Pour l'instant la structure n'est pas vraiment encore là. Ya deux grosses procédures "client" et "serveur".
+
+L'idée c'est que lemmings peut se jouer en réseau à exactement deux joueurs (au delà c'est chiant, et seul, c'est pas en réseau). Donc, l'archi quon aura tout le temps c'est :
+1 serveurs, et 2 clients connectés dessus pour une partie donnée.
+On pourra faire de sorte que le serveur gère plusieurs parties en parallèle, mais c'est pas une préoccupation pour l'instant, juste une idée à garder sous le coude, une porte à ne pas se fermer.
+
+Le client pour l'heure n'a pas d'interaction avec l'utilisateur, ça envoi juste des trames ethernet de tests. A terme, la procédure client() devrais lancer l'IHM qui permet de se déclarer à un serveur, choisir un autre mec connecté et un level, et lancer une partie.
+
+Le serveur pour l'instant ne s'occupe pas de la mise en relation des clients qui se connectent. Il accepte deux clients et emmagasine les "events" reçu des clients dans une "eventlist" doublement chaînée sur laquelle il y a une super procédure de tri QuickSort (bon ok, qui fais des recopies abusives pour permuter des éléments mais bon... ça viendra).
+
+Dans mon fil de pensée j'en suis à essayer d'écrire la structure globale, les procédures de plus haut niveau (main, server, client) mais en ayant toujours quelque chose qui compile et qui s'exécute sans fuites mémoire et qui met en évidence que ce qui viens d'être codé tiens la route même si c'est pas complet. J'essaye aussi de coder des points dur de l'appli : la gestion de la synchronisation du temps et des évènements, la gestion de la synchronisation globale des données...
+
+Ya aussi une grosse procédure longue mais pas difficile à faire bientôt : la procédure qui fait évoluer la situation de jeu d'un pas de temps (d'un "tick"). C'est à dire la procédure qui fais bouger tous les lemmings d'un pixel dans la bonne direction s'ils sont en train de marcher, grimper, changer de marche d'escalier... Il manque au moins les 3/4 de la structure de données pour représenter la situation de jeu, ya un début dans game.h avec le type state_game_t. Il manque par exemple à représenter l'altération du terrain (gros tableau de pixels sûrement). Je n'ai pas encore mis la représentation du terrain dans la strucutre de données car je me suis dit qu'on va essayer d'écrire du code pas trop trop pourri en performances et que, par conséquence, la façon de représenter le terrain va sûrement dépendre de la librairie graphique qu'on va employer, or j'ai rien fixé du tout pour l'instant. Je me dit que ça devrais pouvoir être sympa en SDL. Donnes-moi ton avis.
+
+
+##################################################
+# Gestion des évènements et transmissions réseau #
+##################################################
+Chaque évènement (event_t) est issu d'une action d'un utilisateur a un instant donné (donc, côté client() ). Le "a un instant donné" est stocké dans le champ event.tick. On fera de sorte, dans l'IHM que cette affirmation soit vraie : un joueur donné, a un tick donné ne peut déclancher qu'un seul évènement. Le client envoi cet évènement sous forme de trame réseau au serveur. Le serveur fais une liste d'évènements récemment reçus. Une seule liste pour les deux joueurs. Les évènements sont mélangés.
+A un instant donné (déterminé par la partie gestion du temps que j'explique après), le serveur réordonne la liste des évènements (quicksort sur liste chaînée, déjà codé) et l'envoi aux 2 clients et archive ce bout de liste envoyé dans une autre liste d'actions, qui sera enfait le tas d'infos permettant de jouer le mode replay du niveau.
+
+A la réception de ces évènements, les clients mettent à jour leur situation de jeu respective et comme les algos de l'évolution du jeu sont déterministes, avec un état de jeu et une séquence d'évènements, on sais qu'on va arriver toujours dans la même nouvelle situation de jeu, donc les deux clients font le calcul de leur côté, mais on sais qu'ils seront dans la même situation au final.
+Enfait, côté client, il va y avoir un truc qui va compliquer un poil la vie, mais sans le quel le jeu est injouable : sur un client donné, la situation de jeu doit pouvoir évoluer à un rythme pseudo régulier (12 FPS si je me souviens bien dans lemmings original) même si on a pas encore connaissance de tous derniers évènements générés par l'autre joueur. Donc, on se retrouve à faire de la prédiction. On considère que durant tout le temps entre le dernier évènement reçu de l'autre joueur et l'instant courant, l'autre joueur n'a rien fait, et que donc, la situation de jeu au prochain coup est : la situation courante + les altérations par l'éventuelle action du joueur locale (unique pour un tick donné on a dit) + l'évolution du jeu d'un pas par la produre qui donne vie a nos lemmings (pas donné de nom encore à cette procédure). Enfait, c'est exactement comme si entre le dernier message reçu et l'instant présent, on fesait tourner le moteur de jeu en mode "single player".
+Dans les FPS comme UT ou CStrike ou autre, c'est pareil, on a ce même système. Le moteur de jeu connais la position des objets mobiles et un vecteur vitesse, voire accélération et consière et que ces paramètres ne vont pas changer et prédit les nouvelles positions. Si un mec a changé de direction, bah il va se être violemment recalé sur l'écran dès qu'on le saura, mais si la précision est assez fine et la vitesse de propagation des évènements est bonne, le joueur peut viser tranquille...
+Dans lemmings, la contrainte, c'est que le terrain s'abîme et transférer juste la position des objets mobiles suffit pas. On a besoin d'être sûr qu'on a reçu tous les évènements dans l'ordre chronologique pour être capable de calculer la "vraie" situation de jeu courante.
+
+Du coup pas d'udp ou on bourrine tant qu'on peut pour envoyer les positions de tous les joueurs le plus souvent possible, mais du tcp ou on envoi tous les évènements au serveur, où le serveur fusionne en ordonnant bien les évènements qui arrivent des deux joueurs et les retransmet aux deux clients. Je veux pas rentrer dans l'idée on envoi les évènements ou la position des lemmings en udp et pi quand un truc s'est perdu et qu'un des jeu est out of sync, on renvoi toute la situation de jeu, y compris avec les trous dans le terrain car c'est violent en terme de pic de débit sur le réseau, c'est difficile à programme, et ça marchera sûrement jamais bien.
+
+Donc en fait, il y a deux situations de jeu a conserver en mémoire pour chaque client :
+La dernière situation "réseau" connue par les deux joueurs dont on est sûr qu'elle est valide (mais un peu périmée) et la situation "locale" courante qui est basée sur la dernière situation réseau, mais ou les ticks ont avancé et les évènements locaux ont été appliqués (la prédiction).
+
+
+############################
+# Synchronisation du temps #
+############################
+
+C'est le serveur qui est le maître du temps. On peut très bien imaginer de faire d'une pierre deux coups : lorsque que le serveur a besoin d'envoyer une liste d'évènements aux clients, il ajoute son tick courant et une valeur de tick pour chaque joueur : la date où il a reçu le dernier évènement de chacun.
+
+Les clients calculent en fonction de ça si leur horloge à eux va trop lentement ou trop vite, et corrigent en l'accélérant ou en la ralentissant avec un coefficient. Le calcul de "à l'avance ou en retard" n'est pas si simple car il faut éviter de croire qu'on a systématiquement 10 ticks de retard car ya un lag de transmission réseau d'environ 100ms.
+
+Pour ce calcul, on fait supposition : le temps de transmission du dernier évènement = le temps de transmission de la liste d'évènements par le serveur.
+
+Dans l'ordre, avec un point de vue omniscient, la séquence des évènements est celle la, entre un client et le serveur :
+
+Le client envoi le dernier évènement qui va déclancher une émission par le serveur à un instant pour le client tc1 (tc1 fait partie de la charge utile du paquet transmis).
+
+Le serveur reçoit ce paquet et met a jour immédiatement une variable locale qu'on va noter ts1 qui est le tick, selon le serveur auquel le message à été reçu.
+
+Le serveur attends un peu et/ou prends du temps pour ordonner la séquence d'évènement et préparer son envoi.
+
+Le serveur s'apprête à envoyer la séquence d'évènement. Il y a ajoute la valeur ts1 et aussi une nouvelle valeur ts2 qui est le tick courant du serveur, au moment de l'émission.
+
+Le client reçoit cette trame. Il positionne immédiatement une autre variable locale tc2 qui est la date de réception de cette trame.
+
+Le client cherche maintenant à savoir s'il est en retard ou en avance sur la date du serveur, indépendament du temps de transmission des paquets. On va noter delta cette estimation de la différence entre la date actuelle du serveur et la date actuelle du client.
+
+Le client risque d'être sévèrement occupé a corriger la situation de jeu avec ce qu'il viens de recevoir, et il fais ça en priorité car la distorsion de la situation du jeu est plus grave que la distorsion temporelle dans l'expérience du joueur.
+
+Le client fini par entrer dans la procédure de détermination de delta.
+Il calcule d'abord le temps aller-retour des paquets réseau, noté rtt (round trip time).
+Notons lag1 le nombre de ticks écoulés pendant la transmission client -> serveur
+Notons lag2 le nombre de ticks écoulés pendant la transmission serveur -> client
+
+En admettant que les dérives d'horloges entre le client et le serveur durant le transmissions sont nulles, on a :
+ts1-tc1 == delta1 + lag1 (au moment de la réception par le serveur)
+tc2-ts2 == lag2 - delta2 (au moment de la réception par le client)
+rtt == lag1 + lag2
+
+On suppose que :
+1) delta1==delta2, c'est à dire que les horloges n'ont pas dérivé pendant le (court) temps de l'aller retour des paquets.
+2) on peut mélanger les équations du dessus et considérer qu'elles sont toutes les deux vraies au moment de la réception par le client.
+
+Donc : rtt=(ts1-tc1)+(tc2-ts2)
+On considère que lag1=lag2=rtt/2.
+
+On remplace dans tc2-ts2 == lag2 - delta2 :
+tc2-ts2 == rtt/2 - delta2
+et donc :
+delta2 == rtt/2 + ts2 - tc2
+
+Donc on sais que au moment de la réception par le client (tc2), la différence d'horloge est de delta2.
+
+On peut donc estimer delta3, différence d'horloge à l'instant présent du client (noté tc3), par interpollation linéraire de la dérive depuis le début du jeu :
+
+delta3=delta2*tc3/tc2
+
+On n'a plus qu'a rattraper se décalage. La méthode violente de faire un bon dans le futur ou de bloquer le jeu pendant ce nombre de ticks est une mauvaise idée car la l'approximation lag2=rtt/2 sera fausse ponctuellement, en cas de reémission de paquet TCP. Donc faut y aller progressif. Si on se donne 100 ticks pour rattraper, il suffit d'attendre ou d'accélérer de delta3/100 jusqu'à avoir une nouvelle valeur de delta3.
+
+Reste à régler la question des périodes où il ne se passe pas grand chose, pas d'évènement, pas de syncro d'horloge. Faudra que les clients génèrent des évènements vide pour stimuler un peu le serveur. On peut faire un génération d'event si delta3 n'a pas été calculé depuis n ticks par exemple.
+