Re: [boost] Boost.ntree_container (bi_tree, quad_tree, oct_tree, etc ptr containers) Is there any interest in this?

Subject: Re: [boost] Boost.ntree_container (bi_tree, quad_tree, oct_tree, etc ptr containers) Is there any interest in this?
From: Klaim - Joël Lamotte (mjklaim_at_[hidden])
Date: 2012-03-09 07:40:11

On Fri, Mar 9, 2012 at 00:47, Dan Walters <dan_at_[hidden]> wrote:

> Your comments regarding moving entities are interesting. Supporting this

well would be a great feature although I think there is a huge risk in
> making this library too feature-full and a more tightly defined library
> would be much more flexible.

I don't consider allowing adding/removing values in a tree in a very short
time (or at least in a predictable time) a feature addition.
Also, I don't see in your interface how do you populate the tree?

> For a game, you may want your static objects
> to be stored separately to your moving objects.

It depends (on the game).
Basically, static objects might be still needed in the same tree than
moving objects if there are possible interractions (physics, graphics or
not).

> This is how the major
> physics libraries do it I think.

I'm not sure, but I guess it would allow some kind of optimizations.

> Note that if you are using soft bodies or
> other physical simulations, then your physical library would do all the
> spacial management for you and so you wouldn't need your own spacial
> container anyway.
>

That's why i'm not interested in it as a replacement for other libraries.
However it can be really useful when you need to get a space partionning
container with specific data that have nothing to do with graphics or
physics.
I have such use case for a game, so maybe your library would be fit, maybe
not.

>
> For moving objects, depending on how they move, how frequently, etc. will
> determine the best choice of container, and a tree may not be it. I think
> it is useful to define the tree structure as being a fixed interval
> container, with dimensions to the power of two as this gives the fastest
> and most fundamental type of tree (as I understand).
>

It's only about removing an object then reinsert it in the tree, with an
optimization to no-operation if the operation is detected as unnecessary
(the entity is still in the same leaf).
That's how most game quadtree and octree work.

I'm not talking about applying physics, only space partition and efficiency
of the remove/insert algorithm.

>
> In practical terms, the tree would represent AABB of size 2^n and would be
> accessed using integers.
>

That was my understanding, but what would the leaves contain?
Also, what would the integers represent? Is it too early to ask for an
example of use you might have think about?

>
> I hadn't thought about memory management strategies. I had assumed a
> ptr_container style container would be the most useful but actually std
> style containers make a lot of sense also.
>
>
As I said, if you want to target (soft) real time simulation (including
most kind of games), you need it to be very fast and very stable on memory.
Boost libraries aren't guaranteed to be "very fast" but most are fast
enough, and the new containers are now solving problems specific to
constrains we have with simulations.

For this particular problem, something that would behave like a std::map
would be "interesting" to some game developers but wouldn't be interesing
for most,
mainly because of the cost of insertion/remove of leafs
(allocation/deallocation).
However, if you manage to get something that behave like a boost::flat_map (
http://www.boost.org/doc/libs/1_49_0/doc/html/container/non_standard_containers.html#container.non_standard_containers.flat_xxx
)
then it would be very interesting even in hard constrained context because
the user can reserve memory from the beginning and never make it
grow(allocate) or shrink (deallocate).
If the insertion and remove is fast or constant, then it becomes very
useful.

The std::map-like version would be enough for me to use it, while the flat
version would allow me to not pay the node allocation/deallocation cost
each time I have to manipulate the map,
with moving entities.

Allowing custom allocator is, I think, basic requirement for any generic
container to be accepted in boost.

Hope it helps.

Joël Lamotte