descubriendo la sincronización detrás de los juegos multiplayer lucas guaycochea – javier luiso...

Descubriendo la sincronización Descubriendo la sincronización detrás de los juegos multiplayerdetrás de los juegos multiplayer

Lucas Guaycochea – Javier Luiso10 y 11 de Diciembre – Hotel Panamericano - Buenos Aires

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Índice

• Introducción• Un sistema distribuido• La Sincronización• Solución desarrollada• Usos de la plataforma

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Índice

• Introducción• Un sistema distribuido• La Sincronización• Solución desarrollada• Usos de la plataforma

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Introducción Juegos Multiplayer (I)

Un juego multijugador o multiplayer es aquel donde al menos dos participantes desarrollan el juego en el mismo mundo virtual y existe

interacción entre ellos.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

IntroducciónJuegos Multiplayer (II)

Los jugadores pueden:

• Jugar en un mismo dispositivo (PC, consola).

• Jugar en distintos dispositivos:• dentro de una misma red local.• conectados a Internet.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

IntroducciónEl Desafío

• El principal desafío es que en cada dispositivo, donde se lleva a cabo el juego, se perciba la misma realidad virtual.• Los resultados de las acciones de cada jugador deben

percibirse de la misma manera por todos.• Las acciones deben comunicarse entre los participantes

del juego.• No debe degradarse la interacción de cada jugador en su

dispositivo, manteniendo la fluidez del juego.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Introducción Sistema Distribuido

• Un juego multiplayer tiene las características de un sistema distribuido.• “Un conjunto de computadoras independientes que se

presentan a sus usuarios como un sistema único y coherente” [1]

• En este caso, el juego, el mundo virtual, es el que se presenta como único a cada participante en cada dispositivo.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Índice

• Introducción

• Un sistema distribuido• La Sincronización• Solución desarrollada• Usos de la plataforma

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuido Características

• Dispositivos interconectados en una red.• La comunicación se realiza mediante el envío de

mensajes.• Las latencias de la comunicación no deben degradar

notoriamente la performance respecto de un sistema centralizado.

• Existen distintos modelos de comunicación o arquitecturas.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoArquitecturas

• Los distintos tipos son:– Cliente/Servidor

– Peer-to-peer

– Híbridas

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuido Cliente/Servidor

Esquema Arquitectura Cliente - Servidor

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoCliente/Servidor

• Características• Nodos clientes que requieren servicios de un nodo

servidor. [1]• El servidor concentra el principal procesamiento

del sistema.• Las interacciones son sólo entre cada cliente con

el servidor.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoCliente/Servidor

• Características en los juegos…• Nodos clientes que requieren servicios de un nodo servidor. [1]

• Clientes envían acciones de los jugadores y consumen información para evolucionar el mundo virtual.

• El servidor concentra el principal procesamiento del sistema.

• El servidor mantiene y evoluciona el estado del juego.• Procesa las acciones de los clientes y difunde el nuevo

estado.• Las interacciones son sólo entre cada cliente con el servidor.

• Cada jugador se entera de las acciones de los demás ( o sus resultados) a través del servidor.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoPeer-to-peer

Esquema Arquitectura Peer-to-peer

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoPeer-to-peer

• Características• Los nodos son todos iguales, no se diferencian

entre ellos.• El procesamiento es compartido entre todos los

nodos.• Todos los nodos se conectan entre ellos.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoPeer-to-peer

• Características en los juegos …• Los nodos son todos iguales, no se diferencian entre ellos.

• Cada nodo mantiene una réplica del estado del juego.• El procesamiento es compartido entre todos los nodos.

• No existe un punto central de procesamiento.• Cada nodo procesa todas las acciones y evoluciona su copia

del juego.• Todos los nodos se conectan entre ellos.

• Cada nodo comunica a todos los demás las acciones realizadas por el jugador local.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoArq. Híbrida

Esquema Arquitectura Híbrida

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoArq. Híbrida

• Características• Nodos clientes conectados a un nodo servidor.• Nodos servidores interconectados entre ellos.• El procesamiento principal se concentra en el

grupo de servidores.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoArq. Híbrida

• Características en los juegos …• Nodos clientes conectados a un nodo servidor.

• Clientes envían acciones de los jugadores y consumen información para evolucionar el mundo virtual.

• Nodos servidores interconectados entre ellos.

