Multi User Games Tulio Mono

INF 2056 – Algoritmos Distribuídos Monografia – 2006/01 Algoritmos Distribuídos em Jogos Multi-Usuário

Professor: Markus Endler Aluno: Tulio Jorge A. N. S. Anibolete

ÍNDICE 1)

INTRODUÇÃO ...................................................................................................... 3

2)

TIPOS DE JOGOS.................................................................................................. 5

3)

ARQUITETURAS DE REDES PARA JOGOS ..................................................... 6

4)

ALGORITMOS DISTRIBUÍDOS PARA SINCRONIZAÇÃO ............................ 9

5)

CONCLUSÃO ...................................................................................................... 16

6)

REFERÊNCIAS.................................................................................................... 17

1)

INTRODUÇÃO

Os jogos são, sem dúvida, uma das grandes opções de entretenimento proporcionado pelos computadores. Acostumados a apaixonar muitos durante a juventude, os jogos costumam ser responsáveis pelo interesse de alguns em pesquisas e desenvolvimento na área da informática. Com a evolução das redes de computadores, principalmente a internet, foi possível criar ambientes virtuais nos quais os jogadores podem interagir entre si e com objetos de um “mundo virtual”, compartilhando tempo e espaço. Surge então o conceito de jogos distribuídos ou jogos multi-jogadores. Jogos multi-jogadores (também chamados de jogos multi-player) são jogos de computador que permitem a participação simultânea de vários jogadores em uma mesma partida, contrastando com a maioria dos jogos de computador mais antigos que possibilitavam apenas um jogador por partida. [1] Para suportar esta evolução, vários tipos de arquiteturas foram propostas e estão em constante estudo. [3] Inicialmente, os jogos multi-jogadores surgiram da necessidade de simulações militares. Uma simulação militar real acarreta um alto custo financeiro e um grande risco de vida. A solução foi partir do real para o virtual e, desta maneira, os jogos multi-player se originaram. [3] Juntamente com a evolução dos jogos, vieram vários desafios, alguns serão abordados neste trabalho, no que diz respeito à sincronização. A maioria dos jogos distribuídos é considerada uma aplicação de tempo real. Ou seja, são sistemas que possuem restrições de tempo para a execução de suas tarefas. [4]

3

Figura – Exemplos de jogos distribuídos. Estima-se que até o ano de 2009, a indústria de jogos multiplayer na internet irá crescer até 9.2 bilhões de dólares. A previsão para este ano, 2006, é de 5.2 bilhões. [6] A internet é a maior responsável em prover uma infra-estrutura para conectar os jogadores. Nos primeiros três meses de 2000, nos EUA, 45% dos pacotes UDP da internet se originaram exclusivamente de jogos. [7]

4

2)

TIPOS DE JOGOS

Existem quatro categorias diferentes de jogos: [3] ▪ FPS – Jogos de tiro em primeira pessoa (First Person Shooters) ▪ RTS – Jogos de estratégia em tempo real (Real Time Strategy) ▪ MMORPG – Jogos de multiplayer massivos (Massively Multiplayer Online Role Playing Game) ▪ NRT – Jogos de tempo não real (Non Real Time)

Segue a tabela com as características de cada um dos tipos supracitados. As arquiteturas serão abordadas com detalhes no próximo tópico. FPS

RTS

MMORPG

NRT

Arquitetura

Cliente/Servidor

Cliente/Servidor, P2P

Cliente/Servidor

P2P

Jogadores

Poucos

Poucos

Muitos

-

Servidores

Muitos

Poucos

Poucos

Nenhum

Persistência

Curta

Curta

Longa

-

Exemplos

Quake, HL

Starcraft, Warcraft

WoW, Ultima

Xadrez

5

3)

ARQUITETURAS DE REDES PARA JOGOS

Existem duas arquiteturas de rede que podem ser implementadas: peer-to-peer e cliente/servidor. [5] Na arquitetura p2p, todos os computadores estão conectados diretamente uns aos outros. Dessa forma, um computador conhece todos os outros conectados na rede. Nas sessões de jogo baseadas nessa arquitetura, cada máquina é responsável por enviar seus dados para todas as outras. Algumas das características deste modelo são: [3] ▪ A dificuldade para manter a consistência (sincronismo) do jogo em todos os computadores. ▪ O alto número de conexões requeridas caso existam muitas máquinas na rede, o que acarreta um alto tráfego de dados. O andamento do jogo também pode ser prejudicado caso um dos participantes possua uma conexão lenta com relação aos demais. Por esses motivos, essa arquitetura é indicada para redes pequenas, pois as mesmas costumam ser velozes e estáveis.

Figura – Exemplo de uma rede P2P (Peer-to-peer).

6

