Nei videogiochi si usano anche strutture meno generiche, come i BSP - Binary Space Partition: una sorta di binary tree dove ogni nodo è rappresentato da un triangolo e a destra e sinistra di ciascun nodo ci stanno i triangoli in direzione normale / antinormale.
Quad-tree (2D) e Oct-tree (3D) sono pressocchè identici a normali binary-tree ma hanno per ciascun nodo 2/3 direzioni da discriminare, con altrettante funzioni di selezione. Per la visione robotica, visto che generalmente ci si muove su un piano, basta un quad-tree.
Puoi immaginare ogni nodo come un quadrante del piano cartesiano e, ricorsivamente, i nodi suoi figli sono altri 4 quadranti cartesiani, e così via fino alle foglie che contengono i singoli oggetti.
Detto questo, prendi un qualsiasi algoritmo di esplorazione per binary tree, aggiungi un asse/direzione e in fase di esplorazione avrai 2 variabili (x,y) da discriminare invece di una soltanto.
