One remark: It's good only for static objects that don't move a lot, otherwise you should rebuild your quad tree each time on object position changes to hold it in actual state. For dynamic objects the Spatial Hashing more preferable if you ask
Unless coded incorrectly a Hierarchical Spatial Hash Grid should be way more performant then a Quad Tree, especially for moving objects because insertions/deletions have a reasonable cost (especially if using balanced tree) on top of the traversal and AABB check cost.
Unless coded incorrectly a Hierarchical Spatial Hash Grid should be way more performant then a Quad Tree, especially for moving objects because insertions/deletions have a reasonable cost (especially if using balanced tree) on top of the traversal and AABB check cost.
Oh that's amazing, this explains why none of the package.json has any dependencies in the repo lol Are you following some guide or course or other resources?
I think Albion online does this but in scale to support open world gameplay. Each cell has a corresponding servers that manages it. Imagine each cell is mapped to a single region, e.g. Asia, US, Europe.
it's hard to say without benchmarking. a quad tree is good for non uniformly distributed game objects. when playing this game, I've noticed many zombies will group together as they try to path find to the player. IMO this means non uniform distribution. Additionally, the collidable trees in the game are a little non uniform. it's one of those things where you won't know unless you benchmark, and after you benchmark I would be the difference isn't that great after all.
From when I’ve read online, you put it in the parent Cell if it overlaps two of the boundary boxes. I think this would mean that the capacity can go over if you have a bunch of objects that lay on line between two cells.
I didn't follow your series from the beginning, but why not have a map of position as the key and content as the value and then you just add/subtract 1 from the player's position and see if it exists on the map which would mean that the player is about to touch the thing in that position, IDK how the "touching" approximation work in your game. - Good Game
The quad tree is used to reduce the checks required to see what objects are colliding in the game. Having a map where every object that can move constantly updating keys is ridiculously inefficient in comparison.
@@afailable to be fair, what they're suggesting is essentially (at least conceptually) what a spatial hash is. I feel like both are valid depending on how spread out the enemies are (quadtree probably performs better on average if they're spread out equally) and whatnot. From some searches there seems to be benchmark and study comparing these two so you can look at that and use them depending on your scenarios.
work on your side project 30 minutes to an hour a day. Everyone can at least find 30 minutes of free time a day, some choose to use it on tv or gaming, I choose to code with that time.
![Felix "Unfair" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/Oswujxm2Ag0/mqdefault.jpg)
Just as added note for those interested: the version of this for 3d is called octree
very cool, I'm sure that's used a lot for 3d games
Octrees are really fun to make
so that's basically a 2D binary tree, pretty neat.
One remark: It's good only for static objects that don't move a lot, otherwise you should rebuild your quad tree each time on object position changes to hold it in actual state. For dynamic objects the Spatial Hashing more preferable if you ask
that's a good point!
Unless coded incorrectly a Hierarchical Spatial Hash Grid should be way more performant then a Quad Tree, especially for moving objects because insertions/deletions have a reasonable cost (especially if using balanced tree) on top of the traversal and AABB check cost.
You’re killin it babe!!! Love it
This is so cool! Inspires me to make something like this
What was the performance gain? Did you measure before and after? Or was it just for fun?
Just for fun, no measurements
Unless coded incorrectly a Hierarchical Spatial Hash Grid should be way more performant then a Quad Tree, especially for moving objects because insertions/deletions have a reasonable cost (especially if using balanced tree) on top of the traversal and AABB check cost.
what tech stack are you using to build your game?
Typescript, from scratch
Oh that's amazing, this explains why none of the package.json has any dependencies in the repo lol
Are you following some guide or course or other resources?
Haven’t watched yet, but guessing quad trees from diagram, 🍿 time
I think Albion online does this but in scale to support open world gameplay. Each cell has a corresponding servers that manages it. Imagine each cell is mapped to a single region, e.g. Asia, US, Europe.
Before watching, I'm guessing it's a quadtree based of the thumbnail, it's commonly used in gamedev, for collisions and other things
LFG I'm gonna make it
you're in the club now
You can convert the x,y to a geohash string and do O1 lookup
I would be surprised if a quadtree performed better than a spatial hash for this type of game.
it's hard to say without benchmarking. a quad tree is good for non uniformly distributed game objects. when playing this game, I've noticed many zombies will group together as they try to path find to the player. IMO this means non uniform distribution. Additionally, the collidable trees in the game are a little non uniform.
it's one of those things where you won't know unless you benchmark, and after you benchmark I would be the difference isn't that great after all.
What if a data point falls in two quadrants? What do you do then?
From when I’ve read online, you put it in the parent Cell if it overlaps two of the boundary boxes. I think this would mean that the capacity can go over if you have a bunch of objects that lay on line between two cells.
This is great stuff right here
Can you please make a video how to download a csv on FE with very large data?
Can you please show the production level approach?
Looks like it's a collision map that uses breadth first search
wow, how algorithms works in frontend and game..
I didn't follow your series from the beginning, but why not have a map of position as the key and content as the value and then you just add/subtract 1 from the player's position and see if it exists on the map which would mean that the player is about to touch the thing in that position, IDK how the "touching" approximation work in your game.
- Good Game
The quad tree is used to reduce the checks required to see what objects are colliding in the game. Having a map where every object that can move constantly updating keys is ridiculously inefficient in comparison.
@@afailable to be fair, what they're suggesting is essentially (at least conceptually) what a spatial hash is. I feel like both are valid depending on how spread out the enemies are (quadtree probably performs better on average if they're spread out equally) and whatnot. From some searches there seems to be benchmark and study comparing these two so you can look at that and use them depending on your scenarios.
that's kinda smart
How would you recommend balancing building side projects with a full time job?
work on your side project 30 minutes to an hour a day. Everyone can at least find 30 minutes of free time a day, some choose to use it on tv or gaming, I choose to code with that time.
do your side projects at work
also the most interesting way to show WASD 👀
Siick!
using chatgpt is gay