したかみ ぶろぐ

Unity成分多め

【Unity】NativeMultiHashMapを使った近傍探索Boidsシミュレーション

Unity JobSystem Boids

始めに

趣味でJobSystemを使ったBoidsシミュレーションを作成しています。そのときにNativeMultiHashMapがとても有用だったので備忘録として記事を書きます。


前提

今回の記事ではBoidsとJobSystemについては一切解説しません。

Boidsについては、Unity Graphics Programming vol.1 の第3章を参照してください。こちらの内容をもとに実装をしています。

github.com


JobSystemはUnity公式の解説動画やネット上にたくさん記事が挙げられているのでそれらを参照してください。


www.youtube.com



環境

  • Unity 2021.3.10f1
  • Unity.Burst 1.6.6
  • Unity.Collections 1.2.4
  • Unity.Mathematics
  • CPU core i7 8700k

プロジェクトはこちらです。

github.com



Boids実装概要

この記事では全探索と近傍探索それぞれのBoidsを実装します。

その両方で共通となる実装について簡単に触れていきます。


Boidsの設定データ

Boidsでは3つの力（結合、整列、分離）があり、それぞれ重みと影響範囲を持ちます。 また、加えて個体の最大速度やシミュレーション範囲などを設定する必要があります。

これらをInspectorで管理するのは大変なので、ScriptableObjectとして作成しております。

以下のコードは後で解説する全探索用の設定データになります。

AllSearchBoidsSettings

using Unity.Mathematics;
using UnityEngine;

namespace Boids.Settings
{
    [CreateAssetMenu(fileName = "AllSearchBoidsSetting", menuName = "Boids/AllSearchSetting")]
    public class AllSearchBoidsSetting : ScriptableObject
    {
        [Header("結合")]
        [SerializeField] private float _cohesionWeight;
        [SerializeField] private float _cohesionAffectedRadius;

        [Header("分離")]
        [SerializeField] private float _separationWeight;
        [SerializeField] private float _separationAffectedRadius;

        [Header("整列")]
        [SerializeField] private float _alignmentWeight;
        [SerializeField] private float _alignmentAffectedRadius;

        [Header("シミュレーション空間")]
        [SerializeField] private Vector3 _simulationAreaCenter;
        [SerializeField] private Vector3 _simulationAreaScale;
        [SerializeField] private float _avoidSimulationAreaWeight;

        [Space(20)]
        [SerializeField] private float _maxSpeed;
        [SerializeField] private float _maxSteerForce;

        [Header("個体のスケール")]
        [SerializeField] private float3 _instanceScale;

        public float CohesionWeight => _cohesionWeight;
        public float CohesionAffectedRadiusSqr => _cohesionAffectedRadius * _cohesionAffectedRadius;

        public float SeparateWeight => _separationWeight;
        public float SeparateAffectedRadiusSqr => _separationAffectedRadius * _separationAffectedRadius;

        public float AlignmentWeight => _alignmentWeight;
        public float AlignmentAffectedRadiusSqr => _alignmentAffectedRadius * _alignmentAffectedRadius;

        public Vector3 SimulationAreaCenter => _simulationAreaCenter;
        public Vector3 SimulationAreaScale => _simulationAreaScale / 2; // MEMO: 計算では 1/2 の方が書きやすいため
        public float AvoidSimulationAreaWeight => _avoidSimulationAreaWeight;

        public float MaxSpeed => _maxSpeed;
        public float MaxSteerForce => _maxSteerForce;

        public float3 InstanceScale => _instanceScale;
    }
}


Boids実行クラス

Boidsのシミュレーションを呼び出して、結果を描画するクラスを作ります。

今回描画する個体数は1000以上なので、描画がボトルネックにならないよう RenderMeshInstanced を使用します。

今回はInspectorで設定されたenum値に応じて、全探索と近傍探索のシミュレーションを分岐させます。

BoidsSimulator

using System;
using Boids;
using Boids.Settings;
using Unity.Collections;
using UnityEngine;
using UnityEngine.Rendering;

