Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Proposta de Trabalho Final
CMP189 – Algoritmos Geométricos
Carlos Eduardo Benevides Bezerra
Carlos Eduardo Benevides Bezerra
1 / 21
Defesa de Mestrado
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Problema

Dado um espaço bidimensional, através do qual estão
distribuídos avatares (pontos), dividí-lo em N regiões, de
forma que:

c(Si) seja o mesmo* para todas as regiões Ri, onde a função c(S)
calcula a carga de uma região com base no conjunto S de avatares
contidos nela
* Como geralmente não é possível que c(Si) seja exatamente o mesmo, o objetivo é
minimizar o seu desvio.

Dada uma divisão onde o c(Si) de uma região Ri desvia além
do tolerável, modificar a divisão de maneira que a carga de
Ri esteja dentro de um limite aceitável
Carlos Eduardo Benevides Bezerra
2 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Exemplo
Carlos Eduardo Benevides Bezerra
3 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Contexto


Em MMOGs, existem dezenas de milhares de
jogadores simultâneos
Solução: multi-servidor



O ambiente do jogo é dividido em partições, cada uma
administrada por um servidor
Cada jogador precisa de atualizações de estado do
ambiente do jogo (uso da banda de upload do server)
A carga sobre os servidores deve ser rebalanceada,
sempre que algum deles estiver sobrecarregado
Carlos Eduardo Benevides Bezerra
4 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Cálculo da carga em um MMOG


A carga da região depende da distribuição dos avatares dos jogadores
Cada jogador deve receber atualizações de estado de seu próprio avatar e
daqueles com quem interage
Carlos Eduardo Benevides Bezerra
5 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Possível solução

KD-Tree

Divisão inicial


A cada passo é definida uma linha de corte que divida o
conjunto de avatares restantes em dois conjuntos de carga
semelhante
Rebalanceamento



As coordenadas x e y das linhas de corte são modificadas
Feito primeiro no nível das folhas, partindo do corte entre a
região sobrecarregada e sua região vizinha
Percorre-se a árvore enquanto a divisão não satisfizer o
critério de balanceamento
Carlos Eduardo Benevides Bezerra
6 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Utilizando uma KD-Tree
Carlos Eduardo Benevides Bezerra
7 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Utilizando uma KD-Tree
Carlos Eduardo Benevides Bezerra
8 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Utilizando uma KD-Tree
Carlos Eduardo Benevides Bezerra
9 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Utilizando uma KD-Tree
Carlos Eduardo Benevides Bezerra
10 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Utilizando uma KD-Tree
Carlos Eduardo Benevides Bezerra
11 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Utilizando uma KD-Tree
Carlos Eduardo Benevides Bezerra
12 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Utilizando uma KD-Tree
Carlos Eduardo Benevides Bezerra
13 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Trabalhos Relacionados

(DE VLEESCHAUWER et al., 2005) Dynamic microcell assignment
for massively multiplayer online gaming. In: Proceedings of the
ACM SIGCOMM workshop on Network and system support for games,
NetGames

(AHMED; SHIRMOHAMMADI, 2008) A Microcell Oriented Load
Balancing Model for Collaborative Virtual Environments. In:
Proceedings of the IEEE Conference on Virtual Environments, HumanComputer Interfaces and Measurement Systems

(BEZERRA; GEYER, 2009) A load balancing scheme for massively
multiplayer online games. In: Massively Multiuser Online Gaming
Systems and Applications, Special Issue of Springer’s Multimedia
Tools and Applications
Carlos Eduardo Benevides Bezerra
14 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Células e regiões



Propõe-se uma divisão do espaço em células
estáticas de mesmo tamanho
As células são agrupadas, formando uma região,
que é então atribuída a um servidor
Para rebalancear a carga, as células são transferidas
entre regiões
Carlos Eduardo Benevides Bezerra
15 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Exemplo de divisão em células
Carlos Eduardo Benevides Bezerra
16 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Exemplo de divisão em células
Carlos Eduardo Benevides Bezerra
17 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Exemplo de divisão em células
Carlos Eduardo Benevides Bezerra
18 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Resultados Esperados


Reduzir o uso de memória para armazenamento da estrutura de
dados
Reduzir o tempo necessário para que os servidores executem o
rebalanceamento




Ao invés de reenviar a lista de todas as células que mudaram de região,
basta enviar o novo valor x ou y das linhas de corte que se moveram
Maior granularidade com células = células menores = maior tráfego
quando rebalanceando
Utilizando a KD-Tree, a linha que separa as regiões pode ter qualquer
coordenada x ou y.
Obter uma melhor divisão do espaço em alguns casos especias
que não seriam bem tratados com a baixa granularidade das
células
Carlos Eduardo Benevides Bezerra
19 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Caso especial
KD-TREE
Células
Carlos Eduardo Benevides Bezerra
20 / 21
CMP189 – Algoritmos Geométricos
Proposta de Trabalho Final: Particionamento dinâmico de espaço bidimensional
Cronograma

Revisão bibliográfica


Análise do problema e busca de soluções


De 01/06 a 14/06
Simulações e análise dos resultados


De 18/05 a 31/05
Implementação do(s) algoritmo(s)


Semana de 11/05 a 17/05
De 15/06 a 28/06
Escrita do artigo e montagem da apresentação

Deadline: 12/07
Carlos Eduardo Benevides Bezerra
21 / 21
CMP189 – Algoritmos Geométricos