Check for objects intersecting an area?

Help and Feedback Scripting Support
#1

Hello. In an effort to create my own custom pathfinding system, I am currently creating the process to map out all nodes in an octree which are occupied with some sort of object. To check if a specific node is occupied, what I am currently doing is using a region3 check. However, this proved to be quite inaccurate because it only checks if the bounding box of the object is intersecting the region and not the actual geometry of the object.

What I have thought about doing is using a ghost basepart and moving it and sizing it to every node that I want to check using its gettouchingparts method. However, I feel that the performance implications of this might be bad.

If any of you know of any viable methods to this problem I would appreciate if you would let me know. Thanks!

2 Likes
#2

If I understand this correct, are you trying to make an automated system that takes in a model and maps each vertex in your polygon (geometric shape) which would then act as the hitbox to check when a vertex intersects an area? I don’t think it’s possible within Roblox because you’d have to wrap the shape / texture into 2D and then somehow get the vector coordinate data of each vertex, then wrap it back into 3D and it should have all the nodes.

Sorry that I can’t really provide you a direct answer for this, but remember that most games don’t use this kind of system for hitbox detection because every time you get the point of a vertex (especially because most games probably have some form of mesh deformation so you’d need to calculate the hitbox for the mesh itself every frame) (and models can have thousands of them), you’re going to get as you said performance implications VS having a square hitbox.

If you figure out a way to get the vector coordinate for each Vertex in 3D space, you can loop each point in your object relative to the to areas object space with the use of clamping the X and Z size of your area.

This is what I do (remember don’t use wait()) and it takes orientation into consideration:

local b = workspace.bounds
local p = workspace.Part

local x 
local z

local function clamper(r)
	local posX = math.clamp(r.X,-b.Size.X/2,b.Size.X/2)
	local posZ = math.clamp(r.Z,-b.Size.Z/2,b.Size.Z/2)
	return posX, posZ
end

while wait() do
	local bcf = b.CFrame

	local r = bcf:PointToObjectSpace(p.Position)
	
	x, z = clamper(r)
	local ori = p.Orientation
	local cf = CFrame.new(x, 0, z)
	local newcf = b.CFrame:ToWorldSpace(cf)
	p.CFrame = newcf
	p.Orientation = ori
end

You’d still have to make a system that loops through each vertex and this only works for pre-mapped models (in my case it’s just the center position of the given object). Again, I’m sorry that this isn’t an answer to your Vertex mapping question. I just don’t think it’s possible within Roblox because you can’t really scan textures nor do they retain any vector coordinate data.

2 Likes
#3

Yeah it seems I won’t be able to do that because of the limitations of Roblox you just mentioned. Thanks for trying anyways though.

1 Like
#4

Update:
As expected using gettouchingparts worked like a charm. However, at almost 70ms per calculation with a search area of 100, 30, 100 and min voxel resolution magnitude of 1 it is far too slow to be used with a game that has many pathfinding agents.

Image showing nodes that are occupied.

image
image1345×463 178 KB

2 Likes
#5

Out of curiosity, did you predetermine all the nodes seen or did you scan the texture (since you said voxel resolution magnitude) or how exactly does this work? :slight_smile: Glad to see you found your answer but yeah, it’s quite expected. Can you get away with reducing performance cost if you don’t instance the parts (simply by storing all nodes vector coordinates, then again this would mean you can’t check their collisions, but try the clamping function I sent) and make them transparent or is this done post calculation?

Or did I misunderstand and what I’m seeing is the actual custom area ?

edit:

I just realized you could probably scan meshes directly in the engine with rays, I always thought this wasn’t possible.

#6

If I’m honest I’m not actually sure if what I’m doing is correct. It’s just using stuff that I’ve learnt from youtube tutorials in the past 2 days… since secondary school computer science doesn’t teach ANY of this.

Here are the steps which my program performs (sorry if I mix up terminology and make it confusing):

  • Create a root node. Each node is a table which stores: its world position, its size, its children nodes and if the space which it represents is empty.
  • The program will check if the root node contains any objects which intersects with it. If it does find intersecting objects, then it will create 8 children nodes, which will each a represent an octant of the root.
  • The program will perform the above operations recursively for each node until the child node created does not have an intersecting parts (in which it will be marked) or if when divided, an octant of the child node is smaller in magnitude compared to a specified minimum.

If you want to have a look at the code I could send you a copy of the rojo project or test place in dms.

edit: Yeah, I thought about using rays too. I’m kind of reluctant to do that because it might miss detecting extremely small objects depending on how many I use, despite potentially being more performant.

edit 2: What you saw in the image was the nodes which collide with the wedge part. The other nodes aren’t represented because no parts intersect them.

1 Like