namespace BoidsSimulator
{
    public class BoidsSimulator : MonoBehaviour
    {
        private enum BoidsSimulationType
        {
            AllSearch,
            NeighborSearch,
        }

        [Header("シミュレーション法")]
        [SerializeField] private BoidsSimulationType _boidsSimulationType;

        [SerializeField] private int _instanceCount;

        [Header("描画関係")]
        [SerializeField] private Mesh _mesh;
        [SerializeField] private Material _material;
        
        private BoidsData[] _boidsDatas;
        private RenderParams _renderParams;

        [Header("AllSearchSetting")]
        [SerializeField] private AllSearchBoidsSetting _allSearchBoidsSetting;

        [Header("NeighborSearchSetting")]
        [SerializeField] private NeighborSearchBoidsSetting _neighborSearchBoidsSetting;

        private void Start()
        {
            InitializeBoidsInstance();
            _renderParams = new RenderParams(_material) { receiveShadows = true, shadowCastingMode = ShadowCastingMode.On };
        }

        private void Update()
        {
            switch (_boidsSimulationType)
            {
                case BoidsSimulationType.AllSearch:
                    UpdateBoidsByAllSearch();
                    break;
                case BoidsSimulationType.NeighborSearch:
                    UpdateBoidsByNeighborSearch();
                    break;
                default:
                    throw new ArgumentOutOfRangeException();
            }
        }

        private void UpdateBoidsByAllSearch()
        {
            var allSearchBoidsSimulator = new AllSearchBoidsSimulator(_allSearchBoidsSetting);
            var matricesArray = new NativeArray<Matrix4x4>(_instanceCount, Allocator.TempJob);
            
            allSearchBoidsSimulator.Calculate(matricesArray, _boidsDatas);

            RendererUtility.InstanceRenderUtility.DrawAll(_mesh, _renderParams, matricesArray);
            
            matricesArray.Dispose();
        }

        private void UpdateBoidsByNeighborSearch()
        {
            var matricesArray = new NativeArray<Matrix4x4>(_instanceCount, Allocator.TempJob);

            var neighborSearchBoidsSimulator = new NeighborSearchBoidsSimulator(_neighborSearchBoidsSetting);
            neighborSearchBoidsSimulator.Calculate(matricesArray, _boidsDatas);
            
            RendererUtility.InstanceRenderUtility.DrawAll(_mesh, _renderParams, matricesArray);

            matricesArray.Dispose();
        }

        private void InitializeBoidsInstance()
        {
            _boidsDatas = new BoidsData[_instanceCount];

            BoidsInitializer.In(_boidsDatas, _allSearchBoidsSetting.SimulationAreaCenter, _allSearchBoidsSetting.SimulationAreaScale, 0.1f);
        }
    }
}

RendererUtility

using Unity.Collections;
using UnityEngine;

namespace RendererUtility
{
    public static class InstanceRenderUtility
    {
        public static void DrawAll(Mesh mesh, RenderParams renderParams, NativeArray<Matrix4x4> matricesArray)
        {
            const int instanceCountPerDraw = 1023; // RenderMeshInstancedが一度に描画できる最大数
            var instanceCount = matricesArray.Length;

            for (int i = 0; i < instanceCount; i += instanceCountPerDraw)
            {
                var length = Mathf.Min(instanceCountPerDraw, instanceCount - i);
                Graphics.RenderMeshInstanced(renderParams, mesh, 0, matricesArray, length, i);
            }
        }
    }
}


Boids計算クラス

設定データをもとにBoidsの計算をして、描画用Matrixを求めるクラスを定義します。

このクラス内で計算に必要となるNativeArrayを生成してBoidsの計算を行うJobSystemを実行します。

計算が完了したら、NativeArrayの破棄と計算結果の反映を行います。（コードは全探索から）

AllSearchBoidsSimulator

using Boids.Job;
using Boids.Settings;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;
using UnityEngine;

namespace Boids
{
    public class AllSearchBoidsSimulator
    {
        private readonly AllSearchBoidsSetting _allSearchBoidsSetting;

        public AllSearchBoidsSimulator(AllSearchBoidsSetting boidsSetting)
        {
            _allSearchBoidsSetting = boidsSetting;
        }

