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.

380px-Quad_tree_bitmap.svg

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.

400px-Octree2

Agora vamos aos exemplos práticos:

[…]