Cell checking through quadtrees.

[Y-Less]

I just came up with a new streaming method based on quadtrees, which I think could be interesting - it would totally do away with the need to determine a list of appropriate cells in advance. For simplicity, I'll have a root cell from which all others are children, and anything stupidly huge or stupidly out of range will just end up in that cell. However, this idea can be extended WAAY up should it be needed.

A quad tree divides an area in to four parts, then recurses. So given the whole map of San Andreas you chop it in to found quarters, then each of those quarters becomes a new area to process and chop in to quarters. At each step, you know which of the quarters the player is in, and so only need to process items from that cell before dropping down a level. When adding items to the streamer, they are added to the smallest cell that can contain them entirely (for areas that's easy, for other things that would be determined by their view distance - this should be entirely contained).

The map shows several examples:

The yellow and green ovals are objects with their view distances shown. They are about the same size, but crucially the yellow one's view distance is entirely contained within a smaller cell than the green one's. The cell it is in is shown by the yellow box (and the green one the green box). If the player were in the yellow box, both objects would be checked, since the yellow box is a child of the green box. If the player were in the purple box, only the green object would be checked as the purple box is also a child of the green box, but a sibling of the yellow box. As it happens, the player is the red spot in front of Las Venturas airport, and so the boxes bordered in red are the ones processed (the system can be extended beyond the normal bounds).

The blue blob shows a much larger poly area, whose bounds are the blue box. Again, this does not need to be checked for the current player as none of their nested cells contain the area.

Using bits.

This is a note on optimisations. If you assume a minimum cell size of 100 units (which is 1/3 of the current one), the maths becomes quite nice. Assuming a player position x, y:

int xidx = ~((int)x + 50) / 100; // Round to the nearest centre point.
int yidx = ~((int)y + 50) / 100; // Round to the nearest centre point.

You then have a map to their location in binary! This maps well to the normal GTA bounds as well - 32 becomes 3200, just bigger than then +/- co-ordinates for the main map.

Assume x = 567.3, y = 1532.8 (negatives require a tiny bit more processing first):

// Nearest hundred = 600, divided by 100 = 6, inverted.
int xidx = ~6;  // Binary: 0b11111001
int yidx = ~15; // Binary: 0b11110000

For x, 1 means left and 0 means right. For y, 1 means up and 0 means down (I know GTA co-ordinates are a little mixed up, for now I'm treating this the normal way - X is horizontal, Y is vertical on the map).

struct Cell
{
	// Recursion information.
	Cell * Children[2][2];
	// Streamer information.
	CObjects Objects;
	CAreas Areas;
	// etc..
}

const int START_DEPTH = 8;

void ProcessPlayer(player_t playerid, int depth, int xidx, int yidx, Cell * cur)
{
	// If the cell pointer is NULL, nothing has yet been created with this small
	// a cell in this area (cells are created lazilly when needed and added to
	// their parents).
	if (!cell)
		return;
	// ... 
	// Do the streaming for items here now.
	// Note that anything not in these cells can be instantly hidden.
	// ...
	// Recurse to the correct child.
	if (depth)
	{
		// Predecrement, so that the first actually done shift is 7, and the
		// final actually done one is 0, with the recursion ending after that.
		--depth;
		ProcessPlayer(playerid, depth, xidx, yidx, cur->Children[x >> depth & 1][y >> depth & 1]);
	}
	// The use of 2 element arrays with bit manipulation of the position always
	// selects the correct child for the player's location.
}

// Begin the process with the top node.
ProcessPlayer(playerid, START_DEPTH, 0xF9, 0xF0, &gRootNode);

Adding things.

This would be a similar recursive process to checking areas. Do something like AddItem(item, START_DEPTH, posx, posy, sizex, sizey, &gRootNode);. Check if the item will fully fit in one of the four child cells, and if so recurse (may require actually constructing the child at this point). If it doesn't (or if this is the smallest cell size, i.e. depth = 0) add it to the current cell. I'm sure there must be a slightly better way than checking all four children. In fact there is since you know which child the centre point is in from the bitmap, so you can just check that one and then potentially recurse.

Notes.

There is one major disadvantage to this method - things that cross the boundaries between two quads are not handled well - they need to pushed up to the parent quad. Unless they are also on the parent's border, in which case the process is recursive. The huge corner-case to all of this is anything that crosses the X or Y origin (i.e. X=0 or Y=0). Anything for which this happens will be pushed all the way up to the root node. Everything along those axes will be in the same cell.

The advantage is huge items - things that may span many cells or those with massive view distances. You place them in the smallest zone that totally encompasses them and will have them processed normally. An area covering the whole of Las Venturas for example would fit nicely in one cell of sufficient size and only need processing if the player is within that zone. It is also more accurate, with smaller minimal cells, but with less zones processed per player.

The other advantage is that because when streaming you generally start with larger items in larger cells, they would be favoured to the smaller ones, and so in the case of having too many items in range, the big ones are used first in this scheme for free.

I have no idea if this method would be useful, just thought I should document it - since it is (IMHO) an improvement over my old methods, which relied on similar but fixed out of bounds or oversized cells.

[samp-incognito]

This is a good point, and quadtrees could certainly offer some performance improvements over the current system. Boost.Geometry also has a nice R-tree library now, which I think would be pretty trivial to implement.

There are lots of other spatial indexing methods besides quadtrees and R-trees as well. I don't consider myself an expert when it comes to these particular data structures, so I don't know all of their specific use cases, but if anyone does, feel free to chime in.