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
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.
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.
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 RUclips which is great.
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.
@@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.)
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)
Interesting concept, those spherical hashes. Seems to be more adapted to situations where it's not immediately obvious how to partition the space (or even where that changes). Either because you don't have a fixed "game area" (which only procedurally generated games really would), or because you have too many dimensions (which games really usually don't). But finding THE ONE nearest neighbor (or k of them) seems very different of a problem than finding all neighbors within a certain radius; and I think games rarely need to do the former. So I don't see how you'd benefit from that xor-based distance function. Unless you need to very very very often calculate distances, where an estimate would do but "it's simply too far to care" isn't a thing. But then x*x+y*y+z*z is 5 elementary operations or 3 multiply-accumulate operations whereas popcnt(xor) is 1 or 2. So a speed up of between 1.5 and 5.0 fold, which I can't imagine matters for games. One thing that isn't immediately obvious to me: Is there a way to efficiently search a bounding box (or in that case probably a "bounding radius") around a point? *Never mind,* there is: You distinguish the cases where the "bounding sphere" is fully inside one of the partitioning spheres, or full outside of it, and otherwise you search both all partition spaces that are inside and all that are outside with respect to that partitioning sphere. But wouldn't the partitioning spheres have more surface area than partitioning planes (or at least more surface area that falls within the "game area bounds")? And thus make it more likely that you have to search both partitions (or save an entity in both)?
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!
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
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 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 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.
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 !
@@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'm learning to make a simple 3D game engine with my brother for our game, and I've been banging my head trying to figure out "what *-tree would be best to use" for a while now. But watching your videos (and specifically the line "sometimes simple solutions implemented well are good enough") made me realize that, I don't need todo all that just to get initial results; whatever works, works. Thank you for the content!
Yeah a lot of people get caught up in that. You'd be surprised the number of big games or even major products you use, that shipped with just arrays in place of complex data structures.
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.
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.
You did a great job presenting this, you made clear the big idea and what to implement! Also... Prototype was one of the best sandbox games I've played!
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!
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 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.
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
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 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.
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
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.
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
🎯 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
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.
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.
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.
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
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 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 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)
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.
Having been through all this with sims, games and other things I highly recommend looking at iso surfaces, and proximity db's. Extremely high perf and far more organized. You can have _vast_ areas and the code is _simple_. It surprises me people dont use them much. And interesting you talk about arrays. Arrays are king :) .. stop using maps.. use dual linked arrays... perf and mem overhead difference is massive. And swap out all your vectors with a decent array type (esp hashed ones if you can get away with it, but plain indexed arrays are generally king). And my last favorite perf boost, that everyone forgets about on PC (and other platforms) is 64KB alignment. This.. can get you 3->10x performance boost across your whole game. Chunk all your mem blocks into 64KB and make sure all those addresses are nicely 64KB aligned (esp heavily used ones). The cache friendliness and CPU perf improvements are kinda insane. HIghly recommended.
Сетка даже с хэшем не так эффективна как q-tree. Чтобы в quad tree хранить объекты больше чем сектор, надо оставлять объект на ветви выше, в которой он полностью помещается. А уникальные пары столкновений можно быстро делать через unirdered set. В качеств хешера подойдёт (a
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.
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.
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 : )
Did you work on Wolf 2009?? I was a QA tester on it. Even though they switched from Id Tech 4 to Unreal 3, so many of the graphics, ideas, the viel, etc. were transferred over from Wolverine and then Wolfenstein. Really good gameplay tropes that were becoming signature to Raven, having being able to be a FPS and a RPG with magic system being common methodologies they were trying out. It's a shame those didn't catch on or stay. It's also a shame that Raven had a really good streak but the public didn't care too much. There should have been a Wolfenstein sequel.
Nah never worked on that. Yeah it's too bad about Raven, what are they up to these days? Are you still there? I remember them from those old Heretic games which were great.
My gosh man, your skills are top tier, in code and organization. I learned from LaMothe, then years of dinking around. I need to up my math and algorithms to keep up as naturally as you express these things. I can understand it, but I'm taking a bit of time to stop and look. The bounds and points aren't too difficult, but how to organize it just rolls off your tongue without even stopping to think or any visible editing. I'm definitely not there in my career. Your OOP skills though... those are top-notch. People aren't taught how to do OOP. They tell you how terrible it is then write poor samples or point to terrible code. If you teach anywhere...
Andre LaMothe, that's a name I haven't heard in forever! Does he still make books? It's cool, take your time in getting through the videos. I prefer to teach by explaining concepts and letting you work out the details, although the code is there if you need to fall back on it. It's how I learn. I've mentored people internally at companies, but this is the first time I've tried teaching outside of that. It's interesting and fun.
@@simondev758 Oh nice! Yeah, your skills, and others who've been in the game industry... I feel like I just get a sample sometimes. I mentor in structure but I've never made an engine. My senior made a few engines and shadowed at EA younger. Andre's been doing a Udemy course, which I bought on sale... it's 100 hours and is basically his PCB from ground-up book but it goes further than just consoles. I've been a UI coder primarily, so I don't have the same skillset, but I can recognize talent. Find someone who knows Hungarian Notation and you can trust they've been around systems.
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.
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...)
Definitely, that's done in the follow up video "How I optimized my JavaScript project". In general, when conveying a concept, I try to keep it as simple as possible. Which may mean the presented version isn't as optimized as it could be.
Prototype IS dope! I bought the prototype 1 and 2 two pack for ps4 so my kid could enjoy it as well. Got lost in the shuffle, people missed it, it was a great IP!!
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.
@@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.
smart, i kinda started with that same structure, a hashgrid, but ended up moving to a quadtree cus it was specifically faster for my game(big map many entities map)
I'd like to note that such problems are prime candidates for porting into a compute shader format where a naive solution would hit these numbers alone, with the optimized version as a compute shader it would take microseconds not milliseconds. If you can accept the results being 1-3 frames late that is. (Usually fixable by having a conservative estimate if you're not relying on perfect accuracy which this technique already drops)
In a 2D game, can you use a "3d" table to fake things like levels?. Think of iso games like Zelda. You have a dungeon room with 2 or 3 platform levels. I was thinking of just adding a variable 0-2 and set that value depending on where the entity is. But can a spatial grid like this be used to track platform level external from the entity?
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?
because ... you don't get paid writing documentation and you have a crazy deadline that is only achievable by working 30 hours a day.
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
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 RUclips which is great.
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.
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.)
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)
Interesting concept, those spherical hashes. Seems to be more adapted to situations where it's not immediately obvious how to partition the space (or even where that changes). Either because you don't have a fixed "game area" (which only procedurally generated games really would), or because you have too many dimensions (which games really usually don't).
But finding THE ONE nearest neighbor (or k of them) seems very different of a problem than finding all neighbors within a certain radius; and I think games rarely need to do the former. So I don't see how you'd benefit from that xor-based distance function.
Unless you need to very very very often calculate distances, where an estimate would do but "it's simply too far to care" isn't a thing. But then x*x+y*y+z*z is 5 elementary operations or 3 multiply-accumulate operations whereas popcnt(xor) is 1 or 2. So a speed up of between 1.5 and 5.0 fold, which I can't imagine matters for games.
One thing that isn't immediately obvious to me: Is there a way to efficiently search a bounding box (or in that case probably a "bounding radius") around a point? *Never mind,* there is: You distinguish the cases where the "bounding sphere" is fully inside one of the partitioning spheres, or full outside of it, and otherwise you search both all partition spaces that are inside and all that are outside with respect to that partitioning sphere.
But wouldn't the partitioning spheres have more surface area than partitioning planes (or at least more surface area that falls within the "game area bounds")? And thus make it more likely that you have to search both partitions (or save an entity in both)?
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'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!
_cache misses galore_
I chuckled. I really appreciate your humor and writing :)
😀
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
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 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 channel is a gold mine.
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.
I've never touched javascript in my life but i still watched this video instead of studying.
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'm learning to make a simple 3D game engine with my brother for our game, and I've been banging my head trying to figure out "what *-tree would be best to use" for a while now. But watching your videos (and specifically the line "sometimes simple solutions implemented well are good enough") made me realize that, I don't need todo all that just to get initial results; whatever works, works. Thank you for the content!
Yeah a lot of people get caught up in that. You'd be surprised the number of big games or even major products you use, that shipped with just arrays in place of complex data structures.
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.
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.
You did a great job presenting this, you made clear the big idea and what to implement! Also... Prototype was one of the best sandbox games I've played!
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!
It's absolutely wild what a good teacher you are. This should not be so simple to understand or appreciate
this is so interesting. algorithmic efficiency is such a broad topic but you manage to make it so digestable. thank you!
I still play Prototype now and then. I very much enjoy it. Cheers!
Underrated dev right here. Your explanations are so easy to follow.
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.
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.
Literally bought prototype 3 days ago, and I’m still having a blast on it in 2022
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.
This Tutorial format is awesome. 👍
Great! I should be following this up with some easy optimizations soon.
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!
6:05 "Let's say you got a whole bunch of crap"
Gets me everytime. 😂😅
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.
Prototype was a good game and technically impressive at the time. Good job!
The best content on Game Dev. Thank you!
Played Prototype game when I was 11. Thanks for a great childhood!
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.
This guy is a legend I really love him
These are the programming languages I would like to learn JavaScript and C++
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!
I played Prototype last year. What surprised me was how much fun the mechanics were. A true banger.
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.
Really enjoyed the part where you inserted the client dict.
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
🎯 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
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.
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 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.
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
My favorite code channel
Yay!
Never thought Bob from Bob's Burgers would be teaching me gamedev
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.
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 :)
That was brilliant. Thank you for your contribution. Please do continue this excellent content.
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
Holy....Prototype was one of my favourites game! Nice video btw.
Declaring everything within a function as const when possible is genius. Why haven't I thought of this?
really informative video, this helps massive with game development, it's also awesome that you worked on prototype, it was a fun game.
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)
Really well explained and really interesting! I'll keep an eye on your channel!
That'd be great, hope to see you around!
I so late to this but I spent so many hours playing prototype just because the systems were fun and crunchy. It deserved to sell so much more
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!
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)
Having been through all this with sims, games and other things I highly recommend looking at iso surfaces, and proximity db's. Extremely high perf and far more organized. You can have _vast_ areas and the code is _simple_. It surprises me people dont use them much. And interesting you talk about arrays. Arrays are king :) .. stop using maps.. use dual linked arrays... perf and mem overhead difference is massive. And swap out all your vectors with a decent array type (esp hashed ones if you can get away with it, but plain indexed arrays are generally king).
And my last favorite perf boost, that everyone forgets about on PC (and other platforms) is 64KB alignment. This.. can get you 3->10x performance boost across your whole game. Chunk all your mem blocks into 64KB and make sure all those addresses are nicely 64KB aligned (esp heavily used ones). The cache friendliness and CPU perf improvements are kinda insane. HIghly recommended.
Сетка даже с хэшем не так эффективна как q-tree. Чтобы в quad tree хранить объекты больше чем сектор, надо оставлять объект на ветви выше, в которой он полностью помещается. А уникальные пары столкновений можно быстро делать через unirdered set. В качеств хешера подойдёт (a
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.
I randomly came up with the tree structure once.
It was already discovered, but it just means all roads lead to Rome
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.
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 : )
:)
Thank you for making this, I enjoyed watching it!
Glad you enjoyed it!
Did you work on Wolf 2009?? I was a QA tester on it. Even though they switched from Id Tech 4 to Unreal 3, so many of the graphics, ideas, the viel, etc. were transferred over from Wolverine and then Wolfenstein.
Really good gameplay tropes that were becoming signature to Raven, having being able to be a FPS and a RPG with magic system being common methodologies they were trying out. It's a shame those didn't catch on or stay. It's also a shame that Raven had a really good streak but the public didn't care too much. There should have been a Wolfenstein sequel.
Nah never worked on that. Yeah it's too bad about Raven, what are they up to these days? Are you still there? I remember them from those old Heretic games which were great.
@@simondev758 Raven is sadly a support studio responsible for COD Warzone. I'm at ATVI going to start COD Vanguard next month
Just thought about Prototype like a month ago because it was very fun
Fun game to work on, great people on that team.
Man, it's surreal who you find on youtube. I played the crap out of Prototype growing up, lol
:D
My gosh man, your skills are top tier, in code and organization. I learned from LaMothe, then years of dinking around. I need to up my math and algorithms to keep up as naturally as you express these things. I can understand it, but I'm taking a bit of time to stop and look.
The bounds and points aren't too difficult, but how to organize it just rolls off your tongue without even stopping to think or any visible editing. I'm definitely not there in my career. Your OOP skills though... those are top-notch. People aren't taught how to do OOP. They tell you how terrible it is then write poor samples or point to terrible code. If you teach anywhere...
Andre LaMothe, that's a name I haven't heard in forever! Does he still make books?
It's cool, take your time in getting through the videos. I prefer to teach by explaining concepts and letting you work out the details, although the code is there if you need to fall back on it. It's how I learn.
I've mentored people internally at companies, but this is the first time I've tried teaching outside of that. It's interesting and fun.
@@simondev758 Oh nice! Yeah, your skills, and others who've been in the game industry... I feel like I just get a sample sometimes. I mentor in structure but I've never made an engine. My senior made a few engines and shadowed at EA younger.
Andre's been doing a Udemy course, which I bought on sale... it's 100 hours and is basically his PCB from ground-up book but it goes further than just consoles.
I've been a UI coder primarily, so I don't have the same skillset, but I can recognize talent. Find someone who knows Hungarian Notation and you can trust they've been around systems.
This is absurdly useful. Thank you.
np!
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!
Omg prototype was my favourite game, subbing just for that lmao
One of my friends was crazy about playing Prototype during mid 2010. He is building military fighter jets these days.
Very neat, I've worked with some people from military backgrounds, weird the amount of overlap with game development.
Fascinating!
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.
so many stuff we can learn from game dev as roboticist....
ah shit, now I have to look at all your other videos... I DONT HAVE TIME FOR THIS GREAT CONTENT!!
hah thx!
this is amazing again! I actually maxed out Prototype back then.
Hah yeah it was a fun game
OMG this guy made prototype!!
Hero!
that was very easy to build and works great, thanks!
Do you need to generate key for the cells? Isn't it enough to use two indices, like grid[x][y] ?
Definitely, that's done in the follow up video "How I optimized my JavaScript project".
In general, when conveying a concept, I try to keep it as simple as possible. Which may mean the presented version isn't as optimized as it could be.
Prototype IS dope! I bought the prototype 1 and 2 two pack for ps4 so my kid could enjoy it as well. Got lost in the shuffle, people missed it, it was a great IP!!
Yeah, some of the most fun years of my career. Too bad the studio is gone now. I'd love to work on #3 if it happens.
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.
smart, i kinda started with that same structure, a hashgrid, but ended up moving to a quadtree cus it was specifically faster for my game(big map many entities map)
I'd like to note that such problems are prime candidates for porting into a compute shader format where a naive solution would hit these numbers alone, with the optimized version as a compute shader it would take microseconds not milliseconds. If you can accept the results being 1-3 frames late that is. (Usually fixable by having a conservative estimate if you're not relying on perfect accuracy which this technique already drops)
absolutely great. I came here cause because I searched for a solution for a simalar problem^^.
In a 2D game, can you use a "3d" table to fake things like levels?. Think of iso games like Zelda. You have a dungeon room with 2 or 3 platform levels. I was thinking of just adding a variable 0-2 and set that value depending on where the entity is. But can a spatial grid like this be used to track platform level external from the entity?
Sure