Unity Trick: Find closest Object fast! (k-d Tree)

[@maruthemonkey]

Hi Ditzel, as a duck-tape-and-hatchet-kinda amateur programmer, there are a few basic things I do not understand about this approach, before even diving into the code. As I understand it, data structured in a k-d tree facilitates the search for an element by reducing the (maximum) number of queries to the number of child nodes going from (and including) the root node, instead of querying every single element. >> just talking about a single dimension now

[@BuffaloSanta]

Awesome tutorial! I learned about kd trees in school and always wondered how I could use them in unity. Excited to try this out

[@toneit8016]

I've quickly implemented this into my 3rd person shooter. You are a GOD amongst men! It works flawelessly!

[@jacobzak7494]

ok but how? the component RandomWalk is missing from unity

[@rcdemoral1982]

Thank you! This is very useful. I may be 4 years too late but exactly what I'm looking for. Thank you!

[@TREXYT]

can you implement kdtree.remove function please ? we have kdtree.add but remove is missing

[@whitetiana3022]

wish you had recorded this in a resolution where i could actually see the difference between = and -

[@s.c9063]

you saved me probably a weeks worth of trouble man, thank you so much.

[@CamoflaugeDinosaue]

I'm curious how much of the frame drop was from the gizmo line drawing.

[@crimmson27]

It was not from the gizmo but from the "Update" Line "the script is trying to find the closest object at every frame, and this causes the CPU to overload a bit. To fix this you can make a cooldown just like Damage Cooldown but using like 0.1 seconds or less.

[@MathsPlusGames]

What if a unit gets destroyed? Cant remove object from list while iterating no?

[@AlexanderHarris]

That’s true. I guess what you could do is give each object a boolean value that marks a white ball for deletion, and if that boolean is set to true, skip it in the loop. Then once the loop is over, destroy all objects that are marked. I’m sure there’s a better solution, but that’s what I could come up with off the top of my head.

[@AlexanderHarris]

Oh, alternatively just don’t use a foreach loop. Use a for loop instead. That should fix your problem.

[@BrokenNat]

is it possible to find the seccond closest object with kdTree?

[@FourKelvin]

Hi Ditzel, Is your code CC0, or what license would that be? Essentially can I just take it and use it in an open source project? If yes, do I need to credit you somehow?

[@DitzelGames]

No Credit needed. Normally I use MIT

[@EricDaily]

This is awesome!!! thank you for sharing :)

[@lintonfor4035]

instead of looping thorugh all the balls, each ball could just use a sphere cast to find the ones nearest and loop thorugh those

[@HuySoraTran]

That will actually be slower depend on your sphere radius, it called kNN search

[@floatingchimney]

@Linton FOR, That might be convenient, but it would be even worse performance-wise. Detecting collisions is more expensive than simply calculating the distance between two points.

[@floky001]

@@floatingchimneyNot quite, it depends. If you do a Physx Overlap Sphere for example to get neighbors within a radius around an object, the Physx engine already has spatial partitioning and spatial query acceleration data structures low level. So in this exact example it can work even faster. Not to mention the overlap sphere already has a jobified command approach supported built-in so you can batch multiple overlap queries simultaneously on a separate job. But this is just an extra approach and it doesn’t beat the purpose of this example video where it offers a sample raw K-d Tree approach which is still very useful to know when you don’t have the physx colliders and rigidbodies setup. ✌️

[@floatingchimney]

@@floky001 lol what? My head hurts.

[@floky001]

@@floatingchimney give it a try for this exact example. 😉 No need to believe me.

[@mrabtruse]

I might try to convert the script to Jobsystem for more faster speed. but to be blunt you should instance the balls would show it's try potential

[@greenapplecat629]

Thank you for posting the code!

[@Shasaur]

Dwarf Fortress background music vibes

[@jacobzak7494]

how tf you add new component RandomWalk and why there is no script for that? I can't use the kdTree without this component

[@edwarddewolf3392]

I would need the closest 4 objects in a 3D space?

[@alejmc]

I have this exact same question, solvable in an efficient way. I would guess that the Kd-Tree when it updates it keeps a list or re-orders things by distance maybe? I’m trying to learn but it still isn’t clear to me for your exact question if quadtrees/octrees would be better suited in the end?

[@abdelrahmanmohammed9405]

Any advice on how to use this with the jobs system?

[@qquarzwar]

what if I wanted to find the closest 3?

[@JohnnyThousand605]

Brilliant! Thank you very much for this =)

[@littlearvin1641]

What's in "RandomWalk" ? I can't get my head around with templates/lists.

[@wiiu7640]

I'm wondering the same thing, I'll let you know when I find something.

[@wiiu7640]

Okay, after some searching I believe that "RandomWalk" is a class that takes in arguments based on predefined parameters. Basically, it defines what an item in a list looks like. You can find some more information here: learn.unity.com/tutorial/lists-and-dictionaries?signup=true#5c89434eedbc2a0d28f48a70

[@AuditorsUnited]

