Approximation Algorithm for Estimating Distances in Distributed Virtual Environments

Olivier Beaumont (1) , Tobias Castanet (2) , Nicolas Hanusse (2) , Corentin Travers (2)

1 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

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.

Mots clés: Distributed Virtual Environments; Online games; Random walks; Peer-to-peer algorithms; Distributed approximation algorithms

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Olivier Beaumont, Tobias Castanet, Nicolas Hanusse, Corentin Travers. Approximation Algorithm for Estimating Distances in Distributed Virtual Environments. [Research Report] LaBRI - Laboratoire Bordelais de Recherche en Informatique; Inria Bordeaux Sud-Ouest; CNRS LaBRI; Bordeaux INP. 2020. ⟨hal-02486218v2⟩