A few spatial methods

Feature Requests Engine Features
#1

I’m proposing a new set of methods for Workspace and a few for BasePart, to allow us to access internal spatial information from Lua. I’ve seen many a naive programmer do something like

[code]local function checkPartColission(partA,partB)
–a bit of math here
end

local newPart = Instance.new(“Part”, workspace)
local function recurse(t)
for i,v in pairs(t) do
if v:IsA(“BasePart”) and checkPartColission(newPart, v) then
–do something
end
recurse(v:GetChildren())
end
end
recurse(Workspace:GetChildren())[/code]

Possible stack overflow aside, this is incredibly bad code. However, many newer programmers (or lazy ones) don’t have the understanding to create a spatial data type and get it to work with ROBLOX. ROBLOX has to have an internal representation, so it would certainly be useful to expose it, or some sort of spatial data type. What I’m proposing is

Octtree Workspace::GetOcttree() – or some sort of other spatial data type; whatever ROBLOX uses internally

Which will allow us to efficiently determine whether or not certain parts have a chance of colliding, thus reducing the number of collision checks, drastically increasing performance.

In addition, for added convenience and ease for newer programmers, the following methods should be added:

BasePart[] Workspace::GetPartsNearPosition(Vector3 position, double radius)
and
BasePart[] BasePart::GetPossiblyCollidingParts()
BasePart[] BasePart::GetNearbyParts(double radius)
OcttreeBucket[] BasePart::GetCurrentBuckets()

These methods will simplify the parsing of the spatial data type so that newer programmers don’t have to wrap their head around the concept of an octtree or similar, a complex concept for a beginner.

The API for the new Octtree and OcttreeBucket classes themselves would be decided upon based on the internal representation of them, or just a plain old Lua table. Either way, that is a discussion for a future time; right now, we need to either accept this API or propose changes. The way it stands, it is unacceptable to have to write your own spatial data type whilst ROBLOX has one internally.

#2

Why do you want this stuff though? Roblox already does the physics for us. If you’re doing your own physics then you can make your own octtrees. What could this be used for?

#3

There are many use cases for having a spatial data type. A good example that’s an official ROBLOX gear is the gravity bomb (or whatever it’s called). Have you looked at the code for that? It uses a bunch of globals and is a bit spaghetti, but if you look at it, you’ll see that it applies a force to all the parts within a certain range of the bomb… by iterating over every single part in the entire game and doing a magnitude check. Try doing that in a modern place with many, many parts, and you’ve got a terribly slow bomb.

If you need more use cases, I can provide more.

#4

Would it be faster if we had octtrees? We’d still have to iterate through every part.

#5

Octtrees are there to PREVENT us from iterating through every part. We would find the buckets that MIGHT have parts close enough, and iterate through those. We could also use one of the convenience methods (that works directly from the octtree) to do something like this:

--assume bomb is the part that was dropped for i,v in pairs(bomb:GetNearbyParts(30)) do -- or however many studs applyForce(v) end

That would loop over only parts in nearby buckets, as well as (possibly, depending on the API) get parts who are large enough that a simple magnitude check based on the center is insufficient. For example, suppose we had a large building we’re trying to cause to get pulled to one point. The parts that represent the floors might be too large for their center to be within 30 studs, despite them definitely being within the area of the “explosion”. In fact, if you build something like this, you can see this in effect; having an API like this would

  1. allow us to do more complex math without sacrificing speed, and in fact gaining it, e.g. allowing us to account for those parts
    and
  2. have the engine do math like that for us at a faster speed than we could in Lua, thus allowing us to do more things
#6 
BasePart[] Workspace::GetPartsNearPosition(Vector3 position, double radius)
BasePart[] BasePart::GetPossiblyCollidingParts()

These functions are great. (:GetNearbyParts(radius) is not efficiently possible to query. Better to use GetPartsNearPosition(part.Position) due to performance concerns))

But why do you want the other one? I don’t think it would be wise to expose the nature of the physics / geometry handling to the Lua API (and it’s not going to happen for a lot of reasons too), and I don’t see what cases those first two functions don’t cover that exposing the internals could either.

#7

[quote] BasePart[] Workspace::GetPartsNearPosition(Vector3 position, double radius) BasePart[] BasePart::GetPossiblyCollidingParts()

These functions are great. (:GetNearbyParts(radius) is not efficiently possible to query. Better to use GetPartsNearPosition(part.Position) due to performance concerns))

But why do you want the other one? I don’t think it would be wise to expose the nature of the physics / geometry handling to the Lua API (and it’s not going to happen for a lot of reasons too), and I don’t see what cases those first two functions don’t cover that exposing the internals could either. [/quote]

There are cases where you would want to query various buckets to determine things without using a part, nor iterating through many parts in an area. For a simple example, look at all the raycast based laser guns in ROBLOX. What if we want to have these be volumetric? Doing volumetric checks for cylinders right now is damned hard. You either have to make your own spatial data type or iterate over everything there is. If I just want to check for parts that might intersect with a laser, one is very overkill and one is incredibly slow. If we instead have octtrees, we can instead calculate what buckets it would intersect with, and only check those buckets.

Now, you might look at that example and say “just make a cylinder and check for collisions there”. First of all we don’t have a truly acceptable cylinder implementation (that’s another issue). But also, what if we want to expand this to other shapes? What about a cone, or something? We can’t just use GetPartsNearPosition because while definitely better, if we have a large enough cone that’d encompass a very wide radius anyways, so it’s still not optimal. We also don’t have a cone primitive or anything that could be a good substitute for it for a quick’n’dirty workaround. Overall shapes like that just wouldn’t be optimal with only the two functions you like.

And why is BasePart::GetNearbyParts(radius) not efficiently queryable? The implementation could just be as simple as internally calling GetPartsNearPosition(Part.Position, radius). Basically, not a real requirement, but a useful shortcut with minimal overhead.

#8

“but a useful shortcut with minimal overhead.”

That would be fine (Although I don’t like that simple of a shortcut, just write the function in your script if you need to call it enough that the difference matters). I thought that you were suggesting an extruded-by-radius volume from the part, which, is actually possible to query, but significantly more expensive than the alternative.

As for the rest… sure, if you had the BSP tree, then your implementation of you own raycast volumes or whatever would be 3x more efficient (On the small scale you can actually get reasonably close to zero overhead space partition traversal right now with FindPartsInRegion if you know the fast-path through the code) and 2x easier. But… 2x easier than “almost impossible” is still “almost impossible”, and not something that you should reasonably be doing. The bottom line is that you just shouldn’t be hand coding spacial queries and stuff like that on the Lua side, that’s not the right way to do things. And that’s even ignoring the fact that you just plain can’t properly do a raycast or spacial queries right now since there’s no CSG API, so you will handle CSG parts incorrectly.

#9

Any word on this? I got the Edit of Review but nothing else; I’d love to know if this idea has been shot down, postponed, put on some sort of future “to do” list, etc…