[PATCH] Adaptive quadtree

[Don]

This is a templated adaptive quadtree class. It comes with its own memory pool, and has minimal entanglement with the game object it contains.

Once the quadtree is reviewed, it would be trivial work to submit a patch for an octree class as well. Then developers will be free to try either one, or both.

[Jorma Rebane]

• Memory pool implementation. We have been working on a general solution for 0 A.D. already that doesn't require fixing pointers if the pool is out of memory. To make transition easier you should replace the allocation routines with new/delete.

• You are correct that an integer implementation of a Quadtree has to be in power-of-two size. However, you check [size % 2 == 0]. Consider the case [14 % 2 == 0]; and 14 is not a power of two, so that's a bug in the code. ​http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2

• I know that having a 2D array m_Child[2][2] seems like a good idea, but for a Quadtree the preferred solution is to have 4 variables: NW, NE, SW, SE. Why? This lets us unroll the loops and actually speeds up the code a lot.

[Don]

Contains updated quadtree code, plus an octree with almost identical interface.

[Don]

Updated patch is now attached. (Wow. Where did my summer go?)

The CQuadtree class now uses new/delete, which can be replaced by calls to our memory pool any time.

The power-of-two bug is fixed.

Unrolling the loops didn't improve performance in my tests (which involved creating a large-ish quadtree, filling it with game objects and removing them, times 10,000), perhaps because the compiler is doing so already. So I went with the more concise original code.

The patch includes a COctree class that works in three dimensions. Other developers can enjoy the argument over which is better.

There was a suggestion in the forum that I hook one of these new classes into CCmpRangeManager. I did look over CCmpRangeManager, but it would take a lot of study before I could modify it. Better to submit the patch now, so it's in the hands of someone else who understands the game better.

[sanderd17]

A remark: you seem to use an other commenting style than the one described in  http://trac.wildfiregames.com/wiki/Coding_Conventions#Documentation. This probably won't work with doxygen (​http://svn.wildfiregames.com/docs/annotated.html).

Apart from that, it looks quite good, although I'm no c(pp) specialist. I'd like to have it in quite soon, so it's easier to use in other work like optimizing the RangeManager.

[Jorma Rebane]

Don's commenting style follows Doxygen guidelines. See ​http://www.stack.nl/~dimitri/doxygen/manual/docblocks.html

It is true however that 0AD codebase mainly uses Javadoc style commenting, so /* * @note ... */ instead of /*! \note ...*/. I wouldn't really worry about it though. The comments can stay as they are, since they're perfectly valid Doxygen.

As for the octree - I don't see any reason why we would ever need it.

[Jorma Rebane]

Hi Don, I've gotten back to patch reviewing.

Since A14 is going to be released, we can start working on A15 changeset and I really want to see your Quadtree implementation in A15.

I'll incorporate it into the build as soon as the feature lock on A14 is lifted and we move on to A15.

[historic_bruno]

Judging by discussions in IRC, a generic quadtree doesn't really help us and each class of problem will need a different design (quadtree may not even be the best design for said problem). So I'm bumping to A16 and we can think about it again later.

[historic_bruno]

As this isn't really in a committable form by itself, I'm going to close the ticket, but link to the forum discussion: http://www.wildfiregames.com/forum/index.php?showtopic=17384

That topic also cross-references this ticket, so if anyone wants to analyze a particular problem were quadtrees might help, they will hopefully be able to find both as a useful starting point :)