Each of the parts are just unions, let me get a screenshot of a few of them unioned for you.
Cool, if all of the regions are put into a single group and are flat on the XZ plane I’ll write a script that goes through each one, breaks it into its parts, finds the points, and then calls the previous function. I’ll start on it in an hour or two.
Awesome man, I’ll union them up while you work on that. Thank you so much for your help!
One option is to practically brute force it, taking advantage of the semi-accurate union physics.
- Raycast a bunch of grid points in a square, only whitelisting a single region part. This will let you find which points hit and which points don’t hit, letting you find an approximate border.
- Raycast a bunch of grid points a few grid positions away from the approximate border, whitelisting only every other region. This will let you find bordering regions.
Since this only needs to be ran once in Studio, the overall efficiency is not very important, but the dev time you put in is. Writing a simple brute-force solution like this will save you time.
I could do something like this, it was also my original idea, however @IdiomicLanguage seemed to come up with a potential solution that would work miles better then a bruteforce would it not?
This entirely depends on where and how you will use your solution. Both should give you similar results.
We can draft out two scenerios:
- You need to calculate this data in real-time in a live game. You want computational efficiency at the expense of longer dev time.
- You need to pre-calculate this in Studio. You want short dev time at the expense of computational efficiency.
To my understanding, you have all these regions set up in Studio and you won’t be generating any new ones in the game. Because of this, you can pre-calculate the surrounding regions, save it, and use that saved data in a live game. Your scenario is #2, then, not #1, right?
IdiomicLanguage’s solution certainly sounds more computational efficient and correct, but if – for example – you can spend 1 hour writing a brute force solution and 1 hour pre-generating data, that’s better than 4 hours writing an efficient solution that you’ll only use once.
How would I actually save a module full of the required data though? Can’t you only write to a modulescript/script via plugin? I’m not really looking to make a plugin for this haha.
You can give each region an id and convert the adjacency matrix into JSON using the IDs instead of tables for keys. You’d just have to name the regions the tostring of their ID. Just starting.
If you trigger the code from the command bar, then you can write to a module’s source with it. Lua scripts you save as .lua and run with the Run Script button also have write access to the Source property.
If you don’t want to do that, you can just save it to a StringValue then copy the Value to a modulescript. If you want an easy way to output approximate Lua code for a table, this module will format non-recursive tables with normal types like Lua syntax.
Another option is to save it as JSON and decode the JSON at runtime.
Here’s an example format you can save that data in:
return {
['001'] = { -- region name
'002', '003', '004', '007', '023', -- bordering region names
},
['002'] = {
'001', '003', -- etc.
}
}
1 Like
I am a tad bit confused on the usage of the module you provided. There doesn’t seem to be any actual examples for it, unless I’m looking in the wrong places?
Was looking in the wrong place, I’ll look in to this now.
You would need to copy the code into a ModuleScript. The usage looks something like this:
-- stick the source of inspect.lua ( https://github.com/kikito/inspect.lua/blob/master/inspect.lua ) in an `inspect` ModuleScript in ReplicatedStorage
local inspect = require(game.ReplicatedStorage.inspect)
local regions = {}
-- calculate your regions here!
-- now we make a module!
local regionsModule = Instance.new('ModuleScript')
regionsModule.Name = 'Regions'
regionsModule.Source = 'return '..inspect(regions)
regionsModule.Parent = game.ReplicatedStorage
print('YOUR REGIONS: '..inspect(regions))
inspect is really useful for checking out table contents in the output, but you can also use it like this for run-once internal dev utilities if you want a table formatted as Lua syntax.
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.
4 Likes
Well it sure does like to lag me game a ton, we’ll see it it works. I’m currently stuck in a not responding state…
lol It does compute a lot… you can add some wait() statements in there and print out the percentage to make sure there wasn’t an edge case and it is caught in an infinite loop. Just make sure to overwrite the old plugin when you save the edits so you don’t have two running.
Did it complete and did it do what you wanted it to?
It did a good 50% of it, I had to do the rest by hand but I’ll give you the solution either way.
What happened? Could it have been too short of a maximum gap?
It may have been, I also had some that were islands as well.
1 Like
Thank you! One last question for my future reference… About how long did it take to execute?
I’d say about 45 seconds to one minute
1 Like