Trail Collision Detection

So I am working on game that utilizes Roblox’ Trail object for core game play; Think slither.io… and one issue that is holding me back is detecting when a player touches another player’s trail, as there is no .Touched event, or actual Vector3 of the trail to compare to.

I have created a few different methods of collision detection which work great, however there is noticeable performance issues with each of them.

My current system is as such:

(1) (My current method)
a) Client constantly listens to every other player in the game, and constantly tracks their v3 position to a
table, removing it from the table after their Trail.Lifetime.
b) Client constantly raycasts from each of the tracked v3 positions to their own character position, with a very
small distance (<1 units)
c) If the raycast hits our own character, then a collision has been detected, and reports to the server.

(2) (An alternate method)
a) Client constantly listens to every other player in the game, and constantly tracks their v3 position to a
table, removing it from the table after their Trail.Lifetime.
b) Client constantly checks magnitude between the tracked v3 position to their own character position
c) if magnitude <1 (or so), then a collision is detected, fire to server.

(3) (another, poor method, which is out of the question)
Same as (2), but 100% on the server. Very laggy and inconsistent for the client.

(4)
a) Constantly create a part at each player’s position, deleting it after their Trail.Lifetime
b) Listen for .Touched on the part
c) on .Touched, verify it and send it server.

I am looking for some alternate methods on how I could achieve Trail collision detection without sacrificing performance. My current method (method (1)), begins to have lag spikes when the server starts to fill up (10-15 players), very noticeable and microprofile proves that it is the abundance of Raycasts causing the spikes.

This would make a great feature request

I’m going to assume that modeling the points through a curve/function is out of the question, so you will need to store point samples

So you need a datastructure that supports insertions,removals, and queries to do one of the following:

  1. find closest point in datastructure to query (and then compare the distance and check if it is less than some threshold)
  2. box query (so something like roblox region3) and then check points for magnitude
  3. sphere/circle range query (like roblox region3, but sphere instead of region3 - probably really messy)

So TBH probably the fastest solution to implement (and the cleanest) would be for you to use solution 2 with roblox region 3 with whitelist:
https://wiki.roblox.com/index.php?title=API:Class/Workspace/FindPartsInRegion3WithWhiteList

a) Constantly create a part at each player’s position, deleting it after their Trail.Lifetime
b) Client constantly uses FindPartsInRegion3WithWhiteList with region centered at the client’s character and with radius whatever you want (will need to make side length 2*circle radius because its a box not a sphere :/)
c) if from the output table of parts, one of the parts satisfies the conditions, send it to server

5 Likes

I will try that out and see if it performs any better than my current Ray/magnitude implementations.

I can probably get away with Instantiating the parts with a while loop instead of RenderStepped, too.

1 Like

Do you remember the old Tron bike gear? What if you did something like that except the parts were invisible and lasted as long as the particles? It would be a couple more parts but it’d be a good placeholder until they possibly DO release this! :raised_hands:

Yea I think the way to go with this is to make the parts

Also the parts should be sized as small as possible ((0.05,0.05,0.05) is the min atm) and they should spawn in every 2*trail radius (or trail diameter) if it doesnt lag @Fm_Trick this would be more precise than doing it on a time based while loop/renderstepped

Excuse the sloppiness of the code, but here is what I’ve got for this method of part creation:

	function Trail.Movement(to_player, humanoid, toggle)
		if toggle == true then
			if to_player and humanoid and Trail.Trails[to_player.Name] then			
				Trail.Trails[to_player.Name].MovementConnection = humanoid.Running:Connect(function(speed)
					if Trail.Trails[to_player.Name] then
						if speed > 0 then
							if Trail.Trails[to_player.Name].Moving == false then
								Trail.Trails[to_player.Name].Moving = true
								spawn(function()
									while Trail.Trails[to_player.Name] and Trail.Trails[to_player.Name].Moving == true do
										if to_player and to_player.Character and to_player.Character.HumanoidRootPart and Trail.Trails[to_player.Name].TrailInstance then
											local position = to_player.Character.HumanoidRootPart.CFrame:toWorldSpace(CFrame.new(0,0,2)).p
											local part = MakePart(position, to_player)
											
											table.insert(Trail.Trails[to_player.Name].Parts, part) -- insert the position into a table.
											table.insert(Trail.Parts, part)
											
											delay(Trail.Trails[to_player.Name].TrailInstance.Lifetime, function()
												if Trail.Trails[to_player.Name] then
													LuaExtended.TableDotRemoveByKey(Trail.Trails[to_player.Name].Positions, part)
													LuaExtended.TableDotRemoveByKey(Trail.Parts, part)
													part:Destroy()
												end
											end)
										end
										wait()
									end
								end)
							end
						else
							Trail.Trails[to_player.Name].Moving = false
						end
					end
				end)
			end
		else
			if Trail.Trails[to_player.Name].MovementConnection then Trail.Trails[to_player.Name].MovementConnection:Disconnect() end 
		end
	end

