Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Question about Mike Acton's boids example.

Discussion in 'Entity Component System' started by calvinxie1, Nov 22, 2018.

  1. calvinxie1

    calvinxie1

    Joined:
    Sep 22, 2017
    Posts:
    5
    In the process of learning 'IJobNativeMultiHashMapMergedSharedKeyIndices' and 'NativeMultiHashMap' in Mr Acton's boids example, I have this question that I don't know anyone here has noticed.
    According the spatial hashing algorithm used in the example, does each boid only iterate through the neighbors in its own hash bucket?

    To my understanding of the boid algorithms, each boid should iterate through all boids in a certain radius of itself. That could potential include boids that are very close to each other but just happen to be different buckets. But the demo algorithms do not address this in this example unless I'm missing something. I understand that this boids example could just be there to illustrate the effectiveness of the job system and ECS. Functionally it does not need to fulfill all the criteria of a full boids system.

    Can anyone, or possibly Mr. Acton himself, clarify this? Is this a simplified boids system?
     
  2. Robber33

    Robber33

    Joined:
    Feb 22, 2015
    Posts:
    52
    I did not look into the quantize function used for hashing, but afaik each boid only iterates through the neighbors in its own hash bucket.You could say this is an optimization of the algorithm. In the long run and on a bigger scale the effect of the spatial partitioning in stead of true radius for each boid is not very noticable and provides a huge performance boost.
     
    Antypodish likes this.
  3. Robber33

    Robber33

    Joined:
    Feb 22, 2015
    Posts:
    52
    checking out HashUtility.cs provided with the samples you can see that the hashing does not just put the boids in a fixed grid. I'm not exactly sure how it works but basically the boids are partitioned with changing/overlapping ? offsets in the grid, providing a bit of randomization how the boids are put in buckets, and over a couple of frames this will match the effect of personal radius for each boid.
     
    Last edited: Nov 22, 2018
  4. calvinxie1

    calvinxie1

    Joined:
    Sep 22, 2017
    Posts:
    5
    I'm fairly certain the quantize function is just a static/deterministic function. I've modified this example to account for 'true' neighbors but got a substantial decrease in performance because of the extra lookups and additional data structures. Just curious if anyone has a better solution/algorithm for distance-based neighbor search?

    I believe the hashing function in the utility class does nothing special. If the cellSize is 2, then in one dimension a position 1.9 and 2.1 will have two different hashes, thus not take each other's information when doing their own headings.
     
  5. calvinxie1

    calvinxie1

    Joined:
    Sep 22, 2017
    Posts:
    5
    The quantize function
    Code (CSharp):
    1. public static int3 Quantize(float3 v, float cellSize)
    2. {
    3.     return new int3(math.floor(v / cellSize));
    4. }
    The hash function
    Code (CSharp):
    1. public static int Hash(int3 grid)
    2. {
    3.     unchecked
    4.     {
    5.         // Simple int3 hash based on a pseudo mix of :
    6.         // 1) https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
    7.         // 2) https://en.wikipedia.org/wiki/Jenkins_hash_function
    8.         int hash = grid.x;
    9.         hash = (hash * 397) ^ grid.y;
    10.         hash = (hash * 397) ^ grid.z;
    11.         hash += hash << 3;
    12.         hash ^= hash >> 11;
    13.         hash += hash << 15;
    14.         return hash;
    15.     }
    16. }
    As you can see these functions are static and deterministic.
     
  6. Robber33

    Robber33

    Joined:
    Feb 22, 2015
    Posts:
    52
    you are right, i thought it was doing something with the celloffsets defined earlier in the struct.
    but what you could try is what i thought the quantize function did, so you vary the positions of the quantized cells each frame, by some random of predefined offset, this will average out over a couple of frames so each cell will have some overlap over time.