Algorithms Mega-Thread

[Sharp]

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)

[Sharp]

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, 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.

[Fractality]

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

[Fractality]

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)

[CJ_Oyer]

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!

[CJ_Oyer]

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!

[Fractality]

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

[Plutonem]

Just to clarify beforehand, those are 3d equations.

Closest Distance from Line

Find the distance between a point and a line.

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.

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

[EncodedLua]

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

[HowManySmall]

Fuzzy Search

This basically will sort an array of strings by searching through them to see which one is closest based on a “distance” between them. I’m not really one to explain it, so you can check the Wikipedia page for fuzzy search and Levenshtein distance if you want to know more.

--!strict
type Array<Value> = {Value}
type int = number -- This is just so I have more specific types.

export type ResultsEntry = {
	Distance: int,
	String: string,
}

export type SortFunction = (ResultsEntry, ResultsEntry) -> boolean

--[[**
	Calculates the Levenshtein distance of two strings. This function is better than most because it takes utf8 characters into account. See the Wikipedia entry for more information.
	@param [t:string] String1 The first string.
	@param [t:string] String2 The second string.
	@returns [t:integer] The distance between the two strings.
**--]]
local function Levenshtein(String1: string, String2: string): int
	if String1 == String2 then
		return 0
	end

	local Length1 = utf8.len(String1) :: number -- I apparently have to do this?
	local Length2 = utf8.len(String2) :: number

	if Length1 == 0 then
		return Length2
	elseif Length2 == 0 then
		return Length1
	end

	local Matrix = {} -- Would love to use table.create for this, but it starts at 0.
	for Index = 0, Length1 do
		Matrix[Index] = {[0] = Index}
	end

	for Index = 0, Length2 do
		Matrix[0][Index] = Index
	end

	local Index = 1
	local IndexSub1

	for _, Code1 in utf8.codes(String1) do
		local Jndex = 1
		local JndexSub1
		local PreviousArray

		for _, Code2 in utf8.codes(String2) do
			local Cost = Code1 == Code2 and 0 or 1
			IndexSub1 = Index - 1
			JndexSub1 = Jndex - 1
			PreviousArray = Matrix[IndexSub1]

			Matrix[Index][Jndex] = math.min(PreviousArray[Jndex] + 1, Matrix[Index][JndexSub1] + 1, PreviousArray[JndexSub1] + Cost)
			Jndex += 1
		end

		Index += 1
	end

	return Matrix[Length1][Length2]
end

local function SortResults(A: ResultsEntry, B: ResultsEntry): boolean
	return A.Distance < B.Distance
end