And the region3 method:

		spawn(function() -- spawn the main loop.
			while wait() do
				if tick() - Trail.last_touched >= 0.5 then
					if local_player and local_player.Character and local_player.Character.HumanoidRootPart then
						local hrp = local_player.Character.HumanoidRootPart
						-- create a region3 around the character, and get parts inside of region 3. If there's any parts inside of the region 3, we touched.
						local r_min = Vector3.new(hrp.CFrame.p.X-hrp.Size.X/2, hrp.CFrame.p.Y-hrp.Size.Y/2, hrp.CFrame.p.Z-hrp.Size.Z/2)
						local r_max = Vector3.new(hrp.CFrame.p.X+hrp.Size.X/2, hrp.CFrame.p.Y+hrp.Size.Y/2, hrp.CFrame.p.Z+hrp.Size.Z/2)
						local region = Region3.new(r_min, r_max)
						local part = workspace:FindPartsInRegion3WithWhiteList(region, Trail.Parts, 1)
						if part then
							local owner = GetOwner(part[1])
							if owner then
								ClientServerEvents.Player.TouchedTrail:FireServer(owner, part[1].CFrame.p)
							end
						end
					end
				end
			end			
		end)

Detection works great, however I have not yet stress tested it (nor tried online)
Would you change anything to make it more efficient, or can you expand on how I could perform these checks without using a while wait() do loop?

2 Likes

the delay function where you delete the parts after lifetime is very inefficient
im assuming tabledotremovebykey searches the table for the “key” (which im pretty sure is actually the value) and then calls table.remove on the table / manually shifts everything down / some sort of fast remove / watever
a faster way would be to use a hashtable (roblox dictionary) or your own implementation of a list

you should probably just use roblox dictionary for simplicity so you could replace the thing starting at the first table.insert and ending at the end of delay function with:

Trail.Trails[to_player.Name].Parts[part] = true
Trail.Parts[part] = true

delay(Trail.Trails[to_player.Name].TrailInstance.Lifetime, function()
if Trail.Trails[to_player.Name] then
Trail.Trails[to_player.Name].Parts[part] = nil
Trail.Parts[part] = nil
part:Destroy()
end
end)

in my previous post i said you should make the parts be size 0,0,0 and the region take up more space but you can do it the way you’re doing it too (and with the additions im saying below it will be better i think)

idk how your makepart works but ideally it should do this:

  1. x size = trail diameter
  2. y size = 0.05 (since trails are 2d i think?)
  3. z size = DIAMAETER - more info on what this is later in this post
  4. position = hrp pos with offset like u have now, but make it face hrp lookVector

your region3 around the humanoid doesnt handle rotation so that might be problematic

ok so for DIAMETER and creating parts:
dont create parts every wait() (like your Trail.Movement function does)

instead of the wait() at the bottom wait until player position has changed by DIAMETER - i think you need to make your own function for detecting this

so DIAMETER is a constant you configure: higher DIAMETER = less parts made = faster and less lag
lower DIAMETER = better collision detection
you can tune it how you want

also i think you might have a bug with multiple humanoid.Running instances spawning your part creation multiple times and resulting in issues so you should just get rid of humanoid.Running and since you will anyways have distance change yielding instead of time waiting it will be fine

