Spatial Hash Grids & Tales from Game Development
VloĆŸit
- Äas pĆidĂĄn 8. 06. 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. - VÄda a technologie
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?
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
Now I see why you write more reasonable code than most programmers: you were a game developer.
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
This channel is so underrated.
Thanks! Appreciate it!
Totally agreed! Simon is a Rockstar!
Way too underrated
I strongly agree
NO CAP!!!
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 CZcams which is great.
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)
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.
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
_cache misses galore_
I chuckled. I really appreciate your humor and writing :)
đ
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.)
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!
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 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.
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.
I've never touched javascript in my life but i still watched this video instead of studying.
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!
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
It's absolutely wild what a good teacher you are. This should not be so simple to understand or appreciate
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.
I still play Prototype now and then. I very much enjoy it. Cheers!
this is so interesting. algorithmic efficiency is such a broad topic but you manage to make it so digestable. thank you!
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.
This channel is a gold mine.
Underrated dev right here. Your explanations are so easy to follow.
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.
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.
This Tutorial format is awesome. đ
Great! I should be following this up with some easy optimizations soon.
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.
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'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
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!
Played Prototype game when I was 11. Thanks for a great childhood!
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.
The best content on Game Dev. Thank you!
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
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.
That was brilliant. Thank you for your contribution. Please do continue this excellent content.
really informative video, this helps massive with game development, it's also awesome that you worked on prototype, it was a fun game.
Literally bought prototype 3 days ago, and Iâm still having a blast on it in 2022
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
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.
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
I played Prototype last year. What surprised me was how much fun the mechanics were. A true banger.
This guy is a legend I really love him
These are the programming languages I would like to learn JavaScript and C++
Thank you for making this, I enjoyed watching it!
Glad you enjoyed it!
Really well explained and really interesting! I'll keep an eye on your channel!
That'd be great, hope to see you around!
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.
Fascinating!
Omg prototype was my favourite game, subbing just for that lmao
that was very easy to build and works great, thanks!
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 :)
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)
Thanks! for the great Stuff. Really appreciate it.
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.
Yes! I played Prototype and it was very cool!
Loved Prototype. Great game
ah shit, now I have to look at all your other videos... I DONT HAVE TIME FOR THIS GREAT CONTENT!!
hah thx!
This is absurdly useful. Thank you.
np!
Very interesting, many thanks!
Man, it's surreal who you find on youtube. I played the crap out of Prototype growing up, lol
:D
My favorite code channel
Yay!
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 sharing this!
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!
đŻ 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
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.
Declaring everything within a function as const when possible is genius. Why haven't I thought of this?
Awesome! Thank you so much for sharing!
ty
fantastic video, thanks
Wow, thank you so much for sharing your coding wisdom!
Np, lemme know if you have topics you want covered too!
Thanks for the content, it's very interesting đ
Let me know if you have suggestions too!
this is amazing again! I actually maxed out Prototype back then.
Hah yeah it was a fun game
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.
amazing tutorials, thank you!
Glad you like them!
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.
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 : )
:)
OMG this guy made prototype!!
Hero!
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.
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.
holy shit this guy worked on prototype!
Just thought about Prototype like a month ago because it was very fun
Fun game to work on, great people on that team.
Great tutorial!
absolutely great. I came here cause because I searched for a solution for a simalar problem^^.
Nice video, it works!
I do actually know of a library that has Quadtrees that's for C++/C, and has a Java port: ODE. It also has a spatial hash space. (my game currently uses the simple, naive version though, as I have a total of 5 objects)
great videos!
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.
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.
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!
Bro Prototype fucking slapped, dont sell yourself short, me and all my friends played it back in the day
I was been so naive.
Thank you Sir.
No worries, glad you got something out of it!
Great content ... Thank you!
Glad you liked it!
so many stuff we can learn from game dev as roboticist....
UNDERRATED!
i really enjoyed prototype