[MUD-Dev] Re: Quadtrees?

[Miroslav Silovic]

Ling <K.L.Lo-94 at student.lboro.ac.uk> writes:

> The disadvantage of r-trees is that they are computationally more
> intensive to construct.

You will almost always want to dynamically update the tree contents,
because some of them will want to move around. Not walls, but things
like cars and monsters. The problem with R-trees is that this means
that coordinate change will want to propagate upwards, touching
several nodes each time you cross the inter-node boundary. R-trees
efficiency depends on the overlaping area of the rectangles (it has to
be as small as possible), and as the boundaries move, this may become
very messy problem. Yes, you /could/ delete/read the object, but you
still have to rebalance the tree to minimise the overlap. OTOH, you
can greatly lower the memory overhead of a quadtree by storing the
objects in the nodes that correspond to their approximate size (so
that an object won't be in more than 4 nodes) - this means you don't
just store the objects in quadtree leaves but in all the nodes.

--
I refuse to use .sig



_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev