Recommended Posts

Hello!

I read this article https://www.gamedev.net/resources/_/technical/game-programming/spatial-hashing-r2697 about spatial hashing but i have a question.

In my 2d engine, the world's borders are specified and its actually a square with length 2^32 .

In the spatial hash article, i read that in order to place a point inside a bucket you can use this hash function: row = (int) (y / cell_size), column = (int) (x / cell_size) . So if i have a 2d array, the function above will give me the row and the column of the 2d array where i have to insert my point.

Then i said to my self "And how do you initialize the dimension of the array and also make sure that the hash function won't give you a row or a column out of range of the array?"

Then i thought about this: Say that i want to divide my space in 100 squares. I know that my world is actually a square with length 2^32, so how do i find the size of the cell? In order to solve this i started thinking with mathematics so i reached to this:

2^32 / cell_size = 100 <=> cell_size  = 2^32 / 100 <=> cell_size  = 42949672.96

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

Please correct me if i am wrong.

Edited by babaliaris

Share this post


Link to post
Share on other sites

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).

Share this post


Link to post
Share on other sites

 

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).

You are right, if my cell size is 42949672.96, then the spatial table won't do anything to increase performance since all of my objects most likely will be placed into a single bucket (Because buckets will be too big). So lets say that my biggest object has a width of 1920 pixels and a height of 1080 (Full HD LOL  :P ).  Lets say that my cell size will be the largest value (1920). 1920 its not a power of two so lets make it. If i do log2(1920) = 10.90689059560852 and ceil this number i will get 11. So the closest power of two will be 2^11 = 2048. Now i can easily say 2^32 / 2048 = 2097152. 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.

Edited by babaliaris

Share this post


Link to post
Share on other sites
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?

Edited by Alberth

Share this post


Link to post
Share on other sites

 

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?

 

Unfortunately i can't answer these questions. All of this depends on the programmer. My game engine is not designed to work for a specified game but to give functionalities in order other programmers be able to create 2d games very easy.

But one of the problems i think can be sovled. I know that my full world is a square with length 2^32, but of of course the game programmer won't use all of this space. So, after he creates the scene when the game runs i can calculate which of these objects has the less x coordinate the greater x coordinate the y less coordinate and the y greater coordinate or even better i can force the programmer to tell me exactly the borders of his world. And using this coordinates i can create another square with length = less x coordinate + greater x coordinate (and make sure its power of two) to surround his world. So now i can use the new length in order to restrict the space and create a hash table only for that space. But i also must make sure that on runtime, nothing can go farther of this square (all the objects inlcuding new spawn ones) because if an objects has (x,y) coordinates greater than this square it will cause the hash function to return out of range keys.

How does this sounds?

Edited by babaliaris

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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).

Share this post


Link to post
Share on other sites
On 17/6/2017 at 6:57 PM, JoeJ said:

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).

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.

Red lines represents the spatial hash table while the blue ones quadtrees.

Untitled.png

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

Is this going to be better than having a single quadtree?

Edited by babaliaris

Share this post


Link to post
Share on other sites

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.

Edited by Alberth

Share this post


Link to post
Share on other sites
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.

 

 

 

 

 

 

 

 

Edited by JoeJ

Share this post


Link to post
Share on other sites

Much like a normal hash map, there's no particular requirement that a bucket in a spatial hash represent exactly one location in the world. It is required that nearby objects hash to the same bucket, but not that all objects in the same bucket are nearby to one another.

You can trivially define the buckets to repeat across the world (i.e. by adding a modulo to your hash function), and then when checking for nearby objects, you first find the matching bucket, and then check the actual distance of each object in the bucket.

This matches the behaviour of a normal hash map a little more closely, and removes the need for arbitrarily large cells, or other complicated datastructures.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now