Algorithms Mega-Thread

Algorithm Mega-Thread

This thread is the place to find and share common algorithms that you use on frequently while developing on Roblox.

Read Before Posting

In the interests of keeping this thread clean, please keep the following in mind before submitting a reply:

  • Posts should be limited to algorithms only, nothing else.
  • Posts should use a common format (shown below) for consistency.
  • Before posting, check if someone else has already shared the algorithm.
  • If you’re open to alterations, consider making a wiki post.

If you have a question about an existing algorithm, please create a new post and link back to this thread.

If you believe your implementation is superior, please give details about what sets it apart from the existing post when submitting your revision.

Most importantly – Thanks for contributing!

Example Post

Algorithm Name

An explanation about what the algorithm does and how it can be used.

-- implementation of algorithm

Additional details that might be relevant to the user

Source: (if applicable)

7 Likes

Angle Between Vectors

To calculate the angle between two vectors without a normalization step:

local function angleBetweenVectors(a, b)
	return math.atan2(a:Cross(b).Magnitude, math.abs(a:Dot(b)))
end

The more common acos(a:Dot(b)) method should be avoided due to imprecision issues close to the poles, and because it relies on how well the vectors are normalized.

6 Likes

Test if a point is in a box

To test if a 3D point pt is inside a bounding box defined by a CFrame cf and size sz:

local function testPointOBB(pt, cf, sz)
    -- transform pt to cf's local space
    local objPos = cf:pointToObjectSpace(pt)

    -- test axis magnitudes against extents
    return
        abs(objPos.x) <= sz.x*0.5 and
        abs(objPos.y) <= sz.y*0.5 and
        abs(objPos.z) <= sz.z*0.5
end

Optimized test for lots of boxes: Article | Code

3 Likes

Wait for the first of N signals to fire

Given a tuple of Lua signals, to wait only for the first of them to fire without leaking memory:

local function waitForFirst(...)
	local shunt = Instance.new("BindableEvent")
	local slots = {...}
	
	local function fire(...)
		for i = 1, #slots do
			slots[i]:Disconnect()
		end
		return shunt:Fire(...)
	end
	
	for i = 1, #slots do
		slots[i] = slots[i]:Connect(fire)
	end
	
	return shunt.Event:Wait()
end

Usage

waitForFirst(humanoid.Died, character.AncestryChanged)
4 Likes

Get Angle from Three Side Lengths of a Triangle

The underlying math used here is often referred to as the “Law of Cosines”. Googling that exact phrase will also get you a handy visualization / calculator.

All I’ve done is taken the math above and translated it into lua.

function getTriAngle(a, b, c)
    local numerator = (a^2) + (b^2) - (c^2)
    local denominator = (2*a*b)
    return math.acos(numerator/denominator)
end

I’ve used this algorithm a ton in working with inverse-kinematics among other things. Enjoy!

2 Likes

Euler numbers are common in 3D manipulation code. On Roblox, they’re formatted to automatically round to be within -180 and 180 degrees. This can make combining Euler numbers on the same axis difficult.

To overcome this difficulty I’ve developed 3 basic algorithms to allow me to treat Euler numbers like regular numbers. They all use radians, however, I’ll be discussing them using degrees because I feel they’re more accessible to think about as many of us were taught about angles using degrees first.

Euler Round

Manipulating a stored Euler number directly can lead to numbers being outside -180 to 180. Usually, Roblox will automatically round that number to be within acceptable ranges when it’s applied to one of their custom data types. However, if you’ve temporarily stored an Euler Number as a regular number it will not do this. If your programming assumes the number to be between 180 and -180 (like the other methods in this post) you’ll need a way to round numbers to be within 180 and -180.

function eulerRound(radNum)
    if math.abs(math.deg(radNum)) > 180 then
        return -math.sign(radNum) * (math.rad(180) - math.abs(radNum - (math.sign(radNum) * math.rad(180))))
    else
        return radNum
    end
end

Euler Subtract / Distance

This finds the closest distance between two Euler numbers similar to how 5 - 3 = 2 gives the distance between two regular numbers.

This properly handles instances where a large positive Euler number needs to find the quickest route to a large negative one. For example, going from 150 to -170 in traditional math will lead to the conclusion that you need to rotate -320 degrees to reach that point. However with Euler 180 = -180, thus the shortest path is actually to rotate 40 degrees.

function eulerDistance(radNum1, radNum2)
    local res1 = eulerRound(radNum2) - eulerRound(radNum1)
    local res2 = -math.sign(res1)*(math.rad(360)-math.abs(res1))
    if math.abs(res1) < math.abs(res2) then
        return res1
    else
        return res2
    end
end

Euler Lerp

In my opinion, the most useful method on this list as well as the product of the two previous methods is Euler Lerp. This method will return a number between two radians in proportion to the alpha (a number from 0 to 1).

function eulerLerp(radNum1, radNum2, alpha)
    return eulerRound(radNum1 + (eulerDistance(radNum2, radNum1) * alpha))
end

I can’t vouch for these being the most optimized ways to accomplish these tasks, but they work. If anyone has a faster route I’ll be more than happy to update the code in both this post as well as my own games. Enjoy!

2 Likes

SurfaceGui-to-World

Given a 2D position on a SurfaceGui, convert it to 3D world space.

function guiPointToWorld(gui, point)
	local adornee = assert(gui.Adornee)

	local normalizedPoint = point/gui.AbsoluteSize
	local dir = Vector3.FromNormalId(gui.Face)

	local projY = math.abs(dir.z + dir.x)
	local projZ = dir.x + math.abs(dir.y)

	local origin = Vector3.new(
		dir.x - dir.y - dir.z,
		dir.y + projY,
		dir.z + projZ)*0.5
	
	local surfX = Vector3.new(dir.z, 0, -projZ)*normalizedPoint.x
	local surfY = Vector3.new(dir.y, -projY, 0)*normalizedPoint.y

	local pos = origin + surfX + surfY

	return adornee.CFrame*(adornee.Size*pos)
end
2 Likes

Just to clarify beforehand, those are 3d equations.

Closest Distance from Line

Find the distance between a point and a line.
image

local function getDistanceFromLine(point, linePoint, lineDirection)
    return (point - linePoint):Cross(lineDirection).Magnitude / lineDirection.Magnitude
end

Closest Point from Line

Given any point, return the coordinates of the closest point on the line.
image

local function getClosestPointFromLine(point, linePoint, lineDirection)
    local projection = (point - linePoint):Dot(lineDirection) / lineDirection.Magnitude ^ 2
    return linePoint + projection * lineDirection
end
3 Likes

Scale Model From Pivot

This is an adapted version of Sleitnick/Crazyman32’s scaling function found here.

function ScaleModel(model, scale, origin)
	origin = origin or model.PrimaryPart.Position
	
	for _, part in ipairs(model:GetDescendants()) do
		if part:IsA("BasePart") then
			local pos = part.Position
			local rotCf = part.CFrame - pos
			local fromOriginDir = pos - origin
			part.Size *= Vector3.new(scale, scale, scale)
			part.CFrame = rotCf + origin + fromOriginDir*scale
		end
	end
end
2 Likes