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

Should I bother with spatial partitioning?

Discussion in 'Scripting' started by BakeMyCake, May 28, 2019.

  1. BakeMyCake

    BakeMyCake

    Joined:
    May 8, 2017
    Posts:
    175
    Hi people,
    In my project I have an average of 70 objects being evaluated against each other based on proximity. These objects are laid out sequentially in memory to promote cache hits. At the moment I just iterate the array and do a coarse early exit sphere test before doing the heavy stuff.

    My question is would there be any reasonable performance gain from using something like a k-d tree?

    I have some doubts because the object count isn't very high in my case, and I'm wondering if any performance gained from doing less lookup would be eaten by the maintenance of the spatial partitioning container of choice when the objects change position and the less friendly memory layout.
     
  2. csofranz

    csofranz

    Joined:
    Apr 29, 2017
    Posts:
    1,556
    I recommend you run the Profiler to find out where you lose most of your cycles. I'm betting that the visibility calculations and rendering Pipeline is using up much more in terms of performance than anything you can gain from switching to tree structures in your objects. You should only start thinking about this kind of optimizations when you have exhausted all other venues, picked all the low-hanging fruit, and the profiler indicates that this is the next item to tackle.

    tl;dr: No.
     
  3. BakeMyCake

    BakeMyCake

    Joined:
    May 8, 2017
    Posts:
    175
    Can't find any way to make Unity do its' thing any faster I'm afraid. At least it doesn't look to me that way. Even if I knew for a fact that there's something Unity does slow in any of it's mandatory functions, I wouldn't be able to address it. I can only optimize my code, hence the question.
     
  4. mgear

    mgear

    Joined:
    Aug 3, 2010
    Posts:
    9,350
    you can often make basic calculations faster by caching everything (transforms, array sizes..)
    and not using unity mathf or vector3 maths, or manually using .x, .y, .z components from vectors.

    can also calculate distances only when object is moved, or only every 1second, or in another thread completely. (and of course there is unity jobs, ecs)

    maybe you can post your script there to check, but in any case, deep profiler would would say what to look for.
     
  5. hippocoder

    hippocoder

    Digital Ape

    Joined:
    Apr 11, 2010
    Posts:
    29,723
    Seems extreme to optimise 70 objects in 2019. What did the profiler say?
     
    AlejMC and Kurt-Dekker like this.
  6. BakeMyCake

    BakeMyCake

    Joined:
    May 8, 2017
    Posts:
    175
    Code (CSharp):
    1. int bitIndex2 = 1;
    2. for (int i = 0; i < mineCount; ++i)
    3. {
    4.     Sphere sphere = MineColliders.CoarseColliders[i];
    5.     if(!GeometryUtils.SpheresCollide(playerCollider, sphere))
    6.         continue;
    7.  
    8.     Box box = MineColliders.Colliders[i];
    9.     if (!GeometryUtils.SphereCollideBox(playerCollider, box))
    10.         continue;
    11.     MinesToResolve[bitIndex2] = true;
    12.     PlayerToResolve = true;
    13.     bitIndex2 *= 2;
    14. }
    I've attached a profiler snapshot. Captured on a mobile device.
     

    Attached Files:

  7. mgear

    mgear

    Joined:
    Aug 3, 2010
    Posts:
    9,350
    screenshot from profiler (from the biggest spike),
    looks like your script is not too slow there (if this is the one your check is running) *deep profiler could show more details
    upload_2019-5-28_21-49-30.png
     
  8. mx3307

    mx3307

    Joined:
    Jul 8, 2019
    Posts:
    8
    Hi, did you end up using spatial partitioning? I am doing something similar, where every character loops through all the opposing characters and calculates distance. I am using Vector2.distance to calculate the distance. After around 15 characters or more, it starts to lag, at it goes around 30 to 15 fps.
    If you did use spatial partitioning, where did you look the information about it? I am looking for it but many are really complicated for me to understand.
     
  9. BakeMyCake

    BakeMyCake

    Joined:
    May 8, 2017
    Posts:
    175
    Hello, I'm afraid I never went through with that plan. I've arrived to the same conclusion as you did in that to do spatial partitioning well(I don't consider splitting the world into evenly sized volumes containing potential colliders a good solution) you will likely need a complicated system, aka a nightmare to maintain.

    I remember I've benchmarked a scene with collision enabled and disabled and the difference wasn't even conclusively measurable. With the insight of a half a year in the future version of myself I can say that in your case(and mine) there are plenty of places where you could spend less time to get better performance gains. Jobs, scriptable render pipelines and memoization being some examples.

    On a side note: Vector2 has a faster alternative for distance checks. You can subtract vectors and check the squared magnitude against a squared distance https://docs.unity3d.com/ScriptReference/Vector2-sqrMagnitude.html The difference is peanuts though. This will not win you a single fps point in general purpose gamedev.

    Based on what you've described, your problem lies elsewhere. Hope you find it soon.
     
    markythemurloc and DeanNemphos like this.