        public void Calculate(NativeArray<Matrix4x4> instanceMatricesArray, BoidsData[] boidsDatas)
        {
            var instanceCount = boidsDatas.Length;
            var boidsDataArray = new NativeArray<BoidsData>(instanceCount, Allocator.TempJob);
            var boidsSteerArray = new NativeArray<float3>(instanceCount, Allocator.TempJob);

            boidsDataArray.CopyFrom(boidsDatas);
            
            var boidsJob = new AllSearchBoidsSimulatorJob
            (
                _allSearchBoidsSetting.CohesionWeight,
                _allSearchBoidsSetting.CohesionAffectedRadiusSqr,
                _allSearchBoidsSetting.SeparateWeight,
                _allSearchBoidsSetting.SeparateAffectedRadiusSqr,
                _allSearchBoidsSetting.AlignmentWeight,
                _allSearchBoidsSetting.AlignmentAffectedRadiusSqr,
                _allSearchBoidsSetting.MaxSpeed,
                _allSearchBoidsSetting.MaxSteerForce,
                boidsDataArray,
                boidsSteerArray
            );

            var boidsJobHandler = boidsJob.Schedule(instanceCount, 0);
            boidsJobHandler.Complete();

            var applySteerForce = new ApplySteerForceJob
            (
                boidsDataArray,
                boidsSteerArray,
                instanceMatricesArray,
                _allSearchBoidsSetting.SimulationAreaCenter,
                _allSearchBoidsSetting.SimulationAreaScale,
                _allSearchBoidsSetting.AvoidSimulationAreaWeight,
                Time.deltaTime,
                _allSearchBoidsSetting.MaxSpeed,
                _allSearchBoidsSetting.InstanceScale
            );

            var applySteerForceHandler = applySteerForce.Schedule(instanceCount, 0);
            applySteerForceHandler.Complete();
            
            boidsDataArray.CopyTo(boidsDatas);

            boidsDataArray.Dispose();
            boidsSteerArray.Dispose();
        }
    }
}


JobSystem

Boidsの計算を2段階に分けて計算します。

  1. 各個体の操舵力を求める（全探索と近傍探索の2種類）
  2. 操舵力を各個体に反映、描画用Matrixの計算

1.の各個体の操舵力を求める計算は次のようになります

BoidsSimulatorJob.Execute

        public void Execute(int ownIndex)
        {
            var ownPosition = _boidsDatasRead[ownIndex].Position;
            var ownVelocity = _boidsDatasRead[ownIndex].Velocity;

            var cohesionPositionSum = new float3();
            var cohesionTargetCount = 0;

            var separateRepluseSum = new float3();
            var separateTargetCount = 0;

            var alignmentVelocitySum = new float3();
            var alignmentTargetCount = 0;

            // 全探索、近傍探索で各個体のインデックス targetIndex を取得
            {
                if (ownIndex == targetIndex)
                {
                    continue;
                }

                var targetPosition = _boidsDatasRead[targetIndex].Position;
                var targetVelocity = _boidsDatasRead[targetIndex].Velocity;

                var diff = ownPosition - targetPosition;
                var distanceSqr = math.dot(diff, diff);

                if (distanceSqr <= _cohesionAffectedRadiusSqr)
                {
                    cohesionPositionSum += targetPosition;
                    cohesionTargetCount++;
                }

                if (distanceSqr <= _separateAffectedRadiusSqr)
                {
                    separateRepluseSum += math.normalize(diff) / math.sqrt(distanceSqr); // 距離に反比例する相手から自分への力
                    separateTargetCount++;
                }

                if (distanceSqr <= _alignmentAffectedRadiusSqr)
                {
                    alignmentVelocitySum += targetVelocity;
                    alignmentTargetCount++;
                }
            }

            var cohesionSteer = new float3();
            if (cohesionTargetCount > 0)
            {
                var cohesionPositionAverage = cohesionPositionSum / cohesionTargetCount;
                var cohesionDirection = cohesionPositionAverage - ownPosition;
                var cohesionVelocity = math.normalize(cohesionDirection) * _maxSpeed;
                cohesionSteer = MathematicsUtility.Limit(cohesionVelocity - ownVelocity, _maxForceSteer);
            }

            var separateSteer = new float3();
            if (separateTargetCount > 0)
            {
                var separateRepulseAverage = separateRepluseSum / separateTargetCount;
                var separateVelocity = math.normalize(separateRepulseAverage) * _maxSpeed;
                separateSteer = MathematicsUtility.Limit(separateVelocity - ownVelocity, _maxForceSteer);
            }

            var alignmentSteer = new float3();
            if (alignmentTargetCount > 0)
            {
                var alignmentVelocityAverage = alignmentVelocitySum / alignmentTargetCount;
                var alignmentVelocity = math.normalize(alignmentVelocityAverage) * _maxSpeed;
                alignmentSteer = MathematicsUtility.Limit(alignmentVelocity - ownVelocity, _maxForceSteer);
            }

            _boidsSteerWrite[ownIndex] =
                cohesionSteer * _cohesionWeight +
                separateSteer * _separateWeight +
                alignmentSteer * _alignmentWeight;
        }