• Los servidores se comunican entre ellos las acciones de los jugadores que tienen conectados.

• El procesamiento principal se concentra en el grupo de servidores.

• Cada servidor procesa las acciones y evoluciona el estado del juego.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoAnálisis de los modelos

• Los modelos vistos pueden analizarse según:• Su escalabilidad• Latencia de las acciones• Su robustez• El manejo de la consistencia• Su seguridad ante trampas (cheating)• Motivos comerciales

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoEscalabilidad

• En C/S, el servidor puede saturarse, se convierte en cuello de botella.

• En el modelo híbrido, la carga puede distribuirse entre los servidores.

• En P2P, cada nodo puede saturarse en presencia de muchos peers.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoLatencias

• El modelo C/S presenta mayores latencias.

• En P2P, la comunicación de acciones es directa.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoRobustez

• El servidor presenta un único punto de falla.• En P2P, la caída de un nodo no afecta al resto.• En arquitecturas híbridas, ante la caída de un

servidor otro toma su lugar.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoConsistencia

• En C/S, es sencillo, fácil de implementar.

• En P2P, se requieren mecanismos especiales de sincronización.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoSeguridad

• En C/S, es sencillo controlar y detectar a los cheaters.

• En P2P, es más difícil detectar y evitar a los cheaters. Existen mecanismos más complejos para hacerlo.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoMotivos Comerciales

• C/S permite:– Dar control a la empresa productora.– Autenticar usuarios legales– Actualizar las copias clientes– Cobrar por uso de los servidores

• P2P, permite jugar sin la intervención de la empresa productora.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Un sistema distribuidoConsecuencias

• Múltiples participantes dentro de un mismo mundo virtual.• Acciones que afectan al mundo, originadas en múltiples nodos.• El orden en que se ejecuten dichas acciones determina hacia donde evoluciona el juego.

La necesidad de establecer un orden único para ejecutar las acciones requiere incorporar un mecanismo que permita sincronizar los distintos dispositivos participantes.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Índice

• Introducción• Un sistema distribuido

• La Sincronización• Solución desarrollada• Usos de la plataforma

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

La Sincronización

La sincronización es la base de los juegos multiplayer.

Hace posible que los participantes jueguen “juntos” dentro de un mismo mundo virtual y que este sea percibido de manera consistente

por todos.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

La Sincronización

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

La SincronizaciónLas acciones de cada jugador generan eventos que tendrán

su incidencia en el mundo virtual. • Para una evolución consistente los resultados de las

acciones deben ser vistos en el mismo orden por todos los participantes.

Sincronizar se trata de decidir cuando es consistente ejecutar un evento.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

La Sincronización

Tipos de soluciones• Conservativa• Previenen la inconsistencia verificando que los eventos

se ejecuten sólo cuando sea seguro hacerlo.• Optimista• Ejecutan los eventos al disponer de ellos. Cuando se

detecta una inconsistencia se intenta corregirla deshaciendo las últimas operaciones realizadas.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

La Sincronización

Soluciones conservativasLockstep Synchronization: El servidor ejecuta una acción en un instante de tiempo luego de recibir los comandos de todos los participantes. [2]

Bucket Synchronization: El servidor espera un cierto tiempo antes de actualizar el estado del mundo virtual. Muchos RTS utilizan este mecanismo, esperando al participante “mas lento”.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

La Sincronización

Soluciones optimistas

Time Warp Synchronization (TWS): En cada ciclo se guarda una captura del estado del juego, para poder restaurarlo si llega a ser necesario. SI esto sucede, se generan “anti-mensajes” para deshacer las acciones que se tornaron inválidas.

Trailing State Synchronization (TSS): Se mantienen dos copias del estado del juego, tomadas en diferentes momentos. “Volver para atrar” es tomar la copia más antigua y volver a ejecutar todas las acciones nuevamente.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Índice

• Introducción• Un sistema distribuido• La Sincronización

• Solución desarrollada• Usos de la plataforma

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Solución Desarrollada Punto de partida

• Tenemos un motor gráfico para el desarrollo de simuladores• El motor gráfico permite:

– Modelar mundos virtuales.– Crear un escenario tridimensional.– Instalar objetos gráficos.– Dar comportamiento a los objetos gráficos.– Visualizar el escenario a través de una o más cámaras en diferentes

