Spatial Hash Grids & Tales from Game Development
ฝัง
- เผยแพร่เมื่อ 26 มิ.ย. 2024
- 🛒 Recommended books (on Amazon): www.amazon.com/hz/wishlist/ls...
❤️ Support me on Patreon: / simondevyt
🌍 My Gamedev Courses: simondev.teachable.com/
Disclaimer: Commission is earned from qualifying purchases on Amazon links.
Follow me on:
Twitter: / iced_coffee_dev
Github: github.com/simondevyoutube/
In this project we're covering spatial hash grids, or spatial hashing, people seem to call it all sorts of different names. Anyway, we'll be covering a spatial hash grid implementation in JavaScript, working through it line by line. We'll walk through the code step by step, explaining it as we go, and as an added bonus, I've implemented a small scene in Three.js with hundreds of moving agents that we can use to visualize what's visible from the perspective of any given agent.
I'll also tell a small but interesting little story from way back when I was working on xbox/playstation games. Somewhat related to the topic.
Having a comprehensive understanding of data structures is fundamental to being a solid game developer. You need to understand the trade-offs, not just in time complexity. Questions like memory consumption, implementation and on-going maintenance costs, these all factor in. Sometimes simple solutions, implemented well, that get you 95% of the way there but at a fraction of the developer cost, are the way to go.
The three.js library is available in JavaScript for cross-browser 3d graphics, wrapping webgl and making high level functionality available in the web browser. It’s an extremely mature and well maintained library that I use for many of these videos.
In the video, we cover:
* What problem are we trying to solve? We'll look at examples from major games to understand their needs in different situations.
* We'll touch on alternative spatial data structures, and discuss the tradeoffs.
* I'll talk about an instance in my career that's relevant to this problem
* Step by step walk through for the full implementation of a basic spatial hash grid. - วิทยาศาสตร์และเทคโนโลยี
If you enjoyed this, help support me: www.patreon.com/simondevyt
this is great stuff from a legit CS breakdown..
except for the fact that you didn't factor in marginalized communities in the "sublinear access time" calculation. #equitymath
#endmathhate #logarithmsareoppressive
no sh**... #equitymath hashtag was joke, but there exists content on the topic.. 🤭
private properties exist.... 👀
"There was no documentation of any kind, because... games." - that hit SO CLOSE TO HOME, I died.
"It's self documenting"
Just look at the variable names they will explain everything.
var wtf = new ref omg;
@@roboterson if it was that would be "any kind" of documentation, wouldn't it?
Now I see why you write more reasonable code than most programmers: you were a game developer.
I love this channel because it just never explains things from absolute basics. It assumes you know enough to just learn a new thing. For me as a senior game programmer this is amazing as I don't need to have 5 minutes of explaining what arrays and hashes are, I can just learn something new I can apply, and for that I really rate this channel. It's like learning from someone at work rather than watching a tutorial.
Hah, I'm super happy you see it that way, because that's kinda where I'm targetting. People who already know things, and might just pick up a few extra tricks.
Lol, me too, I hate it when someone makes a tutorial about something kinda complex, but they still explain what a for loop is
This channel is so underrated.
Thanks! Appreciate it!
Totally agreed! Simon is a Rockstar!
Way too underrated
I strongly agree
NO CAP!!!
Playing prototype is one of my awesome gaming memories from childhood, absolutely loved it. Thanks for your work and the video is awesome too 🔥🙏
Glad you enjoyed it!
I'd like to jump on the train. I still love Prototype! So thank you and the whole team for building such a nice game! I'll go and rewatch some memory on my(*edit: old) channel😂
@@simondev758 Jumping in as well, I loved that game so much! I replayed through it and stopped midway through before the infection totally took over, so I could disguise as a soldier and pretend I was helping.
@@MrAssflap Was a super fun game. Personally, I loved the freedom. I'd often just sit for a few minutes at a time while working on it, and just run/climb tall buildings and glide, that was my favourite.
Childhood? Now I feel old... I'm 27 and I would have thought the game is hardly older as your comment
I’m not a game dev but I’ve randomly thought of this exact problem while taking a shower. Without a degree in mathematics, this seems like a very daunting task to do efficiently. Then I randomly get this video suggested by TH-cam which is great.
6:05 "Let's say you got a whole bunch of crap"
Gets me everytime. 😂😅
when my guy states his frametime budget in cycles I know I'm in the right place
I still vividly remember xbperfview
Spatial partitioning has been haunting me lately. The deeper I go into the subject the worse performance I get back. I was about to go one step further into mathematic and data structure complexity and dropped it. I thought I was going crazy. Thanks.
_cache misses galore_
I chuckled. I really appreciate your humor and writing :)
😀
There are some beautiful methods using spherical hashing for doing more generalized nearest neighbor search. In the DB world, the real win of spatial hashes (and hierarchical versions or better sparse ensembles) is the raw speed of the popcnt(xor) distance function itself paired with arrays. There’s a lovely balance between array speed and gains from partitioning...the adaptive radix tree would be a nice “pure” example of this to share with your viewers. Wonderful content!
Very neat, haven't run into spherical hashing, cursory glance at Google seems to imply this is (very vaguely) in the same vein as morton order? I'll have to read more.
You have given me so much homework in one paragraph. Thanks! (not sarcasm)
I was looking up how to grow hashish but I found this and now I'm a programmer
Well the difference netween addition and addiction is just "C", which is a programming language. ;)
@@achtsekundenfurz7876 And it's the best one, too.
@@anon_y_mousse So much this.
With soooo many "modern" programming languages, you can say "It does really well, and it's easy to do , and then there's it does quite well AND easily..." With C, it's more like, "It's generally very good, except has some ugly syntax, and is a bit harder to do than it should." With C, the flaws (rather than the highlights) are the exception.
BTW, the flaws that stand out for me would be, "Anything between quotes should be interpreted literally, even backslash etc." (example:
outside quotes should be newline; "
" should be just that, a backslash followed by the letter n), "characters by ordinal (e.g. \23 for ESC is octal; should be decimal unless prefixed by a zero, just like usual numbers) should obey the same parsing rules as integer values.", and some minor preprocessor hiccups.
@@achtsekundenfurz7876
On Unix, it actually makes sense to make '
' interpreted as the newline character, since backslash is commonly used in the shell for all of that. So C uses a similar set of codes, that is also used in 'grep' and other places that uses regexes. The ability to type common characters simply means you also need to escape the escape character. But it might not be commonly understood outside Unix circles.
@@tibfulv So far, so good. My pet peeve in there is that no character should be "magic" between quotation marks.
Of course, quotation marks themselves must be handled somehow, but the rest should work their magic only OUTSIDE quotation marks. The "backslash followed by certain letter" being always the same in Unix is fine (consistency is good). But AFAIK, there are only two OS strains which "process" escape characters inside strings as such (i.e. don't take them literally): Unix and its descendants, and the other is DOS and its descendants, where the shell does hardly any preprocessing at all, so programs do all kinds of crazy stuff on their own, and often very inconsistently. (Unix is at least consistent, with the exception of tar syntax.)
Aaah prototype, takes me back to simpler times taking turns playing with my brother on a rainy Sunday.
My brother loves it more though, he played every sequel. :)
Now I miss my brother, I think I'll give him a call, see how he's doing.
I've used this technique before, as the broad phase of a collision system. Came up with it from first principles. Seemed kind of obvious; didn't think I'd come up with something new. Now I know it has a name!
I've never touched javascript in my life but i still watched this video instead of studying.
I still play Prototype now and then. I very much enjoy it. Cheers!
I love how you managed to jump through all the tree solutions I slowly fought to learn over the years and simplified it.
With modern CPUs, highly pointer-dependent data structures are becoming less and less desirable.
I also had to implement this in a number of scenarios where octrees and other structures were no a good fit. One of the applications was molecular dynamics - molecules are more or less equally distributed in space and doing different kinds of calculations on them using spatial grid was a ton faster (and yea, easier to implement). Another awesome feature is that this can be initialized and even ran in parallel
This is crazy cool AND also super validating. Back when I had attempted to write an entire 2d game engine from scratch (in c# on the uwp using Win2d) i had implemented collision detection with a spacial hash. I had always wondered if I did the implementation correctly and now I know that I got the basics right!
100% agree regarding spatial grids being much better option for many games than Quad/Oct trees. It's a sign of an beginner/uninformed dev when a tutorial with a fixed size 2d game world jumps straight into quad trees, blissfully unaware of spatial grids. 'Quad tree' does sound much cooler/impressive though!
Nice video too, but personally I think you should have just shown the classic optimized approach instead of a beginner version as it ends up less code and simpler to follow anyway, and faster of course which is the whole point. By 'classic approach' I mean a flat one dimensional array of lists, each array location/list representing a grid cell. Then each key (array index) is just Y * grid_width + X. X and Y are just quantized (divided by cell_size) from floating point position/bounds of your entity.
yea people tend to forget or not consider that o(log n) types algorithms might be hundreds of times slower than o(n) types algorithm for small values of n due to all those things like cache misses and contigous memory.
your fancy whatever-tree might be shit compared to a simple array if you have just 10k elements.
Hah that's one of the topics I have lined up. I nearly failed my Google interview when my interviewer didn't understand that.
In one word : mastery.
I must admit : I've just discovered this video and i've already seen it several times. The second part is at the same level.
Thank you for this.
Again !
Np, glad you enjoyed it! And don't hesitate to suggest future topics.
@@simondev758 All right !
What would be great is the "making off" of something from scratch. A game (ambitious) or something lighter, more generic and reusable. The key concept is making it from scratch. You think, you type some code, you make mistakes, you revise, you test, you profile... Learning is easier like this I think.
I loved the episode when you think optimizing the code. Learned of a lot, and I understood the importance of data structures. By seeing it. Great job !
BTW, a learned more with this video than hours of crawling YT searching for good content !
Go check the "Meth Meth Method" YT channel. Another great content.
Sorry for my bad english, not natural ;)
@@davidf9062 Good suggestions! What I tend to do here is present concepts, and then bigger projects that show how to tie everything together quickly and easily.
I do want to touch on some data structures as well, although I have a bunch more concepts to do videos on after the last set of bigger videos.
Btw, don't apologise for your English, it's perfectly fine! It's better than my "any other language". More data structures is definitely on the roadmap.
this is so interesting. algorithmic efficiency is such a broad topic but you manage to make it so digestable. thank you!
Your channel is awesome!
I've both implemented an octree and a quadtree and they shine when they store static entities. ie, the level and static objects.
Use them on dynamic entities and the build times alone would be very slow. Also thrashes your cache.
Spatial hash grids really do shine with dynamic entities.
Underrated dev right here. Your explanations are so easy to follow.
It's absolutely wild what a good teacher you are. This should not be so simple to understand or appreciate
This Tutorial format is awesome. 👍
Great! I should be following this up with some easy optimizations soon.
This channel is a gold mine.
Never would’ve guessed one of the games you worked on was Prototype! That game really resonated with me
Was my first game in the industry, awesome experience.
The best content on Game Dev. Thank you!
This is exactly how we do it in molecular dynamics simulations where we need to calculate interactions between atoms in 3d space. Though we don't call it a spatial hash grid, I guess we just call it a "cell method".
Interestingly we often use some other optimisations as well, although whether or not these are useful depend on a lot of physical parameters.
Instead of using the cell method directly to per-timestep ("frame") calculate the neighbours, we use the cell method to create a neighbour list. This list is constructed by only iterating over the adjacent cells (or the cells within a cutoff radius from the center of the identified cell, if the cutoff radius for the interaction is larger than the cell), taking all the entities in the relevant cells, and then keeping the ones whose squared separation length is less than or equal to the squared interaction cut off length PLUS a buffer length (no need to square root).
The buffer length contributes to intentional over-counting of neighbours in the neighbour list, the reason we do this is so that we do not have to reconstruct the neighbour list every timestep ("frame"). Instead only when the maximum displacement of a particle since last neighbour list construction equals half the buffer radius is there any need to reconstruct the list. Basically we purposely over count neighbours so we only call the cell and list construction methods once every potentially dozens to thousands of timesteps.
How well this speeds stuff up depends a lot on the speed of the entities, and the entity-density in the world (one reason why the -tree approach often ends up faster than this, if you can implement and maintain it) and your chosen cell/list parameters. But you can tweak these variables for the particular simulation to make sure it stays efficient. We often choose a smaller-than-cutoff cell size to reduce spurious calculations (which is about 84% in 3d w/ cell size = interaction cutoff radius. You can prove this by calculating the volume of the sphere vs the volume of adjacent cells).
Also, if you have fixed sized cells you can simply use integer division between the world-space particle position and the cell size to produce the bucket-sort index for the particle, which is quite nice.
OMG, I have stumbled on your channel a couple of times when searched some information. Now I learned that you worked on Prototype - instant sub. The Prototype is a super rare game for me because I get bored of games and rarely complete them (time spent doesn't justify the amount of fun that's left), but I played prototype through two times and I'm sure I'll play it more at some point.
Prototype was neat! It had a tonne of really fun and inventive combat / stealth / movement mechanics, and I remember it running very efficiently on my old PC, in contrast to most comparable open-world games of the time. Thanks so much for all your explanatory videos! I'm not a gamedev but lots of visual and spatial math stuff meant for games is really broadly useful, especially for UI dev/design. You're very good at explaining things!
Prototype was a good game and technically impressive at the time. Good job!
WAIT U WERE A DEV FOR PROTOTYPE??
was going through all the threejs vids for a project submission and had to stop to comment this,3 years late but that era of games (prototype + infamous series) will forever be part of my core memory
That was brilliant. Thank you for your contribution. Please do continue this excellent content.
Thank you for making this, I enjoyed watching it!
Glad you enjoyed it!
Played Prototype game when I was 11. Thanks for a great childhood!
really informative video, this helps massive with game development, it's also awesome that you worked on prototype, it was a fun game.
Really well explained and really interesting! I'll keep an eye on your channel!
That'd be great, hope to see you around!
I was given a take home project to implement a K-d tree for a raytracing algorithm. I studied up on the structure, and understood how to create one. The issue was how to implement the tree in a raytracing algorithm. This was a year ago, but I'd still be happy with a video explanation. I couldn't find any sources or hints on how to go about doing such a thing.
Fascinating!
I really do like your videos Simon, so relaxing and easy to learn. thank you so much. If I can get by project off the ground and be financially supported, by sure days I'll buy you two coffee's. thank you again "tip of the hat to you" SimonDev
This tutorial format is really really good, thank you.
Prototype was one of my favorite games growing up. I could say with confidence now that It also contributed to my education lol
Hah
I'd love to see the numbers for a perfected version where you either do distance checks on the first set of results to discard those that are too far away or crank up the dimensions so that a cell is only like 1% of a client's width. Because in most, you need to have accurate results, e.g. when dodging abilities
This guy is a legend I really love him
These are the programming languages I would like to learn JavaScript and C++
man i loved playing prototype, i even played prototype 2, i really hoped prototype 3 would come too. Such a legendary game.
It was crazy fun to work on, awesome group of people.
I randomly stumbled upon your chanel and I have to say that I really like your videos!
I just started uni for CS and I can't say that I know much of data structures (at least not the more advance one), but still your video was comprehensible enough and learned a lot! Keep up the good work!!! :D
P.S.
Prototype what a series... they where some of my first games, love them! :D
Awesome, glad to have you aboard, and I'll also be covering data structures & algorithms as well. Hopefully those can help you out too.
@@simondev758 Can't wait, specially for algorithms :D
I played Prototype last year. What surprised me was how much fun the mechanics were. A true banger.
Wow! Prototype was an amazing game, I also remember it running really smoothly, much smoother then some games made currently
Thanks! I did a large number of the optimization work on that to keep the framerate stable and on target.
Literally bought prototype 3 days ago, and I’m still having a blast on it in 2022
You made this video when I need this solution and I didn't find it till 2 years after having to make my own workaround. 😭 I'll have to see if this is faster than my method. Thx man
Thanks! for the great Stuff. Really appreciate it.
My favorite code channel
Yay!
This is absurdly useful. Thank you.
np!
Very interesting, many thanks!
that was very easy to build and works great, thanks!
Thanks for sharing this!
The video's you make are true treasures. Thank you very much!
(Now im trying to implement this aaaaaaaaaaaaaand yeah idk how to use it)
Wow, amazing content, I work in the game industry as well and this is golden. Thank you very much for this!
Sweet, what are you working on?
@@simondev758 Unfortunately i cant say yet, but our last game was medieval game from bohemia :)
@@lukask.3465 No worries, I know most devs keep things under wraps until the public announcement. I'll look out for when you announce it :)
Omg prototype was my favourite game, subbing just for that lmao
Loved Prototype. Great game
fantastic video, thanks
Man, it's surreal who you find on youtube. I played the crap out of Prototype growing up, lol
:D
Prototype was a great game. I loved playing it. Although I also enjoyed number 2 I was really disappointed in how they made the player from the first game the antagonist of the second whom you had to kill.
This actually looks remarkably similar to something I put together 12 years ago on a personal project, while working as an intern.
Just about the same time Prototype was released, actually.
[edit]I actually took it just a step further, having the objects look through every cell they were being added to and then throw any matches into a searchable list.
OMG this guy made prototype!!
Hero!
Awesome! Thank you so much for sharing!
ty
Nice video, it works!
🎯 Key Takeaways for quick navigation:
00:00 🎮 Introduction to Spatial Hash Grids
- Introduction to the problem spatial hash grids solve in game development.
- Brief mention of what will be covered, including coding it up.
01:11 🐌 The Naive Solution
- Explanation of the naive approach to finding objects in the vicinity.
- Discusses why this method is inefficient, resulting in O(n^2) time complexity.
02:08 🌳 Tree Structures as Alternatives
- Introduction to tree-like data structures (Quad Trees, KD Trees, etc.) as alternatives.
- Discusses the benefits and drawbacks of these structures.
03:19 🛠️ Industry Experience and Lesson
- Shares a personal story from the speaker's game development career.
Emphasizes the importance of easy-to-maintain solutions through the story.
05:41 🎯 The Core of Spatial Hash Grids
- Introduces the core concept of spatial hash grids.
- Explains how they work and what problem they solve in game development.
07:05 👨💻 Coding the Spatial Hash Grid (Part 1)
- Walks through the code to create a basic spatial hash grid.
- Explains function definitions, parameters, and basic operations.
10:36 🛠️ Calculating Cell Indices
- Details the calculations required for converting positions to cell indices.
- Clarifies the math involved in these calculations.
13:25 👨💻 Coding the Spatial Hash Grid (Part 2)
- Continues the coding walkthrough, focusing on the 'find nearby' function.
- Explains how the function works and what each piece of code does.
15:17 🔄 Updating and Deleting Clients
- Discusses the update and delete operations for the spatial hash grid.
- Explains the code responsible for these operations.
16:27 📊 Performance Metrics
- Compares the performance of the spatial hash grid against the naive solution.
- Shows the timing metrics for various operations.
18:32 🚀 Optimized Version and Future Plans
- Introduces an optimized version of the spatial hash grid.
- Discusses future tutorials and performance improvements.
19:00 📢 Conclusion and Further Resources
- Wraps up the tutorial and mentions the code will be available on GitHub.
- Invites feedback and discusses future content.
Made with HARPA AI
Yes! I played Prototype and it was very cool!
this is amazing again! I actually maxed out Prototype back then.
Hah yeah it was a fun game
Wow, thank you so much for sharing your coding wisdom!
Np, lemme know if you have topics you want covered too!
Considering you already culled out all very far objects, you can run the proper radius check on the returned result for a more precise selection, absolute win
Definitely!
Thanks for the content, it's very interesting 😊
Let me know if you have suggestions too!
ah shit, now I have to look at all your other videos... I DONT HAVE TIME FOR THIS GREAT CONTENT!!
hah thx!
Great tutorial!
great videos!
amazing tutorials, thank you!
Glad you like them!
UNDERRATED!
Сетка даже с хэшем не так эффективна как q-tree. Чтобы в quad tree хранить объекты больше чем сектор, надо оставлять объект на ветви выше, в которой он полностью помещается. А уникальные пары столкновений можно быстро делать через unirdered set. В качеств хешера подойдёт (a
Came across your channel today and have had a scout around and have to say this is a great site, really surprised at the low subscriptions. Maybe the old adage (1980's) build it and they will come, - from the profit Kevin, you know the days when Pontius was a pilot and bows and arrows were on the secret list ? LOL anyway do keep them coming you have a great style : )
:)
Just amazing 👏
A little optimization tip, so long as you're not subculling Huge meshes, it's almost always a Heck of a lot faster to use sphere radius bounds for bound testing than AABB boxes. As in an order of magnitude faster especially if you don't know how to ensure the box test will cache hit.
Simply do distance squared tests.
It's awesome to learn about these optimization techniques in js, especially in three. Thank you for taking the time to both demonstrate implementation and teach through your experiences. I have been wanting to build silly little game engines and I feel like you've already helped me think about better avenues to start from.
Do you have a Discord? I feel like that is a fun way to share stuff and create a community around it.
Also this is likely a longshot, but have you played around with making things audio reactive? One of my end goals is to create audio reactive landscapes, and I have a general idea of how to do things naively, but I fear that my super basic knowledge of buffers would end up blowing up people's devices.
I should have a followup in a few days that steps through profiling & optimization as well.
Nah, no discord right now. I barely have enough time to do videos for the channel between work/family.
I've kinda wanted to do an audio reactive 3d thing for a while, has always taken the backburner. Maybe over the holidays I can go fiddle with it.
I needed to hear that story. Went down a deep rabbit hole of spatial trees recently and its sobering to hear that a simpler system worked for well for something in the real world that shipped.
and by deep im talking several days lost haha
Yeah it's super normal, in fact another game I helped ship a few years later had the exact same issue. A senior engineer had implemented super weird custom data structure, I forget the details but it was some multi-dimensional thing, think the whole thing was over 1000 lines of code. Anyway, he left, along with all the understanding of how it worked. I inherited the team and had a junior engineer rewrite it as a simple loop on an array, and sat down to help them optimize it by hand. Was just as fast, only a couple dozen lines long, and pretty much everyone understood how it worked. Way fewer bugs too.
I was been so naive.
Thank you Sir.
No worries, glad you got something out of it!
Declaring everything within a function as const when possible is genius. Why haven't I thought of this?
My game with 10,000 simultaneously moving colliding entities is running faster now using a spatial hash grid than it was using rbush (a popular rtree implementation). Went from 30 fps to 80 fps.
keep in mind this works well as long as the agents/clients don't bunch up.
As long as they keep a nice uniform density, simple works. If everyone decides to get into the same cell, the hash is no longer useful.
Definitely some degenerate cases, but in reality they'll never occur, especially if you have some basic logic running in the world to prevent it
@@simondev758 if you actually want to prevent it.
Think of cellphone towers: they work great until you're at a concert and there's thousands of cellphones in the same cell, active and not leaving.
Great content ... Thank you!
Glad you liked it!
Nice video! Looking forward for the next ones. Just out of curiosity: did you ever work on dual contouring? I'm looking for a good tutorial on this subject (google did already point out good resources, but still...)
It's on my list of topics I wanna cover, but who knows when I'll actually get to it.
Just thought about Prototype like a month ago because it was very fun
Fun game to work on, great people on that team.
I loved prototype❤️
Me too!
I love these videos!! I’m not a game dev but these are well explained and really fascinating. Keep it up!
By the way, have you considered using TypeScript? I love the simplicity and speed of raw JS but I find having types a must have these days.
Thanks, will do!
I've had a few people mention it, seems to be eternally on my todo list to check out. I can't say I've run into any serious issues with the lack of types in JavaScript, although having actual types wouldn't be a bad thing. My understanding of TypeScript is that it's transpiled to JavaScript. How's the debugging situation there? I love being able to just open devtools in Chrome, and drop breakpoints. Is the resulting JS easy to work with?
@@simondev758 yeah you can output a “source map” file that allows you to debug as per usual using chrome (super easy). I think beyond the types it gives some nice syntactic sugar like the ability to mark class methods as “private” without you doing the implicit “_” prefix to method names.
After having started with TS several years ago, I’d never start a new project without it, especially if I’m working with other people on the codebase.
@@Righey Ah gotcha, thanks for clearing that up!
I just decided on this very thing... Keep it maintainable, keep it EASY for the brain to follow and predict. Make your systems so obvious, they document themselves.
Easy systems are also easy to optimize, and easy to debug. Make it complicated only when absolutely necessary.
So you worked on the prototype of prototype!? I loved that game!
holy shit this guy worked on prototype!
Loved the video, hate the brace formatting, after 35+ years in games dev, 10+ assembler only the rest c and c++ I just cannot abide the braces on anything other than matching columns. It is just easier to follow, period.