2.では1.で求めた操舵力を各個体に反映します。こちらは全探索と近傍探索の両方で共通です。

また、ここで個体の描画用Matrixを求めます。（本当は別で分けた方が良さそう）

ApplySteerForceJob

using Boids.Mathematics;
using Unity.Burst;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;
using UnityEngine;

namespace Boids.Job
{
    [BurstCompile]
    internal struct ApplySteerForceJob : IJobParallelFor
    {
        private NativeArray<BoidsData> _boidsDatasWrite;
        [ReadOnly] private readonly NativeArray<float3> _boidsForceRead;
        [WriteOnly] private NativeArray<Matrix4x4> _instanceMatrices;

        [ReadOnly] private readonly float3 _simulationAreaCenter;
        [ReadOnly] private readonly float3 _simulationAreaScale;
        [ReadOnly] private readonly float _avoidWallWeight;

        [ReadOnly] private readonly float _deltaTime;
        [ReadOnly] private readonly float _maxSpeed;
        [ReadOnly] private readonly float3 _instanceScale;

        public ApplySteerForceJob(
            NativeArray<BoidsData> boidsDatasWrite,
            NativeArray<float3> boidsForceRead,
            NativeArray<Matrix4x4> instanceMatrices,
            float3 simulationAreaCenter,
            float3 simulationAreaScale,
            float avoidWallWeight,
            float deltaTime,
            float maxSpeed,
            float3 instanceScale
        )
        {
            _boidsDatasWrite = boidsDatasWrite;
            _boidsForceRead = boidsForceRead;
            _instanceMatrices = instanceMatrices;
            _simulationAreaCenter = simulationAreaCenter;
            _simulationAreaScale = simulationAreaScale;
            _avoidWallWeight = avoidWallWeight;
            _deltaTime = deltaTime;
            _maxSpeed = maxSpeed;
            _instanceScale = instanceScale;
        }

        public void Execute(int ownIndex)
        {
            var boidsData = _boidsDatasWrite[ownIndex];
            var force = _boidsForceRead[ownIndex];

            force += AvoidAreaEdge(boidsData.Position, _simulationAreaCenter, _simulationAreaScale) * _avoidWallWeight;

            var velocity = boidsData.Velocity + (force * _deltaTime);
            boidsData.Velocity = MathematicsUtility.Limit(velocity, _maxSpeed);
            boidsData.Position += velocity * _deltaTime;

            _boidsDatasWrite[ownIndex] = boidsData;

            var rotationY = math.atan2(boidsData.Velocity.x, boidsData.Velocity.z);
            var rotationX = (float) -math.asin(boidsData.Velocity.y / (math.length(boidsData.Velocity.xyz) + 1e-8));
            var rotation = quaternion.Euler(rotationX, rotationY, 0);
            _instanceMatrices[ownIndex] = float4x4.TRS(boidsData.Position, rotation, _instanceScale);
        }

