Carregamento de mapas em games: Quadtree e Octatree (Octree)

Existe um grande problema na área de games que é o carregamento de mapas. Uma das soluções mais utilizadas  é utilizar estruturas quadtrees para games 2D e octatrees para games 3D.

Quadtree é um tipo de estrutura na qual tem-se um nó raiz(quadrado maior) que se abre em 4 filhos, aonde cada filho será responsável por um quadrante do quadrado repesentado pelo nó pai.

De maneira análoga, o octatree é uma estrutura na qual se tem um nó raiz(cubo maior) que se abre em 8 filhos, aonde cada filho será responsável por um octante do cubo representado pelo nó pai.

Agora vamos aos exemplos práticos:

Para exemplificar o Quadtree, encontrei neste site um applet exemplificando o quadtree, o mesmo segue logo abaixo. Para adicionar pontos na estrutura, clique no quadrado, para visualizar a estrutura da árvore clique em show tree.

Your browser does not support Java, so nothing is displayed.

Para exemplificar uma octree, não encontrei nenhum applet, mas encontrei uma outra estrutura de dados para mapas 3D: BSP. Para usar o exemplo abaixo, basta utilizar o primeiro quadrado. Dentro dele, para desenhar uma parede no mapa, clique e arraste com o botão direito. Para mover a camera clique com o botão esquerdo no ponto vermelho e arraste. Os demais campos são representações do mapa.

Your browser does not support Java, so nothing is displayed.

Nesta sexta-feira(20/11/2009) tentamos implementar árvores quadtree.

• Eu fiz um exemplo em C# e com XNA:
  • Codigo-Fonte (necessita do XNA framework 3.1 e Visual Studio C# 2008)
  • Executavel (necessita do XNA 3.1 Redistributable e .NET 3.5)
• Ian Liu juntamente com o Fenando Lucchesi implementaram em Python com Pygame
  • Código-Fonte (necessita do Pyhon e do Pygame)

Espero que tenham gostado, qualquer dúvida, entre em contato.