No modelo cliente/servidor, todos os participantes (clientes) estão conectados no computador central (servidor). O servidor é responsável por receber os dados de cada jogador e repassar para os outros. Os clientes, a priori, não possuem conhecimento sobre os outros computadores. Esse tipo de arquitetura possui as seguintes características: [3] ▪ Redução do número de conexões na rede, pois cada cliente só precisa estar conectado a um único computador (o servidor). O único computador que necessita de uma conexão rápida é o servidor, para que este possa enviar os dados para cada cliente adequadamente; ▪ Melhor escalabilidade, ou seja, é possível aumentar a carga sobre o sistema semprejudicar a qualidade de serviço percebida pelos jogadores (até um certo limite); ▪ A centralização da gestão do estado do jogo no servidor possibilita que seja feita uma validação dos dados enviados, o que é importante para combater trapaças nos jogos em rede. A principal desvantagem do modelo é que o servidor precisa ter alto poder de processamento e uma conexão veloz para suprir a demanda. A arquitetura cliente servidor costuma ser implementada em jogos possuidores de uma grande quantidade de jogadores simultâneos (normalmente da ordem de milhares).

Figura – Exemplo de uma rede cliente/servidor.

7

Segue a tabela com uma comparação entre as arquiteturas.

Cliente/Servidor

P2P

Alta, usuário deve esperar ao menos uma rodada para ter visualizar a execução das suas ações.

Baixa, mensagem trocada diretamente entre os clientes.

Escalabilidade

Boa, enquanto o servidor possuir banda suficiente.

Ruim, pois o multicast não foi comercialmente implantado na internet, mensagens são enviadas de forma unicast.

Controle Central

Sim, reduzindo trapaças e limitando pirataria.

Não.

Cópia do Estado do Jogo

Somente uma cópia do estado do jogo é mantida pelo servidor.

Múltiplas cópias do estado do jogo são mantidas sem controle central.

Entrada dinâmica (um jogador pode entrar no jogo depois do mesmo já ter iniciado)

Fácil, o servidor tende a rodar o jogo por um tempo indefinido permitindo que os usuários sejam livres para sair ou entrar.

Difícil.

Latência

8

4)

ALGORITMOS DISTRIBUÍDOS PARA SINCRONIZAÇÃO

Um dos maiores problemas encontrados nos jogos multi-jogador é o atraso de transmissão da rede. Isto significa a demora entre a geração de um evento por parte de algum jogador e a disseminação do mesmo para os outros. É indispensável que cada cliente possua uma visão consistente do estado do jogo, ou seja, é necessário um mecanismo para garantir a ordem global dos eventos. [2] Uma grande complicação para a consistência se deve à natureza contínua dos jogos. A ordem na qual os comandos são executados podem criar várias restrições (ex: um jogador que deu um tiro, não pode “resolver” voltar atrás). O sucesso do jogo é totalmente dependente da sincronização. Duas classificações de algoritmos são propostas para resolver o problema da sincronização: [5] ▪ Algoritmos Conservadores ou Pessimistas: Não permite a ocorrência da inconsistência. ▪ Algoritmos Otimistas: Permite a ocorrência da inconsistência, porém toma medidas para sua correção. Com base nos tipos de algoritmos já citados, seguem algumas implementações dessas técnicas: ▪ Stop and Wait (Lockstep) [1] Considerado um algoritmo conservador, o Stop-and-wait ou Lockstep é, de longe, a técnica mais simples para garantir a consistência. Funciona em esquemas de turnos nos quais nenhum jogador pode avançar para o turno seguinte enquanto todos estiverem no corrente. Este esquema provê uma ordem geral de acontecimentos, pois previne a geração de eventos fora de ordem (todos os eventos do turno K acontecem no turno K). O método impossibilita a ocorrência de inconsistências, afinal todos os jogadores estão sempre computando exatamente a mesma informação. No entanto, não existem garantias do avanço constante do jogo. O jogador com conexão mais lenta irá, fatalmente, atrasar os turnos e a interatividade será totalmente prejudicada. A maioria dos jogos FPS deve funcionar como uma simulação constante com baixa latência, sendo assim, este tipo de algoritmo acaba se tornando complicado para estes jogos.

9

▪ Time Warp e Algoritmo de Buckets [1] O Time Warp é considerado um algoritmo otimista. A abordagem é, ao invés de impedir que o erro ocorra (conservadorismo), detectar e corrigir quaisquer diferenças nos estados do jogo. Os algoritmos otimistas executam eventos ANTES de saberem ao certo que nenhum evento anterior pode chegar e, se erram, reparam as inconsistências. Este tipo de algoritmo se comporta bem melhor em situações interativas e contínuas. A sincronização Time Warp trabalha utilizando um snapshot de cada estado antes de cada execução (snapshot de contexto de execução) e executa um rollback para um estado anterior caso algum evento anterior ao último executado seja recebido.

