the need
picture this: you’re building a smart weapon in your 3D game, and you need the projectiles of that weapon to find the nearest enemy to target. you could just run some quick and dirty code to iterate over every single enemy in the game and compare it to the weapon/projectile’s location. that could work if you have a small amount of enemies, but what if you have 1000, or 10,000 enemies, and they’re spread out all over the 3D map? your quick and dirty code is gonna make your game lag… a lot. that’s where an Octree comes in.
the what
an octree is a tree data structure that divides 3D space into smaller and smaller partitions. it’s like a binary tree that you might use in a 2D game, but in 3D. the octree gets divided into 8 octants, and each octant can be divided into 8 more octants, and so on. this makes it fast and easy to find the nearest object to a given point in 3D space. this can help itn a lot of ways, like visibility determination, collision detection, pathfinding, and a lot more.
the how
here’s a simple rundown of building a bounds-based octree in Unity:
Defining an Octree Node
each node represents a cube in 3D Space, containing objects and up to 8 children (sub-cubes).
csharp1class OctreeNode {
2 Bounds bounds; // spatial bounds of this node
3 List<GameObject> objects; // objects within this node
4 OctreeNode[] children; // child nodes
5}Inserting objects
insert objects into the tree. if a node exceeds a certain capacity, it subdivides into 8 children and tries to insert the object into the appropriate child node.
csharp 1void Insert(OctreeNode node, GameObject obj) {
2 if (!node.bounds.contains(obj.position)) return;
3 if (node.objects.count < MAX_OBJECTS || node.children == null) {
4 node.objects.add(obj);
5 } else {
6 if (node.children == null) subdivide(node);
7 // find the correct child to insert into and recurse
8 foreach (child in node.children) {
9 if (child.bounds.contains(obj.position)) {
10 Insert(child, obj);
11 return;
12 }
13 }
14 }
15}subdividing a node
when a node’s capacity is exceeded, it subdivides into eight smaller nodes.
csharp1void Subdivide(OctreeNode node) {
2 float size = node.bounds.size / 2;
3 Vector3[] offsets = {new Vector3(-size, -size, -size), new Vector3(-size, -size, size), ...};
4 node.children = new OctreeNode[8];
5 for (int i = 0; i < 8; i++) {
6 Vector3 newCenter = node.bounds.center + offsets[i];
7 node.children[i] = new OctreeNode(new Bounds(newCenter, new Vector3(size, size, size)));
8 }
9}finding the nearest object
to find the nearest object to a given point, we recursively search the tree, starting from the root node and moving down to the leaf nodes.
csharp 1GameObject FindNearest(OctreeNode node, Vector3 point) {
2 GameObject nearest = null;
3 float nearestDist = float.MaxValue;
4 // check objects in this node
5 foreach (obj in node.objects) {
6 float dist = Vector3.Distance(obj.position, point);
7 if (dist < nearestDist) {
8 nearest = obj;
9 nearestDist = dist;
10 }
11 }
12 // check children
13 if (node.children != null) {
14 foreach (child in node.children) {
15 if (child.bounds.distanceTo(point) < nearestDist) {
16 GameObject childNearest = FindNearest(child, point);
17 float childDist = Vector3.Distance(childNearest.position, point);
18 if (childDist < nearestDist) {
19 nearest = childNearest;
20 nearestDist = childDist;
21 }
22 }
23 }
24 }
25 return nearest;
26}update positions
if objects move, we need to update their positions in the tree.
csharp 1void UpdatePosition(GameObject obj, Vector3 oldPosition) {
2 if (obj == null) return; // check for null object
3
4 // firstly check if the object is still within it's current node's bounds
5 OctreeNode currentNode;
6 if (_objectToNodeMap.TryGetValue(obj, out currentNode)) {
7 if (!currentNode.bounds.contains(obj.transform.position)) {
8 // if the object has moved outside of the current node's bounds, remove it
9 Remove(currentNode, obj); // remove the object from the current node
10
11 // reinsert the object at its new position
12 Insert(_root, obj, true); // reinsert starting from the root
13 }
14 // if the object is still within the bounds, theres no need to move it in the octree
15 } else {
16 // if for some reason the object wasn't in the map, add it back in
17 Insert(_root, obj, true);
18 }
19}remove objects
if an object gets destroyed or moves out of the tree’s bounds, we gotta remove it from the tree.
csharp 1void Remove(OctreeNode node, GameObject obj) {
2 if (node == null || obj == null) return;
3
4 if (node.Objects.Remove(obj)) {
5 _objectToNodeMap.Remove(obj);
6 } else {
7 foreach (var child in node.Children) {
8 if (child != null && child.bounds.contains(obj.transform.position)) {
9 Remove(child, obj);
10 break;
11 }
12 }
13 }
14}what’s left?
so we’ve got a basic implementation of an octree in unity, but you’ll still need to implement a Manager that should handle the creation of the root node, crud operations and any other related tasks. you’ll also have to make sure any objects that move around are updated into the octree.
good luck~!