Question about Mike Acton's boids example.

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?

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.

1 Like

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.

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.

The quantize function

public static int3 Quantize(float3 v, float cellSize)
{
    return new int3(math.floor(v / cellSize));
}

The hash function

public static int Hash(int3 grid)
{
    unchecked
    {
        // Simple int3 hash based on a pseudo mix of :
        // 1) https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
        // 2) https://en.wikipedia.org/wiki/Jenkins_hash_function
        int hash = grid.x;
        hash = (hash * 397) ^ grid.y;
        hash = (hash * 397) ^ grid.z;
        hash += hash << 3;
        hash ^= hash >> 11;
        hash += hash << 15;
        return hash;
    }
}

As you can see these functions are static and deterministic.

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.