Multi resolution grids

You could use a quadtree. It's basically similar to a binary tree. Rather then left and right you have top-left, top-right, bottom-left and bottom-right.

or an octree if u have varying heights.

Its all the same they just have less children.

The complicatedness of a binary tree is you have to decide how to partition and on which axis(or even arbitary) however with an octree/quadtree you simple binary partition per axis.

X + Y = 2 * 2 = 4 Children per parent
Z + Y + Z = 2*2*2 = 8 Children per parent.

all of these trees are damn fast as you the possible area keeps shrinking with each depth

on a binary tree it halves
an quadtree its 1/4 of the previous area
and an octree its 1/8 of the previous area which justifies the extra memory and checks

Hey, I have already prototyped, implemented, tested, profiled and optimized my own Quadtree class some time ago :-) and now I'd like to prototype, implement, test, profile and optimize other space partitioning algorithms, and compare them against criteria such as speed, memory usage, ease of implementation, flexibility etc. That's why I asked about multiple resolution grids, since normal grids are way too in-flexible for my needs (grid cell size is determined by size of biggest object).

So, I'll reiterate question: I tried Googling for any sources/demos/articles about multi resolution grids but found nothing. Maybe you will know any good links? :-)

How is a multi-reolution grid different from a quad-tree? Does it have a low-res grid and each cell can contain another grid? Or is it a recursive structure like a quadtree, but on a more generalised level?

I can't see the advantages over the quadtree but I guess finding them (or not finding them) is the point of your investigation!

Well, the differences are fundamental :-)

In quadtree, each node contains pointers to its 4 children. Nodes that are placed lower in hierarchy, contain proportionally (25% for each level) less space and objects. There's also root node. So, we can visualize quadtree with normal tree, something along this:

 // sorry, I wasn't able to make it look good :-/ // google for Gamedev quadtree to see how quadtree is structured

Normal grid divides game level into regular grid of cells (all with the same size). Game objects belong at most to 4 cells (depending on their size and position). There's no root node, there's no recursion:

 |---------------------------| |      |      |      |      | |      |      |      |      | |------|--------------------| |      |      |      |      | |      |      |      |      | |-------------|-------------| |      |      |      |      | |      |      |      |      | |------|------|-------------| |      |      |      |      | |      |      |      |      | |---------------------------|

Now, in regular grids there's a problem of grid cell size - if it's too small, some objects may belong to more than 4 cells - and that's a big problem, since in collision detection we made some assumptions, which aren't satisfied in aformentioned situation. So, sometimes, we may not detect collisions. Theoretical solution to this problem is to simply increase cell size, but with this approach, collision detection will eat more and more processor time and resources, since small objects that are far away from each other, will still lay inside one cell/neighbour cells, and therefore - they will be tested:

 |--------------------------| |             |            | |     A       |            | |             |            | |             |            | |-------------|------------| |             |            | |             |            | |             |            | |             |        B   | ----------------------------

A will be tested with B. This wouldn't occur if grid would look like this, since only objects in same / neighbouring cells are tested:

 |---------------------------| |      |      |      |      | |    A |      |      |      | |------|--------------------| |      |      |      |      | |      |      |      |      | |-------------|-------------| |      |      |      |      | |      |      |      |      | |------|------|-------------| |      |      |      |      | |      |      |      |   B  | |---------------------------|

Now, at last, multiple resolution grids provide solution to cell size problem, simply by creating set of grids with varying cell sizes. Objects belong to grid, which cell size is bigger than its size, ie.

 // A is very big object, therefore it's contained within first grid |--------------------------| |                          | |                          | |                          | |                          | |      A                   | |                          | |                          | |                          | ---------------------------- // B and C aren't so big as A, so they can be placed inside this grid: |--------------------------| |             |            | |     B       |            | |             |            | |             |            | |-------------|------------| |             |            | |             |            | |             |            | |             |        C   | ---------------------------- // D, E and F are very little objects |---------------------------| |      |      |      |      | |      |      |  D   |      | |------|--------------------| |      |      |      |      | |      |  E   |      |      | |-------------|-------------| |      |      |      |      | |      |      |      |   F  | |------|------|-------------| |      |      |      |      | |      |      |      |      | |---------------------------|

Remember: there's no recursion, no children and parent pointers. Each grid is stored by it's own, as an entry in array.

Quote:

I can't see the advantages over the quadtree but I guess finding them (or not finding them) is the point of your investigation!

No, you're wrong. With quadtree, in order to detect collision / perform "render all operation", you have to move a lot in the tree, which means you have to perfrom a lot of pointer dereferences, which obviously mean a lot of cache missess - which are very painfull on modern CPU's. Of course, there's a solution to this problem, which was described in GPG, but it's not that easy (but not that hard either :-) ) to implement.

Obviously, with normal grids / multiple resolution grids you have access to each cell in constant time - no cache missess etc. Also, grids and their multiple resolution version should be easier to implement than quadtrees, and for my needs (I won't have 1000s of objects, rather than max. few dozens) they may be more effective than quadtrees. And that's why I'd like to implement and profile it, to see whether it's true.

-------

So, now, are there any experienced Googlers who can help me? :-)


EDIT: first tree "collapsed", had to repair it.
EDIT2: grrr, had to remove it since it still was broken, despite my tries