What will you do if you have 100 Bushes then?
Will you store them all under one instance or under different instances? (20 Bushes under every instance)
1 Like
Different folders located in different parts of the workspace
2 Likes
In that case, you’ll have to make references to all of these Folders, and then loop through all of their children (Bushes)
But if these Folders were stored under one instance (Workspace for example), you can loop through all of the Workspace’s descendants, and then specify the descendants you want to loop through, like:
If Bushes.Name == "Bush" and Bushes:IsA("Part") then
This will only loop through the Bushes.
Makes sense?
1 Like
Makes sense except im trying to avoid using this, basically another way to implement collection service maybe even using object oriented programming. Not sure if this there is a way then since no one really knows
2 Likes
Use it. It’s not that bad.
To organize it, store these Folders in a table in your Script.
Something like
local Folders = {game.Workspace.Folder1, game.Workspace.Folder2, etc}
I don’t think there is such a way without CollectionService.
2 Likes
Nope no other way other than collection services.
The only other method I can think of is if you manually use a dictionary or table which is too much effort.
Everything is bad with too many instances.
It’s a really bad excuse to not use it, it is pretty much all we are given.
The better question is how do you make the most with what you are given?
Perhaps you got tricked by a game dev optimization technique? It is only an illusion of thousands of instances rather the game is only processing far fewer 500 grass instances that the player can see.
If you study a grass module it uses a data structure to only get the ones in view. Previously the module was using Octrees but this time the module is using vector map which I haven’t heard of personally. And hey it still uses collection services as well.
-- Update objects in view at their respective refresh rates
self.VectorMap:ForEachObjectInView(camera, renderDistance, function(className: string, object: BasePart | Bone)
2 Likes
I was looking for something like this
Example im surrounding by trees how would i still collect the instances tbe player is looking at?, i thought of using raycasts.
1 Like
I am not the expert here relying on @boatbomber knowlege.
According to his module it is more efficient to do it mathematically without relying on raycasts for collision data, have all the vector 3 positions of the trees collected and the camera CFrame.
You could try but its up to you.
local function isPointInView(point: Vector3): boolean
-- Check if point lies outside frustum OBB
local relativeToOBB = frustumCFrameInverse * point
if
relativeToOBB.X > farPlaneWidth2
or relativeToOBB.X < -farPlaneWidth2
or relativeToOBB.Y > farPlaneHeight2
or relativeToOBB.Y < -farPlaneHeight2
or relativeToOBB.Z > distance2
or relativeToOBB.Z < -distance2
then
return false
end
-- Check if point lies outside a frustum plane
local lookToCell = point - cameraPos
if
rightNormal:Dot(lookToCell) < 0
or leftNormal:Dot(lookToCell) > 0
or topNormal:Dot(lookToCell) < 0
or bottomNormal:Dot(lookToCell) > 0
then
return false
end
return true
end
2 Likes
Coming back to this, what is a octree and a vector map?
1 Like
I wrote a breakdown on Twitter that explains how Windshake accomplished this, and documented my whole process of how I got to my final efficient algorithm.
https://x.com/BoatbomberRBLX/status/1666597175407828994
In case y’all don’t have Twitter, I’ll copy paste it all here.
WindShake should animate only the objects in view. Here’s an illustrated breakdown on how I implemented sub-millisecond frustum culling in Roblox!
Before we start, we have to spatially partition our objects. To keep things fast, we don’t use any dynamic tree algos (like Octrees). We just chop the world into voxel cells and put objects in the box they occupy (which I’ve called a VectorMap, since it’s just a dictionary of vectors to object lists).
First, we get our camera’s view. We find the far plane using a configurable render distance, then we create a voxel-aligned bounding box around it. This gives us the cells that could possibly be in view, which we’ll narrow down next.
Narrowing it down can be expensive, so we try to use cheap methods first when we can.
We’ll start with a simple distance check. If a cell is farther than the far plane corners, we know it must be outside our frustum and we can discard it and move on.
Now we want to do a little better. We’ll check if the cell is beyond the far plane by converting it to the plane’s local space and seeing if there’s a negative Z component. This gives us the proper render distance we asked for.
Then we do the same thing on the other side. We check if the cell is behind the plane of the camera.
We can use trig to determine the vertical and horizontal angles of our view. We convert the direction to the cell into camera space, flatten one axis, convert it back to world, and check if the angle is outside the view angle of that axis. These two are the main checks!
At this point, we know all the cells that are in the camera’s view!
I didn’t show it because it makes it harder to understand the shapes, but we actually immediately discard cells that are empty so that by the end all we have are the cells with items in them!
We can now animate the objects in these cells.
Future plans: We’re currently checking each cell individually. It’s fast enough for now, but we could likely improve this by checking cells in big groups to discard bunches of cells at a time.
We’re back with more! I had new ideas and threw out basically everything.
Now, we calculate the oriented bounding box of the frustum to do cheap checks if cells intersect with it. This allows us to drop the distance check, the far plane check, and the near plane check!
Next we calculate the normal of the frustum’s top, bottom, left, and right (shown in those green lines) and discard if the cell is on the outside of any of the planes. We don’t need to check front or back since the OBB takes care of those!
By narrowing it down to just two techniques, it is both faster (yay) and easier to maintain (super yay!)
In the example from those images, the grid aligned bounding box had 240 cells to check. 117 of them were discarded by OBB, then another 46 by frustum normals. We are left with the 77 cells you see in blue! In practice, more are dropped for being empty.
~120 microseconds!
Thanks to MrChickenRocket for an idea! We know the frustum is convex, so there can’t be a gap in the cells. Therefore, when checking along the line we can skip the rest once we hit a cell that’s no longer inside! In this demo, we skipped 26% of the cells!
It occurred to me that once you find the first filled voxel, the subsequent voxels are sorted (filled on the left and empty on the right).
Instead of linearly searching for the last filled voxel, I wrote a binary search from that first point onward!
3 Likes
To summarize some main ideas of that thread:
- You only want to do work on the objects the player can actually see (ie: within the cameras’s view frustum).
- You want to find those objects as cheaply as possible.
- By storing the objects in cells, we can look for cells in view instead of objects in view. This means that more objects doesn’t mean more searching, since the number of cells isn’t changing.
- By studying the attributes of a system, we can find ways to use those facts to skip extra work. In this case, we noticed that:
- The camera’s frustum is convex, so once we hit a cell that is no longer inside it, all cells further down the row must also be empty and we can drop them.
- The frustum has no holes, so if a cell is surrounded by cells in view then it must also be in view, so we can skip checking it and just include it.
3 Likes
How do you even implement something like this? i didnt know something like this was possible and it couldve solved alot of headaches earlier.
1 Like
The core idea is very simple. An object has some position, so to determine what cell to put it in, you can divide and floor its position by the cell size.
That simple math means that anything from the starting edge of the cell to the ending edge of the cell gives the same value, since they’d be the cell value + some fraction (the fraction is how far along the cell it is, so halfway positioned would be + 1/2) that you’ve now floored down to the same base number. This makes all objects in the cell space give the same Vector3.
That vector3 is the key to that cell, which can be used as a dictionary key (since Luau has vector as a native type now) so you can grab the list of objects in the cell and add this object to it.
This implementation is slightly different in that each cell contains multiple lists, one for each Class. This is so that Parts and Bones can be animated differently.
2 Likes
This looks so complex ill keep re reading this, thanks for sharing this information with people who will find it useful
2 Likes
Actually the code can be written even simpler now since we got the // floor division operator in Luau.
Here’s a very simple example:
local Cells = {}
local CellSize = 5 -- measured in Studs
local function addObject(object: BasePart)
-- Find which cell this object sits in
local cellKey = object.Position // CellSize
if Cells[cellKey] then
-- If we already have that cell, add this object to it
table.insert(Cells[cellKey], object)
else
-- We haven't used this cell yet, so create the cell's list with this object in it
Cells[cellKey] = { object }
end
print("Added", object:GetFullName(), "to cell", cellKey)
end
addObject(workspace:WaitForChild("Part"))
1 Like
So its basically adding that object into the table but what is the point of doing that?
1 Like
Because then you can easily reach into the table to get lists of objects in a certain area, like around the player or in front of the camera. You decide which cells you need (see thread above for that) and then get the object lists and do whatever you need with them.
The point of the system is to make it possible to have thousands of objects all over your map, each with some effect like wind, but only perform the effect on the objects that are necessary. You couldn’t possibly animate tens of thousands of leaves, but you can have all those leaves and only animate the hundreds of them that are in the cells in view.
This concept is called spatial partitioning, if you want to find more resources. You split up (partition) the world (space) into cells/chunks/buckets/nodes so that you can more easily get objects in an area without having to check every single object individually.
2 Likes
Oh that makes sense but im still very confused on how to split the world into these chunks is it just like a bunch of invisible parts?
1 Like
It’s not literally changing anything about the world, just about how your code is interacting with the world. The partitioning exists only as a data structure in your code.
2 Likes
This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.