If you look at this screenshot you will see multiple regions separated by a brown line, I need to know the surrounding regions of a current region.
Here is another picture of what I’m attempting to find out, the green one will be our selected region and the red ones will be the ones that I want to find out about.
I have over 250 regions and I don’t really want to go through and attach each region to the ones that surround it, so would it be possible to make a system for this?
Did you create these regions yourself? Is there an underlying datastructure we can use or are these just parts?
You’ll probably have to run a geometrical algorithm of getting the smallest geometrical shape from center points of each region, while checking that these points create a geometry that contain the green center.
There were visualisations of them here: https://www.roblox.com/games/905378009/Algorithm-Showcase by @sircfenner. I think this is the correct link, I totally forgot if it was it, because last time I checked I lost track of the link and also I don’t have access on my primary device yet.
All of these were custom made and hand placed.
You can use a Region3 check (the Region3 would probably be centered at the region you want to check with a size that’s twice the size of the bounding box of the region) to get a list of all all possible neighbors.
For each possible neighbor, check with a raycast if there’s a direct line of sight between it and the original region. If there is, then it’s an actual neighbor. Otherwise, it isn’t.
What a nasty problem! Do you have access to the points of the parts? Are these actual parts, unions, or mesh parts? To make the problem more complicated, these arn’t even convex shapes…
If you have the points, I’ll probably write the script for you
Each of these parts happen to be a union. I wonder if it’d be possible to union each part, get all of the unioned parts and there corners, then write a general shape from that.
Okay, I have the bulk of the code complete but untested. To make it work, findAdjacent needs to be called with a table whose keys are arrays of the Vector2 points of each region. Let me know if you need help doing that. This code is pretty close to the solution and should only have minor bugs, if any. Also lmk if you have any trouble debugging it.
It returns a table whose keys (key 1) is each region, and the value is a table with the keys (key 2) equal to all the regions adjacent to key 1. Value 2 is just true. It should make sense when you look at the code.
local function union(from, to)
for key, value in next, from do
to[key] = value
end
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 = Vector2.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(c - a) * ab:Cross(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 maxGap = 0.5
local function expand(originalRegion)
local region = {}
local center = getCenter(originalRegion)
local prevI = #region
for i, point in next, originalRegion do
local prev = originalRegion[prevI]
local next = originalRegion[(i % #region) + 1]
local normA = getOutwardNormal(point, prev, center)
local normB = getOutwardNormal(point, next, center)
region[i] = point + maxGap * (normA + normB)
end
return region
end
local function contains(region, other, center)
for i, a in next, region do
local b = region[(i % #region) + 1]
for j, p in next, other do
if not isInside(a, b, center, p) then
other[j] = nil
end
end
end
if next(other) then
return true
end
end
-- 2D intersection algorithm
-- For 2D shapes to intersect, one must have a point inside another
-- Since they are convex the seperating line must be the line between them
local function isIntersecting(region1Original, region2Original)
local region1 = union(region1Original, {})
local region2 = union(region2Original, {})
return contains(region1Original, region2, getCenter(region1))
or contains(region2Original, region1, getCenter(region2))
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 findAdjacent(originalRegions)
local toOriginal = {}
local adjacent = {}
local circles = {}
for region in next, originalRegions do
adjacent[region] = {}
for part in next, findConvexParts(expand(region)) do
toOriginal[part] = region
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
I am a bit confused on initializing this so it works, could you explain what you mean by…
Would that just be the position of the union, or the position of all of the parts inside the union?
That would be the points that define the boundry of each region, the edge points / corners. The first point is any point on the edge of the region and the next point is a point adjacent to it. The first and last points are also adjacent, forming a closed shaped. I’m not sure how you’ll get the points… it depends on how the unions were created. If you post some more information, maybe I could help with that too.
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.
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:
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.
}
}
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.