Exécution concurrente et réseaux

Exécution concurrente

Avant de commencer à concevoir des solutions pour le jeu en réseau, il faut tout d’abord être capable de faire fonctionner le moteur de règles dans un thread séparé des aspects d’interface utilisateur. À terme, l’objectif est de faire fonctionner un moteur dans un processus différent sur une machine distante.

Cette section présente également plusieurs approches usuelles et les patrons associés pour gérer l’exécution concurrente de traitements, avec pour exemple la parallélisation de l’exploration de l’arbre de recherche pour les IA avec planification.

1. Séparer Moteur de règles et Interface utilisateur

a. Échanges entre les acteurs

Pour mettre en place la parallélisation, trois principaux acteurs sont à considérer :

Le moteur de règles qui modifie l’état en fonction des commandes.
Le moteur de rendu qui dessine l’état et produit des commandes.
Le pilote qui orchestre les échanges, incarné par la classe PlayGameMode dans le jeu exemple Pacman.

Ces acteurs ont besoin d’informations communes, comme les données de l’état du jeu. Certains acteurs modifient ces données communes, ce qui rend leur lecture impossible lors des changements. D’autres acteurs produisent des messages, comme le moteur qui notifie les modifications de l’état, ou l’interface utilisateur qui produit des commandes. Enfin, l’ensemble est soumis à des contraintes de temps réel, comme le rendu qui doit être exécuté à 60 images par seconde.

Pour chaque type d’échange, il faut trouver une solution pour permettre l’accès ou la modification de l’information, sans erreurs ni blocage. Un autre problème courant en exécution concurrente concerne la « course aux données » (data race). Ceci se produit lorsque plusieurs acteurs souhaitent consulter ou modifier les mêmes informations au même moment. Cela ne conduit pas forcément à un blocage, mais ralentit l’ensemble du programme. Lors de ces situations, les acteurs sont en permanence en train d’attendre leur tour pour pouvoir travailler. À la latence engendrée par ces conflits...

Communication réseau

Dans ce chapitre, la mise en œuvre de jeux multijoueurs sur un réseau est proposée. L’approche suivie repose sur des services web de type HTTP REST, le tout via un protocole TCP/IP. Cette approche réunit des solutions techniques très populaires dans tous les domaines des réseaux. Elle a été choisie pour sa simplicité, tout en assurant tous les critères habituels de robustesse et stabilité. En outre, utiliser des protocoles largement éprouvés à grande échelle offre des garanties, tout en évitant d’avoir à réinventer la poudre. Elle répond aux besoins de pratiquement tous les jeux vidéo, quelle que soit la plateforme (PC, smartphone, etc.). Les seuls jeux dont l’utilisation est possible, mais sous-optimale, sont les jeux qui requièrent une très faible latence et un très haut taux de mise à jour des données du jeu, comme les FPS ou les jeux de combat. Pour ceux-ci, une approche très basique via UDP, également présentée, est suffisante.

1. Notions essentielles

Cette section présente les éléments techniques requis pour la compréhension des conceptions proposées par la suite. Ces présentations sont loin de couvrir la totalité des notions réseau abordées, certaines sont très approximatives mais suffisantes pour les besoins à venir. Davantage de détails sur ces sujets peuvent être trouvés dans l’ouvrage « Réseaux informatiques - Notions fondamentales », José Dordoigne, Éditions ENI, 2017.

a. Couches réseau

La communication entre machines sur un réseau repose sur l’échange de lots d’informations, généralement appelés « paquets ». Différents types et échelles de paquets sont considérés lors de ces échanges, et dans chaque cas, un paquet est accompagné par un en-tête. Chaque en-tête est propre à la couche réseau correspondante, et permet d’obtenir ou de paramétrer les informations qui s’y réfèrent. Ces en-têtes s’empilent généralement les unes à la suite des autres : pour...

Jeu en réseau

1. Principes

