ambiguousname
commented
8 months ago Alright, here's what I'm thinking:
- An Octree doesn't work because objects can move. Like say if an animal wants to move from one area to another.
- Don't want to prevent interactions while an animal is moving (say if they have a dynamic behavior).
- One potential solution to this is to group interactables by local areas and update them if they're moving.
- Too many edge cases.
- Another is to list some game objects as static while the ones that will move will just go through a linear search.
- Too many steps for the designers, and too restrictive.
- Probably way too complicated. As cool as an Octree implementation would be.
- There's other algorithms for organizing, especially for something like nearest neighbor search or even approximate nearest neighbor: Greedy Search with HNSW, Locality Sensitive Hashing,
- Most of these require lots of expensive computation to set up ahead of time, which makes moving points within them expensive as well.
- The research papers that are about say, moving points, take way too long to compute.
- But let's think about the wider picture here. Who needs an algorithm like this? If we're doing Open World stuff, or even boxed in levels (or some mix), then there's no need for these algorithms. Let's say that the maximum amount of interactables per "zone" is 50-100. Our search is still O(n) (modified by however many processor steps it takes for the if-statement and euclidean distance). My guess is that we can take two steps:
- Occlusion culling. Check if the renderer is active, don't perform the calculation if it's not.
- If occlusion culling isn't good enough for whatever reason, we can hook into whatever other system we're using to manage objects for the scene, game objects, etc. And activate interactables along with the other system. My guess is that this system will use a combination of occlusion culling and partitioning. The terrain/map will probably need to always be active if animals are moving out of player sight, but game objects will be a different story.
So basically, I'm putting this on pause until we figure out the open world stuff. In case you can't tell, I really wanted to make an Octree. Sigh.
Per #31.