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

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

7 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

4 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!

3 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
``````
4 Likes

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
``````
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
``````
3 Likes

## 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] = { = Index}
end

for Index = 0, Length2 do
Matrix[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;
}
``````
2 Likes