jcantero

Thank you again, RedFox. I do not want to spend another minute of your valuable time with this, but I really want to know what's going on. I owe you a few dozen programming hours. I'll see how I can return them.

Is that code available somewhere yet?

Obviously, a broad phase is required, otherwise the algorithm should compare every entity in the map against each other. Now this broad phase is based on a fixed size grid (implemented with a std:vector). The question that remains is if another type of partition could accelerate the process, and I'm afraid that that doesn't work, not when the algorithm needs to resolve a "fixed" area, making the adaptative partition useless in practice. However, in the collision detection scenario it works (or it should work). Sweep&Prune is a broad phase that takes a different aproach to the problem: it exploits the algorithmic advantages of sortered sequences (binary search in O(log n), etc). And the sorting criteria is precisely the spatial position of the objects. It doesn't divide the space in "areas" (squares, cubes, ...) so this is not an issue.

A sidenote: the problem with those structures is that they don't help with the range objects computation, only with collision detection. If an entity has another 100 entities in line of sight, the 100 entities must be reported by the algorithm, whatever it is. In the case of tree-based partitions, you have the 100 entities separated in groups, but ultimately you have to add up these groups to build the 100 elements list to return it. There is no gain (the upper-level algorithm has to do the n*(n-1)/2 comparations yet) and now there is also the overhead of maintain the tree structure (balanced, or whichever the algorithm demands). So whatever solution would be, it can't be a spartial partition, that only serves to maintain an adjusted dinamic tiling to reduce collision checks below certain level.

If you plan to to change the scripting language, please please consider Lua prior of any other language. It's the preferred one of the game industry for these type of things*, and for good reasons. Also, it's very efficient and easy to integrate with C++ (enough to copy the sources in a directory of the project). It is used mainly for AI scripting, but it can be used for anything. Of course it's open source (MIT license). * The list of games that use Lua is quite big, including a pair of the more recent Total Wars, Civilization V, SimCity 4, Crysis and World of Warcraft, to name a few. It's also used in well-known open source games.

First, thanks for your patience and time. And second, thanks also for your detailed reports, they really encourages to participate in the development of 0 A.D. I am really looking forward to see future improvements of performance in the simulation :-)

Impressive work Red Fox. Let me point to the source code using Github mirror (GH let do that) to refer lines of code: https://github.com/0ad/0ad/blob/3a5c4008e95a7919bde5a46fdfb61a629d25658a/source/simulation2/helpers/Spatial.h#L201-L202 I've been researching if std::sort algorithm could impact the performance. According to this Wikipedia entry http://en.wikipedia.org/wiki/Sort_%28C%2B%2B%29, the worst case is O(n log n) (it's not QuickSort, but a hybrid algorithm to avoid QS worst-case scenario). This doesn't mean it can't be improved, but then I was thinking why it should be sorted in first place. OK, it's required in order to use later std:unique(). But why the need of remove duplicate entities, when an entity should not be in two cells (in two std:vectors) at the same time. Am I right? If it's true, then you could safely remove these 2 lines. Except that these results are expected sorted by the calling methods, of course. Another solution is to use sets instead of vectors to avoid duplicates, but that only has sense if the std:set is more efficient (I don't know), and again if they don't need to be sorted later.

Excuse me for the question, I've read the discussion about Octrees/Quadratrees, and I'd like to ask: are you already using a Sweep&Prune* algorithm (or have you considered to use it) for the broad phase of collision/pathfinding/rangefinding? The Octree/Quadtree/k-d tree/... way is expensive, only worthwhile if you plan to filter a large number of objets (for example to reduce hundreds of thousands to thousands polygons in a 3D rendering engine). Sweep&Prune only requires two sorted arrays (or vectors) of entities, one for each coordinate x and y, and keep those arrays sorted when the positions of the entities change. And this can be very efficient using the appropriate sorting algorithm. Especially if you treat the entities as a simple point on the map (you can also treat it as a AABB). * http://en.wikipedia.org/wiki/Sweep_and_prune