Cette section s’intéresse à la distribution d’un jeu vidéo sur plusieurs machines, dont l’une fait office de serveur, et les autres sont les clients graphiques des joueurs. Pour synchroniser tous ces acteurs, il existe deux grandes approches : l’une consiste à propager régulièrement l’intégralité du jeu, et l’autre à ne propager que les informations qui l’ont modifié.

La première approche est naturellement la plus simple à mettre en œuvre. Pour ce faire, il faut être capable de convertir l’état du jeu dans un format transportable sur le réseau, comme le JSON vu précédemment. Cette approche n’est malheureusement possible que lorsque l’empreinte mémoire des données du jeu est faible, voire très faible. En effet, il est difficile d’imaginer propager plusieurs mégaoctets des dizaines de fois par seconde sur les réseaux actuels - une taille pourtant rapidement atteinte de nos jours. Cela interdit également toutes les optimisations qui reposent sur la notification de changements mineurs dans l’état du jeu, comme ce qui a été fait dans le jeu exemple Pacman avec le moteur de jeu qui notifie le moteur de rendu. Pour les jeux qui requièrent cette approche, comme les jeux extrêmement rapides comme les FPS et les jeux de combat, l’état du jeu est très petit et une simple propagation de celui-ci convient pleinement.

La deuxième approche est plus complexe à mettre en œuvre, sauf si le terrain a déjà été préparé. En effet, si la mise à jour de l’état du jeu repose sur un patron commande, il existe déjà une mécanique qui permet de connaître ce qui a été modifié. Pour être plus précis, cette mécanique permet de connaître non pas ce qui a été modifié, mais ce qui modifie l’état du jeu, à savoir les commandes. Celles-ci sont peu nombreuses et peu complexes puisque produites par des êtres humains : même les plus grands joueurs de Starcraft ne dépassent jamais les 1 000 commandes par minute, ce qui est largement...

Solutions des exercices

1. Exercice 1.3.1 : Paralléliser la recherche exhaustive de collisions

Une solution est proposée dans le dossier « examples/chap06/collisions01mt », et des tests unitaires dans la classe ExhaustiveColliderMTTest dans le dossier « examples/chap06/collisions » des packages de test. La classe ExhaustiveColliderMT implante l’interface Collider définie dans le dossier « examples/chap06/collisions ». Elle contient une liste de boîtes, boxes, à utiliser pour la recherche de collisions.

Pour paralléliser la recherche, la liste des boîtes englobantes est découpée en plusieurs morceaux, chaque morceau étant traité par un thread :

public List<AABB> collides(AABB aabb) {

La variable chunkSize définit la taille d’un morceau de la liste. Elle est divisée par 16 pour obtenir un nombre un peu plus grand que le nombre de threads sur les machines les plus puissantes :

   int chunkSize = boxes.size() / 16;

Cette valeur de division ne signifie pas que 16 threads sont utilisés : cela dépend du pool de threads utilisé.

La variable chunkIndex contient l’indice de la première boîte pour le prochain morceau :

   int chunkIndex = 0;

Une liste de futurs est définie pour suivre le résultat des tâches parallèles qui sont soumises :

   ArrayList<Future<List<AABB>>> futures = new ArrayList();

Tant que tous les morceaux de la liste ne sont pas planifiés pour traitement :

   while (chunkIndex < boxes.size()) {

Calcul des indices du prochain morceau :

       int fromIndex = chunkIndex; 
       int toIndex = chunkIndex + chunkSize; 
       if (toIndex >= boxes.size()) { 
           toIndex = boxes.size(); 
       }

Extraction du prochain morceau de la liste des boîtes :

       List<AABB> subList = boxes.subList(fromIndex, toIndex);

Le traitement du morceau est soumis au pool de threads par défaut dans la JVM. Le futur renvoyé est mémorisé dans la liste futures :

       futures.add(ForkJoinPool.commonPool().submit(new...