A data structure based on the R-Tree: creating new child nodes when a node is full, but what if I have a lot of objects at the exact same position?

Question

I realize my title is not very clear, but I am having trouble thinking of a better one. If anyone wants to correct it, please do.

I'm developing a data structure for my 2 dimensional game with an infinite universe. The data structure is based on a simple (!) node/leaf system, like the R-Tree.

This is the basic concept: you set howmany childs you want a node (a container) to have maximum. If you want to add a leaf, but the node the leaf should be in is full, then it will create a new set of nodes within this node and move all current leafs to their new (more exact) node. This way, very populated areas will have a lot more subdivisions than a very big but rarely visited area.

This works for normal objects. The only problem arises when I have more than maxChildsPerNode objects with the exact same X,Y location: because the node is full, it will create more exact subnodes, but the old leafs will all be put in the exact same node again because they have the exact same position -- resulting in an infinite loop of creating more nodes and more nodes.

So, what should I do when I want to add more leafs than maxChildsPerNode with the exact same position to my tree?

PS. if I failed to explain my problem, please tell me, so I can try to improve the explanation.

Update: this is how I check if all leafs in a full node have identical positions:

//returns whether all leafs in the given leaf list are identical
    private function allLeafsHaveSamePos(leafArr:Array<RTLeaf<T>>):Bool {
        if (leafArr.length > 1) {
            var lastLeafTopX:Float = leafArr[0].topX;
            var lastLeafTopY:Float = leafArr[0].topY;
            for (i in 1...leafArr.length) {
                if ((leafArr[i].topX != lastLeafTopX) || (leafArr[i].topY != lastLeafTopY)) return false;
            }
        }
        return true;
    }

Answer 1

From common sense I'd not assume having two objects in the same position ever, but if this is a part of the idea, then I would introduce one more axis, say 'spin', an integer number, and impose a restriction that all your objects are fermions (cannot have the same location and spin at the same time).

Answer 2

It looks like a bit of a mismatch between your data and your structure, since you have a structure that assumes N objects within an arbitrarily large area when you're supplying it with >N objects on an infinitely small point. It might be worth using a different structure for this data?

Hack fix: apply a tiny random displacement to your newly created objects. This should allow the space to be subdivided by the existing algorithm.

Better fix: ensure that your algorithm for splitting a leaf node always generates at least 2 new leaf nodes to begin with. When reassigning objects to the new leaf nodes, or when performing normal insertions, iterate over all the candidates, and if more than one is equally suitable then you can tie-break based on how full they are. This should result in your co-located players ending up split evenly across the otherwise identical nodes.

Answer 3

I would like to ask a question...

• is it that important than the maxChildsPerNode constraint be respected ?

I would rather think of this maximum as a hint to the structure for when to split, and simply ignore it when there is no meaningful way to perform the split.

Of course you'd better rethink the name then, otherwise it'd be odd for the next maintainer.

In pseudo code I would use something like this:

def AddToNode(node, item):
  node.items.append(item)
  if len(node.items) > node.splitHint:
    leftNode = Node(node.splitHint)
    rightNode = Node(node.splitHint)
    node.split(leftNode, rightNode)
    if len(leftNode.items) == 0 or len(rightNode.items) == 0:
      node.splitHint *= 1.5 # famous golden ratio ;)
    else:
      node.items = [leftNode, rightNode]

The important step is to modify the hint when it's detected than we can't abide by it in order not to perform this check at each insertion (this way we obtain a constant amortized cost).

Answer 4

If you have a set of objects on the exact same spot, any query for a region that contains one should return all - so there's no reason to split them, as it doesn't gain you anything. Simply either count the number of distinct locations when deciding to split, or have each element on the leaf node be an object that encapsulates (coordinates, [list of objects at those coordinates]).