your code is a little messy in rest but it won’t really affect your performance and people here are all about avoiding microoptimizations but they may attack your sloppiness idk

srry for messy post too lol

1 Like

im assuming tabledotremovebykey searches the table for the “key” (which im pretty sure is actually the value) and then calls table.remove on the table / manually shifts everything down / some sort of fast remove / watever
a faster way would be to use a hashtable (roblox dictionary) or your own implementation of a list

You’re right, I initially wrote it this way to optimize looping through the positions for raycasting, as looping through an ordered loop (for i=1, #tbl) was significantly faster than using for i,pos in pairs(tbl). I will update this to use a dictionary, as I have no need to loop through the parts at all with the Region3.

So you’re saying I should recursively wait on the character’s Position.Changed:Wait(), until the distance between the last part made’s position and the current position is > the DIAMETER constant, before creating a new part? and have the part’s length be DIAMETER, so I can still effectively cover the length of the trail over the distance? (Just clarifying! :smiley: )

I did test what I had posted above and it was far more efficient than the constant raycasting/magnitude, no spikes at all, however I do see the room for improvement.

pretty much but would be cleaner to just use a while loop nested inside of the main while loop instead of a recursive function

… more room for improvement?!? HOLY well I give up

… more room for improvement?!? HOLY well I give up

I meant from what I currently have has room for improvement :joy:, not what you are suggesting!

1 Like

o ok
but i mean if what you are doing works for your situation you shouldn’t really do any extra unless you are doing it for yourself to learn / to use in the future idk because as my friend’s mom always says, don’t fix something if it isnt broken (i speak from experience with this)

Well, I definitely need this collision detection to be as optimal as possible, so I will keep adjusting it until it is the best I can get.

On a side note… Any idea why HumanoidRootPart:GetPropertyChangedSignal(“Position”):Wait() yields infinitely (even when moving), unless I change it manually through the Properties window?

changed only fires when it is changed from a script (so your own scripts or roblox’s scripts whenever they want / on lua side idk) and i guess roblox doesnt want to fire changed for position since it changes so often that it would be inefficient
at least thats why motor6d.Transform doesnt fire changed - even when changing from your own lua script i think

1 Like

Hmph, so I’ll nest this in a while wait() do loop and constantly check for position changes, I suppose

1 Like

I am in no way a scripter but I am HYPED!

a faster way would be to use a hashtable (roblox dictionary) or your own implementation of a list

So upon converting the Trail.Parts table to use a dictionary instead of an array, FindPartsInRegion3WithWhitelist no longer returns any parts. It seems the function does not support dictionaries, only arrays. Any ideas?

with FindPartsInRegion3WithWhitelist make the whitelist be a folder and parent all the trailer parts to that folder

1 Like

Ah, smart. I’ve already got them going into a folder anyways :cool:

I’m going to be honest here, using something very heavy like FindPartsInRegion3WithWhiteList every frame is a very bad idea.

Here’s a way to find if it intersects with the trails:

Store each trail as a {Origin Vector3, Lookvector Vector3, Length Number, Width Number} in a table called Trails.

Loop through each trail and do:

local RelativeLength = (Position-Trail.Origin):Dot(Trail.Lookvector) --Position being the head
if RelativeLength > 0 and RelativeLength < Trail.Length then
 if (RelativeLength*Trail.Lookvector-Position).magnitude < Trail.Width then
  return true --There is collision
 end
end

The above is fast cylinder collision detection and below is slower capsule collision detection.

local RelativeLength = (Position-Trail.Origin):Dot(Trail.Lookvector) --Position being the head
RelativeLength = (RelativeLength<0 and 0) or (RelativeLength>Trail.Length and Trail.Length) or RelativeLength --This method is 3 times faster than math.clamp
if (RelativeLength*Trail.Lookvector-Position).magnitude < Trail.Width then
 return true --There is collision
end
4 Likes

What happens if the trails aren’t straight segments?

Also FindPartsInRegion3WithWhiteList is O(lg N + k) in complexity with N being number of trail parts and k being output size (1 in this scenario)

That is PRETTY FAST