1
$\begingroup$

I have been going through a code base for multi agent motion planning. And I came across a recursive tree building algorithm for the agents. I haven't been able to figure out the algorithm. Does anyone know what it is called? Or any other similar kinds of algorithms so I could read more about it?

Here is what I got from the code: The node of the tree is as follows - 

>   struct AgentTreeNode {
>     int begin;
>     int end;
>     float minX, maxX, minY, maxY;
>     int left;
>     int right;   };

Each node has a max and min value for x and y. And also a begin, end, left and right value.

Then the tree is split either horizontally or vertically based on which limits are longer (x or y). And an optimal value is found and agents are split.

Then these split agents are recursively build again.

Thank you very much.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

It sounds like a KD-tree

If it is a KD-tree, the four floats seem a little redundant, bounding boxes can be calculated on the fly when traversing the tree, you only need to record the splitting plane in the node.

I would guess that begin and end describe range of indices of agents belonging to the current node and left and right are indices of left and right subtree of the current node.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your response. I came across this link on Binary space partitioning which has an algorithm that is related to the one I mentioned. But it's not quite the same. So I was wondering if there is a general class of such algorithms. $\endgroup$
    – simplename
    Commented Oct 15, 2014 at 20:20
  • $\begingroup$ BSP-tree is a more generic variant of KD-tree that doesn't require the splitting plane to be axis aligned. In general these are binary search trees, only extended from 1D (you have an interval, split it, build the same structure recursively on both sides of the split) to higher dimensions (you have a n-dimensional box, split it (somehow), build the same structure on recursively on both sides). $\endgroup$
    – cube
    Commented Oct 16, 2014 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.