        private static float3 AvoidAreaEdge(float3 position, float3 simulationAreaCenter, float3 simulationAreaScale)
        {
            var acc = new float3();

            acc.x = position.x < simulationAreaCenter.x - simulationAreaScale.x
                ? acc.x + 1.0f
                : acc.x;

            acc.x = position.x > simulationAreaCenter.x + simulationAreaScale.x
                ? acc.x - 1.0f
                : acc.x;

            acc.y = position.y < simulationAreaCenter.y - simulationAreaScale.y
                ? acc.y + 1.0f
                : acc.y;

            acc.y = position.y > simulationAreaCenter.y + simulationAreaScale.y
                ? acc.y - 1.0f
                : acc.y;

            acc.z = position.z < simulationAreaCenter.z - simulationAreaScale.z
                ? acc.z + 1.0f
                : acc.z;

            acc.z = position.z > simulationAreaCenter.z + simulationAreaScale.z
                ? acc.z - 1.0f
                : acc.z;

            return acc;
        }
    }
}

全探索Boids

実装

全探索なので、各個体は全ての個体を見て自身に与える力を求めます。計算量は O(n2) になります。

AllSearchBoidsSimulatorJob

using Boids.Mathematics;
using Unity.Burst;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;
using UnityEditor.U2D;

namespace Boids.Job
{
    [BurstCompile]
    internal struct AllSearchBoidsSimulatorJob : IJobParallelFor
    {
        [ReadOnly] private readonly float _cohesionWeight;
        [ReadOnly] private readonly float _cohesionAffectedRadiusSqr;
        [ReadOnly] private readonly float _separateWeight;
        [ReadOnly] private readonly float _separateAffectedRadiusSqr;
        [ReadOnly] private readonly float _alignmentWeight;
        [ReadOnly] private readonly float _alignmentAffectedRadiusSqr;

        [ReadOnly] private readonly float _maxSpeed;
        [ReadOnly] private readonly float _maxForceSteer;

        [ReadOnly] private readonly NativeArray<BoidsData> _boidsDatasRead;
        [WriteOnly] private NativeArray<float3> _boidsSteerWrite;

        public AllSearchBoidsSimulatorJob(
            float cohesionWeight,
            float cohesionAffectedRadiusSqr,
            float separateWeight,
            float separateAffectedRadiusSqr,
            float alignmentWeight,
            float alignmentAffectedRadiusSqr,
            float maxSpeed,
            float maxForceSteer,
            NativeArray<BoidsData> boidsDatasRead,
            NativeArray<float3> boidsSteerWrite
        )
        {
            _cohesionWeight = cohesionWeight;
            _cohesionAffectedRadiusSqr = cohesionAffectedRadiusSqr;
            _separateWeight = separateWeight;
            _separateAffectedRadiusSqr = separateAffectedRadiusSqr;
            _alignmentWeight = alignmentWeight;
            _alignmentAffectedRadiusSqr = alignmentAffectedRadiusSqr;
            _maxSpeed = maxSpeed;
            _maxForceSteer = maxForceSteer;
            _boidsDatasRead = boidsDatasRead;
            _boidsSteerWrite = boidsSteerWrite;
        }

