I ran into a few problems while debugging the code, one of which I should mention. Unlike what the wiki has listed, UnionOperations do no have a :Separate method. I had to use plugin:Separate instead, which means that this script must be saved as a local plugin.
To run it, simply put the region parts / unions inside of a model named ‘Model’ in the workspace. Once saved as a local plugin it will immediately rename the parts / unions to their ID and print out the connection table in a format you can copy / paste into a script. Don’t forget to set the maxGap variable to be half the largest gap between regions. I say half because this number is used to expand both regions before their intersection is tested. Make sure to remove the plugin before continuing your work, it will continue to run in every time you test the game or load a place.
local DEBUG = false
local maxGap = 0.5
-- All regions must be near flat on the XZ plane
local surfaceNormal = Vector3.new(0, 1, 0)
local function union(from, to)
for key, value in next, from do
to[key] = value
end
return to
end
-- We can cache centers since regions are immutable
local centerCache = setmetatable({}, {__key = 'k'})
local function getCenter(region)
if centerCache[region] then
return centerCache[region]
end
local center = Vector3.new()
for i, point in next, region do
center = center + point
end
center = center / #region
centerCache[region] = center
return center
end
-- Line point a, line point b, center c, point p
local function isInside(a, b, c, p)
local ab = b - a
return ab:Cross(ab:Cross(c - a)):Dot(p - a) > 0
end
local function findConvexParts(originalRegion)
local region = union(originalRegion, {})
local convexParts = {[region] = true}
local center = getCenter(region)
local i = 1
local a = region[1]
local b = region[2]
local c = region[3]
while c do
if isInside(a, c, center, b) then
local prev
if i == 1 then
prev = region[#region]
else
prev = region[i - 1]
end
-- Triangle are garenteed to be convex, being the 2D simplex
convexParts[{b, a, prev}] = true
-- Bye-bye point a
table.remove(region, i)
center = center - a / #region
else
i = i + 1
end
a = b
b = c
c = region[(i+1 % #region) + 1]
end
return convexParts
end
local function getOutwardNormal(a, b, center)
local line = b - a
return line:Cross(line:Cross(center - a)).Unit
end
local function expand(originalRegion)
local region = {}
local center = getCenter(originalRegion)
local prevI = #originalRegion
for i, point in ipairs(originalRegion) do
local prev = originalRegion[prevI]
local next = originalRegion[(i % #originalRegion) + 1]
local normA = getOutwardNormal(point, prev, center)
local normB = getOutwardNormal(point, next, center)
region[i] = point + maxGap * (normA + normB)
prevI = i
end
return region
end
-- 2D intersection algorithm
-- Doesn't handle one containing another
local function isIntersecting(region1, region2)
local a = region1[#region1]
for i, b in next, region1 do
local c = region2[#region2]
for j, d in next, region2 do
local ab = b - a
local cd = d - c
local e = a - c
local t
local abm = ab.X / ab.Z
local cdm = cd.X / cd.Z
if math.abs(ab.X) > math.abs(ab.Z) then
t = (e.Z * cdm - e.X) / ab.X / (1 - cdm/abm)
else
t = (e.X / cdm - e.Z) / ab.Z / (1 - abm/cdm)
end
local u
if math.abs(cd.X) > math.abs(cd.Z) then
u = (e.X - ab.X * t) / cd.X
else
u = (e.Z - ab.Z * t) / cd.Z
end
print(t, u)
if t >= 0 and t <= 1 and u >= 0 and u <= 1 then
return true
end
c = d
end
a = b
end
end
local function getBoundingCircle(region)
local center = getCenter(region)
local maxRadius = 0
for i, point in next, region do
local radius = (point - center).Magnitude
if radius > maxRadius then
maxRadius = radius
end
end
return {
center = center;
radius = maxRadius;
}
end
local function circlesIntersect(circle, otherCircle)
return (circle.center - otherCircle.center).Magnitude < circle.radius + otherCircle.radius
end
local function unionToParts(instance, parts)
if instance:IsA 'UnionOperation' then
-- UnionOperations don't have the 'Separate' method despite what
-- the wiki page says. This means that we must use the plugin
-- version, meaning that this script must be run as a plugin.
--for subInstance in next, instance:Separate() do
for i, subInstance in next, plugin:Separate{instance} do
unionToParts(subInstance, parts)
end
elseif instance:IsA 'BasePart' then
parts[#parts + 1] = instance
end
return parts
end
local X = 'X'
local Y = 'Y'
local Z = 'Z'
local others = {
X = {X = Y, Y = Z};
Y = {X = X, Y = Z};
Z = {X = X, Y = Y};
}
local function partToPoints(basepart)
local cf = basepart.CFrame
local s = basepart.Size / 2
local vectors = {
X = s.X * cf.RightVector;
Y = s.Y * cf.UpVector;
Z = s.Z * cf.LookVector;
}
local maxDot = 0
local maxAxis
for axis, vector in next, vectors do
local curDot = surfaceNormal:Dot(vector)
if curDot * curDot > maxDot * maxDot then
maxDot = curDot
maxAxis = axis
end
end
local dirs = others[maxAxis]
local p = basepart.Position + math.sign(maxDot) * vectors[maxAxis]
local points = {
p + vectors[dirs.X] + vectors[dirs.Y];
p + vectors[dirs.X] - vectors[dirs.Y];
p - vectors[dirs.X] + vectors[dirs.Y];
p - vectors[dirs.X] - vectors[dirs.Y];
}
if maxAxis == X and basepart:IsA 'WedgePart' then
points[1] = points[4]
points[4] = nil
end
return points
end
-- This function allows all points within a stud grid cell
-- to be combined into a single point. If greater precision
-- is required, round each number to the desired accuracy.
local partKey = '%d %d %d'
local function pointToKey(point)
return partKey:format(
math.floor(point.X + 0.5),
math.floor(point.Y + 0.5),
math.floor(point.Z + 0.5)
)
end
local debugHeight = 10
local function makePoint(point, isInside)
local p = Instance.new 'Part'
p.Anchored = true
p.Shape = Enum.PartType.Ball
p.Size = Vector3.new(0.2, 0.2, 0.2)
p.Color = isInside and Color3.new(0, 0, 1) or Color3.new(0, 1, 0)
p.Position = point
p.Parent = workspace
end
local function partsToPoints(parts)
local points = {}
local isInternal = {}
for i, part in next, parts do
for j, point in next, partToPoints(part) do
local key = pointToKey(point)
if points[key] then
isInternal[key] = true
else
points[key] = point
end
end
end
local outsidePoints = {}
for key, point in next, points do
if not isInternal[key] then
outsidePoints[#outsidePoints + 1] = point
end
if DEBUG then
makePoint(point, isInternal[key])
end
end
return outsidePoints
end
local function findAdjacent(model)
local adjacent = {}
local unions = model:GetChildren()
local regions = {}
local toOriginal = {}
local circles = {}
for i, union in ipairs(unions) do
union.Name = tostring(i)
regions[i] = partsToPoints(unionToParts(union:Clone(), {}))
adjacent[i] = {}
end
for i, region in ipairs(regions) do
for part in next, findConvexParts(expand(region)) do
toOriginal[part] = i
circles[part] = getBoundingCircle(region)
end
end
-- Use very quick bounding circle tests to cut down number of checks
local checkList = {}
for part, circle in next, circles do
for other, otherCircle in next, circles, part do
if toOriginal[part] ~= toOriginal[other] and circlesIntersect(circle, otherCircle) then
checkList[{part, other}] = true
end
end
end
-- Perform exact 2D intersection tests on near parts
for set in next, checkList do
local part1 = set[1]
local part2 = set[2]
local original1 = toOriginal[part1]
local original2 = toOriginal[part2]
-- We'll need to see if the regions the parts are from
-- have already been found to be adjacent
if not adjacent[original1][original2]
and isIntersecting(part1, part2)
then
adjacent[original1][original2] = true
adjacent[original2][original1] = true
end
end
return adjacent
end
local tab = ' '
local function _deepPrint(t, tabs, visited)
if visited[t] then
return print(tabs, t)
end
visited[t] = true
for key, value in next, t do
if type(value) == 'table' then
print(tabs, key, '= {')
_deepPrint(value, tabs .. tab, visited)
print(tabs, '};')
else
print(tabs, key, '=', value, ';')
end
end
end
local function deepPrint(t)
print '{'
_deepPrint(t, '', {})
print '}'
end
local t = findAdjacent(workspace.Model)
deepPrint(t)
Let me know if you have any questions or issues.