Octree

[Don]

I see that there's not a consensus about

whether an octree is The Way, but if the dev manager likes it I'm willing

to go forward. I have some questions about what I'd be delivering.

* I understand there are several different uses for an octree, including

graphical rendering, route finding, and so on. That suggests the best

interface is a pretty low-level one, e.g., I create an object of type

Octree and then just treat it as a sparse array in three dimensions. Is

that how you want to use it, or are there some operations (find a certain

value? copy? prune off everything under a certain node?) that are going to

be needed frequently enough to build it in?

* What data types are likely to be stored in the nodes?

* I've found an open source templated octree class. Maybe this project is

already done, or maybe this implementation I've found is too slow. Can you

suggest what operation(s) need to be especially quick for our purposes?

Don

[RedFox]

I see that there's not a consensus about

whether an octree is The Way, but if the dev manager likes it I'm willing

to go forward. I have some questions about what I'd be delivering.

First thing I'd like to point out is that 0 A.D. does not need an Octree (a 3-dimensional space partitioning structure). It needs a Quadtree (a 2-dimensional space partitioning structure). The position values in the Quadtree would still be stored as Vector3 values.

* I understand there are several different uses for an octree, including

graphical rendering, route finding, and so on. That suggests the best

interface is a pretty low-level one, e.g., I create an object of type

Octree and then just treat it as a sparse array in three dimensions. Is

that how you want to use it, or are there some operations (find a certain

value? copy? prune off everything under a certain node?) that are going to

be needed frequently enough to build it in?

A quadtree can be used for:

-) Efficient collision detection - you minimize the amount of collision checks by only checking objects in a single quadtree node.

-) Efficient pathfinding - you can minimize the number of grids checked by A* if you use a quadtree (

). Bigger cells have bigger movement cost values, so it works very well for long-range and short-range pathfinding.

-) Range detection - you can easily get a small list of objects close to you just by checking the neighbouring cells.

-) Culling - its very easy to cull your world with a quadtree. You only need to compare the frustrum against the quadtree once. Right now 0 A.D. compares the viewing frustrum against all objects in the world.

* What data types are likely to be stored in the nodes?

-) A Quadtree cell should contain a singly linked-list structure that contains pointers to a generic "GameObject". This greatly speeds up add/remove/create on the cells.

The "GameObject" itself should contain Position.xyz, Radius, BoundingBox - everything needed for interactions between objects.

* I've found an open source templated octree class. Maybe this project is

already done, or maybe this implementation I've found is too slow. Can you

suggest what operation(s) need to be especially quick for our purposes?

A Quadtree is actually a very simple structure and in the best interest of speed, it should use a custom variant, with a Cell allocation memory pool and a Listnode allocation memory pool. Otherwise the amount of new/delete would cripple the implementation.

[Don]

I don't feel strongly either way about quad- versus octree. There's a strong efficiency argument for the quadtree, and there's a strong argument that an octree will allow us more realistic 3d modeling of the game world. I, for one, want to be able to fire arrows down from a highway overpass as my enemy marches underneath, but that probably won't happen any time soon. Perhaps I'll add a compile-time flag that turns the third dimension on and off, so my code is still useful after the argument is decided.

Building an object pool sounds like a good idea, and a good enough reason for a custom implementation.

Just so we're clear, you want an efficient sparse array, and all the culling, range finding, etc happens in other code, correct?

[scroogie]

I don't feel strongly either way about quad- versus octree. There's a strong efficiency argument for the quadtree, and there's a strong argument that an octree will allow us more realistic 3d modeling of the game world. I, for one, want to be able to fire arrows down from a highway overpass as my enemy marches underneath, but that probably won't happen any time soon. Perhaps I'll add a compile-time flag that turns the third dimension on and off, so my code is still useful after the argument is decided.

This is a misconception that I tried to clarify in the other thread. Using a Quadtree absolutely does not rule out stuff as this. You can have units flying as high as you want with Quadtrees, even having thousands of units on top of each other. It just won't give you the same speedup for the Z axis. Using a Quad/Octree does not mean that you do not compare locations at all any more. It just means that you compare much less positions, as you can rule out the majority through the subdivison (you know they are not close enough). With only a quadtree, you'd have to compare all unit positions of units that are above each other, while with an octree you save most of the comparisons due to the subdivision.

About the implementation, I'd just start with a loose quadtree as described in GPG, with just the basic methods, and then as people figure out where and how to use it, more will be added later.

[quantumstate]

