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.
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.
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.
