Algoritmos eficientes e escalabilidade em jogos online de massa

Speaker: Vinícius Gusmão, UFRJ.

Date: 26 sep 2018, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Jogos online para muitos jogadores, conhecidos como MMO (massive multiplayer online games), são boa fonte de problemas computacionais interessantes. A grande quantidade de jogadores simultâneos, produzindo enorme quantidade de informação a cada instante, somadas à exigência de baixíssima latência no processamento (para que a experiência do jogador não seja degradada por um retardo perceptível nos movimentos e ações), faz com que os jogos MMO tenham na eficiência de seus algoritmos um ponto crucial para sua existência. Em uma arquitetura cliente-servidor, que é bastante comum, na qual cada jogador transmite e recebe dados de um ou mais computadores (os servidores do jogo) mas não diretamente de outros jogadores, é preciso também orquestrar o funcionamento de diversas máquinas em cooperação para que se possa escalar livremente o número suportado de jogadores simultâneos.

Veremos alguns problemas interessantes que aparecem nesse tipo de ambiente, e focaremos no problema de se encontrar a melhor distribuição dos jogadores pelos servidores disponíveis, de forma a minimizar a troca de informação necessária entre os servidores do jogo sem contudo sobrecarregar qualquer um deles. Proporemos um algoritmo randomizado que, surpreendentemente, é o melhor que conhecemos para resolver o problema proposto, e faz uso -- talvez de forma didática -- dos celebrados filtros de Bloom.