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?