Figura – Algoritmo Time Warp (GVT – Global Virtual Time ou Tempo do Jogo). O rollback restaura o estado do snapshot anterior ao evento que deveria ter sido executado (não foi devido ao atraso), executa-o e, posteriormente, executa todos os outros eventos novamente. O problema da sincronização Time Warp é que ela requer uma máquina rápida e muita memória. Afinal, é necessário um snapshot para cada mensagem e as mensagens costumam chegar em uma frequência muito alta (uma a cada 30 milissegundos em média, dependendo do jogo). Manter um “histórico” do jogo pode sair caro. Uma otimização para remover este gargalo é capturar o snapshot periodicamente, ao invés de fazê-lo a cada mensagem. Porém os rollbacks acabam perdendo um pouco de precisão. Outra complicação para os rollbacks é que o Time Warp assume que eventos geram novos eventos diretamente. Se um evento A gera o evento B, o cancelamento de A (eventos são cancelados no rollback através de anti-messages) provocará o cancelamento de B.

10

Eventualmente, uma geração encadeada de anti-messages pode ocorrer, fazendo com que a rede e o jogo percam tempo “corrigindo” ao invés de “executando” o jogo. Sem contar o aspecto pouco amigável do rollback para o jogador. Para compensar um pouco este fato, o algoritmo acelera a aplicação até chegar no estado mais avançado (antes do rollback). Para completar, Time Warp executa o rollback imediatamente após detectar um comando atrasado. Por um lado isso é bom, pois faz com que os rollbacks sejam pequenos. Por outro lado, acaba causando a execução de excessivos rollbacks caso ocorram muitos atrasos. Outra proposta otimista é o algoritmo de buckets, que funciona como um time slice. Cada jogador possui buckets de tempo para inserir seus eventos. Se algum evento de um bucket anterior chegar, o mesmo é perdido. Caso não cheguem eventos em um certo bucket, aquele bucket sofre “Dead Reckoning”. Dead Reckoning é uma técnica baseada em eventos anteriores para simular eventos que não aconteceram (missing events). Ou seja, se o jogador nada enviou em algum momento em que deveria, então o jogo simula alguma ação baseada no último estado. [15]

Figura – Algoritmo de buckets otimista.

Figura – Outro exemplo de sincronizaçao com buckets.

11

▪ Trailing State Synchronization (TSS) [1] O TSS, assim como o Time Warp, é um algoritmo otimista e também executa rollbacks quando inconsistências são detectadas. Porém, ele não utiliza snapshots e é capaz de agregar vários rollbacks em um único. Quando um rollback se faz necessário, ao invés de copiar o estado de um snapshot anterior, o TSS copia o estado de uma “segunda cópia” do mesmo jogo. Esta segunda cópia estava, com um delay relativo, trilhando (trailing) a principal. Eventualmente, esta “segunda cópia” não possuirá a inconsistência. Na verdade, veremos que é ela a responsável pela detecção da inconsistência. O TSS mantém e atualiza um número fixo de copias dos estados do jogo, porém com diferentes tempos de simulação. Cada cópia tera um atraso embutido. O estado principal, possuidor do menor delay, é o que será renderizado para a tela dos clientes enquanto os outros trailing states são utilizados para detectar e corrigir as inconsistências.

Figura – Protocolo TSS. Em um dado tempo T da simulação, se o estado principal S0 esta executando um comando no tempo T – D0, então o trailing state S1 estará executando um comando T – D1 e assim sucessivamente, onde D0 < D1 < D2 < ... < DN. Os delays podem não se dividir linearmente. O TSS assume que o custo de executar os comandos (trailing states) muitas vezes é menor que o custo de capturar snapshots. Os comandos enviados pelo cliente só serão efetivamente renderizados após o tempo T + D1. Quando os comandos chegam, eles são colocados em uma lista de "pendentes" para cada trailing state em ordem de tempo (timestamp).

12

Se um comando chega atrasado e perde seu tempo de execução, ele é inserido como próximo evento e é executado imediatamente. Para detectar inconsistências, cada trailing state compara seu estado com o do precedente. Quando um comando é executado no último dos trailing states, este comando é deletado de TODOS os estados, pois ele se torna inútil. O último traling state não possui um estado de "backup", logo, inconsistências nele não são detectadas. Se alguma inconsistência é detectada, um rollback para o estado correto é realizado. Isto consiste em copiar o estado do trailing state para o estado principal adicionando na lista de "pendentes" do mesmo todos os comandos que foram executados incorretamente. Finalmente, o estado principal executa novamente estes comandos e acaba retornando para o tempo de execução apropriado. Nota-se que inconsistências nos trailing states promovem uma correção em cascata até chegar no estado principal. No Time Warp, o rollback ocorre no momento em que se recebe um evento fora de ordem. Em contrapartida, no TSS os rollbacks sofrem um delay até o trailing state chegar no ponto da inconsistência. Com esta característica, o TSS é capaz de corrigir vários eventos atrasados em um único rollback eliminando a necessidade de futuras correções para tais inconsistências. Quando um rollback ocorre, a posição do jogador retrocede para a posição correta e o jogo continua. Ocasionalmente, rollbacks podem causar algumas mudanças drásticas como fazer um jogador "ressuscitar".

