Main.SideBar (edit) |
Main /
ItemQuadTreeIdea is to keep all items in a quadtree instead of per-cell lists. AB: I'd rather use _in addition_ to per-cell lists. We often need (see pathfinder) to access a particular cell, this would be inconvenient to implement in a quadtree
This would speed up lots of queries which need list of units/items on a certain area, such as Unit::unitsInRange(). Required operationsThis is for the whole quadtree
SELECTION includes:
AB: "All items" is a special case of items in rect.
AB: I think pretty much all of these can be implemented using a simple algorithm: 1. find all items in given area 2. return all [units|air units|land units|whatever] that was returned by 1. The performance is essentially defined by 1., the 2. is a simple linear search over the result, which typically will be a low number of elements
Data structuresThe main data structure of course is the quadtree.
Note that QValueVectors here should perhaps be replaced with BoItemLists. ATM they just emphasize that they contain only units, not e.g. shots AB: I don't think that's a good design idea. See memory usage.
Memory usageThe quadtree would have about 1.33*n*n nodes in total for a map of size n x n cells. AB: note that the "lists" is what defines memory usage here. Think about it: on a 500x500 map with 10 players (current maxplayers) that would be > 1.33*500^2*10/(1024^2) MB per byte. That's 3.17 MB per byte in a quadtree node. Now assume every list would take 16 bytes (it takes much more!) - 50.7 MB of memory WITHOUT STORING ANYTHING! And that is only for a single (!) list per node.
Every level of the quadtree would store every unit in the game about 4 times (once in each list). As the quadtree has log n levels, the lists would store about log n * 4 * x units in total, where x is number of units in the game. AB: note that "about" is actually "at least": a unit usually is on more than one cell and thus on more than one node per level. But the real number should be close to log n for every list. Storing it in 4 lists every time however, is pretty unelegant imho: you need to update EVERY list WHENEVER a unit moves. In total you must be careful that you don't make it slower than a version without quadtree.
Thus, total amount of memory used by the quadtree is 1.33*n*n * sizeof(node) + 4*x*sizeof(list item)*log n where sizeof(node) is about 2*sizeof(int) + 4*MAXPLAYERS*sizeof(list) To reduce memory usage, it might make sense to construct the quadtree so that each leaf would represent not a single cell but e.g. 4x4 cells. This would remove two bottom levels of the tree reducing memory usage to 54*n*n + 48*x*(log n - 2) which is just 16mb for map of size 500. AB: note that such tricks only help temporarily. You don't fix the principle problem, but move it farther away only. If it goes away far enough, then that's allright, but I think the initial proposal already takes so much memory, that it's better to fix that one first. In particular remove the lists[MAXPLAYERS] thing.
The pathfinder would probably then require it's own datastructure which for each cell would store all land units on that cell. Memory usage of that would be n*n * 16 + 12*x which for the above map would be 4mb. Keeping another datastructure up to date would of course need additional time but otoh the quadtree would have less levels to keep up to date and most unit movements would affect only the bottom (i.e. removed) levels anyway. Operations' implementations
AB:
Both operations may take quite some time. In your proposal, it'd be at least log(n)*MAXPLAYERS*4 - on every quadtree level you need to update MAXPLAYERS*4 lists. (Updating a list of a large node may take O(#units) time which might be significant, too. But let's neglect this for now). If MAXPLAYERS is 10, then 4*MAXPLAYERS is already more than the time between two advanceNone() calls, which call unitsInRange() which is the performance issue we are trying to solve. So if a lot of units are moving, you may actually make the whole program significantly slower. |