How can they not be straight segments? Even Roblox’ Trail object uses straight segments.
A*O(log(N)+k) and B*O(N) and here in this case A is much bigger than B. I think my method would be faster if you don’t put more than 10 thousand objects and at that point probably both of the equations would lag too much anyway. I suppose you would want to run this on mobile. There is also the point of FindPartsInRegion3 being not actually an accurate way of collision detection since the region orientation is fixed. There is also the point of you actually creating and deleting those parts which is a cause of lag on its own. With my method, you wouldn’t need to put any parts.
My bad about the trail segments, I thought you were storing one segment per trail not multiple segments
idk I still think it might be difficult to get good segments though because of non straight player movement and you run the risk of it turning into OP’s scenario 2 (perhaps even more inefficient though because of the math you are doing)
For your collision detection you can use region3 to get an estimate and then something more specific to get more accurate collision detection (although your k would increase) - but you have flexibility with this solution and you can tune it to whatever is optimal for your use case, idk if you really have that for an inherent O(n) solution
Yes it’s nearly the same as scenario 2 but since we’re checking a whole segment not points, you can just listen to it every 0.5 seconds or something and create the segments requiring much less calculations total.
Actually you don’t have to listen to it. Just do previous position to the new position that’s already known. You don’t actually have to send trail info as it is already available to you by knowing just the current position of all the other characters which Roblox already makes readily available.
If a player moves zig zag it will be practically like solution 2 unless you want to completely lose accuracy
I’m not sure what you mean, you still have to look back at previous trail segments that haven’t expired (been in existance for longer than trail.lifetime)
I mean I would imagine either the server handling collisions and telling clients or clients handling their own collision and telling server (telling = sending through remote events)
But that is only when there is a collision and would be the exact same as your scenario
Checking position would obviously not be done via remote events lol
Alright yeah, that’d be the good way to do it. There’s also the fact that you can combine segments. While adding a new segment, check if their lookvectors are very close (product the two) to each other and if they are don’t create a new entry but just update their tick time and length. Even though you would lose disappearance accuracy doing it maximum of twice per segment wouldn’t cause any trouble and it might even give you a 20% increase in performance on average.
Merging segments sounds like a good idea
I’m assuming by disappearance accuracy you mean trail lifetime thing? If so then you could augment your segment by adding a queue of {originPosition,tick} and when you are checking lifetime, you check against queue:Top() and if it is < time you remove just that part of the segment and iterate through etc
You could do that but we’re trying to be very efficient here. If you wanted to do that, you can combine every straight line and get better performance.
If the player was always to walk straight you would gain 50% performance increase and if I make the assumption that the player turns every 3 segments on average, it’d be 20%.
I kinda wanna code a solution for this so I’ll show you what I mean maybe but its: either you create a new segment, or (EXCLUSIVE OR), if your conditions for merging segments are satisfied, instead of just updating the tick and length of the previous, you push the tick and new origin position to the previous segment’s queue (note: instead of doing origin position you could do length to maintain the level of accuracy your solution currently has, but origin position would allow updatnig slope to most recent)
And when you check for segment collision you would do what you said with just the Top of the queue of each segment (not all items so checking (which is the main bottleneck in your solution) would be the same speed)
I said combine every straight line only once so if the guy is moving straight, instead of using say 100, you’d be using 50 segments (since it’s O(N) method, it’s 50% increase in performance) and if the player takes a turn every third segment (assuming) that means a segment will be left which changes that (1/2) to (1/2)*(1/3) which is 1/5 and that is 20%.
Well I made a script for what I meant and the cylinder collision idea you said
I haven’t really benchmarked it though but if you (@Fm_Trick ) decide to use this type of method instead of the region3 please lmk
--[[
TrailCollision
Detects whether trail collides
100% abstract and is O(n) but merges segments with similar directions
accurate as sampling is
uses cylinder-point collision (treats trail as a cylinder)
does not handle rotations
Idea:
https://devforum.roblox.com/t/trail-collision-detection/148935
--]]
-- Constants
local mergeThreshold = math.cos(math.rad(5)) -- cos of merge threshold
-- cached vars
local tick = tick
-- main
local function addSegment(trail,start,fin,expireTime,canMerge)
-- expireTime = tick()+lifetime
-- canMerge = is it safe to try merging with previous segment? (if you have been calling addsegment without pause (can assume that start of this segment = end of previous segment) then set canMerge to true
-- note that canmerge will not restrict new segments from merging with this segment
local i = trail[3]
local sx = start.X
local sy = start.Y
local sz = start.Z
local dx = fin.X-sx
local dy = fin.Y-sy
local dz = fin.Z-sz
-- normalize d
dx = dx*dx
dy = dy*dy
dz = dz*dz
start = (dx+dy+dz)^.5 -- reuse vars, this is actually len
fin = 1/start -- just a temporary now
dx = dx*fin
dy = dy*fin
dz = dz*fin
-- fin norm z
local prev = trail[i]
if canMerge and i ~= 3 and prev and (prev[1]*dx + prev[2]*dy + prev[3]*dz) > mergeThreshold then -- dot product (both vecs are normalized already)
-- add to segment
prev[7] = prev[7]+start -- update total segment length
-- get insertion point and update size
local j = prev[9]
j = j+2
prev[9] = j
-- insert to q
prev[j] = start
prev[j+1] = expireTime
else
-- make a new segment
i=i+1
trail[3] = i
trail[i] = {
-- direction
dx, -- 1
dy, -- 2
dz,-- 3
-- start
sx, -- 4
sy, -- 5
sz, -- 6
start, -- 7: total segment len
10, -- 8: queue start pos
10, -- 9: queue end pos (start with 1 elem (curr segment))
start, -- 10: segment len
expireTime, -- 11: segment expire time
}
end
end
local function collides(trail,pos) -- sqdist if collides, nil if not
-- O(n)
local flag -- whether or not to check expiration on future segments
local time = tick()
local sqrad = trail[1]
for i = trail[2],trail[3] do
local seg = trail[i]
local dx
local dy
local dz
-- point in local coordinates of start (pos-start)
local px
local py
local pz
local totalLen
if not flag then -- check expiration
local addLen = 0 -- len to add
-- start and end of q
local start = seg[8]
local fin = seg[9]
for j = start,fin,2 do
if time>seg[j+1] then
-- this piece of the segment is expired
local len = seg[j]
addLen = addLen+len
seg[j] = nil
seg[j+1] = nil
start=start+2 -- increase start pos
else
flag = true -- no other ones after this will be expired since sequential
break
end
end
if start>fin then
-- entire segment is expired
trail[i] = nil -- remove from trail
trail[2] = i+1 -- increase start pos
seg = nil -- use as flag to tell that it expired so dont check collision
-- feels bad not having continue
else
totalLen = seg[7] - addLen -- subtract expired segments
seg[7] = totalLen -- update total len
seg[8] = start -- update start pos
dx = seg[1]
dy = seg[2]
dz = seg[3]
-- update new start
px = seg[4]+dx*addLen
py = seg[5]+dy*addLen
pz = seg[6]+dz*addLen
seg[4] = px
seg[5] = py
seg[6] = pz
-- point in local cords
px = pos.X-px
py = pos.Y-py
pz = pos.Z-pz
end
end
if seg then -- its not expired
if not dx then
-- if flag was true then retrieve vars
dx = seg[1]
dy = seg[2]
dz = seg[3]
px = pos.X-seg[4]
py = pos.Y-seg[5]
pz = pos.Z-seg[6]
totalLen = seg[7]
end
-- cylinder-point collision
local dot = dx*px + dy*py + dz*pz
if dot > 0 and dot < totalLen then
local sqdist = px*px+py*py+pz*pz - dot*dot
if sqdist < sqrad then
return sqdist
end
end
end
end
end
local TrailCollision = {
AddSegment = addSegment,
Collides = collides,
}
function TrailCollision.New(rad)
return {
AddSegment = addSegment,
Collides = collides,
rad*rad, -- sq rad
4, -- queue start position
3, -- queue end position
}
end
return TrailCollision