ventanas.– Evolucionar los comportamientos en el tiempo.– Realizar consultas y obtener reportes de eventos del mundo virtual.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Solución DesarrolladaMetas Fijadas

• Desarrollar simuladores distribuidos.

• Aprovechar el motor gráfico.

• Abstraer al desarrollador de la distribución respecto a la actividad sobre el motor gráfico.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Solución Desarrollada Ideas

• No introducir cambios en el motor gráfico.• Encapsular el motor gráfico dentro de una

plataforma.• Desarrollar una capa encargada de la

distribución sobre el motor gráfico.• Proveer a la aplicación usuaria la misma

interfaz que provee el motor gráfico.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Solución Desarrollada Diseño general

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

• Arquitectura distribuida

• Organización lógica de los participantes

• Mecanismo de sincronización

Solución DesarrolladaDecisiones de diseño

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Solución Desarrollada Arquitectura Distribuida

• Adoptamos una arquitectura P2P:– Evitamos la necesidad de realizar sistemas que

precisen un servidor especial para los aspectos gráficos. (Escalabilidad y Robustez)

– Los simuladores estarán en una red local. (Seguridad)

– El tiempo de respuesta es fundamental (Baja Latencia)

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Solución Desarrollada Organización lógica

• Usamos contextos de ejecución.– Representan la simulación de un mundo virtual

particular.– Se establecen subgrupos de peers.– Son independientes entre sí.– Un nodo puede participar en dos o más

simultáneamente.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Solución Desarrollada Sincronización (I)

• Resolvemos la sincronización para garantizar la consistencia en cada nodo.

• Sincronizamos SÓLO las acciones que afectan al modelado del mundo virtual.

• Visualización, reportes y consultas se resuelven localmente en cada nodo.

• Utilizamos un mecanismo conservador.• Para asegurar un orden temporal de las acciones, nos

basamos en un algoritmo propuesto por Chandy y Misra [3].

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Solución DesarrolladaSincronización (II)

• El mecanismo de sincronización consta de 4 tareas o procesos:

1. Detecta las acciones locales, les incluye una marca de tiempo, y las difunde a los demás participantes.

2. Recibe las acciones de los demás participantes.3. Ordena temporalmente las acciones locales y

remotas.4. Ejecuta las acciones de manera ordenada.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Solución Desarrollada

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Solución Desarrollada Sincronización (III)

• Consideraciones importantes:– Cuando hay inactividad de un jugador, la primer

tarea también debe enviar “acciones nulas”. – En cada nodo se implementó un reloj que marca el

paso del tiempo de manera discreta.– Periódicamente los relojes se sincronizan con uno

que es elegido como referencia o líder.– Localmente, la evolución del modelo en intervalos

de tiempo también se ordena entre las demás acciones.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Índice

• Introducción• Un sistema distribuido• La Sincronización• Solución desarrollada

• Usos de la plataforma

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Usos de la plataforma• Simulador para entrenamiento de tripulaciones de

tanques de guerra argentinos.• Ejercicios de uno o más vehículos.• Ejercicios dirigidos por un instructor externo.• Un instructor puede dirigir varios ejercicios

simultáneamente.• Simulador de vuelo en varias pantallas.

• La visión del piloto se muestra utilizando 2 o más proyectores.

• Demo: Pac–Tank ©

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Usos de la plataforma

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Referencias

[1]. Tanenbaum, A., V. Steen, M.: Distributed Systems, Principles and Paradigms. Prentice Hall, Lugar (2002)

[2]. Cronin, E., Filstrup, B., Jamin, S.: Cheat-Proofing Dead Reckoned Multiplayer Games. In Proc. ADCOG 2003, January 2003

[3]. Chandy K.M., Misra J.: Distributed Simulation: A Case Study in Design and Verfication of Distributed Programs. IEEE Transactions on Software Engineering, Vol. SE-5, No. 5, September 1979.

[]. Luiso, J. , Guaycochea, L., Abbate, H.: Simuladores de entrenamiento distribuidos: Plataforma de desarrollo para ocultar los aspectos de la distribución. In Proc. WAVI 2010.

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

¿ Preguntas ?

10 y 11 de Diciembre – Hotel Panamericano – Buenos Aires

Muchas Gracias por su atención !

Lucas GuaycocheaJavier Luiso