Brevet FR2864659A1 — publié le 20050701

PROCEDE DE RECHERCHE D'ENTITE DANS UN ENVIRONNEMENT VIRTUEL Domaine technique et art antérieur L'invention concerne un procédé de recherche d'entité dans un environnement virtuel. L'invention s'applique, par exemple, à la communication entre entités immergées dans un monde virtuel massivement partagé. Un monde virtuel est un espace partagé généré par ordinateur dans lequel plusieurs entités interconnectées peuvent interagir entre elles et avec l'espace partagé. Les entités sont contrôlées par des utilisateurs ou par ordinateur. D'un point de vue concret, le support physique d'un monde virtuel est constitué d'un ensemble de terminaux, par exemple des ordinateurs personnels, reliés en réseau et échangeant des données. Un terminal peut héberger plusieurs entités différentes. Quand une entité produit une action dans l'environnement virtuel (déplacement, disparition, changement d'apparence, etc.), cette action doit être transmise à d'autres entités afin de garantir la cohérence du monde virtuel. La transmission des actions ou événements utilise généralement beaucoup de ressources. Dans le cas où le monde virtuel est massivement partagé et où le nombre de terminaux est important, la transmission des signaux peut consommer beaucoup de bande passante et nécessiter des temps de calcul assez longs. Il est alors nécessaire de réduire le nombre d'entités concernées par un événement à un ensemble restreint d'entités dites entités voisines de l'événement. Traditionnellement, chaque entité dispose d'une position dans le monde virtuel. La connaissance de la position des différentes entités permet un calcul des distances entre les entités. Il est alors possible de définir les entités devant être considérées comme voisines. Selon l'art connu, différentes architectures existent pour définir et mettre en relation les entités qui doivent être considérées comme voisines. Une première architecture comprend un serveur central relié à l'ensemble des entités du monde virtuel. Le serveur central a la connaissance des positions des entités et en déduit les entités qui sont considérées comme voisines dans le monde virtuel. D'autres architectures existent telles que, par exemple, l'architecture hiérarchique dans laquelle le monde virtuel est découpé en différentes zones d'entités voisines, chaque zone étant placée sous l'autorité d'un responsable. Quand une entité pénètre dans une zone, elle prend alors contact avec le responsable de la zone qui lui fournit les informations nécessaires pour pouvoir se mettre en relation avec les autres entités de la zone. Une autre architecture existe sous la forme d'un réseau de pairs dans lequel chaque entité collabore avec les entités qui sont ses voisines. La figure 1 représente un exemple d'architecture de monde virtuel à serveur central. L'architecture comprend un ensemble d'entités E1, E2, E3, E4, E5, ..., En et un serveur central SC. Chaque entité Ei (i=1, 2, 3, 4, 5, ..., n) est hébergée par un terminal TEi. Dans l'exemple de la figure 1, les entités El, E2, E3 constituent un premier groupe d'entités voisines et les entités E3, E4 et E5 constituent un deuxième groupe d'entités voisines. Les entités voisines de chaque groupe échangent des données entre elles. Toutes les entités sont reliées au serveur central SC. Lorsqu'une entité recherche une entité munie d'un prédicat P particulier (par exemple capable de transmettre la vidéo ou encore dont le pseudo commence par la lettre B ), elle s'adresse d'abord aux entités de son voisinage. Si l'entité recherchée est au-delà de son voisinage, le serveur central intervient pour réaliser la recherche. La recherche des entités par le serveur central peut conduire à utiliser de manière importante les ressources du serveur central. Le fonctionnement du monde virtuel peut alors s'en trouver affecté. Par ailleurs, toute défaillance du serveur central peut également conduire à perturber gravement le fonctionnement du monde virtuel. L'invention ne présente pas les inconvénients mentionnés ci-dessus. Exposé de l'invention En effet, l'invention concerne un procédé de recherche, dans un monde virtuel comprenant un premier ensemble d'entités voisines et au moins un deuxième ensemble d'entités voisines, d'au moins une entité du monde virtuel vérifiant un prédicat, le procédé comprenant l'émission, par un terminal qui héberge une première entité appartenant au premier ensemble d'entités voisines, d'une requête vers au moins un deuxième terminal qui héberge une deuxième entité appartenant au premier ensemble d'entités voisines, la requête comprenant une adresse du terminal qui héberge la première entité, une référence de port de communication pour l'établissement d'une communication entre le terminal qui héberge la première entité et un autre terminal et le prédicat. Le procédé comprend au moins une étape supplémentaire dans laquelle au moins un terminal qui héberge une entité qui appartient au premier ensemble d'entités voisines et au deuxième ensemble d'entités voisines reçoit la requête et retransmet la requête à au moins un terminal qui héberge une autre entité du deuxième ensemble d'entités voisines. Si l'autre entité du deuxième ensemble d'entités voisines à laquelle la requête est retransmise vérifie le prédicat, le terminal qui héberge l'autre entité émet une réponse positive vers le terminal qui héberge l'entité qui a émis la requête. Cette réponse peut être transmise directement ou via tout ou partie des terminaux qui ont participé à la transmission de la requête. Que l'autre entité du deuxième ensemble d'entités voisines à laquelle la requête est retransmise vérifie ou non le prédicat, le terminal qui héberge ladite autre entité peut retransmettre la requête vers au moins un terminal qui héberge une de ses entités voisines. Avantageusement, l'invention permet ainsi à une entité d'effectuer une recherche de prédicat de proche en proche, au-delà de l'ensemble de ses voisins, par propagation d'une requête, quelle que soit l'architecture du monde virtuel qui est utilisée pour la mise en relation des entités voisines. Du fait de la coopération entre les entités, l'architecture de monde virtuel qui met en oeuvre le procédé de l'invention ne nécessite alors aucune structure spécifique dédiée à la recherche. L'invention concerne également un programme d'ordinateur stocké sur un support d'information, caractérisé en ce que le programme comporte des instructions pour la mise en oeuvre d'un procédé selon l'invention. L'invention concerne encore un support d'information lisible par un système informatique, caractérisé en ce qu'il contient des instructions d'un programme d'ordinateur pour la mise en oeuvre d'un procédé selon l'invention. Brève description des figures La figure 1, déjà décrite, représente un exemple d'architecture de monde virtuel selon l'art antérieur. La figure 2 représente, à titre d'exemple, une architecture de monde virtuel selon l'invention. Sur toutes les figures, les mêmes repères désignent les mêmes éléments. Description détaillée de modes de mise en oeuvre de l'invention La figure 2 représente, de façon symbolique, un exemple de monde virtuel comprenant huit entités A, B, C, D, E, F, M, G. C'est pour des raisons de clarté, afin de ne pas surcharger la figure, que le monde virtuel représenté en figure 2 ne comprend que huit entités. Comme cela est connu de l'homme de l'art, un monde virtuel est généralement composé d'un très grand nombre d'entités, par exemple plusieurs dizaines de milliers. Les entités A, B, C, E, F, G constituent un premier groupe d'entités voisines. Les entités C, D, E constituent un deuxième groupe d'entités voisines. Les entités D, E, M constituent un troisième groupe d'entités voisines. Les entités E, F, M constituent un quatrième groupe d'entités voisines. Le procédé de recherche de prédicat selon l'invention basé sur la coopération entre les entités du monde virtuel va maintenant être décrit. Supposons que l'entité A souhaite entrer en contact avec une entité du monde virtuel qui vérifie le prédicat P. Le prédicat P est une caractéristique particulière telle que, par exemple, capable de transmettre de la vidéo ou dont le pseudo commence par la lettre B . Le terminal TA qui héberge l'entité A envoie alors à au moins un des terminaux qui hébergent les entités voisines de A (B, C, E, F, G) une requête r1 contenant, entre autres, l'adresse IP(TA) du terminal TA (par exemple une adresse de type Internet Protocol )), une référence de port de communication disponible du terminal TA pour l'établissement d'une communication entre le terminal TA et un autre terminal et le prédicat P. Supposons que le terminal TE qui héberge l'entité E voisine de A reçoive la requête r1. Si l'entité E vérifie le prédicat P, le terminal TE adresse une réponse positive RE(rl) directement à l'entité A. Par réponse positive, il faut entendre que le signal qui est envoyé du terminal TE qui héberge l'entité E vers le terminal TA qui héberge l'entité A contient des informations qui indiquent que l'entité E vérifie le prédicat P. Outre ces informations, le signal envoyé du terminal TE vers le terminal TA contient l'adresse du terminal TE qui héberge l'entité E et une référence de port de communication disponible du terminal TE. Si l'entité E ne vérifie pas le prédicat P, elle peut ou non décider de retransmettre la requête de l'entité A à certains de ses propres voisins, par exemple l'entité M. Si l'entité E décide de retransmettre la requête reçue de l'entité A vers l'entité M, le signal envoyé par le terminal TE contient la requête, l'adresse du terminal TE et une référence de port de communication disponible du terminal TE. Si l'entité M vérifie le prédicat P, le terminal TM qui héberge l'entité M émet alors une réponse positive destinée à l'entité A. La réponse de l'entité M à l'entité A fait alors un trajet inverse de celui effectué par la requête émise. En l'occurrence, la réponse est alors transmise du terminal TM vers le terminal TA, via le terminal TE. Il est également possible que la réponse de l'entité M à l'entité A s'effectue directement de M vers A, en utilisant les données relatives à l'adresse du terminal TA et à la référence de port de communication du terminal TA qui sont contenues dans la requête qui a été transmise. Le procédé de recherche selon l'invention prévoit avantageusement plusieurs manières différentes pour sélectionner les entités en vue d'une recherche de prédicat. Selon un premier mode de réalisation de l'invention, chaque entité du monde virtuel qui reçoit une requête de recherche de prédicat retransmet la requête à toutes ses entités voisines. Selon un deuxième mode de réalisation de l'invention, une requête contient des données de comptage qui indiquent le nombre de fois où la requête a été retransmise. Il est alors possible qu'une requête ne soit plus retransmise dès lors que le nombre de fois où la requête a été retransmise atteint une valeur prédéterminée. Selon un troisième mode de réalisation de l'invention, une entité retransmet une requête selon une loi de probabilité. Selon une variante du troisième mode de réalisation de l'invention, la loi de probabilité varie en fonction du nombre de voisins de l'entité qui retransmet la requête. Selon un quatrième mode de réalisation de l'invention, il est prévu qu'au moins une entité vérifie quelles entités, parmi les entités qui sont ses voisines, ont déjà reçu la requête avant de retransmettre celle-ci et, si une entité voisine a déjà reçu la requête, il est prévu de ne pas lui transmettre la requête. Comme cela a été mentionné précédemment, le procédé de recherche d'entité selon l'invention est avantageusement indépendant de l'architecture utilisée pour la mise en relation des entités virtuelles. Il est alors possible d'utiliser l'une quelconque des architectures de mise en relation mentionnées précédemment, à savoir une architecture à serveur central, une architecture hiérarchique, ou un réseau de pairs. REVENDICATIONS 1. Procédé de recherche, dans un monde virtuel comprenant un premier ensemble d'entités voisines (A, B, C, E, F, G) et au moins un deuxième ensemble d'entités voisines (D, E, M), d'au moins une entité du monde virtuel vérifiant un prédicat, le procédé comprenant l'émission, par un terminal qui héberge une première entité (A) appartenant au premier ensemble d'entités voisines, d'une requête (ri) vers au moins un deuxième terminal qui héberge une deuxième entité (B, C, E, F, G) appartenant au premier ensemble d'entités voisines, la requête comprenant une adresse du terminal qui héberge la première entité (A), une référence de port de communication pour l'établissement d'une communication entre le terminal qui héberge la première entité (A) et un autre terminal et le prédicat, caractérisé en ce qu'il comprend au moins une étape supplémentaire dans laquelle au moins un terminal qui héberge une entité (E) qui appartient au premier ensemble d'entités voisines et au deuxième ensemble d'entités voisines reçoit la requête (ri) et retransmet la requête (ri) à au moins un terminal qui héberge une autre entité (M) du deuxième ensemble d'entités voisines (D, E, M). 2. Procédé de recherche selon la revendication 1, caractérisé en ce que, si l'autre entité (M) du deuxième ensemble d'entités voisines (D, E, M) à laquelle la requête est retransmise vérifie le prédicat, le terminal qui héberge ladite autre entité émet une réponse positive (RM(r1)) vers le terminal qui héberge l'entité qui a émis la requête (ri). 3. Procédé selon la revendication 2, caractérisé en ce que la réponse positive (RM(rl)) émise par le terminal qui héberge ladite autre entité (M) est transmise via tout ou partie d'un ensemble de terminaux qui ont participé à la retransmission de la requête (ri). 4. Procédé selon la revendication 2, caractérisé en ce que la réponse positive (RM(r1)) émise par le terminal qui héberge ladite autre entité (M) est transmise directement du terminal qui héberge ladite autre entité (M) vers le terminal qui a émis la requête (ri). 5. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le terminal qui héberge l'autre entité (M) du deuxième ensemble d'entités voisines (D, E, M) retransmet la requête (ri) vers au moins un terminal qui héberge une des entités voisines de ladite autre entité (M). 6. Procédé de recherche selon la revendication 1, caractérisé en ce que, si l'autre entité (M) du deuxième ensemble d'entités voisines (D, E, M) à laquelle la requête est retransmise ne vérifie pas le prédicat, le terminal qui héberge ladite autre entité retransmet la requête (ri) vers au moins un terminal qui héberge une des entités voisines de ladite autre entité. 7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que chaque terminal qui héberge une entité du monde virtuel qui reçoit une requête retransmet la requête à tous les terminaux de ses entités voisines. 8. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'une requête comprend des données de comptage qui indiquent le nombre de fois où la requête a été retransmise. 9. Procédé selon la revendication 8, caractérisé en ce que la requête n'est plus retransmise dès lors que le nombre de fois où la requête a été retransmise atteint une valeur prédéterminée. 10. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que la requête est retransmise selon une loi de probabilité. 11. Procédé selon la revendication 10, caractérisé en ce que la loi de probabilité varie en fonction du nombre de voisins de l'entité qui retransmet la requête. 12. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que, avant qu'un premier terminal qui héberge une entité ne retransmette une requête vers un deuxième terminal qui héberge une autre entité, il est vérifié si le deuxième terminal a déjà reçu la requête et, si le deuxième terminal a déjà reçu la requête, la requête n'est pas retransmise au deuxième terminal par le premier terminal. 13. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que, si l'entité voisine (E) de la première entité (A) vérifie le prédicat, le terminal qui l'héberge émet une réponse positive (RE(rl) vers le terminal qui héberge l'entité (A) qui a émis la requête. 14. Programme d'ordinateur stocké sur un support d'information, caractérisé en ce que le programme comporte des instructions pour la mise en uvre d'un procédé selon l'une quelconque des revendications 1 à 13. 15. Support d'information lisible par un système informatique, caractérisé en ce qu'il contient des instructions d'un programme d'ordinateur pour la mise en oeuvre d'un procédé selon l'une quelconque des revendications 1 à 13.