--[[**
	Runs a Levenshtein distance on an array of strings, and sorts them based on which ones matched the passed string the closest.
	@param [t:string] String The string you are using to search with.
	@param [t:array<t:string>] ArrayOfStrings The array of strings you are searching against.
	@param [t:optional<t:callback>] SortFunction The optional sorting function to use. Check the function signature if you are going to use it. Default is sorting by closest distance.
	@returns [t:array<ResultsEntry>] The array of results.
**--]]
local function FuzzySearch(String: string, ArrayOfStrings: Array<string>, SortFunction: SortFunction?): Array<ResultsEntry>
	local Results = table.create(#ArrayOfStrings)

	for Index, Value in ipairs(ArrayOfStrings) do
		Results[Index] = {
			Distance = Levenshtein(String, Value);
			String = Value;
		}
	end

	table.sort(Results, SortFunction or SortResults)
	return Results
end

return {
	Levenshtein = Levenshtein;
	FuzzySearch = FuzzySearch;
}

[AstroCode]

Update: This has been implemented as Random.new():NextUnitVector().

Unbiased random unit vector

Generates random Vector3s uniformly distributed on the unit sphere. Found in this article.

It uses the Box-Muller transform to convert four random uniformly distributed points into three normally distributed points that are used as the coordinates of the vector. Then the vector is unitized.

local function randomUnitVector()
	local sqrt = math.sqrt(-2 * math.log(math.random()))
	local angle = 2 * math.pi * math.random()

	return Vector3.new(
		sqrt * math.cos(angle),
		sqrt * math.sin(angle),
		math.sqrt(-2 * math.log(math.random())) * math.cos(2 * math.pi * math.random())
	).Unit
end

[AstroCode]

Reflect CFrame over plane

Reflects a CFrame over a plane defined by a position and normal vector.

local function reflectVector(v: Vector3, axis: Vector3)
    return v - 2 * (axis * v:Dot(axis))
end

local function reflectCFrame(cf: CFrame, planePos: Vector3, planeNormal: Vector3)
    return CFrame.fromMatrix(
        planePos + reflectVector(cf.Position - planePos, planeNormal),
        -reflectVector(cf.XVector, planeNormal),
        reflectVector(cf.YVector, planeNormal),
        reflectVector(cf.ZVector, planeNormal)
    )
end

The following code does the same thing but with CFrame multiplication. Importantly, the plane must instead be a CFrame whose LookVector is the normal.

local localReflection = CFrame.new(0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, -1)
local worldReflection = CFrame.new(0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 1)

local function reflectCFrame(cf: CFrame, plane: CFrame)
    return plane * localReflection * plane:Inverse() * cf * worldReflection
end

This version is preferable if you are performing many reflections over the same plane because you can pre-compute the first 2 CFrame multiplies (plane * localReflection * plane:Inverse()).

[AstroCode]

Closest point in box

If a point is outside the box, then it returns the closest point on the box. If a point is inside the box, then it returns the point.

Most readable

local function closestPointInOBB(point: Vector3, boxCF: CFrame, boxSize: Vector3): Vector3
	local localPoint = boxCF:PointToObjectSpace(point)
	local halfSize = boxSize / 2
	local closestPoint = localPoint:Min(halfSize):Max(-halfSize)
	return boxCF:PointToWorldSpace(closestPoint)
end

Fastest

local function closestPointInOBB(point: Vector3, boxCF: CFrame, boxSize: Vector3): Vector3
	local localPoint = boxCF:PointToObjectSpace(point)
	local halfSizeX = boxSize.X / 2
	local halfSizeY = boxSize.Y / 2
	local halfSizeZ = boxSize.Z / 2
	local closestPoint = Vector3.new(
		math.clamp(localPoint.X, -halfSizeX, halfSizeX),
		math.clamp(localPoint.Y, -halfSizeY, halfSizeY),
		math.clamp(localPoint.Z, -halfSizeZ, halfSizeZ)
	)
	return boxCF * closestPoint
end

Note that if you are calling this function repeatedly on the same boxCF, it can be made faster by precomputing boxCFInv = boxCF:Inverse() and doing local localPoint = boxCFInv * point.

Benchmarks

I tested 5 variables.

1. Clamping the coordinates is faster than Vector3:Min/Max
2. Inlining the halfSize coordinates is faster than not
3. boxCF * closestPoint is faster than boxCF:PointToWorldSpace(closestPoint)
4. boxCF:PointToObjectSpace(point) is faster than boxCF:Inverse() * point
5. Precomputing boxCF:Inverse() when possible is faster than boxCF:PointToObjectSpace(point)

benchmarks.lua (5.5 KB)

[Quenty]

I actually have 2 more algorithms that are useful and related in my library which you can use here.

Sometimes it’s useful to clamp a point onto a bounding box, in which case, the following algorithm is used.

Quenty/NevermoreEngine/blob/main/src/boundingboxutils/src/Shared/BoundingBoxUtils.lua#L49

--[=[
	Clamps a point inside of a given bounding box
	See: https://devforum.roblox.com/t/finding-the-closest-vector3-point-on-a-part-from-the-character/130679/2
	@param cframe CFrame -- CFrame of bounding box
	@param size Vector3 -- Size of bounding box
	@param point Vector3 -- Point to transform
	@return Vector3 -- Clamped point
	@return Vector3 -- Center of bounding box
]=]
function BoundingBoxUtils.clampPointToBoundingBox(cframe, size, point)
	local transform = cframe:pointToObjectSpace(point) -- transform into local space
	local halfSize = size * 0.5
	return cframe * Vector3.new( -- Clamp & transform into world space
		math.clamp(transform.x, -halfSize.x, halfSize.x),
		math.clamp(transform.y, -halfSize.y, halfSize.y),
		math.clamp(transform.z, -halfSize.z, halfSize.z)
	), cframe.Position
end

--[=[
	Pushes a point to lie within the bounding box
	@param cframe CFrame -- CFrame of bounding box
	@param size Vector3 -- Size of bounding box
	@param point Vector3 -- Point to transform
	@return Vector3
]=]
function BoundingBoxUtils.pushPointToLieOnBoundingBox(cframe, size, point)
	local transform = cframe:pointToObjectSpace(point) -- transform into local space
	local halfSize = size * 0.5
	local x = transform.x < 0 and -halfSize.x or halfSize.x
	local y = transform.y < 0 and -halfSize.y or halfSize.y
	local z = transform.z < 0 and -halfSize.z or halfSize.z
	return cframe * Vector3.new(x, y, z), cframe.Position
end