        public void Execute(int ownIndex)
        {
            var ownPosition = _boidsDatasRead[ownIndex].Position;
            var ownVelocity = _boidsDatasRead[ownIndex].Velocity;

            var cohesionPositionSum = new float3();
            var cohesionTargetCount = 0;

            var separateRepluseSum = new float3();
            var separateTargetCount = 0;

            var alignmentVelocitySum = new float3();
            var alignmentTargetCount = 0;

            for (int targetIndex = 0; targetIndex < _boidsDatasRead.Length; ++targetIndex)
            {
                if (ownIndex == targetIndex)
                {
                    continue;
                }

                var targetPosition = _boidsDatasRead[targetIndex].Position;
                var targetVelocity = _boidsDatasRead[targetIndex].Velocity;

                var diff = ownPosition - targetPosition;
                var distanceSqr = math.dot(diff, diff);

                if (distanceSqr <= _cohesionAffectedRadiusSqr)
                {
                    cohesionPositionSum += targetPosition;
                    cohesionTargetCount++;
                }

                if (distanceSqr <= _separateAffectedRadiusSqr)
                {
                    separateRepluseSum += math.normalize(diff) / math.sqrt(distanceSqr);
                    separateTargetCount++;
                }

                if (distanceSqr <= _alignmentAffectedRadiusSqr)
                {
                    alignmentVelocitySum += targetVelocity;
                    alignmentTargetCount++;
                }
            }

            var cohesionSteer = new float3();
            if (cohesionTargetCount > 0)
            {
                var cohesionPositionAverage = cohesionPositionSum / cohesionTargetCount;
                var cohesionDirection = cohesionPositionAverage - ownPosition;
                var cohesionVelocity = math.normalize(cohesionDirection) * _maxSpeed;
                cohesionSteer = MathematicsUtility.Limit(cohesionVelocity - ownVelocity, _maxForceSteer);
            }

            var separateSteer = new float3();
            if (separateTargetCount > 0)
            {
                var separateRepulseAverage = separateRepluseSum / separateTargetCount;
                var separateVelocity = math.normalize(separateRepulseAverage) * _maxSpeed;
                separateSteer = MathematicsUtility.Limit(separateVelocity - ownVelocity, _maxForceSteer);
            }

            var alignmentSteer = new float3();
            if (alignmentTargetCount > 0)
            {
                var alignmentVelocityAverage = alignmentVelocitySum / alignmentTargetCount;
                var alignmentVelocity = math.normalize(alignmentVelocityAverage) * _maxSpeed;
                alignmentSteer = MathematicsUtility.Limit(alignmentVelocity - ownVelocity, _maxForceSteer);
            }

            _boidsSteerWrite[ownIndex] =
                cohesionSteer * _cohesionWeight +
                separateSteer * _separateWeight +
                alignmentSteer * _alignmentWeight;
        }
    }
}

結果

5000匹と10000匹を動かした結果になります。

5000匹はそこまで重くはないですが、10000匹まで行くと25fpsまで落ちてしまいます。

Profilerを見ると AllSearchBoidsSimulatorJob がボトルネックになっています。

個体数 5000匹 10000匹
動作
Profiler
fps 約80fps 約25fps
Updateの時間 9.13ms 36.82ms



近傍探索Boids

NativeMultiHashMapについて

Struct NativeMultiHashMap<TKey, TValue> | Package Manager UI website

NativeContainerの一つで、キーに対して複数の値を持つことができます。

NativeMultiHashMapのコンストラクタで格納するデータのサイズと AllocatorManager.AllocatorHandle を指定します。（例のコードでは Allocator.TemJob）

new NativeMultiHashMap<TKey, TValue>(instanceCount, Allocator.TempJob);


要素の追加は Add が使えますが、Job内で要素を追加する場合は NativeMultiHashMap<TKey, TValue>.ParallelWriter で行う必要があります。

var job = new HogeJob { nativeMultiHashMap.AsParallelWriter() };
.....
nativeMultiHasmMapParallelWriter.Add(key, value);


要素へのアクセス方法ですが、NativeMultiHashMapIterator<TKey> を使います。

TryGetFirstValue でイテレータと最初の要素を取得して、TryGetNextValue で次の要素を取得していきます。要素の取得に失敗した場合は false が返されます。

for (var success = nativeMultiHashMap.TryGetFirstValue(key, out var value, out var iterator);
     success;
     success = nativeMultiHashMap.TryGetNextValue(out value, ref iterator))
{
......
}


実装

始めにシミュレーション空間を格子上に分割して、各個体が所属する格子に個体のIndexを NativeMultiHashMap 保存します。

格子の座標計算ではシミュレーション空間内に限定し、範囲外も空間内に納めています。