using System.Linq; GameObject GetNearestTarget() { //so lets say you want the closest target from a array (in this case all Gameobjects with Tag "enemy") and let's assume this script right now is on the player (or the object with which the distance has to be calculated) return GameObject.FindGameObjectsWithTag("deer").Aggregate((o1, o2) => Vector3.Distance(o1.transform.position, this.transform.position) > Vector3.Distance(o2.transform.position, this.transform.position) ? o2 : o1); }

[@DitzelGames]

Did you try how the runtime looks like?

[@AuditorsUnited]

@@DitzelGames no just saw this and its a problem i had to solve so i left an example.. i have solved this in many forms its not the fastest or best but its small and simple..sort of.. i hope it helps some passer by

[@VanOri]

@@AuditorsUnited Thanks, I will use this but with Layers instead of Tags :D

[@martinhromadka7671]

It certainly made my code cleaner, thanks.

[@mauriciopartnoy2789]

I believe using (pos0-pos1).sqrMagnitude for the distance comparisons is slightly more performant than using Vector3.Distance as you don't really need the distance itself, only to know if it's greater/less than. Just wanted to point it out as I didn't saw it mentioned in the comments.

[@LoniekSenpai]

Hey, i'm having a problem, if doesn't find closest but first in list object. I have all objects in list set activa false and they appear in time and gets active true and the closest function just look for the newest set active true

[@SpeedCoder2000]

Hi. Thanks for your amazing script. Is very useful, but i have a question. ¿Is there a way to get the 'N' nearest objects to a point?. In my case at this moment i need to get the two nearest objects to the player's position.

[@SpeedCoder2000]

i was thinking to change the if inside the _findClosest method: if (nodeDist < nearestDist) for something like this: if (nodeDist < nearestDist && current.component.transform.gameobject.isActive) so i would execute the findclosest one time and disable the item founded , and then execute the find method again to find the second one. ¿do you think is a good solution?.

[@timurradman3999]

You don't use Vector3.Distance to find the closest object, it's too expensive

[@user-xr5rq6ci6q]

can you show us the random walk script ?

[@solalcoqueron8492]

Do you have a version to find the furthest object?

[@goblinslayer6375]

Yes

[@SpoookyChannel]

Heads up, this is actually a slower method cause you're calling distance twice: one for the IF and one for the VALUE. Save it to a variable before the if statement and reuse the variable. It will cut your calculations in half. Distance is expensive cause it uses roots.

[@rencis987]

did you watch the video?

[@audreyjensen666]

Bro he changes it at 03:20

Hi, where can I download the full balls example? Thanks

[@wiiu7640]

I get this error: unity The type 'system' cannot be used as type parameter 'T' in the generic type or method 'KdTree'. There is no implicit reference conversion from 'system' to 'UnityEngine.Component'. when using this code: protected KdTree systems = new KdTree(); is wrong The basics of what I am doing is enabling a model solar system when the player gets close to it and disabling the rest of the solar systems. Please help. Thank You!

[@wiiu7640]

I managed to figure out why I was getting this error, the problem is that you must replace ": monodevelop" with ": component" to signal that it is a component which is what his script takes. This is what that line of code looked like for mine: public class system : Component Hope this helps someone!

[@GeoGames_Dev]

Can you make more tennis related stuff please I m trying to make one for console and its pretty hard for me especially some scripting cause i do not know much but I stay positive and keep it going slowly slowly!! Good vid as always wish you the best on soccer royale its fun!

[@seppukun208]

yeah but how does the kd tree work?

[@pirateskeleton7828]

I'm going to try and implement your script in my project. will let you know if it works out.

[@DitzelGames]

I updated the script. There is a method called "exceptself" now.

[@bakor-org]

@@DitzelGames where is the updated script please?

[@FifiMunson]

too blurry I can't read the code.

[@pirateskeleton7828]

How would you go about modifying your code so that objects within the same tree can search for their nearest neighbor without finding themselves?

[@DitzelGames]

I updated the script. There is a method called "exceptself" now.

[@latartine6753]

​@@DitzelGames Looks like it no longer exists ? :/ Maybe there was a problem ?

[@latartine6753]

Well, for those looking for a fix, I figured out a way by adding "&& nodeDist != 0" at "if (nodeDist < nearestDist)" and it works fine. Objects are not detected when they are on the exact same position but in some cases like me, it doesn't really matter. :)

[@zhatar4214]

What do you use to record your screen? It's kinda blurry

[@zhatar4214]

especially the text

[@DitzelGames]

I will work on that.

[@wiiu7640]

@@DitzelGames Zooming in on the text will greatly reduce blurs

[@sammysammy8493]

Very useful for my rts.

[@kumsuTalk]

thanks for the code really helpful And Plz add find an index to the Code. I see remove at in the code. but missing indexOF

[@Bilolado]

music?

[@DitzelGames]

Darude - Sandstorm

[@walney2008]

you speak game zlap.ip ?

[@kranistom]

You did not expain

[@masjawa3349]

Thankyou, may God bless you my friend... 🤩🤩🤩 If someone need to remove spesific item in list (maybe like enemy dead, so it shouldn't be included in list anymore). You can do such this.. public void removeFromList(EnemyData enemyData) { int position = allEnemies.ToList().IndexOf(enemyData); allEnemies.RemoveAt(position); }

[@RimuruDev]

Благодарю😘

[@MrFaciio]

Thank you

[@glitchover9894]

Transform GetClosest(Transform[] arrayOfObject) { Transform _transform = null; float minDist = Mathf.Infinity; Vector3 currentPos = transform.position; foreach (Transform t in arrayOfObject) { float dist = Vector3.Distance(t.position, currentPos); if (dist < minDist) { _transform = t; minDist = dist; } } return _transform ; }

[@jahn_star]

thnx

[@nebelnice8431]

richtiger deutscher "null" anstatt einfach sero

[@timurradman3999]

What a waste of good 4 minutes :)

[@mosth8ed]

As much as I would like to watch this, that white ide is blinding.

[@snake555510]

very inefficient to do this better use sphere overlap

[@DitzelGames]

Wait. How should a sphere overlap been faster?

[@supertenchoo4271]

can you explain the first approach why most of people use MathF.Infinity/float.MaxValue am wondering how this is assigned to the closet distance when distance is less than Mathf.Infinity/float.MaxValue

[@audreyjensen666]

In the algorithm we assume that the nearest distance is the maximum distance possible. And if we find any shorter distance, then we pick that new shorter distance as the smallest distance.