So this tell's me that i need to create a 2d array with dimensions 100x100 and each bucket (cell) will be a square with the above cell_size. Am i right? And if we assume that the maximum dimension of my world is 2^32 (square) then the hash function will always give me a number between 0 and 100 both for row and column because the x and y coordinates of a point will always be between -2^16 and 2^16

Yes, your math is correct and setting 42949672.96 = cell_size will make your lookup function work. However given how large your cells are this seems pretty large. I'm not sure how big sprites will be in your game, but the article recommended that the space of a cell be roughly twice as large as an average moving object in your game. Maybe a better course of action would be to determine how big you want your cells and use that equation above to find out how many you will need.

Of course if you go for more cells you will have a larger array in memory, so you'll need to determine where the sweet spot is for performance. Larger spacial array and less objects to process per cell or a smaller spacial array with more objects per cell.

Another cool idea for performance tweaks would be to make sure your cell count is a power of 2 (which would make your cell size a power of 2 since your total world size is too) that way instead of dividing you can just right shift the bits of your coordinate (i.e. if cell_size = 2^6 instead of doing (int) (y / cell_size) you could do (int) (y >> 6) which is computationally cheaper than division, although it is less obvious programatically what you're doing).

So now i must create a table of 2097152x2097152 :o :o RIP MEMORY! Actually, if we say that each bucket holds up to two integer numbers (8 bytes) 2097152 * 8 = 16777216 and 16777216 * 2 = 33554432 bytes = 32 MB. I guess its not that much.

There you stepped from (2097152*2097152) = 4,398,046,511,104 to (16777216 * 2) = 33,554,432, and you didn't wonder where the remaining 4,398,012,956,672 went?

As a first suggestion, use powers of 2 everywhere, and don't bother expanding them to decimal numbers, as it only confuses matters.

You are correct in 2^11 being the first value > 1920), so the number of entries in 1 one direction is 2^32 / 2^11 = 2^21 ( 2^a / 2^b = 2^(a-b) )

The full table has 2 such dimensions, giving you 2^21 * 2^21 = 2^42 cells. (that's 2^12 * 2^30 cells = 4096 GB if a cell takes 1 byte.) If you want to squeeze that in 32MB (2^25 byte), you get 2^42 / 2^25 = 2^17 cells in each single byte, or for 8 byte memory-bucket you get 2^(17+3) = 2^20 cells in a memory-bucket.

To be honest, I am lost here. Perhaps instead of throwing numbers around, take a step back, and describe some properties of the objects in your world first, so we can give some guidance about good and bad solutions?

Some properties that come to mind:

- World-size (given, 2^32 in both x and y direction).

- Total number of objects in the world

- Accuracy of positioning (integer positions, or fractions)?

- How are objects spread? (evenly, clustered, everything in [0,1), something else? )

Under the assumption that not all objects are equally relevant all the time (eg stuff on the screen or "nearby" may be more relevant, so maybe only keep those in the table?)

- How large is the "relevant" part of the world?

- How many objects of the above are such a part?

- How are they spread?

- How close to each other are they?

Well, if you can't say anything, you can't design a good hash either, since what works for one game will fail horribly for another game.

Generally, the way out is to create options for the user of your engine to define his own hashing, and also provide a default implementation, which imho should just be the general hash table implementation that comes with the compiler.

Stuff works out of the box, and the advanced users can tweak the hashing for improved performance.

I'd leave it at that, and revisit this problem when the need arises.

You could also use a quadtree which is way better than a regular grid:

Using a loose quadtree each object goes to one and only one node, so you need only one pointer to the first object per node and one pointer to the next object per object.

(All the stuff mentioned in the spatial hasing article, like using a map to avoid duplicates or using a list per cell is not really efficient and can even cause memory allocations - it's likely a test every object against each other aproach may be faster in practice.)

Quadtree can handle huge worlds without memory issues (if the world is sparse enough).

The user would only need to give the maximum of objects he wants to use, then you can preallocate everything at startup (which is ideal for games).

Your buckets are just 1 or 2 levels near the top of the quad tree. As such, it won't be significantly faster, while it does create additional problems, since every feature you build into the quadtree must now be replicated in the bucket system as well (and vice versa).

Edit: Oh, and of course you cannot remove empty buckets like you can in a quad tree, eg the rectangles (2..3, 0..1) and (0..1, 2..3) would not be further split in a quad tree.

2 hours ago, babaliaris said:

I was thinking to make a hash table which each bucket will point to a quadtree. So instead of having only one big quadtree, i can have multiple. I think this will be a lot faster than having a single tree.

That's a typical idea for someone being new to this. I'll point some things out...

If your user uses only e.g. the top left corner of the intire space, you can traverse the quadtree once until you find the top most non empty node node.

You can use this node as the root for all your collision or culling queries. This saves you from treversing some top levels of the tree each time for nothing and gives the performance improvement you expect from your idea.

Notice that using a single tree you already have multiple trees (each node represents a subtree), so there is rarely a need to use multiple trees with an additional mechanism to handle this. So, no, use just one quadtree and no hash table at all.

2 hours ago, babaliaris said:

and of course all this will be applied during scene loading. 

There is something you miss: The scene is dynamic, things will move around. The hash table approach causes dynamic memory managenment during runtime because the usage of lists (and maps), but you don't know how large they need to be.

Lets see what happens under the hood (i'll use the term 'grid' instead of spatial hasing, it's the same thing)

Each grid cell needs a resizable vector to store pointers to all objects. The system allocates some memory for the list, but if it becomes too large it needs to allocate a larger chunk of memory and copy the list to the new place. This may happen severall dozens, hundrets or tousand times per frame and can become a bottleneck.

So using the grid we have this:

gridCell->list[obj0, obj1, obj2, ...]

Also, you need to store the objects in multiple cells, and to avoid duplicates, the suggested usage of a map needs to look up the current map each time a new item is to be added. To speed this search up, the system may implement a binary tree or something, resulting in building a tree for each query. (Compare this with the quadtree approach: It uses only one tree and it's already there)

So this is terribly slow, but how can we do better?

Using a multiresolution grid can fix this:

Imagine our finest grid

level 0 has 8*8 cells, each 1*1 in size,

level 1 has 4*4 cells, each 2*2

level 2  has 2*2 cells, each 4*4

level 3 has 1 cell 8*8, the whole scene

Then we have a circle object with a diameter of 1.9 and we put this in a cell of level 1, because we can be sure this and the neighbouring cells will cover the intire object.

To find collisions we need to look at the neighbouring cells but also at the correspondending cells an their neighbours at levels 2 & 3 to detect collisions with larger objects.

We do not need to go down and check cells from level 0, because collisions with smaller objects will be found from those smaller objects.

You can optimize to check only 3 neighbours instead of all 8.

So this works, and because each object needs only one cell we don't need a vector of pointers per cell, all we need is:

mrGridCell->obj0->obj1->obj2

No dynamic allocation or duplicates problem here.

A loose quadtree is just an extension of this idea, you may start with a multiresolution grid and if this works go to quadtree.