Jump to content

  • Log In with Google      Sign In   
  • Create Account


#Actualserumas

Posted 22 April 2013 - 03:27 AM

There are a number of ways to generate the sectors concept ranging from really simple to fairly complex.  As LJ mentions, using a simplified concept such as a quad/octree can give you benefits in this area.  Say with a quad tree you are simply looking for elements completely contained in a quad area (no overlap with other areas), interactions between one and another quad are completely ignored since there is no overlap.  So, say you have 4 objects in quad 1, 4 objects in quad 2 and 4 objects straddling the division.  Normally you have (n-1)*n interactions possible without the quad tree, i.e. (12-1)*12=132.  With 4 objects in quad one, they have to consider themselves and the straddlers, but we leave the straddlers to check interactions between themselves so the equation is (n-1)*(n-s) where s is the straddler count, n is in quad 1 and the straddlers, or in this case: 7*4=28.  The same for the second quad.  And finally check the straddlers against each other for (4-1)*4=12.  So, the total checks needed is down to 2*28+12=68 checks.

Something wrong with your calculations  bruteforce of n objects will be n*(n-1)/2  12*11/2=66. ==  11+10+...+1=66

So its the number checks in worst case.

I cant undertand why everyone suggest to use quadtrees, in my experience its always slower and harder to implement than properly implemented grid or hashgrid.

Maybe it was good algorith in the past, but now its much slower becouse of cache missings.

And if you want even to speedup your grid , you can use sweap and prune inside each cell.

 

 

I don't know if it will help you, but this is my class for hash grid which I use in my game.

Sveiks,

I think its a simle grid implementation becouse there is no hash function smile.png


#4serumas

Posted 21 April 2013 - 09:15 AM

There are a number of ways to generate the sectors concept ranging from really simple to fairly complex.  As LJ mentions, using a simplified concept such as a quad/octree can give you benefits in this area.  Say with a quad tree you are simply looking for elements completely contained in a quad area (no overlap with other areas), interactions between one and another quad are completely ignored since there is no overlap.  So, say you have 4 objects in quad 1, 4 objects in quad 2 and 4 objects straddling the division.  Normally you have (n-1)*n interactions possible without the quad tree, i.e. (12-1)*12=132.  With 4 objects in quad one, they have to consider themselves and the straddlers, but we leave the straddlers to check interactions between themselves so the equation is (n-1)*(n-s) where s is the straddler count, n is in quad 1 and the straddlers, or in this case: 7*4=28.  The same for the second quad.  And finally check the straddlers against each other for (4-1)*4=12.  So, the total checks needed is down to 2*28+12=68 checks.

Something wrong with your calculations  bruteforce of n objects will be n^2/2  12*12/2=72. ==  12+11+10+...+1=72

So its the number checks in worst case.

I cant undertand why everyone suggest to use quadtrees, in my experience its always slower and harder to implement than properly implemented grid or hashgrid.

Maybe it was good algorith in the past, but now its much slower becouse of cache missings.

And if you want even to speedup your grid , you can use sweap and prune inside each cell.

 

 

I don't know if it will help you, but this is my class for hash grid which I use in my game.

Sveiks,

I think its a simle grid implementation becouse there is no hash function smile.png


#3serumas

Posted 21 April 2013 - 09:13 AM

There are a number of ways to generate the sectors concept ranging from really simple to fairly complex.  As LJ mentions, using a simplified concept such as a quad/octree can give you benefits in this area.  Say with a quad tree you are simply looking for elements completely contained in a quad area (no overlap with other areas), interactions between one and another quad are completely ignored since there is no overlap.  So, say you have 4 objects in quad 1, 4 objects in quad 2 and 4 objects straddling the division.  Normally you have (n-1)*n interactions possible without the quad tree, i.e. (12-1)*12=132.  With 4 objects in quad one, they have to consider themselves and the straddlers, but we leave the straddlers to check interactions between themselves so the equation is (n-1)*(n-s) where s is the straddler count, n is in quad 1 and the straddlers, or in this case: 7*4=28.  The same for the second quad.  And finally check the straddlers against each other for (4-1)*4=12.  So, the total checks needed is down to 2*28+12=68 checks.

Something wrong with your calculations  bruteforce of n objects will be n^2/2  12*12/2=72. ==  12+11+10+...+1=72

So its the number checks in worst case.

I cant undertand why everyone suggest to use quadtrees, in my experience its always slower and harder to implement than properly implemented grid or hashgrid.

Maybe it was good algorith in the past, but now its much slower becouse of cache missings.

 

 

I don't know if it will help you, but this is my class for hash grid which I use in my game.

Sveiks,

I think its a simle grid implementation becouse there is no hash function smile.png


#2serumas

Posted 21 April 2013 - 09:12 AM

There are a number of ways to generate the sectors concept ranging from really simple to fairly complex.  As LJ mentions, using a simplified concept such as a quad/octree can give you benefits in this area.  Say with a quad tree you are simply looking for elements completely contained in a quad area (no overlap with other areas), interactions between one and another quad are completely ignored since there is no overlap.  So, say you have 4 objects in quad 1, 4 objects in quad 2 and 4 objects straddling the division.  Normally you have (n-1)*n interactions possible without the quad tree, i.e. (12-1)*12=132.  With 4 objects in quad one, they have to consider themselves and the straddlers, but we leave the straddlers to check interactions between themselves so the equation is (n-1)*(n-s) where s is the straddler count, n is in quad 1 and the straddlers, or in this case: 7*4=28.  The same for the second quad.  And finally check the straddlers against each other for (4-1)*4=12.  So, the total checks needed is down to 2*28+12=68 checks.

Something wrong with your calculations  bruteforce of n objects will be n^2/2  12*12/2=72.

So its the number checks in worst case.

I cant undertand why everyone suggest to use quadtrees, in my experience its always slower and harder to implement than properly implemented grid or hashgrid.

Maybe it was good algorith in the past, but now its much slower becouse of cache missings.

 


I don't know if it will help you, but this is my class for hash grid which I use in my game.

Sveiks,

I think its a simle grid implementation becouse there is no hash function :)


#1serumas

Posted 21 April 2013 - 09:09 AM

There are a number of ways to generate the sectors concept ranging from really simple to fairly complex.  As LJ mentions, using a simplified concept such as a quad/octree can give you benefits in this area.  Say with a quad tree you are simply looking for elements completely contained in a quad area (no overlap with other areas), interactions between one and another quad are completely ignored since there is no overlap.  So, say you have 4 objects in quad 1, 4 objects in quad 2 and 4 objects straddling the division.  Normally you have (n-1)*n interactions possible without the quad tree, i.e. (12-1)*12=132.  With 4 objects in quad one, they have to consider themselves and the straddlers, but we leave the straddlers to check interactions between themselves so the equation is (n-1)*(n-s) where s is the straddler count, n is in quad 1 and the straddlers, or in this case: 7*4=28.  The same for the second quad.  And finally check the straddlers against each other for (4-1)*4=12.  So, the total checks needed is down to 2*28+12=68 checks.

Something wrong with your calculations  bruteforce of n objects will be n^2/2  12*12/2=72.

So its the number checks in worst case.

I cant undertand why everyone suggest to use quadtrees, in my experience its always slower and harder to implement than properly implemented grid or hashgrid.

Maybe it was good algorith in the past, but now its much slower becouse of cache missings.


PARTNERS