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)


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)))

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.


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
        abs(objPos.x) <= sz.x*0.5 and
        abs(objPos.y) <= sz.y*0.5 and
        abs(objPos.z) <= sz.z*0.5

Optimized test for lots of boxes: Article | Code


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 ="BindableEvent")
	local slots = {...}
	local function fire(...)
		for i = 1, #slots do
		return shunt:Fire(...)
	for i = 1, #slots do
		slots[i] = slots[i]:Connect(fire)
	return shunt.Event:Wait()


waitForFirst(humanoid.Died, character.AncestryChanged)

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)

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


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))))
        return radNum

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
        return res2

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))

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!



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 =
		dir.x - dir.y - dir.z,
		dir.y + projY,
		dir.z + projZ)*0.5
	local surfX =, 0, -projZ)*normalizedPoint.x
	local surfY =, -projY, 0)*normalizedPoint.y

	local pos = origin + surfX + surfY

	return adornee.CFrame*(adornee.Size*pos)

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

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

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 *=, scale, scale)
			part.CFrame = rotCf + origin + fromOriginDir*scale

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.

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

	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

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

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

	local Index = 1
	local IndexSub1

	for _, Code1 in do
		local Jndex = 1
		local JndexSub1
		local PreviousArray

		for _, Code2 in 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

		Index += 1

	return Matrix[Length1][Length2]

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

	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;

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

return {
	Levenshtein = Levenshtein;
	FuzzySearch = FuzzySearch;