On considère le terrain de jeu carré.
L'espace est projeté parallèlement a sa direction verticale.
La carte obtenue (que je nomme page racine) est alors subdivisée en 4 sous-pages carrés de coté moitié moins grande. Cette subdivision des sous-pages se réitère récursivement jusqu’à une valeur choisie par l'utilisateur. (typiquement une dizaine de mètres)
Les animaux sont alors placés (aléatoirement par exemple) sur la carte, et attachés a la plus petite page les contenant. (Ainsi chaque page contient soit 4 sous-pages, soit une liste d'animaux.)
Jusque la c'est du classique. C'était l'initialisation.
Lors de l'update de la faune dans la main loop, on cherche les pages a updater.
On considère la page que le joueur arpente actuellement. (la connaitre initialement se résous en temps logarithmique par une dichotomie scindant a chaque récursion l'espace de recherche en 4).
On liste ensuite les pages géométriquement voisines. (Précision importante : on veille lors de la création de l'arbre des pages a donner a chaque page une liste de 8 pointeurs menant aux pages qui lui sont voisines, droite, gauche, haut, bas et diagonales.). On ajoute donc dans une liste les pages voisines de la page du joueur. Puis on va récursivement chercher les voisins des voisins jusqu’à une distance (donné en nombre de page, par exemple 3 ira jusqu’à la page voisine de la voisine de la voisine) donné par l'utilisateur.
A ce moment la nous avons bien un carré de dimension réglable, que l'on peut donc considérer apte a être updaté en temps réel. (Par updater une page, j’entends afficher ses animaux et exécuter les scripts d'IA associés.).
Ce n'est pas fini : le joueur bouge, mais considérons l'heuristique pas trop méchante qu'il est incapable de se téléporter 100m plus loin.
A chaque update de la faune, on teste si le joueur est dans la page courante. Cela se fait par 4 comparaisons : est on a gauche du bord droit, est on en dessous du bord haut, etc.. (Les coords des bords sont stockés dans la page)
Ces 4 booléens donnent a eux 4, 8 états possibles correspondants chacun aux 8pages voisines (imaginons que tout soit Ok sauf que je ne soit ni en bas du bord haute, ni a droite du bord gauche, on déduit que je suis passé dans la page diagonale en haut a gauche).
De cette manière on peut tracer le joueur pour connaitre en permanence la page qu'il arpente. (On re-testera qu'il est bien dans la page ou l'on pense, des fois que je joueur se soit téléporté de 100m. Si c'est la cas, on repasse par la dichotmie sur toute le map)