13

Segue um exemplo de rollback durante a execução do protocolo:

Primeira Figura – Execução “ON TIME”. A primeira figura ilustra uma execução normal, o pacote não chegou atrasado.

Segunda Figura – Comando atrasado. A segunda demonstra um comando atrasado. S0 executa imediatamente o dito cujo e será detectado por S1.

14

Terceira Figura – Verificação da inconsistência.

Quarta Figura – Rollback (pode corrigir mais comandos). Na terceira figura, S1 verifica a inconsistência e, na quarta figura, dispara um rollback. A parte correta de S1 sobrepõe a parte incorreta de S0. Os comandos da lista azul escura são movidos para "pendentes" de S0 e serão executados novamente. Note, na área azul escura da quarta figura, que um outro evento chegou atrasado, mas foi envolvido pelo rollback e será corrigido pelo mesmo. Resumindo, o TSS é um protocolo desenvolvido especialmente para o jogo QUAKE visando melhorar a qualidade da sincronização. Estudos realizados em [1] comprovam a eficiência do Traling State com relação ao Time Warp para este jogo em específico.

15

5)

CONCLUSÃO

Não existem técnicas boas ou ruins, existem técnicas adequadas ou não para os diferentes tipos de jogos. Implementar um algoritmo de Time Warp para um jogo de xadrez ou de truco online é como matar uma formiga com um canhão. Há pouco tempo atrás, as conexões via modem tornavam muitos jogos, principalmente os FPSs, inviáveis. A solução acabava sendo reunir as máquinas em algum lugar e montar uma LAN (Local Area Network). A chegada da banda larga e a disseminação das LAN Houses proporcionaram uma melhora considerável no que diz respeito à qualidade. Com relação aos algoritmos descritos (Lockstep, Buckets e Time Warp, e, por fim, o TSS) podemos dizer que o TSS é bastante adequado aos jogos FPS, pois os mesmos são extremamente sensíveis à latência. Já os outros tipos de jogos (RTS, MMORPG e principalmente o NRT) possuem uma sincronização menos crítica. Devido à já citada considerável melhora das conexões (banda larga), propostas deste tipo de algoritmos são importantes para manter uma boa qualidade dos jogos. Principalmente em virtude da prevenção de trapaças e pelo caráter comercial, a arquitetura cliente/servidor é a mais utilizada para jogos online. No entanto, para jogos de menor porte, peer-to-peer ainda sobrevive. Em virtude da “profissionalização” (E-Sports) dos jogadores e da modernização dos jogos (evolução da tecnologia) este campo tende ao desenvolvimento. É um prato cheio para os apaixonados por jogos multi-player e por computação.

16

6)

REFERÊNCIAS

1. Cronin E., Kurc A., Filstrup B. e Jamin S.: 2003, `An Efficient Synchronization Mechanism for Mirrored Game Architectures`. Kluwer Academic Publishers. http://warriors.eecs.umich.edu/games/papers/mtap-tss.pdf 2. Lamport, L.: 1978, `Time, Clocks, and the Ordering of Events in a Distributed System'. Communications of the ACM 21(7), 558-565. 3. C. Fábio: 2004, `Suporte a jogos distribuídos e de tempo real` Semana acadêmica, UCS. http://gppd.inf.ufrgs.br/wiki/uploads/FreeMMG.FreeMMG/Palestra_UCS_7.pdf 4. Liang X.: 2005, `Incorporating Inconsistency Into Network Computer Games`. Master Degree Research Project, McGill University, http://www.cs.mcgill.ca/~xliang4/ResearchProjectReport.pdf 5. Cronin, E., B. Filstrup, and A. Kurc: 2001, `A Distributed Multiplayer Game Server System'. UM EECS589 Course Project Report, http://www.eecg.toronto.edu/~ashvin/courses/ece1746/2003/reading/cronin-umtr01.pdf 6. DFC Intelligence: The Online Game Market Heats Up. http://www.dfcint.com/game_article/june04article.html

7. S. McCreary and K. Claffy, Trends in Wide Area IP Traffic Patterns: A View from AmesInternet Exchange.

http://www.caida.org/publications/papers/2000/AIX0005/

17