With the quadtree you lose efficiency when height is added since you need to search a larger area. Significant uses in our game are for culling what will be rendered and detecting units under the cursor for mouseover and selection. These are both 3d operations, 2d spatial filtering for gameplay already exists in CCmpRangeManager and the slowness here is not due to the spatial data structure at the moment. So the argument for using an octree is that it should be more efficient for the '3D' operations I mentioned since it will be able to filter out more stuff. It is hard to say which will actually be faster in practice though.

[RedFox]

With the quadtree you lose efficiency when height is added since you need to search a larger area. Significant uses in our game are for culling what will be rendered and detecting units under the cursor for mouseover and selection. These are both 3d operations, 2d spatial filtering for gameplay already exists in CCmpRangeManager and the slowness here is not due to the spatial data structure at the moment.

I think that is incorrect. 0 A.D. uses a fixed-size subdivision implementation, which becomes very slow when a lot of units are in a small area. If a lot of these units are in a single area, they still generate a lot of range comparison complexity.

A proper quadtree implementation would allow dynamic and more precise subdivision of those areas, thus decreasing the amount of checks required even if a large number of entities are in a relatively small space.

Using an octree would provide no speed bonus in this area, since this is not an FPS where units can exist in different rooms and different heights. Adding an extra dimension would just slow down the algorithm, since each octree node will require +4 pointers and will generate +4 subnodes - if compared to a quadtree.

[Don]

... A proper quadtree implementation would allow dynamic and more precise subdivision of those areas, thus decreasing the amount of checks required even if a large number of entities are in a relatively small space.

Please elaborate on this. I understood the oct- or quadtree would be functioning as a sparse array, with a single cell at (x,y,z) corresponding to one leaf node in the tree and one "game object." But you make it sound as if you'd like to be able to subdivide the space further at runtime.

[Don]

For consistency, what would be the best source code directory for the octree code? I thought lib at first, but it seems special in some way.

[RedFox]

Please elaborate on this. I understood the oct- or quadtree would be functioning as a sparse array, with a single cell at (x,y,z) corresponding to one leaf node in the tree and one "game object." But you make it sound as if you'd like to be able to subdivide the space further at runtime.

Each Quadtree/Octree node should have a predefine attribute 'MaxObjects', which can be, for example 4. If the number of objects per node grows larger than that, the node is sub-divided into 4 cells. This is known as an 'adaptive Quadtree/Octree'. Typically it performs better due to less Nodes.

An unadaptive Quadtree/Octree works by dividing up to 'max levels'. This may or may not work better, depending on the nature of data. For a collision/range Quadtree of units, an adaptive Quadtree would work better in cases where a lot of units are in a very small area. Whereas an unadaptive Quadtree would have better tree performance, but suffers if you have a lot of units in a small area.

As for actual nodes themselves, they can be anything, really. For example they can be Entity structures that contain 3D position data. That's why you can calculate the correct ranges in 3 dimensions with a Quadtree and why we'd never need an Octree.

Edited June 20, 2013 by RedFox

[Don]

For a collision/range Quadtree of units, an adaptive Quadtree would work better in cases where a lot of units are in a very small area.

I understand how an adaptive tree would have fewer units per node. I don't think I get how that would save me work in detecting a collision. If I want to move a unit a step forward, surely I have to calculate whether it will collide with any nearby unit, yes? If there are many nearby units and they are scattered among several nodes, how is the calculation easier than if they are all in one node? If there are n units near me, it's O(n) either way, isn't it?

To put the same confusion a different way: I thought the quad- or octree is supposed to act like a sparse array with one cell for each atomic point on the map. Maybe that's my mistaken assumption.

"I'm telling you this because you don't get it, you think you get it, which isn't the same as actually getting it. Get it?"

At least I'm not suffering from the delusion that I get it.

[RedFox]

I understand how an adaptive tree would have fewer units per node. I don't think I get how that would save me work in detecting a collision. If I want to move a unit a step forward, surely I have to calculate whether it will collide with any nearby unit, yes? If there are many nearby units and they are scattered among several nodes, how is the calculation easier than if they are all in one node? If there are n units near me, it's O(n) either way, isn't it?

To put the same confusion a different way: I thought the quad- or octree is supposed to act like a sparse array with one cell for each atomic point on the map. Maybe that's my mistaken assumption.

A quadtree is just a tree structure in itself and isn't anything special. It's how you use it and especially how you specialize it.

If you simply implemented a quadtree and put a bunch of objects in a Q-node, you still don't have anything useful. However, if you store the pointer to the Q-node inside the object too - you'll get something you can use effectively:

struct Object
{
	QNode* node; // this is NULL if not in quadtree, or a valid pointer to a quadtree node
	Vecor3 pos; // 3d position of this gameobject

	/**
	 * Checks if this Object collides with anything and calls the specified collisionFunc
	 */
	void CheckCollision(void (*collisionFunc)(Object* a, Object* , float collisionRange)
	{
		collisionRange *= collisionRange; // pow2(collisionRange)
		for(Object* o : node->children)
		{
			if(o == this)
				continue; // ignore this object

			// is it in range?
			if(pos.SquaredDistance(o->pos) <= collisionRange)
				collisionFunc(a, ;   // trigger collision
		}
	}
};

An important aspect of this approach is that you first move the objects and then check for collisions. According to the collision events you modify the path/position. Then you move on to the next frame.

At least I'm not suffering from the delusion that I get it.

Haha, , don't worry, Quadtree is just a very versatile structure and can be used in many, many ways. For example in pathfinding to reduce the number of grids dynamically:

Edited June 20, 2013 by RedFox

[Don]

I'm reworking the tree along the lines you've described---though I will be hiding the details of the tree implementation from the game object. It should be possible to call a method on the game object that returns all the nearby game objects. And unless I (still) misunderstand, "nearby" is approximately "contained in my sibling nodes in the tree."

[RedFox]

A reason to not hide the implementation is a performance consideration. If you add a method std::vector<Object*> QNode::GetChildren(), you'll get a huge performance penalty due to full vector copy.

Consider writing an iterator function instead:

template<class Lambda> inline void ForEachChild(Lambda func)
{
	for(Object* o : mObjects)
		func(o);
}

// to use it:
node->ForEachChild( [&](Object* o) {
	if( o == this ) return;
	if(pos.SquaredDistance(o->pos) <= collisionRange)
		 collisionFunc(this, o);
});

But now that I think about it, a more efficient solution might be to leave the collision checking to the Quadtree structure itself. This would make more sense I think.

void QNode::CheckRange(void (*rangeFunc)(Object* a, Object* , float range)
{
	int jcount = mObjects.size();
	int icount = jcount - 1;
	for(int i = 0; i < icount; i++)
	{
		for(int j = i + 1; j < jcount; j++)
		{
			Object* a = mObjects[i], *b = mObjects[j];
			if(RangeCheck(a, b, range)
				rangeFunc(a, ;
		}
	}
}

Or perhaps an unrolled version for a single node if you know the max number of children is 4:

void QNode::CheckRange(void (*rangeFunc)(Object* a, Object* , float range)
{
	// in this case objects is defined as "Object* objects[4];"
	// so we can use indexes without any fear of operator[]
	// also, a way of checking the number of objects should be added.
	// right now I just assume RangeCheck handles that.
	if(RangeCheck(objects[0], objects[1], range)) rangeFunc(objects[0], objects[1]);
	if(RangeCheck(objects[0], objects[2], range)) rangeFunc(objects[0], objects[2]);
	if(RangeCheck(objects[0], objects[3], range)) rangeFunc(objects[0], objects[3]);
	if(RangeCheck(objects[1], objects[2], range)) rangeFunc(objects[1], objects[2]);
	if(RangeCheck(objects[1], objects[3], range)) rangeFunc(objects[1], objects[3]);
	if(RangeCheck(objects[2], objects[3], range)) rangeFunc(objects[2], objects[3]);
}

The unrolled version should be a lot faster. If you combine this with walking through nearby nodes and the lambda method, you'll never even need to pass temporary vector objects. This way you'll take full advantage of what a Quadtree offers. Avoid using std::vector at all cost. It's too heavy object for this structure. You would have thousands of QNodes and thus thousands of std::vectors - very bad performance.

Edited June 21, 2013 by RedFox

[Don]

I take your point about copying a vector. It would be slightly less of a problem for a vector of pointers, perhaps, but it would be good to avoid altogether.

But you give me a better idea. Given a unit U we would like to move:

• We (will) know the node N that contains the unit.
  
• Get the node P that is the parent of N. (Or the grandparent or higher, depends on the situation.)
  
• Traverse P. For each node under P, for each game object in that node,
  
• Call a function in the game object that calculates range to U.
  

This eliminates the need to create a big vector of (pointers to) game objects and return them. And it permits us to keep the code for the tree and the game object in separate modules.

But of course talk is cheap when I haven't delivered any code yet.

[RedFox]

I take your point about copying a vector. It would be slightly less of a problem for a vector of pointers, perhaps, but it would be good to avoid altogether.

But you give me a better idea. Given a unit U we would like to move:

• We (will) know the node N that contains the unit.
  
• Get the node P that is the parent of N. (Or the grandparent or higher, depends on the situation.)
  
• Traverse P. For each node under P, for each game object in that node,
  
• Call a function in the game object that calculates range to U.
  

This eliminates the need to create a big vector of (pointers to) game objects and return them. And it permits us to keep the code for the tree and the game object in separate modules.

But of course talk is cheap when I haven't delivered any code yet.

Exactly! We're on the same page now. That's exactly what I was thinking about when writing those snippets. You never really need to create any vectors - just traverse the QTree and invoke the function on any range matches.

Can't wait to see what you come up with.

[Don]

http://trac.wildfiregames.com/ticket/2016

I implemented a quadtree and submitted a patch. If the reviewers like it, I'll change a few lines and submit an octree as well, then the quadtree and octree supporters can duke it out among themselves.

After trying a few different ways of hiding the game object's implementation from the tree, I compromised. The tree class is a friend to the game object class, and has access to a few private member variables in the game object. Each game object knows the address of its own tree node.

The tree starts out with a single node. As game objects are added, levels are added to the tree to keep the number of objects per node below MAX_OBJECTS. After game objects are deleted, there is the option to traverse the tree and prune unneeded levels.

The implementation of the memory pool is not as simple as I'd like, but it does avoid memory fragmentation.

I'll be curious to see the feedback.

[RedFox]

Awesome work Don. Very good job implementing a generic Quadtree class

I have only a few remarks:

• Memory pool implementation. We have been working on a general solution for 0 A.D. already that doesn't require fixing pointers if the pool is out of memory. Furthermore it's not reusing pointers so there is always a realloc imminent, which is not ideal for a memory pool. Check out the thread: [Discuss] Memory aka game slowing over time.
  Right now it's pretty much finished, but it hasn't been put into the engine yet. Perhaps this is something that can be improved in the future? It would definitely make the code even simpler. Kudos on implementing a memory pool though - that's very important for a Quadtree
  
• You are correct that an integer implementation of a Quadtree has to be in power-of-two size. However, you check [size % 2 == 0]. Consider the case [14 % 2 == 0]; and 14 is not a power of two You should do a proper pow2 check: http://graphics.stan...rmineIfPowerOf2
  
• I know that having a 2D array m_Child[2][2] seems like a good idea, but for a Quadtree the preferred solution is to have 4 variables: NW, NE, SW, SE. Why? This lets us unroll the loops and actually speeds up the code a lot. However I can see that you designed it because you wanted to later be able to use an Octree.
  
• I like how you calculate the child index, that way you have a constant search speed.
  
• Again kudos for not using an std::vector for children. That solution seems to permeate most implementations and is very bad for performance. The MAX_CHILDREN approach is the best one.
  

Again, good work I'll be looking forward to what others also think of this.

Edited June 30, 2013 by RedFox

[Don]

I did follow that thread on your shiny new memory pool class. Once yours is part of the engine, I'll happily use it in the quadtree. The fact that yours doesn't require fixing pointers will allow me to eliminate several lines of code and clean up some needless complexity.

I considered ripping out that assert(), since it's usually considered bad form to leave an assert in production code. But if asserts are OK in 0ad, yes it should check to see that size is indeed a power of two.

There's at least one horrible bug that I realized was there after I submitted the patch, which I'll clean up in the next iteration. Wrote myself a note about it, put it on my desk, now can't find the note (and I can barely find the desk).

[wraitii]

I'm going to try a new format for the spatial subdivisions which would remove the need for uniqueness sorting, potentially improving efficiency.

Basically it's like spatial subdivisions but subdivisions would be a lot smaller ( like about a big bigger than a building footprint, so that most entities boundaries are smaller than a single subdivisions). You only add entities to the subdivisions their center is in, and when you range-query you return the subdivisions around your query too (see schema) sp that you're sure to get it.

Entities that are too big would not be put in the subdivisions but at the basic level, so all entities would be considered "close" to all other entities. If we can manage to have few enough of those, this should work well.

On the schema, the black lines are subdivision limits, the red square the range query, and the reddened squares are what would be returned by the existing query system, which needs to be sorted for uniqueness, while my method would also return the green squares, but won't sort.

So maybe that'll be faster, maybe it won't be, we'll see. My hope is that if we make subdivisions just bigger than most item bounds, we'll have small subdivisions so we wouldn't add too many items, yet it'll be quite efficient since it's still all vectors and mostly static, and we won't have to worry about doubles and stuff like that which would allow faster queries. Maybe.