NeighborSearchBoidsSetting.Calculate

        public void Calculate(NativeArray<Matrix4x4> instanceMatricesArray, BoidsData[] boidsDatas)
        {
            var instanceCount = boidsDatas.Length;
            var boidsDataArray = new NativeArray<BoidsData>(instanceCount, Allocator.TempJob);
            var gridMultiHashMap = new NativeMultiHashMap<int3, int>(instanceCount, Allocator.TempJob);

            boidsDataArray.CopyFrom(boidsDatas);

            var registerInstanceToGridJob = new RegisterNeighborSearchGridJob
            (
                gridMultiHashMap.AsParallelWriter(),
                boidsDataArray,
                _neighborSearchBoidsSetting.MinNeighborSearchGridPoint,
                _neighborSearchBoidsSetting.NeighborSearchGridScale,
                _neighborSearchBoidsSetting.NeighborSearchGridCount
            );

            var registerInstanceToGridHandler = registerInstanceToGridJob.Schedule(instanceCount, 0);
            registerInstanceToGridHandler.Complete();
            .........
            .........

RegisterNeighborSearchGridJob

using Boids.Mathematics;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;

namespace Boids.Job
{
    internal struct RegisterNeighborSearchGridJob : IJobParallelFor
    {
        [WriteOnly] private NativeMultiHashMap<int3, int>.ParallelWriter _gridWriter;
        [ReadOnly] private readonly NativeArray<BoidsData> _boidsDatasRead;
        [ReadOnly] private readonly float3 _minGridPoint;
        [ReadOnly] private readonly float _gridScale;
        [ReadOnly] private readonly int3 _gridCount;
        
        public RegisterNeighborSearchGridJob(
            NativeMultiHashMap<int3, int>.ParallelWriter gridWriter,
            NativeArray<BoidsData> boidsDatasRead,
            float3 minGridPoint,
            float gridScale,
            int3 gridCount)
        {
            _gridWriter = gridWriter;
            _boidsDatasRead = boidsDatasRead;
            _minGridPoint = minGridPoint;
            _gridScale = gridScale;
            _gridCount = gridCount;
        }

        public void Execute(int index)
        {
            var boidsDataPosition = _boidsDatasRead[index].Position;

            var gridIndex = MathematicsUtility.CalculateGridIndex(boidsDataPosition, _minGridPoint, _gridScale, _gridCount);

            _gridWriter.Add(gridIndex, index);
        }
    }
}

MatematicsUtility 

        internal static int3 CalculateGridIndex(float3 position, float3 minGridPoint, float gridScale, int3 gridCount)
        {
            // MEMO: 範囲外のものは範囲内のGridに収める
            return new int3(
                (int) math.clamp((position.x - minGridPoint.x) / gridScale, 0, gridCount.x),
                (int) math.clamp((position.y - minGridPoint.y) / gridScale, 0, gridCount.y),
                (int) math.clamp((position.z - minGridPoint.z) / gridScale, 0, gridCount.z)
            );
        }


次にBoidsの操舵力を求める処理についてです。　

個体が所属する格子を求めて、周囲の格子から個体のIndexを取得します。これにより、周囲の個体のみで操舵力を求められます。

それ以外の処理は基本全探索と同じです。（共通部分は省略）

NeighborSearchBoidsSimulatorJob

using Boids.Mathematics;
using Unity.Burst;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;

namespace Boids.Job
{
    [BurstCompile]
    internal struct NeighborSearchBoidsSimulatorJob : IJobParallelFor
    {
        [ReadOnly] private readonly float _cohesionWeight;
        [ReadOnly] private readonly float _cohesionAffectedRadiusSqr;
        [ReadOnly] private readonly float _separateWeight;
        [ReadOnly] private readonly float _separateAffectedRadiusSqr;
        [ReadOnly] private readonly float _alignmentWeight;
        [ReadOnly] private readonly float _alignmentAffectedRadiusSqr;

        [ReadOnly] private readonly float _maxSpeed;
        [ReadOnly] private readonly float _maxForceSteer;

        [ReadOnly] private NativeMultiHashMap<int3, int> _grid;
        [ReadOnly] private readonly float _gridScale;
        [ReadOnly] private readonly int3 _gridCount;
        [ReadOnly] private readonly float3 _minGridPoint;

        [ReadOnly] private readonly NativeArray<BoidsData> _boidsDatasRead;
        [WriteOnly] private NativeArray<float3> _boidsSteerWrite;

        public NeighborSearchBoidsSimulatorJob(
            float cohesionWeight,
            float cohesionAffectedRadiusSqr,
            float separateWeight,
            float separateAffectedRadiusSqr,
            float alignmentWeight,
            float alignmentAffectedRadiusSqr,
            float maxSpeed,
            float maxForceSteer,
            NativeMultiHashMap<int3, int> grid,
            float gridScale,
            int3 gridCount,
            float3 minGridPoint,
            NativeArray<BoidsData> boidsDatasRead,
            NativeArray<float3> boidsSteerWrite
        )
        {
            _cohesionWeight = cohesionWeight;
            _cohesionAffectedRadiusSqr = cohesionAffectedRadiusSqr;
            _separateWeight = separateWeight;
            _separateAffectedRadiusSqr = separateAffectedRadiusSqr;
            _alignmentWeight = alignmentWeight;
            _alignmentAffectedRadiusSqr = alignmentAffectedRadiusSqr;
            _maxSpeed = maxSpeed;
            _maxForceSteer = maxForceSteer;
            _grid = grid;
            _gridScale = gridScale;
            _gridCount = gridCount;
            _minGridPoint = minGridPoint;
            _boidsDatasRead = boidsDatasRead;
            _boidsSteerWrite = boidsSteerWrite;
        }

        public void Execute(int ownIndex)
        {
            // 全探索と同じ

            var gridIndex = MathematicsUtility.CalculateGridIndex(ownPosition, _minGridPoint, _gridScale, _gridCount);

            int minX = gridIndex.x - 1 < 0 ? 0 : gridIndex.x - 1;
            int minY = gridIndex.y - 1 < 0 ? 0 : gridIndex.y - 1;
            int minZ = gridIndex.z - 1 < 0 ? 0 : gridIndex.z - 1;

            int maxX = gridIndex.x + 1 >= _gridCount.x ? gridIndex.x : gridIndex.x + 1;
            int maxY = gridIndex.y + 1 >= _gridCount.y ? gridIndex.y : gridIndex.y + 1;
            int maxZ = gridIndex.z + 1 >= _gridCount.z ? gridIndex.z : gridIndex.z + 1;

            for (int x = minX; x <= maxX; ++x)
            for (int y = minY; y <= maxY; ++y)
            for (int z = minZ; z <= maxZ; ++z)
            {
                var key = new int3(x, y, z);

                for (var success = _grid.TryGetFirstValue(key, out var targetIndex, out var iterator);
                     success;
                     success = _grid.TryGetNextValue(out targetIndex, ref iterator))
                {
                    if (ownIndex == targetIndex)
                    {
                        continue;
                    }

                    var targetPosition = _boidsDatasRead[targetIndex].Position;
                    var targetVelocity = _boidsDatasRead[targetIndex].Velocity;

                    // 全探索と同じ

                }
            }

            // 全探索と同じ
    }
}


結果

同じく5000匹と10000匹の実行結果になります。

全探索に比べてかなり高速になったことがわかります。また、5000匹の場合は操舵力の計算を求めるのに1ms以下に抑えられております。

個体数 5000匹 10000匹
動作
Profiler
fps 約240fps 約130fps
Updateの時間 1.55ms 4.64ms



比較

全探索と近傍探索で操舵力を求めるのにかかった時間を比較してみます。

（時間は添付した画像から、近傍探索は 格子に登録する時間+操舵力を計算する時間 ）

5000匹 10000匹
全探索 8.6ms 36.1ms
近傍探索 0.4ms+0.7ms=1.1ms 0.7ms+3.2ms=3.9ms
倍率 7.8倍 9倍

表からわかる通り、10倍近く高速になりました。

全探索では計算量 O(n2) だったのに対して、近傍探索では計算量がおおよそ O(n) になるので大幅に高速化できました。



まとめ

NativeMultiHashMapを使うことでここまで最適化できたことに驚きでした。

これまでBoidsシミュレーションをコンテンツで扱うのは少し難しいと感じていましたが、この結果からそこまで躊躇しなくても良いのではないかと考えております。

今後Boidsで何かしらコンテンツを作っていくので、また何か知見を得られたらまとめます。