Jump to content
  • Advertisement
  • 01/20/14 09:46 PM

    Introduction to Octrees

    General and Gameplay Programming

    slayemin

    What exactly is an Octree? If you're completely unfamiliar with them, I recommend reading the Wikipedia article (read time: ~5 minutes). This is a sufficient description of what it is but is barely enough to give any ideas on what it's used for and how to actually implement one. In this article, I will do my best to take you through the steps necessary to create an octree data structure through conceptual explanations, pictures, and code, and show you the considerations to be made at each step along the way. I don't expect this article to be the authoritative way to do octrees, but it should give you a really good start and act as a good reference.

     

    Assumptions

    Before we dive in, I'm going to be making a few assumptions about you as a reader:

    1. You are very comfortable with programming in a C-syntax-style language (I will be using C# with XNA).
    2. You have programmed some sort of tree-like data structure in the past, such as a binary search tree and are familiar with recursion and its strengths and pitfalls.
    3. You know how to do collision detection with bounding rectangles, bounding spheres, and bounding frustums.
    4. You have a good grasp of common data structures (arrays, lists, etc) and understand Big-O notation (you can also learn about Big-O in this GDnet article).
    5. You have a development environment project which contains spatial objects which need collision tests.

     

    Setting the stage

    Let's suppose that we are building a very large game world which can contain thousands of physical objects of various types, shapes and sizes, some of which must collide with each other. Each frame we need to find out which objects are intersecting with each other and have some way to handle that intersection. How do we do it without killing performance?

    Octree_1a.png

     

    Brute force collision detection

    The simplest method is to just compare each object against every other object in the world. Typically, you can do this with two for loops. The code would look something like this:

    foreach(gameObject myObject in ObjList)
    		{
    			foreach(gameObject otherObject in ObjList) 
    			{ 
    				if(myObject == otherObject) continue; //avoid self collision check 
    				if(myObject.CollidesWith(otherObject)) 
    				{ 
    				//code to handle the collision 
    				} 
    			} 
    		}

     

    Conceptually, this is what we're doing in our picture:

    Octree_1c.png

    Each red line is an expensive CPU test for intersection. Naturally, you should feel horrified by this code because it is going to run in O(N^2) time. If you have 10,000 objects, then you're going to be doing 100,000,000 collision checks (hundred million). I don't care how fast your CPU is or how well you've tuned your math code, this code would reduce your computer to a sluggish crawl. If you're running your game at 60 frames per second, you're looking at 60 * 100 million calculations per second! It's nuts. It's insane. It's crazy. Let's not do this if we can avoid it, at least not with a large set of objects. This would only be acceptable if we're only checking, say, 10 items against each other (100 checks is palatable). If you know in advance that your game is only going to have a very small number of objects (i.e., Asteroids), you can probably get away with using this brute force method for collision detection and ignore octrees altogether. If/when you start noticing performance problems due to too many collision checks per frame, consider some simple targeted optimizations:

    1. How much computation does your current collision routine take? Do you have a square root hidden away in there (ie, a distance check)? Are you doing a granular collision check (pixel vs pixel, triangle vs triangle, etc)? One common technique is to perform a rough, coarse check for collision before testing for a granular collision check. You can give your objects an enclosing bounding rectangle or bounding sphere and test for intersection with these before testing against a granular check which may involve a lot more math and computation time.
      Quote

      Use a "distance squared" check for comparing distance between objects to avoid using the square root method. Square root calculation typically uses the newtonian method of approximation and can be computationally expensive.

    2. Can you get away with calculating fewer collision checks? If your game runs at 60 frames per second, could you skip a few frames? If you know certain objects behave deterministically, can you "solve" for when they will collide ahead of time (ie, pool ball vs. side of pool table). Can you reduce the number of objects which need to be checked for collisions? A technique for this would be to separate objects into several lists. One list could be your "stationary" objects list. They never have to test for collision against each other. The other list could be your "moving" objects, which need to be tested against all other moving objects and against all stationary objects. This could reduce the number of necessary collision tests to reach an acceptable performance level.
    3. Can you get away with removing some object collision tests when performance becomes an issue? For example, a smoke particle could interact with a surface object and follow its contours to create a nice aesthetic effect, but it wouldn't break gameplay if you hit a predefined limit for collision checks and decided to stop ignoring smoke particles for collision. Ignoring essential game object movement would certainly break gameplay though (i.e., player bullets stop intersecting with monsters). So, perhaps maintaining a priority list of collision checks to compute would help. First, you handle the high priority collision tests, and if you're not at your threshold, you can handle lower priority collision tests. When the threshold is reached, you dump the rest of the items in the priority list or defer them for testing at a later time. 
    4. Can you use a faster but still simplistic method for collision detection to get away from an O(N^2) runtime? If you eliminate the objects you've already checked for collisions against, you can reduce the runtime to O(N(N+1)/2), which is much faster and still easy to implement. (technically, it's still O(N^2)) In terms of software engineering, you may end up spending more time than it's worth fine-tuning a bad algorithm & data structure choice to squeeze out a few more ounces of performance. The cost vs. benefit ratio becomes increasingly unfavourable and it becomes time to choose a better data structure to handle collision detection. Spatial partitioning algorithms are the proverbial nuke to solving the runtime problem for collision detection. At a small upfront cost to performance, they'll reduce your collision detection tests to logarithmic runtime. The upfront costs of development time and CPU overhead are easily outweighed by the scalability benefits and performance gains.

     

    Conceptual background on spatial partitioning

    Let's take a step back and look at spatial partitioning and trees in general before diving into Octrees. If we don't understand the conceptual idea, we have no hope of implementing it by sweating over the code. Looking at the brute force implementation above, we're essentially taking every object in the game and comparing their positions against all other objects in the game to see if any are touching. All of these objects are contained spatially within our game world. Well, if we create an enclosing box around our game world and figure out which objects are contained within this enclosing box, then we've got a region of space with a list of contained objects within it. In this case, it would contain every object in the game.

    We can notice that if we have an object on one corner of the world and another object way on the other side, we don't really need to, or want to, calculate a collision check against them every frame. It'd be a waste of precious CPU time.

    So, let's try something interesting! If we divide our world exactly in half, we can create three separate lists of objects. The first list of objects, List A, contains all objects on the left half of the world. The second list, List B, contains objects on the right half of the world. Some objects may touch the dividing line such that they're on each side of the line, so we'll create a third list, List C, for these objects.

    Octree_2a.png

    We can notice that with each subdivision, we're spatially reducing the world in half and collecting a list of objects in that resulting half. We can elegantly create a binary search tree to contain these lists. Conceptually, this tree should look something like so:

    Octree_2b.png

    In terms of pseudo code, the tree data structure would look something like this:

     

    public class BinaryTree 
    { 
    	//This is a list of all of the objects contained within this node of the tree 
    	private List m_objectList; 
    	
    	//These are pointers to the left and right child nodes in the tree 
    	private BinaryTree m_left, m_right; 
    	
    	//This is a pointer to the parent object (for upward tree traversal). 
    	private BinaryTree m_parent; 
    }

    We know that all objects in List A will never intersect with any objects in List B, so we can almost eliminate half of the number of collision checks. We've still got the objects in List C which could touch objects in either list A or B, so we'll have to check all objects in List C against all objects in Lists A, B & C. If we continue to sub-divide the world into smaller and smaller parts, we can further reduce the number of necessary collision checks by half each time. This is the general idea behind spatial partitioning. There are many ways to subdivide a world into a tree-like data structure (BSP trees, Quad Trees, K-D trees, OctTrees, etc).

    Now, by default, we're just assuming that the best division is a cut in half, right down the middle, since we're assuming that all of our objects will be somewhat uniformly distributed throughout the world. It's not a bad assumption to make, but some spatial division algorithms may decide to make a cut such that each side has an equal amount of objects (a weighted cut) so that the resulting tree is more balanced. However, what happens if all of these objects move around? In order to maintain a nearly even division, you'd have to either shift the splitting plane or completely rebuild the tree each frame. It'd be a bit of a mess with a lot of complexity. So, for my implementation of a spatial partitioning tree, I decided to cut right down the middle every time. As a result, some trees may end up being a bit more sparse than others, but that's okay -- it doesn't cost much.

     

    To subdivide or not to subdivide? That is the question.

    Let's assume that we have a somewhat sparse region with only a few objects. We could continue subdividing our space until we've found the smallest possible enclosing area for that object. But is that really necessary? Let's remember that the whole reason we're creating a tree is to reduce the number of collision checks we need to perform each frame -- not to create a perfectly enclosing region of space for every object. Here are the rules I use for deciding whether to subdivide or not:

    • If we create a subdivision which only contains one object, we can stop subdividing even though we could keep dividing further. This rule will become an important part of the criteria for what defines a "leaf node" in our octree.
    • The other important criteria is to set a minimum size for a region. If you have an extremely small object which is nanometers in size (or, god forbid, you have a bug and forgot to initialize an object size!), you're going to keep subdividing to the point where you potentially overflow your call stack. For my own implementation, I defined the smallest containing region to be a 1x1x1 cube. Any objects in this teeny cube will just have to be run with the O(N^2) brute force collision test (I don't anticipate many objects anyways!).
    • If a containing region doesn't contain any objects, we shouldn't try to include it in the tree.

    We can take our subdivision by half one step further and divide the 2D world space into quadrants. The logic is essentially the same, but now we're testing for collision with four squares instead of two rectangles. We can continue subdividing each square until our rules for termination are met. The representation of the world space and corresponding data structure for a quadtree would look something like this:

    Quadtree_1a.png

    If the quadtree subdivision and data structure makes sense, then an octree should be pretty straightforward as well. We're just adding a third dimension, using bounding cubes instead of bounding squares, and have eight possible child nodes instead of four. Some of you might wonder what should happen if you have a game world with non-cubic dimensions, say 200x300x400. You can still use an octree with cubic dimensions -- some child nodes will just end up empty if the game world doesn't have anything there. Obviously, you'll want to set the dimensions of your octree to at least the largest dimension of your game world.

    Octree Construction

    So, as you've read, an octree is a special type of subdividing tree commonly used for objects in 3D space (or anything with 3 dimensions). Our enclosing region is going to be a three dimensional rectangle (commonly a cube). We will then apply our subdivision logic above, and cut our enclosing region into eight smaller rectangles. If a game object completely fits within one of these subdivided regions, we'll push it down the tree into that node's containing region. We'll then recursively continue subdividing each resulting region until one of our breaking conditions is met. In the end, we should expect to have a nice tree-like data structure.

    My implementation of the octree can contain objects which have either a bounding sphere and/or a bounding rectangle. You'll see a lot of code I use to determine which is being used.

    In terms of our Octree class data structure, I decided to do the following for each tree:

    • Each node has a bounding region which defines the enclosing region
    • Each node has a reference to the parent node
    • Contains an array of eight child nodes (use arrays for code simplicity and cache performance)
    • Contains a list of objects contained within the current enclosing region
    • I use a byte-sized bitmask for figuring out which child nodes are actively being used (the optimization benefits at the cost of additional complexity is somewhat debatable)
    • I use a few static variables to indicate the state of the tree

    Here is the code for my Octree class outline:

    public class OctTree
    { 
    	BoundingBox m_region;
    	List m_objects; 
    	/// 
    	/// These are items which we're waiting to insert into the data structure. 
    	/// We want to accrue as many objects in here as possible before we inject them into the tree. This is slightly more cache friendly. 
    	/// 
    	
    	static Queue m_pendingInsertion = new Queue(); 
    	
    	/// 
    	/// These are all of the possible child octants for this node in the tree. 
    	/// 
    	OctTree[] m_childNode = new OctTree[8]; 
    	
    	///
    	/// This is a bitmask indicating which child nodes are actively being used. 
    	/// It adds slightly more complexity, but is faster for performance since there is only one comparison instead of 8. 
    	///
    	byte m_activeNodes = 0;
    	
    	///
    	/// The minumum size for enclosing region is a 1x1x1 cube. 
    	///
    	const int MIN_SIZE = 1; 
    	
    	///
    	/// this is how many frames we'll wait before deleting an empty tree branch. Note that this is not a constant. The maximum lifespan doubles
    	/// every time a node is reused, until it hits a hard coded constant of 64 
    	/// 
    	int m_maxLifespan = 8; // 
    	int m_curLife = -1; //this is a countdown time showing how much time we have left to live 
    	
    	/// 
    	/// A reference to the parent node is nice to have when we're trying to do a tree update. 
    	/// 
    	OctTree _parent; 
    	static bool m_treeReady = false; //the tree has a few objects which need to be inserted before it is complete 
    	static bool m_treeBuilt = false; //there is no pre-existing tree yet. 
    } 

     

    Initializing the enclosing region

    The first step in building an octree is to define the enclosing region for the entire tree. This will be the bounding box for the root node of the tree which initially contains all objects in the game world. Before we go about initializing this bounding volume, we have a few design decisions we need to make:

    1. What should happen if an object moves outside of the bounding volume of the root node? Do we want to resize the entire octree so that all objects are enclosed? If we do, we'll have to completely rebuild the octree from scratch. If we don't, we'll need to have some way to either handle out of bounds objects or ensure that objects never go out of bounds.
    2. How do we want to create the enclosing region for our octree? Do we want to use a preset dimension, such as a 200x400x200 (X,Y,Z) rectangle? Or do we want to use a cubic dimension which is a power of 2? What should be the smallest allowable enclosing region which cannot be subdivided?

    Personally, I decided that I would use a cubic enclosing region with dimensions which are a power of 2, and sufficiently large to completely enclose my world. The smallest allowable cube is a 1x1x1 unit region. With this, I know that I can always cleanly subdivide my world and get integer numbers (even though the Vector3 uses floats). I also decided that my enclosing region would enclose the entire game world, so if an object leaves this region, it should be quietly destroyed. At the smallest octant, I will have to run a brute force collision check against all other objects, but I don't realistically expect more than 3 objects to occupy that small of an area at a time, so the performance costs of O(N^2) are completely acceptable. So, I normally just initialize my octree with a constructor which takes a region size and a list of items to insert into the tree. I feel it's barely worth showing this part of the code since it's so elementary, but I'll include it for completeness. Here are my constructors:

    /*Note: we want to avoid allocating memory for as long as possible since there can be lots of nodes.*/ 
    /// 
    /// Creates an oct tree which encloses the given region and contains the provided objects. 
    /// 
    
    ///The bounding region for the oct tree. 
    ///The list of objects contained within the bounding region 
    private OctTree(BoundingBox region, List objList) 
    { 
    	m_region = region; 
    	m_objects = objList; 
    	m_curLife = -1; 
    } 
    
    public OctTree() 
    { 
    	m_objects = new List(); 
    	m_region = new BoundingBox(Vector3.Zero, Vector3.Zero); 
    	m_curLife = -1; 
    } 
    
    /// 
    /// Creates an octTree with a suggestion for the bounding region containing the items. 
    /// 
    
    ///The suggested dimensions for the bounding region. 
    ///Note: if items are outside this region, the region will be automatically resized. 
    public OctTree(BoundingBox region) 
    { 
    	m_region = region;
    	m_objects = new List(); 
    	m_curLife = -1; 
    } 

     

    Building an initial octree

    I'm a big fan of lazy initialization. I try to avoid allocating memory or doing work until I absolutely have to. In the case of my octree, I avoid building the data structure as long as possible. We'll accept a user's request to insert an object into the data structure, but we don't actually have to build the tree until someone runs a query against it.

    What does this do for us? Well, let's assume that the process of constructing and traversing our tree is somewhat computationally expensive. If a user wants to give us 1,000 objects to insert into the tree, does it make sense to recompute every subsequent enclosing area a thousand times? Or, can we save some time and do a bulk blast? I created a "pending" queue of items and a few flags to indicate the build state of the tree. All of the inserted items get put into the pending queue and when a query is made, those pending requests get flushed and injected into the tree. This is especially handy during a game loading sequence since you'll most likely be inserting thousands of objects at once. After the game world has been loaded, the number of objects injected into the tree is orders of magnitude fewer. My lazy initialization routine is contained within my UpdateTree() method. It checks to see if the tree has been built, and builds the data structure if it doesn't exist and has pending objects.

     /// 
     /// Processes all pending insertions by inserting them into the tree. 
     /// 
     /// Consider deprecating this? 
     private void UpdateTree() //complete & tested 
     { 
    	 if (!m_treeBuilt) 
    	 { 
    		 while (m_pendingInsertion.Count != 0) 
    			m_objects.Add(m_pendingInsertion.Dequeue()); 
    		BuildTree(); 
    	 } 
    	 else
    	 { 
    		 while (m_pendingInsertion.Count != 0)
    			Insert(m_pendingInsertion.Dequeue()); 
    	 } 
    	 m_treeReady = true;
     } 

    As for building the tree itself, this can be done recursively. So for each recursive iteration, I start off with a list of objects contained within the bounding region. I check my termination rules, and if we pass, we create eight subdivided bounding areas which are perfectly contained within our enclosed region. Then, I go through every object in my given list and test to see if any of them will fit perfectly within any of my octants. If they do fit, I insert them into a corresponding list for that octant. At the very end, I check the counts on my corresponding octant lists and create new octrees and attach them to our current node, and mark my bitmask to indicate that those child octants are actively being used. All of the leftover objects have been pushed down to us from our parent, but can't be pushed down to any children, so logically, this must be the smallest octant which can contain the object.

    /// 
    /// Naively builds an oct tree from scratch.
    /// 
    private void BuildTree() //complete & tested
    {
    	//terminate the recursion if we're a leaf node
    	if (m_objects.Count <= 1)
    		return;
    	
    	Vector3 dimensions = m_region.Max - m_region.Min;
    	
    	if (dimensions == Vector3.Zero)
    	{
    		FindEnclosingCube();
    		dimensions = m_region.Max - m_region.Min;
    	}
    	
    	//Check to see if the dimensions of the box are greater than the minimum dimensions
    	if (dimensions.X <= MIN_SIZE && dimensions.Y <= MIN_SIZE && dimensions.Z <= MIN_SIZE)
    	{
    		return;
    	}
    	
    	Vector3 half = dimensions / 2.0f;
    	Vector3 center = m_region.Min + half;
    	
    	//Create subdivided regions for each octant
    	BoundingBox[] octant = new BoundingBox[8];
    	octant[0] = new BoundingBox(m_region.Min, center);
    	octant[1] = new BoundingBox(new Vector3(center.X, m_region.Min.Y, m_region.Min.Z), new Vector3(m_region.Max.X, center.Y, center.Z));
    	octant[2] = new BoundingBox(new Vector3(center.X, m_region.Min.Y, center.Z), new Vector3(m_region.Max.X, center.Y, m_region.Max.Z));
    	octant[3] = new BoundingBox(new Vector3(m_region.Min.X, m_region.Min.Y, center.Z), new Vector3(center.X, center.Y, m_region.Max.Z));
    	octant[4] = new BoundingBox(new Vector3(m_region.Min.X, center.Y, m_region.Min.Z), new Vector3(center.X, m_region.Max.Y, center.Z));
    	octant[5] = new BoundingBox(new Vector3(center.X, center.Y, m_region.Min.Z), new Vector3(m_region.Max.X, m_region.Max.Y, center.Z));
    	octant[6] = new BoundingBox(center, m_region.Max);
    	octant[7] = new BoundingBox(new Vector3(m_region.Min.X, center.Y, center.Z), new Vector3(center.X, m_region.Max.Y, m_region.Max.Z));
    	
    	//This will contain all of our objects which fit within each respective octant.
    	List[] octList = new List[8];
    	
    	for (int i = 0; i < 8; i++) 
    		octList = new List();
    		
    	//this list contains all of the objects which got moved down the tree and can be delisted from this node.
    	List delist = new List();
    	
    	foreach (Physical obj in m_objects)
    	{
    		if (obj.BoundingBox.Min != obj.BoundingBox.Max)
    		{
    			for (int a = 0; a < 8; a++)
    			{
    				if (octant[a].Contains(obj.BoundingBox) == ContainmentType.Contains)
    				{
    					octList[a].Add(obj);
    					delist.Add(obj);
    					break;
    				}
    			}
    		}
    		else if (obj.BoundingSphere.Radius != 0)
    		{
    			for (int a = 0; a < 8; a++)
    			{
    				if (octant[a].Contains(obj.BoundingSphere) == ContainmentType.Contains)
    				{
    					octList[a].Add(obj);
    					delist.Add(obj);
    					break;
    				}
    			}
    		}
    	}
    	
    	//delist every moved object from this node.
    	foreach (Physical obj in delist)
    		m_objects.Remove(obj);
    		
    	//Create child nodes where there are items contained in the bounding region
    	for (int a = 0; a < 8; a++)
    	{
    		if (octList[a].Count != 0)
    		{
    			m_childNode[a] = CreateNode(octant[a], octList[a]);
    			m_activeNodes |= (byte)(1 << a);
    			m_childNode[a].BuildTree();
    		}
    	}
    	
    	m_treeBuilt = true;
    	m_treeReady = true;
    }
    	
    private OctTree CreateNode(BoundingBox region, List objList) //complete & tested
    {
    	if (objList.Count == 0)
    		return null;
    	OctTree ret = new OctTree(region, objList);
    	ret._parent = this;
    	return ret;
    }
    
    private OctTree CreateNode(BoundingBox region, Physical Item)
    {
    	List objList = new List(1); //sacrifice potential CPU time for a smaller memory footprint
    	objList.Add(Item);
    	OctTree ret = new OctTree(region, objList);
    	ret._parent = this;
    	return ret;
    }

     

    Updating a tree

    Let's imagine that our tree has a lot of moving objects in it. If any object moves, there is a good chance that the object has moved outside of its enclosing octant. How do we handle changes in object position while maintaining the integrity of our tree structure?

    Technique 1: Keep it super simple, trash & rebuild everything.

    Some implementations of an Octree will completely rebuild the entire tree every frame and discard the old one. This is super simple and it works, and if this is all you need, then prefer the simple technique. The general consensus is that the upfront CPU cost of rebuilding the tree every frame is much cheaper than running a brute force collision check, and programmer time is too valuable to be spent on an unnecessary optimization. For those of us who like challenges and to over-engineer things, the "trash & rebuild" technique comes with a few small problems:

    1. You're constantly allocating and deallocating memory each time you rebuild your tree. Allocating new memory comes at a small cost. If possible, you want to minimize the amount of memory being allocated and reallocated over time by reusing memory you've already got.
    2. Most of the tree is unchanging, so it's a waste of CPU time to rebuild the same branches over and over again.

    Technique 2: Keep the existing tree, update the changed branches

    I noticed that most branches of a tree don't need to be updated. They just contain stationary objects. Wouldn't it be nice if, instead of rebuilding the entire tree every frame, we just updated the parts of the tree which needed an update? This technique keeps the existing tree and updates only the branches which had an object which moved. It's a bit more complex to implement, but it's a lot more fun too, so let's really get into that!

    During my first attempt at this, I mistakenly thought that an object in a child node could only go up or down one traversal of the tree. This is wrong. If an object in a child node reaches the edge of that node, and that edge also happens to be an edge for the enclosing parent node, then that object needs to be inserted above its parent, and possibly up even further. So, the bottom line is that we don't know how far up an object needs to be pushed up the tree. Just as well, an object can move such that it can be neatly enclosed in a child node, or that child's child node. We don't know how far down the tree we can go.

    Fortunately, since we include a reference to each node's parent, we can easily solve this problem recursively with minimal computation! The general idea behind the update algorithm is to first let all objects in the tree update themselves. Some may move or change in size. We want to get a list of every object which moved, so the object update method should return to us a boolean value indicating if its bounding area changed. Once we've got a list of all of our moved objects, we want to start at our current node and try to traverse up the tree until we find a node which completely encloses the moved object (most of the time, the current node still encloses the object). If the object isn't completely enclosed by the current node, we keep moving it up to its next parent node. In the worst case, our root node will be guaranteed to contain the object.

    After we've moved our object as far up the tree as possible, we'll try to move it as far down the tree as we can. Most of the time, if we moved the object up, we won't be able to move it back down. But, if the object moved so that a child node of the current node could contain it, we have the chance to push it back down the tree. It's important to be able to move objects down the tree as well, or else all moving objects would eventually migrate to the top and we'd start getting some performance problems during collision detection routines.

    Branch Removal

    In some cases, an object will move out of a node and that node will no longer have any objects contained within it, nor have any children which contain objects. If this happens, we have an empty branch and we need to mark it as such and prune this dead branch off the tree.

    There is an interesting question hiding here: When do you want to prune the dead branches off a tree? Allocating new memory costs time, so if we're just going to reuse this same region in a few cycles, why not keep it around for a bit? How long can we keep it around before it becomes more expensive to maintain the dead branch? I decided to give each of my nodes a countdown timer which activates when the branch is dead. If an object moves into this nodes octant while the death timer is active, I double the lifespan and reset the death timer. This ensures that octants which are frequently used are hot and stick around, and nodes which are infrequently used are removed before they start to cost more than they're worth.

    A practical example of this usefulness would be apparent when you have a machine gun shooting a stream of bullets. Those bullets follow in close succession of each other, so it'd be a shame to immediately delete a node as soon as the first bullet leaves it, only to recreate it a fraction of a second later as the second bullet re-enters it. And if there's a lot of bullets, we can probably keep these octants around for a little while. If a child branch is empty and hasn't been used in a while, it's safe to prune it out of our tree.

    Anyways, let's look at the code which does all of this magic. First up, we have the Update() method. This is a method which is recursively called on all child trees. It moves all objects around, does some housekeeping work for the data structure, and then moves each moved object into its correct node (parent or child).

    public void Update(coreTime time)
    {
    	if (m_treeBuilt == true && m_treeReady == true)
    	{
    		//Start a count down death timer for any leaf nodes which don't have objects or children.
    		//when the timer reaches zero, we delete the leaf. If the node is reused before death, we double its lifespan.
    		//this gives us a "frequency" usage score and lets us avoid allocating and deallocating memory unnecessarily
    		if (m_objects.Count == 0)
    		{
    			if (HasChildren == false)
    			{
    				if (m_curLife == -1)
    					m_curLife = m_maxLifespan;
    				else if (m_curLife > 0)
    				{
    					m_curLife--;
    				}
    			}
    		}
    		else
    		{
    			if (m_curLife != -1)
    			{
    				if (m_maxLifespan <= 64)
    					m_maxLifespan *= 2;
    				m_curLife = -1;
    			}
    		}
    
    		List<Physical> movedObjects = new List<Physical>(m_objects.Count);
    
    		//go through and update every object in the current tree node
    		foreach (Physical gameObj in m_objects)
    		{
    			//we should figure out if an object actually moved so that we know whether we need to update this node in the tree.
    			if (gameObj.Update(time) == 1)
    			{
    				movedObjects.Add(gameObj);
    			}
    		}
    
    		//prune any dead objects from the tree.
    		int listSize = m_objects.Count;
    		for (int a = 0; a < listSize; a++)
    		{
    			if (!m_objects[a].Alive)
    			{
    				if (movedObjects.Contains(m_objects[a]))
    					movedObjects.Remove(m_objects[a]);
    				m_objects.RemoveAt(a--);
    				listSize--;
    			}
    		}
    
    		//prune out any dead branches in the tree
    		for (int flags = m_activeNodes, index = 0; flags > 0; flags >>= 1, index++)
    			if ((flags & 1) == 1 && m_childNode[index].m_curLife == 0)
    			{
    				if (m_childNode[index].m_objects.Count > 0)
    				{
    					//throw new Exception("Tried to delete a used branch!");
    					m_childNode[index].m_curLife = -1;
    				}
    				else
    				{
    					m_childNode[index] = null;
    					m_activeNodes ^= (byte)(1 << index);       //remove the node from the active nodes flag list
    				}
    			}
    
    		//recursively update any child nodes.
    		for (int flags = m_activeNodes, index = 0; flags > 0; flags >>= 1, index++)
    		{
    			if ((flags & 1) == 1)
    			{
    				if(m_childNode!=null && m_childNode[index] != null)
    					m_childNode[index].Update(time);
    			}
    		}
    
    
    
    		//If an object moved, we can insert it into the parent and that will insert it into the correct tree node.
    		//note that we have to do this last so that we don't accidentally update the same object more than once per frame.
    		foreach (Physical movedObj in movedObjects)
    		{
    			OctTree current = this;
    			
    
    			//figure out how far up the tree we need to go to reinsert our moved object
    			//we are either using a bounding rect or a bounding sphere
    			//try to move the object into an enclosing parent node until we've got full containment
    			if (movedObj.EnclosingBox.Max != movedObj.EnclosingBox.Min)
    			{
    				while (current.m_region.Contains(movedObj.EnclosingBox) != ContainmentType.Contains)
    					if (current._parent != null) current = current._parent;
    					else
    					{
    						break; //prevent infinite loops when we go out of bounds of the root node region
    					}
    			}
    			else
    			{
    				ContainmentType ct = current.m_region.Contains(movedObj.EnclosingSphere);
    				while (ct != ContainmentType.Contains)//we must be using a bounding sphere, so check for its containment.
    				{
    					if (current._parent != null)
    					{
    						current = current._parent;
    					}
    					else
    					{
    						//the root region cannot contain the object, so we need to completely rebuild the whole tree.
    						//The rarity of this event is rare enough where we can afford to take all objects out of the existing tree and rebuild the entire thing.
    						List<Physical> tmp = m_root.AllObjects();
    						m_root.UnloadContent();
    						Enqueue(tmp);//add to pending queue
    
    						
    						return;
    					}
    
    					ct = current.m_region.Contains(movedObj.EnclosingSphere);
    				}
    			}
    
    				//now, remove the object from the current node and insert it into the current containing node.
    			m_objects.Remove(movedObj);
    			current.Insert(movedObj);   //this will try to insert the object as deep into the tree as we can go.
    		}
    
    		//now that all objects have moved and they've been placed into their correct nodes in the octree, we can look for collisions.
    		if (IsRoot == true)
    		{
    			//This will recursively gather up all collisions and create a list of them.
    			//this is simply a matter of comparing all objects in the current root node with all objects in all child nodes.
    			//note: we can assume that every collision will only be between objects which have moved.
    			//note 2: An explosion can be centered on a point but grow in size over time. In this case, you'll have to override the update method for the explosion.
    			List<IntersectionRecord> irList = GetIntersection(new List<Physical>());
    
    			foreach (IntersectionRecord ir in irList)
    			{
    				if (ir.PhysicalObject != null)
    					ir.PhysicalObject.HandleIntersection(ir);
    				if (ir.OtherPhysicalObject != null)
    					ir.OtherPhysicalObject.HandleIntersection(ir);
    			}
    		}
    	}//end if tree built
    	else
    	{
    		if (m_pendingInsertion.Count > 0)
    		{
    			ProcessPendingItems();
    			Update(time);   //try this again...
    		}
    	}
    }

    Note that we call an Insert() method for moved objects. The insertion of objects into the tree is very similar to the method used to build the initial tree. Insert() will try to push objects as far down the tree as possible. Notice that I also try to avoid creating new bounding areas if I can use an existing one from a child node.

    /// <summary>
    /// A tree has already been created, so we're going to try to insert an item into the tree without rebuilding the whole thing
    /// </summary>
    /// <typeparam name="T">A physical object</typeparam>
    /// <param name="Item">The physical object to insert into the tree</param>
    private bool Insert<T>(T Item) where T : Physical
    {
    	/*if the current node is an empty leaf node, just insert and leave it.*/
    	//if (m_objects.Count == 0 && m_activeNodes == 0)
    	if(AllTreeObjects.Count == 0)
    	{
    		m_objects.Add(Item);
    		return true;
    	}
    
    	//Check to see if the dimensions of the box are greater than the minimum dimensions.
    	//If we're at the smallest size, just insert the item here. We can't go any lower!
    	Vector3 dimensions = m_region.Max - m_region.Min;
    	if (dimensions.X <= MIN_SIZE && dimensions.Y <= MIN_SIZE && dimensions.Z <= MIN_SIZE)
    	{
    		m_objects.Add(Item);
    		return true;
    	}
    
    	//The object won't fit into the current region, so it won't fit into any child regions.
    	//therefore, try to push it up the tree. If we're at the root node, we need to resize the whole tree.
    	if (m_region.Contains(Item.EnclosingSphere) != ContainmentType.Contains)
    	{
    		if (this._parent != null)
    			return this._parent.Insert(Item);
    		else
    			return false;
    	}
    	
    	//At this point, we at least know this region can contain the object but there are child nodes. Let's try to see if the object will fit
    	//within a subregion of this region.
    
    	Vector3 half = dimensions / 2.0f;
    	Vector3 center = m_region.Min + half;
    
    	//Find or create subdivided regions for each octant in the current region
    	BoundingBox[] childOctant = new BoundingBox[8];
    	childOctant[0] = (m_childNode[0] != null) ? m_childNode[0].m_region : new BoundingBox(m_region.Min, center);
    	childOctant[1] = (m_childNode[1] != null) ? m_childNode[1].m_region : new BoundingBox(new Vector3(center.X, m_region.Min.Y, m_region.Min.Z), new Vector3(m_region.Max.X, center.Y, center.Z));
    	childOctant[2] = (m_childNode[2] != null) ? m_childNode[2].m_region : new BoundingBox(new Vector3(center.X, m_region.Min.Y, center.Z), new Vector3(m_region.Max.X, center.Y, m_region.Max.Z));
    	childOctant[3] = (m_childNode[3] != null) ? m_childNode[3].m_region : new BoundingBox(new Vector3(m_region.Min.X, m_region.Min.Y, center.Z), new Vector3(center.X, center.Y, m_region.Max.Z));
    	childOctant[4] = (m_childNode[4] != null) ? m_childNode[4].m_region : new BoundingBox(new Vector3(m_region.Min.X, center.Y, m_region.Min.Z), new Vector3(center.X, m_region.Max.Y, center.Z));
    	childOctant[5] = (m_childNode[5] != null) ? m_childNode[5].m_region : new BoundingBox(new Vector3(center.X, center.Y, m_region.Min.Z), new Vector3(m_region.Max.X, m_region.Max.Y, center.Z));
    	childOctant[6] = (m_childNode[6] != null) ? m_childNode[6].m_region : new BoundingBox(center, m_region.Max);
    	childOctant[7] = (m_childNode[7] != null) ? m_childNode[7].m_region : new BoundingBox(new Vector3(m_region.Min.X, center.Y, center.Z), new Vector3(center.X, m_region.Max.Y, m_region.Max.Z));
    
    	//First, is the item completely contained within the root bounding box?
    	//note2: I shouldn't actually have to compensate for this. If an object is out of our predefined bounds, then we have a problem/error.
    	//          Wrong. Our initial bounding box for the terrain is constricting its height to the highest peak. Flying units will be above that.
    	//             Fix: I resized the enclosing box to 256x256x256. This should be sufficient.
    	if (Item.EnclosingBox.Max != Item.EnclosingBox.Min && m_region.Contains(Item.EnclosingBox) == ContainmentType.Contains)
    	{
    		bool found = false;
    		//we will try to place the object into a child node. If we can't fit it in a child node, then we insert it into the current node object list.
    		for(int a=0;a<8;a++)
    		{
    			//is the object fully contained within a quadrant?
    			if (childOctant[a].Contains(Item.EnclosingBox) == ContainmentType.Contains)
    			{
    				if (m_childNode[a] != null)
    				{
    					return m_childNode[a].Insert(Item);   //Add the item into that tree and let the child tree figure out what to do with it
    				}
    				else
    				{
    					m_childNode[a] = CreateNode(childOctant[a], Item);   //create a new tree node with the item
    					m_activeNodes |= (byte)(1 << a);
    				}
    				found = true;
    			}
    		}
    
    		//we couldn't fit the item into a smaller box, so we'll have to insert it in this region
    		if (!found)
    		{
    			m_objects.Add(Item);
    			return true;
    		}
    	}
    	else if (Item.EnclosingSphere.Radius != 0 && m_region.Contains(Item.EnclosingSphere) == ContainmentType.Contains)
    	{
    		bool found = false;
    		//we will try to place the object into a child node. If we can't fit it in a child node, then we insert it into the current node object list.
    		for (int a = 0; a < 8; a++)
    		{
    			//is the object contained within a child quadrant?
    			if (childOctant[a].Contains(Item.EnclosingSphere) == ContainmentType.Contains)
    			{
    				if (m_childNode[a] != null)
    				{
    					return m_childNode[a].Insert(Item);   //Add the item into that tree and let the child tree figure out what to do with it
    				}
    				else
    				{
    					m_childNode[a] = CreateNode(childOctant[a], Item);   //create a new tree node with the item
    					m_activeNodes |= (byte)(1 << a);
    				}
    				found = true;
    			}
    		}
    
    		//we couldn't fit the item into a smaller box, so we'll have to insert it in this region
    		if (!found)
    		{
    			m_objects.Add(Item);
    			return true;
    		}
    	}
    
    	//either the item lies outside of the enclosed bounding box or it is intersecting it. Either way, we need to rebuild
    	//the entire tree by enlarging the containing bounding box
    	return false;
    }

     

    Collision Detection

    Finally, our octree has been built and everything is as it should be. How do we perform collision detection against it? First, let's list out the different ways we want to look for collisions:

    1. Frustum intersections. We may have a frustum which intersects with a region of the world. We only want the objects which intersect with the given frustum. This is particularly useful for culling regions outside of the camera view space, and for figuring out what objects are within a mouse selection area.
    2. Ray intersections. We may want to shoot a directional ray from any given point and want to know either the nearest intersecting object or get a list of all objects which intersect that ray (like a rail gun). This is very useful for mouse picking. If the user clicks on the screen, we want to draw a ray into the world and figure out what they clicked on.
    3. Bounding Box intersections. We want to know which objects in the world are intersecting a given bounding box. This is most useful for "box" shaped game objects (houses, cars, etc).
    4. Bounding Sphere Intersections. We want to know which objects are intersecting with a given bounding sphere. Most objects will probably be using a bounding sphere for coarse collision detection since the mathematics is computationally the least expensive and somewhat easy.

    The main idea behind recursive collision detection processing for an octree is that you start at the root/current node and test for intersection with all objects in that node against the intersector. Then, you do a bounding box intersection test against all active child nodes with the intersector. If a child node fails this intersection test, you can completely ignore the rest of that child's tree. If a child node passes the intersection test, you recursively traverse down the tree and repeat. Each node should pass a list of intersection records up to its caller, which appends those intersections to its own list of intersections. When the recursion finishes, the original caller will get a list of every intersection for the given intersector. The beauty of this is that it takes very little code to implement and performance is very fast. In a lot of these collisions, we're probably going to be getting a lot of results. We're also going to want to have some way of responding to each collision, depending on what objects are colliding.

    For example, a player hero should pick up a floating bonus item (quad damage!), but a rocket shouldn't explode if it hits said bonus item. I created a new class to contain information about each intersection. This class contains references to the intersecting objects, the point of intersection, the normal at the point of intersection, etc. These intersection records become quite useful when you pass them to an object and tell them to handle it. For completeness and clarity, here is my intersection record class:

    public class IntersectionRecord
    {
    	readonly Vector3 m_position, m_normal;
    
    	readonly Ray m_ray;
    
    	readonly Physical m_intersectedObject1, m_intersectedObject2;
    	
    	readonly double m_distance;
    
    	public class Builder
    	{
    		public Vector3 Position, Normal;
    		public Physical Object1, Object2;
    		public Ray hitRay;
    		public double Distance;
    
    		public Builder()
    		{
    			Distance = double.MaxValue;
    		}
    
    		public Builder(IntersectionRecord copy)
    		{
    			Position = copy.m_position;
    			Normal = copy.m_normal;
    			Object1 = copy.m_intersectedObject1;
    			Object2 = copy.m_intersectedObject2;
    			hitRay = copy.m_ray;
    			Distance = copy.m_distance;
    		}
    
    		public IntersectionRecord Build()
    		{
    			return new IntersectionRecord(Position, Normal, Object1, Object2, hitRay, Distance);
    		}
    	}
    
    	#region Constructors
    	IntersectionRecord(Vector3 pos, Vector3 normal, Physical obj1, Physical obj2, Ray r, double dist)
    	{
    		m_position = pos;
    		m_normal = normal;
    		m_intersectedObject1 = obj1;
    		m_intersectedObject2 = obj2;
    		m_ray = r;
    		m_distance = dist;
    	}
    	#endregion
    
    	#region Accessors
    	/// <summary>
    	/// This is the exact point in 3D space which has an intersection.
    	/// </summary>
    	public Vector3 Position { get { return m_position; } }
    
    	/// <summary>
    	/// This is the normal of the surface at the point of intersection
    	/// </summary>
    	public Vector3 Normal { get { return m_normal; } }
    
    	/// <summary>
    	/// This is the ray which caused the intersection
    	/// </summary>
    	public Ray Ray { get { return m_ray; } }
    
    	/// <summary>
    	/// This is the object which is being intersected
    	/// </summary>
    	public Physical PhysicalObject
    	{
    		get { return m_intersectedObject1; }
    	}
    
    	/// <summary>
    	/// This is the other object being intersected (may be null, as in the case of a ray-object intersection)
    	/// </summary>
    	public Physical OtherPhysicalObject
    	{
    		get { return m_intersectedObject2; }
    	}
    
    	/// <summary>
    	/// This is the distance from the ray to the intersection point. 
    	/// You'll usually want to use the nearest collision point if you get multiple intersections.
    	/// </summary>
    	public double Distance { get { return m_distance; } }
    
    	#endregion
    
    	#region Overrides
    	public override string ToString()
    	{
    		return "Hit: " + m_intersectedObject1.ToString();
    	}
    	public override int GetHashCode()
    	{
    		return base.GetHashCode();
    	}
    	/// <summary>
    	/// check the object identities between the two intersection records. If they match in either order, we have a duplicate.
    	/// </summary>
    	/// <param name="otherRecord">the other record to compare against</param>
    	/// <returns>true if the records are an intersection for the same pair of objects, false otherwise.</returns>
    	public override bool Equals(object otherRecord)
    	{
    		IntersectionRecord o = (IntersectionRecord)otherRecord;
    		//
    		//return (m_intersectedObject1 != null && m_intersectedObject2 != null && m_intersectedObject1.ID == m_intersectedObject2.ID);
    		if (otherRecord == null)
    			return false;
    		if (o.m_intersectedObject1.ID == m_intersectedObject1.ID && o.m_intersectedObject2.ID == m_intersectedObject2.ID)
    			return true;
    		if (o.m_intersectedObject1.ID == m_intersectedObject2.ID && o.m_intersectedObject2.ID == m_intersectedObject1.ID)
    			return true;
    		return false;
    	}
    	#endregion
    }

     

    Intersection with a Bounding Frustum

    /// <summary>
    /// Gives you a list of all intersection records which intersect or are contained within the given frustum area
    /// </summary>
    /// <param name="frustum">The containing frustum to check for intersection/containment with</param>
    /// <returns>A list of intersection records with collisions</returns>
    private List<IntersectionRecord> GetIntersection(BoundingFrustum frustum, PhysicalType type = PhysicalType.ALL)
    {
    	if (!m_treeBuilt) return new List<IntersectionRecord>();
    
    	if (m_objects.Count == 0 && HasChildren == false)   //terminator for any recursion
    		return null;
    
    	List<IntersectionRecord> ret = new List<IntersectionRecord>();
    
    	//test each object in the list for intersection
    	foreach (Physical obj in m_objects)
    	{
    
    		//skip any objects which don't meet our type criteria
    		if ((int)((int)type & (int)obj.Type) == 0)
    			continue;
    
    		//test for intersection
    		IntersectionRecord ir = obj.Intersects(frustum);
    		if (ir != null) 
    			ret.Add(ir);
    	}
    
    	//test each object in the list for intersection
    	for (int a = 0; a < 8; a++)
    	{
    		if (m_childNode[a] != null && (frustum.Contains(m_childNode[a].m_region) == ContainmentType.Intersects || frustum.Contains(m_childNode[a].m_region) == ContainmentType.Contains))
    		{
    			List<IntersectionRecord> hitList = m_childNode[a].GetIntersection(frustum, type);
    			if (hitList != null) ret.AddRange(hitList);
    		}
    	}
    	return ret;
    }

    The bounding frustum intersection list can be used to only render objects which are visible to the current camera view. I use a scene database to figure out how to render all objects in the game world. Here is a snippet of code from my rendering function which uses the bounding frustum of the active camera:

    /// 
    /// This renders every active object in the scene database /// 
    /// 
    public int Render()
    { 
    	int triangles = 0; 
    	//Renders all visible objects by iterating through the oct tree recursively and testing for intersection 
    	//with the current camera view frustum 
    	foreach (IntersectionRecord ir in m_octTree.AllIntersections(m_cameras[m_activeCamera].Frustum)) 
    	{ 
    		ir.PhysicalObject.SetDirectionalLight(m_globalLight[0].Direction, m_globalLight[0].Color); 
    		ir.PhysicalObject.View = m_cameras[m_activeCamera].View; 
    		ir.PhysicalObject.Projection = m_cameras[m_activeCamera].Projection; 
    		ir.PhysicalObject.UpdateLOD(m_cameras[m_activeCamera]); 
    		triangles += ir.PhysicalObject.Render(m_cameras[m_activeCamera]); 
    	} 
    	return triangles; 
    } 

     

    Intersection with a Ray

    /// <summary>
    /// Gives you a list of intersection records for all objects which intersect with the given ray
    /// </summary>
    /// <param name="intersectRay">The ray to intersect objects against</param>
    /// <returns>A list of all intersections</returns>
    private List<IntersectionRecord> GetIntersection(Ray intersectRay, PhysicalType type = PhysicalType.ALL)
    {
    	if (!m_treeBuilt) return new List<IntersectionRecord>();
    
    	if (m_objects.Count == 0 && HasChildren == false)   //terminator for any recursion
    		return null;
    
    	List<IntersectionRecord> ret = new List<IntersectionRecord>();
    
    	//the ray is intersecting this region, so we have to check for intersection with all of our contained objects and child regions.
    	
    	//test each object in the list for intersection
    	foreach (Physical obj in m_objects)
    	{
    		//skip any objects which don't meet our type criteria
    		if ((int)((int)type & (int)obj.Type) == 0)
    			continue;
    
    		IntersectionRecord ir = obj.Intersects(intersectRay);
    		if (ir != null)
    			ret.Add(ir);
    	}
    
    	// test each child octant for intersection
    	for (int a = 0; a < 8; a++)
    	{
    		if (m_childNode[a] != null && m_childNode[a].m_region.Intersects(intersectRay) != null)
    		{
    			m_lineColor = Color.Red;
    			List<IntersectionRecord> hits = m_childNode[a].GetIntersection(intersectRay, type);
    			if (hits != null && hits.Count > 0)
    			{
    				ret.AddRange(hits);
    			}
    		}
    	}
    
    	return ret;
    }

     

    Intersection with a list of objects

    This is a particularly useful recursive method for determining if a list of objects in the current node intersects with any objects in any child nodes (See: Update() method for usage). It's the method which will be used most frequently, so it's good to get this right and efficient. What we want to do is start at the root node of the tree. We compare all objects in the current node against all other objects in the current node for collision. We gather up any of those collisions as intersection records and insert them into a list. We then pass our list of tested objects down to our child nodes. The child nodes will then test their objects against themselves, then against the objects we passed down to them. The child nodes will capture any collisions in a list, and return that list to its parent. The parent then takes the collision list received from its child nodes and appends it to its own list of collisions, finally returning it to its caller.

    Collision_1a.png Collision_1b.png

    If you count out the number of collision tests in the illustration above, you can see that we conducted 29 hit tests and received 4 hits. This is much better than [11*11 = 121] hit tests.

    private List<IntersectionRecord> GetIntersection(List<Physical> parentObjs, PhysicalType type = PhysicalType.ALL)
    {
    	List<IntersectionRecord> intersections = new List<IntersectionRecord>();
    	//assume all parent objects have already been processed for collisions against each other.
    	//check all parent objects against all objects in our local node
    	foreach (Physical pObj in parentObjs)
    	{
    		foreach (Physical lObj in m_objects)
    		{
    			//We let the two objects check for collision against each other. They can figure out how to do the coarse and granular checks.
    			//all we're concerned about is whether or not a collision actually happened.
    			IntersectionRecord ir = pObj.Intersects(lObj);
    			if (ir != null)
    			{
    
    				//ir.m_treeNode = this;
    
    
    				intersections.Add(ir);
    			}
    		}
    	}
    
    	//now, check all our local objects against all other local objects in the node
    	if (m_objects != null && m_objects.Count > 1)
    	{
    		#region self-congratulation
    		/*
    		 * This is a rather brilliant section of code. Normally, you'd just have two foreach loops, like so:
    		 * foreach(Physical lObj1 in m_objects)
    		 * {
    		 *      foreach(Physical lObj2 in m_objects)
    		 *      {
    		 *           //intersection check code
    		 *      }
    		 * }
    		 * 
    		 * The problem is that this runs in O(N*N) time and that we're checking for collisions with objects which have already been checked.
    		 * Imagine you have a set of four items: {1,2,3,4}
    		 * You'd first check: {1} vs {1,2,3,4}
    		 * Next, you'd check {2} vs {1,2,3,4}
    		 * but we already checked {1} vs {2}, so it's a waste to check {2} vs. {1}. What if we could skip this check by removing {1}?
    		 * We'd have a total of 4+3+2+1 collision checks, which equates to O(N(N+1)/2) time. If N is 10, we are already doing half as many collision checks as necessary.
    		 * Now, we can't just remove an item at the end of the 2nd for loop since that would break the iterator in the first foreach loop, so we'd have to use a
    		 * regular for(int i=0;i<size;i++) style loop for the first loop and reduce size each iteration. This works...but look at the for loop: we're allocating memory for
    		 * two additional variables: i and size. What if we could figure out some way to eliminate those variables?
    		 * So, who says that we have to start from the front of a list? We can start from the back end and still get the same end results. With this in mind,
    		 * we can completely get rid of a for loop and use a while loop which has a conditional on the capacity of a temporary list being greater than 0.
    		 * since we can poll the list capacity for free, we can use the capacity as an indexer into the list items. Now we don't have to increment an indexer either!
    		 * The result is below.
    		 */
    	#endregion
    
    	List<Physical> tmp = new List<Physical>(m_objects.Count);
    	tmp.AddRange(m_objects);
    	while (tmp.Count > 0)
    	{
    		foreach (Physical lObj2 in tmp)
    		{
    			if (tmp[tmp.Count - 1] == lObj2 || (tmp[tmp.Count - 1].IsStationary && lObj2.IsStationary))
    				continue;
    			IntersectionRecord ir = tmp[tmp.Count - 1].Intersects(lObj2);
    			if (ir != null)
    			{
    				//ir.m_treeNode = this;
    				intersections.Add(ir);
    			}
    		}
    
    		//remove this object from the temp list so that we can run in O(N(N+1)/2) time instead of O(N*N)
    		tmp.RemoveAt(tmp.Count-1);
    	}
    }
    
    //now, merge our local objects list with the parent objects list, then pass it down to all children.
    foreach (Physical lObj in m_objects)
    	if (lObj.IsStationary == false)
    		parentObjs.Add(lObj);
    //parentObjs.AddRange(m_objects);
    
    //each child node will give us a list of intersection records, which we then merge with our own intersection records.
    for (int flags = m_activeNodes, index = 0; flags > 0; flags >>= 1, index++)
    {
    	if ((flags & 1) == 1)
    	{
    		if(m_childNode != null && m_childNode[index] != null)
    			intersections.AddRange(m_childNode[index].GetIntersection(parentObjs, type));
    	}
    }
    
    return intersections;
    }

     

    Screenshot Demos

     

    Demo_1a.png This is a view of the game world from a distance showing the outlines for each bounding volume for the octree.
    Demo_1b.png This view shows a bunch of successive projectiles moving through the game world with the frequently-used nodes being preserved instead of deleted.

     

    Complete Code Sample

    I've attached a complete code sample of the octree class, the intersection record class, and my generic physical object class. I don't guarantee that they're all bug-free since it's all a work in progress and hasn't been rigorously tested yet.



      Report Article


    User Feedback


    Im not a fan of quadtree or octree, but must admit that article its one of the best...

    Share this comment


    Link to comment
    Share on other sites

    Only one comment? Really? Man, this tutorial is amazing! I plan on implementing something similar into my game engine in the near future and I'm sure I will be able to do it using this tutorial only!

     

    Thank you very much for this amazing work <3

    Share this comment


    Link to comment
    Share on other sites

    Very interesting article, thanks for the explanations!

     

    However, the code would need to be reviewed a little bit, with blocks of codes being put in separate methods, GetIntersection being coded once for all as generic for any kind of intersection checks (with common logic of type check and children intersection tests) - except maybe for the last one (list of objects), where you could also avoid to use a separate tmp list of Physical, and just keep the index of the last object to treat in m_objects instead.

    Share this comment


    Link to comment
    Share on other sites

    Yeah, I found some bugs in my code later on and fixed them. I think the in-place update may have been overly complicating things and adding additional potential sources for errors. I recommend using my code implementation as a good starting point / reference instead of blindly just copy/pasting it. I'm sure someone smarter than I could design it much better, but this was my second iteration :)

    Share this comment


    Link to comment
    Share on other sites

    Great article and super useful code. I have one question. In the FindEnclosingCube() method, there is this:

                //gets the most significant bit value, so that we essentially do a Ceiling(X) with the 
                //ceiling result being to the nearest power of 2 rather than the nearest integer.
                int x = Calc.SigBit(highX);     
    
    

    Did you intend for that to be the highest significant bit of highX, or the largest power of 2 that contains highX? I assume it was the highest that contains the number, so I replaced it with:

           /// Round up to next higher power of 2 (return x if it's already a power
            /// of 2).
            int pow2roundup(int x)
            {
                if (x < 0)
                    return 0;
                --x;
                x |= x >> 1;
                x |= x >> 2;
                x |= x >> 4;
                x |= x >> 8;
                x |= x >> 16;
                return x + 1;
    
            }
    
    

    I probably broke the whole thing... Haven't put it into action yet.

    Share this comment


    Link to comment
    Share on other sites

    Great article and super useful code. I have one question. In the FindEnclosingCube() method, there is this:
    //gets the most significant bit value, so that we essentially do a Ceiling(X) with the
    //ceiling result being to the nearest power of 2 rather than the nearest integer.
    int x = Calc.SigBit(highX);


    Did you intend for that to be the highest significant bit of highX, or the largest power of 2 that contains highX? I assume it was the highest that contains the number, so I replaced it with:
    /// Round up to next higher power of 2 (return x if it's already a power
    /// of 2).
    int pow2roundup(int x)
    {
    if (x < 0)
    return 0;
    --x;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x + 1;

    }


    I probably broke the whole thing... Haven't put it into action yet.

     
    Here is the code you're referencing:
    /// <summary>
    /// This finds the smallest enclosing cube with power of 2 dimensions for the given bounding box
    /// </summary>
    /// <param name="region">The bounding box to cubify</param>
    /// <returns>A cubified version of the input parameter.</returns>
    public static BoundingBox FindEnclosingCube(BoundingBox region)
    {
    	//we can't guarantee that all bounding regions will be relative to the origin, so to keep the math
    	//simple, we're going to translate the existing region to be oriented off the origin and remember the translation.
    	//find the min offset from (0,0,0) and translate by it for a short while
    	Vector3 offset = Vector3.Zero - region.Min;
    	region.Min += offset;
    	region.Max += offset;
    
    	//A 3D rectangle has a length, height, and width. Of those three dimensions, we want to find the largest dimension.
    	//the largest dimension will be the minimum dimensions of the cube we're creating.
    	int highX = (int)System.Math.Ceiling(System.Math.Max(System.Math.Max(region.Max.X, region.Max.Y), region.Max.Z));
    
    	//see if our cube dimension is already at a power of 2. If it is, we don't have to do any work.
    	for (int bit = 0; bit < 32; bit++)
    	{
    		if (highX == 1 << bit)
    		{
    			region.Max = new Vector3(highX, highX, highX);
    
    			region.Min -= offset;
    			region.Max -= offset;
    			return new BoundingBox(region.Min, region.Max);
    		}
    	}
    
    	//We have a cube with non-power of two dimensions. We want to find the next highest power of two.
    	//example: 63 -> 64; 65 -> 128;
    	int x = Calc.SigBit(highX);
    
    	region.Max = new Vector3(x, x, x);
    
    	region.Min -= offset;
    	region.Max -= offset;
    
    	return new BoundingBox(region.Min, region.Max);
    }
    

    What's going on here?

    I'm trying to create a cube which encloses every single object in the game world. A perfect cube has sides which are all of the same length. We could have a cube with side lengths of 1000 which perfectly encloses every object. However, 1000 is a number which doesn't divide by two very cleanly. In my octree, I decided that the smallest a quadrant should be is 1x1x1. I wouldn't get much more of a performance gain by going smaller.
    So, if my enclosing cube is 1000x1000x1000, I can't get a nice 1x1x1 cube by successively dividing by two:
    1000 / 2 = 500
    500 / 2 = 250
    250 / 2 = 125
    125 / 2 = 62.5
    62.5 / 2 = 31.25
    31.25 / 2 = 15.625
    (etc)

    However, if we increase the size of our enclosing cube to be a power of 2, we can easily divide by 2 each time to get clean numbers, all the way down to a 1x1x1 cube. If we have our enclosing cube of 1000x1000x1000, then the nearest cube with a power of 2 we want would be 1024x1024x1024. So, the function you're asking about should take any number and return the power of 2 value which is closest to the given number. ie, 63 would result in 64, 65 would result in 128, etc.

    Share this comment


    Link to comment
    Share on other sites

    In the Insert() method, shouldn't there be a "break;" when an item has been inserted? (talking about the for(int a=0;a<8;a++) loop)

    Share this comment


    Link to comment
    Share on other sites
    Thanks a lot for the explanation and source code. I am currently working on 3D Surface Reconstruction from point cloud data. Solved my 25 % part of the project by reading this wonderful article. Cheers!

    Share this comment


    Link to comment
    Share on other sites

    I felt I have learned something from your article although I just try to implement a RTree spatial partition for my 2D game. You've done an amazing job. I am very interested in updating only the changed branches as my current RTree implementation failed to do so. I will have to come up with a better solution.

    Edited by caymanbruce

    Share this comment


    Link to comment
    Share on other sites

    What would be the difference between the 'BoundingBox.Contains()' and 'Physical.Intersects()' if the Physical object is just another square?

     

    Would they both need to implement Separating Axis Theorem?

    Share this comment


    Link to comment
    Share on other sites
    On 4/21/2018 at 2:29 PM, LajosPolya said:

    What would be the difference between the 'BoundingBox.Contains()' and 'Physical.Intersects()' if the Physical object is just another square?

     

    Would they both need to implement Separating Axis Theorem?

    "Containment" means that the object is entirely enclosed within the box and that the edges of the box do not overlap with the object. "Intersection" means that there is an overlap between the box and the object. As long as your object continues to be contained within each subsequent subdivision, you can continue pushing it down to lower levels of the tree.

    Share this comment


    Link to comment
    Share on other sites

    Nice presentation! I especially liked your "lazy initialization" stuff!

    Just to add to the discussion a bit, I've started to use something I call "sloppy octrees".  It probably has some other name I simply don't know about. I've come to the conclusion that there is no reason that the child cells of a parent cell can't cross each other. The only real requirement is that they don't go outside their parent.  This means that when searching the octree you may have to go down more than one branch for a bit. However it also means that objects can be placed farther down in the tree, because an object that would normally have to be in a parent can now go into the child. Finally it lets you use other shapes for you volumes besides cubes. I've used spheres and cylinders. It any case I think there are some applications where this might be useful.

    Share this comment


    Link to comment
    Share on other sites
    On 11/16/2018 at 10:35 PM, Gnollrunner said:

    Nice presentation! I especially liked your "lazy initialization" stuff!

    Just to add to the discussion a bit, I've started to use something I call "sloppy octrees".  It probably has some other name I simply don't know about. I've come to the conclusion that there is no reason that the child cells of a parent cell can't cross each other. The only real requirement is that they don't go outside their parent.  This means that when searching the octree you may have to go down more than one branch for a bit. However it also means that objects can be placed farther down in the tree, because an object that would normally have to be in a parent can now go into the child. Finally it lets you use other shapes for you volumes besides cubes. I've used spheres and cylinders. It any case I think there are some applications where this might be useful.

    Wouldn't using spheres instead of squares cause gaps?

    I also think your child volumes should never overlap each other. The child volumes could become parents to even smaller volumes, so if two child volumes are allowed to overlap each other, then when you search a tree for a unique object, you'll get multiple hits and then you'd have to do intersection handling against itself.

    It's been a few years since I wrote this code, but I think I had some logic in there which terminated the octant subdivision if an object was the only object contained within the octant. This helps you avoid having really deep trees if you have a sparse set of small objects in your world. Imagine what your octree should look like if you have a 1000m cube and five 1cm pebbles scattered at random. You want to minimize the depth of your tree so that you don't drill 100 layers down into your tree to find a pebble. If you wanted to do collision with thousands of gravel particles, I think you'd eventually also reach a minimum bounding volume size, where continuing unlimited subdivision costs more memory than the CPU time it saves -- so there's also going to be a case by case basis for optimization to be made to balance memory consumption against CPU processing time.

    Share this comment


    Link to comment
    Share on other sites

    Octrees are a way to speed up. It does not simplify collision detection. It adds more code (I am right now not going to read all that). "Sloppy" may not be the official term, but I think I read that multiple members use the Octree in this way.

    Premature optimization and all that..

    Share this comment


    Link to comment
    Share on other sites


    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement
  • Game Developer Survey

    completed-task.png

    We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a $15 incentive for your time and insights. Click here to start!

    Take me to the survey!

  • Advertisement
  • Latest Featured Articles

  • Featured Blogs

  • Advertisement
  • Popular Now

  • Similar Content

    • By Ruben Torres
      [This post was originally posted with its original formatting at The Gamedev Guru's Blog]
      If you've been following me, you will probably know my interest in Unity Addressables. That is for a reason.

      Unity Addressables is a powerful Unity package that upgrades the way you and I have been tackling some of the most important challenges in Game Development: efficient, pain-free content management.
      When managing your game assets, it's hard to keep good standards that prevent our project from becoming a disgusting pile of mess. A big issue there is the coupling between the different responsibilities of our asset management systems.
      The way we store the assets in our project has way too much to do with the method we load them, and later use them.
      For instance, you may decide to store an innocent sprite in the Resources folder. This, in turn, will force Unity to build the player in a way that that sprite is put into special archive files. And the fact that it was put there, will corner you into loading it through the Resources API.
      Things get messy quicker than you can realize!
      One choice, multiple long-term consequences.
      A good system will prevent you and me from easily making sloppy mistakes like that. A great system will be that, and also easy to learn and use.
      With Unity Addressables, we separate the asset management concerns. Our goal is to remain flexible and to keep our project maintainable.
      Here are 3 proven ways Unity Addressables will help you and your games:

      1. Reduce Your Game's Memory Pressure
      When you publish your game, you'll be required on most platforms to specify the minimum hardware specifications your players must meet to buy and play your game.
      The math is easy here: the more hardware power you demand, the fewer will buy your game. Or, seen from another perspective, the better memory management you do, the higher the amount of content and fun you can offer in your game.
      Unity Addressables helps you in this regard enormously!
      To give you a brief idea, converting this kind of code:
      public class CharacterCustomization : MonoBehaviour { [SerializeField] private List<Material> _armorVariations; [SerializeField] private MeshRenderer _armorRenderer; public void ChangeArmorVariation(int variationId) { _armorRenderer.material = _armorVariations[variationId]; } } Into this other one:
      using UnityEngine.AddressableAssets; public class CharacterCustomizationV2 : MonoBehaviour { [SerializeField] private List<AssetReference> _armorVariations; [SerializeField] private MeshRenderer _armorRenderer; public IEnumerator ChangeArmorVariation(int variationId) { var loadProcess = _armorVariations[variationId].LoadAssetAsync(); yield return loadProcess; _armorRenderer.material = loadProcess.Result; } } Will bring you these results:

      Easy gains I'd say.
      -> Read more on Unity Addressables for better memory management in Unity Addressables: It's Never Too Big to Fit (opens in a new tab)
       

      2. Sell Your Next DLC - Quick and Easy
      The fact that Unity Addessables gives you full control over how, when and where to store and load your game assets is incredibly useful for implementing and selling Downloadable Content.
      Even if you are not thinking of releasing DLCs any time soon, just by using Unity Addressables in your project, you will have done already a big chunk of the work ahead.
      Other approaches for selling DLCs, such as Asset Bundles, are a very deprecated way of doing the same thing but at a much higher cost. Maintaining a well-functioning Asset Bundle pipeline is painfully time-consuming and requires a high degree of expensive expertise.
      There are many ways you can approach implementing DLCs in Unity, but for starters, this is a good starting point:
       
      public class DlcManager : MonoBehaviour { // ... public IEnumerator TryDownloadDlc() { if (_hasBoughtDlc && _dlcDownloaded == false) { var operationHandle = Addressables.DownloadDependenciesAsync("DLC-Content"); while (operationHandle.IsDone == false) { _progressText.text = $"{operationHandle.PercentComplete * 100.0f} %"; yield return null; } } } } You get the idea.
      Why would you say no to selling more entertainment for your players at a fraction of the cost?

      3. Reduce Your Iteration Times
      Using Unity Addressables will reduce the time wasted waiting in several areas.
      Tell me, how frustrating is it to be blocked for half a minute after pressing the Unity play button? And it only gets worse if you deploy your build on another platform, such as mobile or WebGL. This all starts adding minutes and minutes to your iteration times. It gets old so quickly.
      I don't like waiting either.
      But do you know what I like? Unity Addressables, my long-awaited hero. This is how Addressables will help you:
      A) Reduced Build Size
      Your game has a lot of content, I get it. Gamers love enjoying content. Developers love creating content.
      That doesn't mean, however, that every single asset you produced has to be included in the build your players will install. In fact, you should remove as much as possible.
      Players want to start playing ASAP. And they're not happy when your game steals 2GB of their data plan and 30 minutes of their gaming time. They'll just keep downloading Candy Crush kind of games that install well under 50MB.
      One strategy is to include only the assets needed to run your game up to the main menu. Then, you can progressively download the rest of your content in the background, starting, of course, downloading the first level of your game.
      It's also neat to realize that your deployment times during development will be much faster. You'll be able to iterate more times each day; this benefit quickly adds up in the long term.

      Unity Addressables - Reduced Build Sizes
      B) Reduced Load Times
      We, both as game developers and as players, hate waiting. Waiting takes us out of the zone and before you realize it, it is time to go to bed.
      Unity is working hard towards reducing the time it takes us to start playing our games, both in the Unity Editor and in the games we distribute.
      But not hard enough.
      Things look promising in the future, but not without side effects. Avoiding domain reloads in Unity 2019.3 looks promising, but as of today that's still in beta and not everyone can profit from it.
      In the mean-time, we can do better than just being frustrated.
      Let's say you're working on a medieval game. Several months ago, you implemented armor types for your game. You did a pretty damn good job and generated over 100MB of content.
      At some point, it was time to move on and right now you're working on something else, let's say sword fighting.
      Realize that, every time you press the play button to work on your features, you are loading an insane amount of data coming from all the already developed features, and loading this data takes a massive amount of time. You press play to test your sword fighting animations, and you spend 5 seconds waiting due to loading the armor features you implemented.
      The time wasted in loading is mostly spent on I/O (Input/Output), because memory bandwidth is expensive. And, on top of that, your CPU has to process it. You, as a developer, pay this time penalty while developing in the Unity Editor. But your players pay it as well in the games you are distributing.
      Knowing how big of a deal this can be, let's ask ourselves: which shortcuts can we take here?
      It turns out that Unity Addressables can help us here in two ways.
      1. Unity Addressables will reduce your Players' Loading Times
      We can alleviate some of our players' pain.
      Keeping indirect references to our assets instead of direct references will drastically improve your loading times.
      By using indirect references (AssetReference), Unity will not load everything at once but only what you tell it to. And more importantly, you have direct control over when that happens.
      2. Unity Addressables will reduce your Unity Editor Iteration Times
      How much do you know about the play mode script in the Unity Addressables Window? The play mode script defines how the Unity Editor should load the content marked as Addressable.
      With Packed Play Mode selected, Unity will directly load your pre-built addressable assets with little to no processing overhead, effectively reducing your Unity Editor iteration times
      Just do not forget to build the player content for this to work

      Unity Addressables - Build Player Content
      What if you applied these strategies to your most demanding content?
      4. Extra: Are You There Yet?
      It is true. Unity Addressables is very helpful. But this package will help only those who want to be helped.
      After reading how Addressables will help you producing better and selling more to your players, you probably want to start with it right away. However, starting in this new unknown area may be challenging.
      To make the most of your chance, answer these questions first:
      Where are you standing right now? Are you just starting, or are your skills production-ready? When to use indirect references, when to use direct references? What's the bigger picture? What is your next logical step? → Take this short quiz now to test your answers ← (opens in a new tab)

    • By Ruben Torres
      [This article was originally posted in The Gamedev Guru's Blog]
      You are leading a team of a handful of programmers and artists to port a good-looking PS4 VR game to Oculus Quest. You have six months to complete it. Well? What's your first move? Let's bring Unity Addressables to the table.
      You do realize you have to tackle quite many challenging tasks at once. I bet some might be personally more concerning than others, depending on your expertise level in each area. If you had to pick one that robbed your sacred sleep the most, which one would it be?
      My initial guess would be this: above 70% of the readers would say CPU/GPU performance is the biggest concern when porting a title to Quest. And to that I say: you can very well be right. Performance is one of the toughest areas to improve on in a VR game. For optimizations of this kind, you require in-depth knowledge about the product, which is a time intensive process. Sometimes you even cannot just optimize further, which usually ends in dropping expensive gameplay or graphics features. And not meeting people's expectations is a dangerous place to be.
      Performance, performance, performance.. The word might let some chills go down your spine. What can you expect in this regard from the Quest platform? How does it perform? The thing is, if you have had some development experience in it, you will probably know that in spite of being mobile hardware, it is astonishingly powerful.
      But Ruben! Don't give me that crap. I tell you my phone slows down significantly the time I open a second browser tab. How dare you say mobile platforms can be so performant?
      I read your mind, didn't I? The massive difference lies on Quest's active cooling system, which gives it a huge boost on its attainable CPU/GPU hardware levels that no other mobile platform can offer. It is a powerful fan that will prevent your hair from gathering dust and avoid melting the CPU together with your face (the GoT crown scene comes to mind).
      Additionally and on the side of the Quest software, the more specialized OS is better optimized for virtual reality rendering (surprise) than the generic Android variant. Mobile hardware has been catching up with standalone platforms so quickly in the last few years.
      But, at the same time, I cannot deny that our task of constantly rendering at 72 fps will prove to be challenging, especially for VR ports coming from high-end platforms. To be more precise, when we talk about the Oculus Quest, you have to picture yourself a Snapdragon 835 with a screen, a battery, four cameras and a fan.
      What could look like a disadvantage can actually be thought of as an edge. This mobile platform is a well researched piece of s*** hardware. One can say there are a myriad of known tricks you can pull off to quickly reduce the CPU and GPU load up to an acceptable point. If it is of your interest, you will be able to read about it in upcoming posts. As of now, we will take performance out of the equation for this post.
      What might catch your attention in our challenge is that, compared to the PS4, there is a single hardware characteristic literally halved on the Quest: the RAM capacity. That's right, we go from 8 to 4GB RAM. This is an approximation since, in both platforms, the operating system does not allow you to use it all so it can keep track of a few subsystems for the ecosystem to work. On the Quest you will be able to roughly use up to 2.2 GB of RAM before things get messy.
      Ruben, what do you exactly mean by messy? The thing is, proper memory handling is crucial for your game. This is so because you have two constraints:
      Hard memory constraint: if you go above a certain threshold, the OS will just kill your game Soft memory constraint: above another certain limit, the OS might decide to kill your game when your user minimizes your game, takes the headset off or you go out of the Oculus Guardian area Obviously, you do not want any of the two to happen in your game. Can you picture an angry player who just lost his last two hours of gameplay? Yes, they will go to your store and nothing pretty will come out of their mouth.

      Disgruntled Player - RUN!
      The thing is, the guaranteed availability of 2.2GB of RAM is not much, honestly. It's usually not a problem for new projects where you track your stats constantly from the beginning, but it definitely is an issue for a port to a severely downgraded hardware.
      If you dealt with similar ports in the past, you will quickly realize how extremely challenging it can become to decrease your game's RAM budget by half. It grandly depends on how well the game architecture was prepared for such a change, but in most cases this will temporally transform you into a tear-producing machine.
      The most popular strategies to reduce memory pressure include tweaking asset compression settings, optimizing scripts, reducing shader variants, etc.. Depending on the specifics of your project, tweaking texture import settings is your first go-to solution, but if you need to you can also resort to compressing meshes, animations and audio. The problem is that those techniques are usually complex in nature and will have a ceiling limit.
      Not all platforms support the same import settings; targeting several devices will dramatically increase your build pipeline overhead, not to mention QA, art, design and programming complexity. Does this Android device support ASTC, or just ETC2 (if at all)? Oh, we also want to build 64 bit builds, but also keep the players on the 32 bit versions. How many split-APKs should we create, and worse, manage and test, for each update we do on the game? You want to make your life easier, so you should not rely exclusively on these techniques.
      We would like to go further. As usual, we want to keep things as simple as possible (TM), especially if you are doing a port. Redesigning the entire game for performance's sake is a worse option than just not porting it. For that matter and in today’s topic, I will offer you one of the biggest gains for the buck: I will show you how to halve a project's memory budget in matter of hours. Boom!
      Wouldn't that be awesome?
      Go ahead, go ahead... ask me: is it really possible for me? The answer is: it depends on your starting point, but in my experience, YES. Unity Addressables can be of a great value here. The catch? You must be willing to put in the work and to master the process. But this workflow will earn you the title of employee of the month. 
      If you are interested, keep reading.
      In this post you and I will go through the journey of moving from a traditional asset management to an addressables-based asset management system. To illustrate the process,  we will port a simplified old-school project to the new era of Unity Addressables.
      Now, you might ask me: why don't you just show me the real-life work you did?
      In a non-competitive world I would just show you all the material I created. In the real world though, that is likely to get me canned. And worse, busted.
      What I will do instead is to offer you my guidance so you and I iterate on project that absolutely represents the difficulties you could find tomorrow in your next project. And we will do so by first welcoming Unity's Addressables to our family of suggested packages.
      In this blog post I will get you started in Addressables ASAP so you can implement your own Unity Addressables system in a matter of minutes.
       

      Unity Addressables: Why?
      Time to pay attention to this very important section. Our goal is to diagnose easy memory gains and implement them fast. There are several ways to do this, but one of the most powerful yet simplest methods to pick the low-hanging fruits by loading the initial scene and opening up the profiler. Why this?
      Because an unoptimized game architecture can frequently be diagnosed at any point during gameplay, so the quickest way to check this is by profiling the initial scenes. The reason for this is the common over-usage of singleton-like scripts containing references to every single asset in the project just in case you need it.
      In order words, in many games there is usually an almighty script causing an asset reference hell. This component keeps each asset loaded at all times independently from whether it's used or not at that time point.
      How bad is this?
      It depends. If your game is likely to be constrained by memory capacity, it is a very risky solution, as your game will not scale with the amount of assets you add (e.g. think of future DLCs). If you target heterogeneous devices, such as Android, you don't have a single memory budget; each device will offer a different one, so you settle for the worst case. The OS can decide to kill your app at any point if our user decides to answer a quick message in Facebook. Then the user comes back and surprise, all their game is gone for good.
      How fun is that?
      Zero. Unless you are overworked and sleep deprived, situation which might grant you a desperation laugh.
      To complicate matters further, if later on you decide (or someone decides for you) to port your game to another less powerful platform while keeping cross-play working, good luck. You don't want to get caught in the middle of this technical challenge.
      On the other side, is there a situation where this traditional asset management solution works just fine? The answer is yes. If you are developing it for a homogeneous platform such as PS4 and most requirements are set from the beginning, the benefits of global objects can potentially outweigh the extra added complexity of a better memory management system.
      Because let's face it: a plain, good old global object containing everything you need is a simple solution, if it works well enough for you. It will simplify your code and will also preload all your referenced assets.
      In any case, the traditional memory management approach is not acceptable for developers seeking to push the boundaries of the hardware. And as you are reading this, I take you want to level up your skills. So it is time for just doing that.
      Greet Unity Addressables.
       
      Requirements for our Unity Addressables project
      If you are planning on just reading this blog entry, your screen will suffice. Otherwise, if you want to do this along with me, you will need:
      Functional hands Overclocked brain Unity 2019.2.0f1 or similar The level 1 project from GitHub (download zip or through command line) Willingness to get your hands dirty with Unity Addressables The git repository will contain three commits, one per skill level-up section in the blog (unless I messed up at some point, case in which I will commit a fix).
       
      Download the project in ZIP format directly from GitHub
       

      Level 1 developer: Traditional asset management
      We are starting here with the simplest asset management method here. In our case, this entails having a list of direct references to skybox materials in our component.
      If you are doing this with me, the setup is a simple 3 step process:
      Download the project from git Open the project in Unity Hit the damn play button! Good, good. You can click a few buttons and change the skybox. This is so original... and boring. I take it, no Unity Addressables yet.
      In a short moment you and I will see why we need to endure this short-lasting boredom.
      To start with, how is our project structured? It pivots around two main systems. On the one side, we have our Manager game object. This component is the main script holding the references to the skybox materials and switches between them based on UI events. Easy enough.
      using UnityEngine; public class Manager : MonoBehaviour { [SerializeField] private Material[] _skyboxMaterials; public void SetSkybox(int skyboxIndex) { RenderSettings.skybox = _skyboxMaterials[skyboxIndex]; } } The Manager offers the UI system a function to apply a specific material to the scene settings through the usage of the RenderSettings API.
      Secondly, we have our CanvasSkyboxSelector. This game object contains a canvas component, rendering a a collection of vertically-distributed buttons. Each button, when clicked, will invoke the aforementioned Manager function to swap the rendered skybox based on the button id. Put in another way, each button's OnClick event calls the SetSkybox function on the Manager. Isn't that simple?
      Unity Addressables - Scene Hierarchy
      Once we're done daydreaming how immersive it was to play X2, it's time to get our hands dirty. Let's launch the multisensory experience and open the profiler (ctrl/cmd + 7; or Window - Analysis - Profiler). I take you are familiar with this tool, otherwise you know what to do with the top record button. After a few seconds of recording, stop it and see the metrics for yourself: CPU, memory, etc.. Anything of interest?

      Performance is pretty good, which is nothing surprising considering the scope of the project. You could literally turn this project into a VR experience and I assure you that your users will not fill any of the bile buckets that so many players filled when playing Eve: Valkyrie.

      In our case, we will be focusing on the memory section. The simple view mode will display something as depicted below:
      Level 1 Asset Management - Simple Memory Profiling
      The numbers on the texture size look pretty oversized for just displaying a single skybox at any given time, don't you agree? Surprise incoming: this is the pattern you will find in many unoptimized projects you are likely to suffer lead. But heck, in this case it's just a collection of skyboxes. In others, it will be more about characters, planets, sounds, music. You name it, I have it.
      If dealing with many assets falls under your responsibility, well, then I am glad you are reading this article. I will help you transitioning to scalable solution.
      Time for magic. Let's switch the memory profiler to detail mode. Have a look!
      Level 1 Asset Management - Detailed Memory Profiling
      Holy crap, what happened there? All skybox textures are loaded in memory, but only one is displayed at any given time. You see what we did? This rookie architecture produced the whoooooooping figure of 400mb.
      This is definitely a no-go, considering this is just a small piece of a future game. Addressing this very problem is the foundation for our next section.
      Come with me!
      Summary:
      Traditional asset management entails direct references Therefore you keep all objects loaded at all times Your project will not scale this way  
      Level 2 developer: Unity Addressables workflow
      In video- games you start at level 1, which is great, but once you know the gameplay rules it is time to leave the safe city walls in our quest to level up. That is exactly what this section is about.
      Grab the level 2 project now.
      As we previously saw in the profiler, we have all skyboxes loaded in memory even though only one is actively used. That is not a scalable solution, as at some point you will be limited on the amount of different variations of assets you can offer to your players. An advice? Don't limit the fun of your players.
      Here, let me help you. Take my shovel so we can dig the so needed tunnel to escape the prison of traditional asset management. Let's add a new fancy tool to our toolbox: the API of Unity Addressables.
      The first thing we need to do is to install the Addressables package. For that, go to Window → Package Manager, as shown below:

      Unity Package Manager - Unity Addressables
      Once installed, it's time to mark the materials as addressables. Select them and activate the addressables flag in the inspector window.
      Level 2 Asset Management (Unity Addressables)
      What this will do is to ask Unity politely to include those materials and their texture dependencies in the addressables database. This database will be used during our builds to pack the assets in chunks that can easily be loaded at any point during in our game.
      I'll show you something cool now. Open Window → Asset Management → Addressables. Guess what's that? It's our database screaming to go live!
      Level 2 Asset Management (Unity Addressables) - Main Window
      My dear reader: that was the easy part. Now comes the fun part.
      I want you to pay a visit to an old friend of ours from the previous section: Sir Manager. If you check it, you will notice it is still holding direct references to our assets! We don't want that.
      We are teaching our manager to use indirect references instead - i.e. AssetReference (in Unreal Engine you might know them as soft references).
      Let us do just that, let's beautify our component:
      using UnityEngine; using UnityEngine.AddressableAssets; using UnityEngine.ResourceManagement.AsyncOperations; public class Manager : MonoBehaviour { [SerializeField] private List<AssetReference> _skyboxMaterials; private AsyncOperationHandle _currentSkyboxMaterialOperationHandle; public void SetSkybox(int skyboxIndex) { StartCoroutine(SetSkyboxInternal(skyboxIndex)); } private IEnumerator SetSkyboxInternal(int skyboxIndex) { if (_currentSkyboxMaterialOperationHandle.IsValid()) { Addressables.Release(_currentSkyboxMaterialOperationHandle); } var skyboxMaterialReference = _skyboxMaterials[skyboxIndex]; _currentSkyboxMaterialOperationHandle = skyboxMaterialReference.LoadAssetAsync(); yield return _currentSkyboxMaterialOperationHandle; RenderSettings.skybox = _currentSkyboxMaterialOperationHandle.Result; } } What happens here is the following:
      A major change happens in line 7, where we hold a list of indirect references (AssetReference) instead of direct material references. This change is key, because these materials will NOT be loaded automatically just by being referenced. Their loading will have to be made explicit. Afterwards, please reassign the field in the editor. Line 13: since we are now in an asynchronous workflow, we favor the use of a coroutine. We simply start a new coroutine that will handle the skybox material change. We check in lines 18-20 whether we have an existing handle to a skybox material and, if so, we release the skybox we were previously rendering.  Every time we do such a load operation with the Addressables API, we receive a handle we should store for future operations. A handle is just a data structure containing data relevant to the management of a specific addressable asset. We resolve specific addressable reference to a skybox material in line 23 and then you call its LoadAssetAsync function, over which you can yield (line 25) so we wait for this operation to finish before proceeding further. Thanks to the usage of generics, there's no need for sucky casts. Neat! Finally, once the material and its dependencies have been loaded, we proceed to change the skybox of the scene in line 26. The material will be offered in the Result field that belongs to the handle we used to load it. Level 2 Asset Management (Unity Addressables) - AssetReference list
      Keep in mind: this code is not production-ready. Do not use it when programming an airplane. I decided to favor simplicity over robustness to keep the matter simple enough.
      Enough with explanations. It is time you and I saw this in action.
      If you would be so kind to perform the following steps:
      In the addressables window, cook the content (build player content) Then make a build on a platform of your choice Run it and connect the (memory) profiler to it. Protect your jaw from dropping.
      Level 2 (Unity Addressables) - Build Player Content
        Level 2 Asset Management (Unity Addressables) - Memory Profiler
          Isn't asset cooking delicious?
      I like happy profilers. And what you saw is the happiest profiler the world has ever seen. A satisfied profiler will mean several things. For one, it means happy players playing your game in a Nokia 3210. It also means happy producers. And as of you, it means a happy wallet.
      This is the power of the Addressables system.
      Addressables which comes with little overhead on the team. On the one side, programmers will have to support asynchronous workflows (easy-peasy with Coroutines). Also, designers will have to learn the possibilities of the system, e.g. addressable groups, and gather experience to make intelligent decisions. Finally, IT will be delighted to set up an infrastructure to deliver the assets over the network, if you opt to host them online.
      I have to congratulate you. Let me tell you what we have accomplished:
      Appropriate memory management. Faster initial loading times. Faster install times, reduced in-store app size. Higher device compatibility. Asynchronous architecture. Opening the door of storing this content online → decoupling data from code. I would be proud of such a gain. It's for sure a good return on investment.
      Oh, and make sure to mention your experience with Addressables in job interviews.
       
      INTERMEDIATE: Instancing and reference counting. Read on it my blog post for information on this topic.
      OPTIONAL: Alternative loading strategies. Read on it my blog post for information on this topic.
       
      Summary:
      Addressables-based asset management scales just well Addressables introduces asynchronous behavior Do not forget to cook content on changes or you'll give your game a pinkish tint!  

      Level 3 Asset Management (??) - Content Network Delivery
        Level 3 Asset Management (??) - Content Network Delivery
      In the previous section, we achieved the biggest bang for the buck. We leveled up our skills by moving from a traditional asset management system to an addressables-based workflow. This is a huge win for your project, as a small time investment gave your project the room to better scale in assets while keeping your memory usage low. That accomplishment indeed made you step up to level 2, congrats! However, one question is yet to answer:
      Is that it?
      No. We barely scratched the surface of Addressables, there are further ways to improve your project with this game-changer package.
      Of course, you do not have to memorize all the details regarding Addressables, but I highly suggest you to have an overview of them because down the road you are likely to encounter further challenges and you will be thankful to have read a bit further. That's why I prepared an extra short guide for you.
      There you will learn about the following aspects:
      The Addressables window: the details matter Addressables profiling: don't leak a (memory) leak ruin your day Network delivery: reduce the time-to-play user experience Build pipeline integration Practical strategies: speed up your workflow, trash your 10-minute coffee breaks  
      And more importantly, answer questions such as:
      What is the hidden meaning behind Send Profiler Events? How useful is the AddressableAssetSettings API? How do I integrate this all with the BuildPlayerWindow API? What's the difference between Fast Mode, Virtual Mode and Packed Mode? In order to grab the level 3 guide check out my blog post
    • By Ey-Lord
      Hello everyone

       
      I am here to gather your opinion, remarks, ideas or any constructive criticism you may have about what I am going to present. Don’t be shy!


       
      A bit of background:

      I am working alone on an indy web-based game, a simulation of RPG (idle game) where the player controls a group of 4 characters that he can sent into battle and that will fight automatically based on some AI preference that are similar to the FF 12 system (but more complex / powerful). He then earns some experience and resources that he can use to improve his unit’s gear, talents and skills. He has a lot of control on what skills his characters will use and how/when.


       
      What brings me here today:

      The AI of Monsters. I have the AI settings for players covered (basically a bunch of if/then/and/or/else settings that he can combine and order so that his units will act as he intends in battle). I’ve been working on the AI of monsters for quite some time, made a long break and came back recently to it.


       
      Short description of the battle system:

      No movement involved. Battle is fully automated. Players setup its units AI settings before battle and monsters are controlled by a separate AI. This is a 4v4 battle, like FF7 with some kind of ATB and any time a unit fill its ATB, it can play and the then the next unit who will fill it will play, etc. The player is completely free of his playstyle and may create very offensive group or very defensive ones. 4 healers or 4 tanks is completely possible.

      The battle system is very complex and allows for very varied and sometimes unusual strategies, like killing your own allies to proc an “on death buff” that will be devastating for the opponent.


       
      What I want for my AI?

      It needs to be fun to fight against and challenging. Ideally, I would like an AI as smart as possible (not omniscient but thinking as a human would). I know that a super-smart AI is not always the best way to make a game fun or challenging but in the context of my game, this is the result I want to achieve. It may seem unfair to have the AI try to kill your squishy while your tank is standing right there but my class design gives the tools to players to counter that so it’s not an issue (tanks are not purely aggro based for example). I want players to always be challenged by AI moves and that they must carefully think about their strategy because if they leave a big hole in it, I want the AI to exploit it.

      In practice, it means a few requirements:

      No dumb decision / do not fall into obvious player’s traps Exploit obvious flaws of the opponent Act in coordination when appropriate with other units Able to find who should be their focus in the player’s team (some notion of threat) Find the best move to use and if there is some kind of combo possible, use it

      These requirements are harder to meet than it looks. The issue is the sheer number of different mechanisms and strategies available to players and to monsters as well. For example, there are many cases where killing or attacking a player unit might be detrimental (units that return damages or that gain power when you hit then for example).


       
      What I have tried before?

      I have tried or at least reviewed many different AI concepts so far.

      -          A simple copy of my player’s AI system (hierarchical if/then/else). It was easy to script as I already have the UI in place for players so I can quickly define a basic AI for any new monster’s group. The main drawbacks are that it needs to be written for every monster group, it does not allow smart targeting and cannot find the best target or the best skill to use. It will also make dumbs decision as the targeting options cannot assess threats at all.

                I’ve rules out planners since for purely selecting the best pair of (skill, target), they do not seem to match my needs.           (H)FSM or BT does not seems to match my needs as monsters do not have states / transition condition that can lead to something useful for me.        I’ve ruled out aNNs as they might, with proper training, be able to find the best action at a given time but it’s very tedious to implement and will not solve my need of finding combo or coordinating with other units very well. (plus, let’s be honest, I’d be a bit out of my depth to program them)           I have spent an extensive period of time trying with tree searches. Mainly: monte-carlo with random sampling and came to the conclusion that due to the complexity of my battle system, it is excessively costly to compute any kind of reliable data this way.
      -        My current AI system is a version of my first one (the same as the players) but with access to some “smarter” targeting function that in theory allow to choose the best target. These functions work by gathering data for thousands of simulated fights during the AI time to play (1 second). It’s a first step to find the best target but not very accurate (lots of big flaws that can be exploited by players) and it is very time consuming and that is something I’m trying to get away from. I do not want to use 100% of the players CPU as I do now.


       
      What is my latest idea?

      I started to study more in-depth the Utility theory as described by Dave Marks (I read his book and watched his GDC AI lectures as well). I liked the idea. I like that I can start on something relatively simple and add more considerations as things progress to handle more and more situations. While my work began as something very close to utility theory, it evolved a bit afterward. Here is what I plan on doing to compute a unit’s best course of action:


       
      A – Score every of its move (each move is a pair [skill, target]).

      B – Chose the move according to a selection strategy (highest score, weighted random, random amongst the top scores… lots of different selection algorithm can be used there).


       
      So far, easy, right? Let’s dig deeper into our first phase of scoring (A), which is the hard part. For all the damage or healing skills:


      Step 1: The final scoring of the move [skill,target] will be function of the a “Survival” scoring for the player team and for the enemy team. An example of this relationship could be: Adding all the survival scores of each unit in Team A and divide the result by the addition of all the survival scores for each unit in team B.

      Step 2: The survival score of each unit will be its Health after the move we are evaluating, divided by the total damage per turn that we estimate other units can deal to her (minus the total heal it ca receive). [This a step where we can process damage and heal over time as well]

      Step 3: This damage per turn estimation will be, initially, the sum for every unit in battle of the damage or heal per second it can deal to that unit. For example: If I’m alone vs 2 bad guy that can deal 1 dmg/turn and if I can deal 1 heal/turn, the damage per turn estimation against me will be 2-1 = 1. [This is not optimal since we are counting the damage of each unit once per enemy unit but it’s a start]

      Step 4: To compute the DPS or HPS of each unit, we review the unit’s skills and compute their output against the unit we want to evaluate it against. From that, we construct a skill sequence to maximize the damage output and once we got the optimal skill sequence, we can compute its DPS or HPS output and pass it along for Step 3.


       
      It might seem like a lot of work, since, in a world with only damage or healing skills, the DPS or HPS sequence of each unit will be the same in every situation and as such only the damage done or healing done by the skill evaluated would be enough. But…


       
      The tricky part comes from buffs and debuffs. If we use the above algorithm, (de)buffs that changes the damage or healing someone does or receive will be evaluated correctly as it will change the damage or heal per second output of units and it would affect the survival score and the final scoring. That is why I chose to include DPS and HPS computations for each unit for each move.


       
      This is all fine until we consider (de)buffs that changes the power of other (de)buffs. Like: I cast a buff that double the length of all my future buffs. My algorithm can’t evaluate it correctly. It’s a situation that will be common enough in my game and I want my AI to deal with it. Note: there are more complex situations where a unit could buff a buff that buffs a buff that buff a buff [….] that will end-up buffing a damage or healing skills, but those cases will not be addressed as they will hopefully be rare and too cumbersome to compute anyway.


       
      So, my goal is to score properly buffs that: 

            Buffs the damage or healing output of someone           Buffs that buffs a skill that does the above

       
      L    Long story short of how I am doing that. I’m using my initial algorithm but while also estimating damage or healing per second change for each dps or hps sequence.To do that I’m evaluating every move of the unit (or every unit in case of AoE but lets keep it simple with single target) that is targeted by the buff. So, we are switching PoV here compared to the initial unit we are evaluating (unless the move evaluated is buffing itself)

      -          I’m doing the above in 2 situations:

      o   A : After a cast of the buff skill I’m evaluating

      o   B : Without the cast of the buff, just like if it was that unit’s turn to play

      -          Using a sort of min/max approach: if the unit targeted by the buff is an ally, we will take the best branch of our tree in A and compare it with the same branch (pair [skill,target]) in B. If the unit targeted by the buff is an enemy, we want to lower their maximum score and will select the tree branch that does that in A to also compare it with the same branch in B.

      -          The information we extract here are DPS or HPS delta for each sequence of DPS/HPS for each unit vs each other unit.

      -          Then, we go back to our steps 1 to 5 and compute our scoring for the move (buff) while using our new dps/hps deltas to get better and more accurate dps/hps sequence for units affected by the buff.


       
      This is basically it. I’ve ran a manual version of the algorithm in 2 different battle settings to test it and see if it gave good results. It worked. Not flawlessly but it worked. Lots of cases will still require tweak and additions to the basic idea but I think its promising. (taunts and CCs are not easy to deal with but it’s manageable)


       
      What I like is that I can add more considerations later (as in the utility theory) like: resource cost, general unit strategy (cleave or focus), behavior (careful, lunatic, reckless). While this will still be a bit time consuming it should be a good order of magnitude faster than my current AI. It also does not prevent me from adding hardcoded AI move if I want to “script” more some monsters. Debugging and tweaking might be a bit painful though, especially when fights will involve lots of skills & stats but that’s an issue that most AI for my game would likely have anyway.


       
      To come back with my initial goals:

              No dumb decision / do not fall into obvious player’s traps
      o   Not perfect but it should choose the best target whenever possible

                 Exploit obvious flaws of the opponent
      o   Same as above

              Act in coordination when appropriate with other units
      o   This can be done simply by adding weight to some targets or computing moves for all units of a group before deciding which one to take (for example to take the best move vs a specific unit, on average)

             Able to find who should be their focus in the player’s team (some notion of threat)
      o   It will naturally focus the unit who is the easiest to kill and debuff or CC the ones that deal the more heal/damage. But, to better solve this, we will need to add other considerations to the AI scoring process, It should not be *too* hard    

            Find the best move to use and if there is some kind of combo possible, use it
      o   Combo are very often in the form of buff/debuff setup before an actual damaging or healing skills and my AI can compute up to a 3 moves combo (buff > buff > skill that dmg or heal) which should cover most cases.


       
      I’m quite happy with my initial tests. I’m not going to be coding it now. My goal was to reflect on the subject on paper and try to see if designing my AI would be a roadblock or not for my project. There are a few other area I want to design and take time to really think about before getting back to my project full time. I’d love to hear your toughs and feedbacks about my AI ideas. Do you see huge roadblocks I’m missing? Does it sound ok to you?

      If you read that far…. thank you and I can"t wait to hear from you guys😊

    • By Sword7
      I googled for terrain collisions but found only some sources about flat worlds.   I want collision detection for spherical terrain worlds.   I have "3D Engine Design for Virtual Globe" book but it did not mention any algorithms about collision detection for landing, rolling, walking, crashing, etc...   Does anyone have any good sources for spherical terrain collision detection?
    • By bzt
      Hi guys,
       
      I've an OpenGL question, which is quite math ad linear algebra related.
      Let's assume we have two coordinate systems, S (scene) and O (object). I'd like to place O inside S, so I need O' (in S coordinates). Using the following transformation matrices I can do that: rotation, scale, displacement. So far so good. I have two questions though:
       
      1) assuming the place of O' is specified with 4 points (zerus, and one for each axii unit vector end points) how can I calculate the required transformation matrices?
      It's a "simple" case, as let's say points are P0, P1, P2, P3 and x = P0->P1, y = P0->P2, z = P0->P3. Also |x| = |y| = |z| (all has the same length) and they enclose 90 degree with each other. This surely can be solved using standard GL transformations easily, I just need an algorithm to calculate the matrices from P0, P1, P2, P3.
       
      2) the more difficult question, how can I do the same if O' can be distorted, so |x| != |y| != |z| and their angle is not necessarily 90 degree? (Imagine that you "sit" on O, so O' became stretched and it's top became larger and moved to the side, so that angle(x, y) = 80 degree for example). How to get the required transformation matrices in this universal case, when you only know P0, P1, P2, P3?
       
      Hope it's clear what I'm asking. I need an algorithm to generate a transformation matrix that I can then use to transform all points in O into O'.
      bzt
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!