# Creating Planar Graphs on Roblox

Hi there! So I have created this puzzle thingy that is a replica of the puzzle game Untangled, where there are a bunch of randomly generated points and lines, which you have to move so that each line is no longer touching another. Here is a video of what I have made so far:

Sorry, the file is pretty big so I uploaded it on twitter. let me know if you can’t see it.

Here is a quick gyazo gif if you can’t see the above:
https://gyazo.com/eef975389ef5db3d58f2579657cc0fc5

So my current system is capable of generating random lines, but it is not capable of calculating whether it is solveable, and how to solve it. It also can’t detect when a puzzle has been solved. So this question should be split into 3 smaller parts:

1. How to calculate whether a puzzle is solvable.

2. How can a script solve it. (Would be nice to have, but not neccesary)

3. How can it check for a completed puzzle

So while doing some research, I found out that the untangle puzzle uses something called planar graphs in plotting each point and caluclating how many lines to come off it. I still don’t exactly understand how it works however, and I am not sure whether something like this could be accomplished on roblox. (Hopefully it can, I’ve already spend a good chunk of time working on what I have so far lol)

Here is my script so far that generates the lines:

``````local MaxConnections = 4
for i,v in pairs(script.Parent:GetChildren()) do

if v:IsA("Frame") then
if v.Name ~= "Ignore" then
local connections = v.Folder
local Possible = true
local tries = 0
local Maxtries = (#script.Parent:GetChildren()) - 1
repeat
if #(v.Folder:GetChildren()) < MaxConnections then
for o,p in pairs(script.Parent:GetChildren()) do
if p.Name ~= "Ignore" then
if p:IsA("Frame") and p ~= v then
local canconnect = true
for q,w in pairs(connections:GetChildren()) do
if w.Value == p then
canconnect = false
end
end

if #(p.Folder:GetChildren()) >= MaxConnections then
canconnect = false
end
if canconnect == true then
local NewObject = Instance.new("ObjectValue")
NewObject.Parent = connections
NewObject.Value = p
local NewObject2 = Instance.new("ObjectValue")
NewObject2.Parent = p.Folder
NewObject2.Value = v
local Frame = Instance.new("Frame")
Frame.Name = "Ignore"
Frame.Parent = Parent
Frame.AnchorPoint = Vector2.new(0.5, 0.5)
local F1 = v
local F2 = p
Moveconnections[#Moveconnections+ 1] = RS.RenderStepped:Connect(function()
local XLength = F1.AbsolutePosition.X - F2.AbsolutePosition.X
local YLength = F1.AbsolutePosition.Y - F2.AbsolutePosition.Y
local Mag = (
Vector2.new(F1.AbsolutePosition.X, F1.AbsolutePosition.Y)
- Vector2.new(F2.AbsolutePosition.X, F2.AbsolutePosition.Y)
)
local CenterPosition = (F2.AbsolutePosition + F1.AbsolutePosition) / 2
Frame.Rotation = DivideSmaller(XLength, YLength)
Frame.Position = UDim2.fromOffset(CenterPosition.X + 15, CenterPosition.Y +15)
Frame.Size = UDim2.fromOffset(Mag.Magnitude, 1)
end)
break

end

end
end

end
else
Possible = false
end

tries  = tries + 1
if tries == Maxtries then
Possible = false
end
until #connections:GetChildren() == MaxConnections or Possible == false
end

end
end
end
``````

Sorry if it is a bit messy

But as you can see, it currently uses folders to see how many connections it currently has. So I want to know if there is a way to calculate everything all at once.

They actually published a journal article on it.

In 2014, mathematician David Eppstein published a paper[15] providing an effective algorithm for solving planar graphs generated by the original Planarity game, based on the specifics of the puzzle generation algorithm.

Here is the article, seems complicated

https://jgaa.info/getPaper?id=319

I believe you can get away doing something simpler by detecting lines crossing if you think of each line as a piecewise cartesian line.

1 Like

I think the article states how to solve a puzzle once it has been create, while it is helpful, I think instead of doing that I should be following whatever algorithm the puzzle uses to generate the puzzle.

As for the detecting lines, do you have any examples of how I might achieve this? I’m not to create with this stuff XD