Approximation Algorithm for Estimating Distances in Distributed Virtual Environments - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Approximation Algorithm for Estimating Distances in Distributed Virtual Environments

Résumé

This article deals with the issue of guaranteeing properties in Distributed Virtual Environments (DVEs) without a server and without global knowledge of the system state and therefore only by exchanging messages. This issue is particularly relevant in the case of online games, that operate in a fully distributed framework and for which network resources such as bandwidth are the critical resources. In the context of games, players typically need to know the distance between their character and other characters, at least approximately. Players all share the same position estimation algorithm but, in general, do not know the current positions of others. We provide a synchronized distributed algorithm Alc to guarantee, at any time, that the estimated distance d est between any pair of characters A and B is always a 1 + ε approximation of the current distance d act. Our result is twofold: (1) we prove that if characters move randomly on a d-dimensional grid, or follow a random continuous movement on up to three dimensions, the number of messages of Alc is optimal up to a constant factor; (2) in a more practical setting, we also observe that the number of messages of Alc for actual game traces is much less than the standard algorithm sending actual positions at a given frequency.
Fichier principal
Vignette du fichier
Approximation_Algorithm_for_Estimating_Distances_in_Distributed_Virtual_Environments.pdf (853.96 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02486218 , version 1 (20-02-2020)
hal-02486218 , version 2 (26-02-2020)
hal-02486218 , version 3 (10-03-2020)

Identifiants

Citer

Olivier Beaumont, Tobias Castanet, Nicolas Hanusse, Corentin Travers. Approximation Algorithm for Estimating Distances in Distributed Virtual Environments. Euro-Par 2020 - 26th International European Conference on Parallel and Distributed Computing, Aug 2020, Warsaw / Virtual, Poland. ⟨10.1007/978-3-030-57675-2_23⟩. ⟨hal-02486218v3⟩
174 Consultations
140 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More