Download

Massive Memory Leak in my Quadtree, but only with > 3 players?

In my recent endeavors I’ve written a Quadtree system for my project in Unreal, which is pretty much self-managing. At the moment, I’m updating the position of each object in the tree per-tick just for the purposes of testing and whatever, but I plan to have the objects update the tree as and when they move to minimize processing power and essentially doing a full object-iterator every frame.

It works practically perfectly in single player, and again with two players in the world as well (multiplayer, server/client). As soon as a third client joins in, my UObject count starts sky rocketing into the several-millions. The issue is definitely causes by the Quadtree, probably an excessive creation of Quadtree nodes (it keeps splitting into four recursively). I could just limit the amount of children allowed in the tree, but there’s clearly a more fundamental issue with it that I need some help with.

The tree is in two parts. A Manager class which is created by the GameInstance on Init(), creates and manages the tree. In the master tree object, I have a big long list of every object in the tree, which I iterate over and tell the tree to update for each object (probably better to have each node manage itself but w/e - still early days). The tree then creates TreeNodes which actually store the objects, and any child nodes they may have.

Here’s some code to ponder over. The ‘UpdateObjectPosition’ first figures out if it’s a leaf node (i.e., no children), and if not passes it down the chain until it is. When it gets there, it checks if an object belongs in there and if it already exists, if not, add to the node. If it doesn’t belong there and it is there, remove it. If it belongs there and it’s already there, skip it. You get the idea. Obviously this is a pretty brutal way to manage the tree itself, but I’m out of ideas at the moment.

The problem seems to be caused somewhere here. It’s constantly adding the objects to the node which is causing it to split and create literally millions of child-nodes. I’ve attached all the code I think is relevant, but I’m fairly convinced this is what it is. UBZGame_GameObjectComponents are just ActorComponents, the GetOwnerLocation() is an inline that points to ‘GetActorLocation()’ of the owner. I didn’t want all the overhead of a Scene Component just for data storage…

BZGame_GOCTreeNode.cpp



void UBZGame_GOCTreeNode::AddObject(UBZGame_GameObjectComponent* ObjectToAdd)
{
	/* If Children, Pass down to them */
	if (Children[0] != NULL)
	{
		for (UBZGame_GOCTreeNode* ChildItr : Children)
		{
			if (ChildItr->ObjectBelongsInThisNode(ObjectToAdd->GetOwnerLocation().X, ObjectToAdd->GetOwnerLocation().Y))
			{
				ChildItr->AddObject(ObjectToAdd);
				return;
			}
		}
	}
	else
	{
		AddObjectToThisNode(ObjectToAdd);
		return;
	}
}

void UBZGame_GOCTreeNode::AddObjectToThisNode(UBZGame_GameObjectComponent* ObjectToAdd)
{
	/* Iterate over the NodeObjects (Because NodeObjects is static size), Check for NULL */
	for (int32 i = 0; i < MAX_OBJECTS_PER_NODE; i++)
	{
		if (NodeObjects* == NULL)
		{
			NodeObjects* = ObjectToAdd;
			return;
		}
	}
	
	/* Otherwise if we've reached the limit, create children */
	if (Children[0] == NULL)
	{
		CreateChildrenForThisNode();
		AddObject(ObjectToAdd);
	}
}

int32 UBZGame_GOCTreeNode::NumElementsInTree()
{
	int32 NumElements = 0;

	if (IsLeaf())
	{
		for (int32 i = 0; i < MAX_OBJECTS_PER_NODE; i++)
		{
			if (NodeObjects* != NULL)
			{
				NumElements++;
			}
		}

		return NumElements;
	}
	else
	{
		for (int32 i = 0; i < 4; i++)
		{
			NumElements += Children*->NumElementsInTree();
		}

		return NumElements;
	}
}

void UBZGame_GOCTreeNode::UpdateObjectPosition(UBZGame_GameObjectComponent* ObjectToUpdate)
{
	/* Go to children if I'm not the leaf node */
	if (Children[0] != NULL)
	{
		for (UBZGame_GOCTreeNode* ChildItr : Children)
		{
			ChildItr->UpdateObjectPosition(ObjectToUpdate);
		}

		TryToCollapse();
	}

	/* If I'm the Leaf Node */
	else
	{
		/* Check to see if object belongs in this node, and if it doesn't exist, add it */
		if (ObjectBelongsInThisNode(ObjectToUpdate->GetOwnerLocation().X, ObjectToUpdate->GetOwnerLocation().Y))
		{
			bool bAlreadyExists = false;

			/* Object belongs here, but is it already in the list? */
			for (UBZGame_GameObjectComponent* ObjectItr : NodeObjects)
			{
				if (ObjectItr == ObjectToUpdate)
				{
					bAlreadyExists = true;
					break;
				}
			}

			/* If it's not here, Add object */
			if (!bAlreadyExists)
			{
				AddObjectToThisNode(ObjectToUpdate);
				return;
			}
		}
		else
		{
			/* Else, if it's not meant to be in this node, remove it */
			for (UBZGame_GameObjectComponent* ObjectItr : NodeObjects)
			{
				if (ObjectItr == ObjectToUpdate)
				{
					Remove(ObjectToUpdate);
					return;
				}
			}
		}
	}
}


What I don’t understand is why the Object count only sky rockets when there are 3 clients in the game? They should have their own Quadtrees and their own GameInstances both in PIE and Standalone, but the client is definitely changing the Servers’ quadtree as well.

Soo… any ideas before I write off quadtrees and do Spatial Hashing instead?

Small update on this, I think the problem lies with my MAX_OBJECTS_PER_NODE being set to 2 temporarily. The problem is that changing that value isn’t going to help me, because when 10 players join I’ll have the same problem etc.

I feel as though this is something to do with the way GameInstances are created in PIE… anybody have any further reading on this?

Did you try outside of PIE as well?

When you AddObjectToThisNode and you’ve already reached MAX_OBJECTS_PER_NODE and then call CreateChildrenForThisNode and AddObject it seems that you are not moving the elements in NodeObjects in this node to the appropriate children unless that’s part of the CreateChildrenForThisNode function? This may be intended but on the other hand NumElementsInTree doesn’t seem to reflect that since even if a node has elements in NodeObjects and also has Children, only objects in the children count towards the result, while those in NodeObjects are ignored.
If you aren’t moving the elements in NodeObjects to the children this can cause problems down the line unless the case is handled. However most of the time you seem to be checking against Children[0] being NULL or not. Also causing problems in UpdateObjectPosition.

You could try to look at the GenericOctree(.h/.inl) implementation in the engine and potentially just use that (ignoring the third dimension) or learn from Epic’s implementation.

Hope this helps.

I’ve figured out exactly what the problem is… I shall explain.

So the Manager system that I pinched basically creates a Singleton, so although there are instances for each PIE instance there is only one Manager and therefore only one Quadtree. However the Quadtree is being updated from all three instances. Each instance has a copy of each object which it’s telling the Quadtree to update, and seeing as there are three instances they are constantly overriding each other and splitting into more and more nodes.

So, it’s not so much a problem with my tree (thank god), but more a caveat of the Manager system I’ve created. What I’ll have to do is create the Manager differently so it’ll run properly in PIE and standalone (though Standalone should work regardless).