Determine connection through multiple parts – like electrical conductivity

Help and Feedback Game Design Support
#1

Hoping for a nudge in the right direction on ways I might accomplish this. I’m using the electrical conductivity as an example, but need to determine connection of smaller parts to the ‘source’ part through adjacent smaller parts.

The small parts are not technically touching, and they are in fixed positions that can either be occupied, or unoccupied. In this example all parts in blue are connected to the yellow source part at the top. The part in red is no longer connected because the adjacent parts are no longer occupied.

image
image1280×505 41.2 KB

Virtually any configuration of smaller parts can exist, so what is the best way to continuously check if a part is connected to the source?

So far I’ve created a table of each small part and its corresponding adjacent parts, and have been experimenting with loops checking if the parts are connected to the top source part by checking the ‘occupied’ value of each adjacent part, but I’ve struggled with the number of times you must cycle through all parts, or determining an order of cycling through – like: check top row first, adjust a value for “source connected” then check adjacent parts…etc.
image

Again, hoping there might be a method I’ve not thought of. Appreciate any suggestions.

#2

You can use a while loop where you get the neighbors of neighbors and at the end of each iteration update the neighbors variable to contain the new neighbors (neighbors of neighbors). The loop should end when there are no new neighbors that haven’t been checked.

Here's a function that I wrote for that. 
function OccupiedGraph:isOccupiedCellConnectedToRoot(cell)
	if not cell.occupied then
		error("not defined for non-occupied cells")
	end
	
	if cell.i1 == 1 then
		return true
	end
	
	local neighbors = {}
	local alreadyChecked = {[cell] = true}

	for _, neighbor in ipairs(self:getNeighbors(cell)) do
		if not neighbor.occupied then
			continue
		end
		if neighbor.i1 == 1 then
			return true
		end
		table.insert(neighbors, neighbor)
		alreadyChecked[neighbor] = true
	end

	while #neighbors > 0 do
		local newNeighbors = {}
		for _, neighbor in ipairs(neighbors) do
			for _, newNeighbor in ipairs(self:getNeighbors(neighbor)) do
				if not newNeighbor.occupied or alreadyChecked[newNeighbor] then
					continue
				end
				if newNeighbor.i1 == 1 then
					return true
				end
				table.insert(newNeighbors, newNeighbor)
				alreadyChecked[newNeighbor] = true
			end
		end
		neighbors = newNeighbors
	end
	return false
end

And below is the whole system I made. It creates the parts and the data structures. Because the possible part locations have a regular pattern, you don’t need to pre-create a table that contains the neighbors of each part. In this system I made a function that will get the neighbors of a given cell. ReplicatedStorage.Modules.OccupiedGraph is a folder.

I made the createBottomPart function just for debugging part placement problems. The placement should work now. You can remove the line createBottomPart(self) from the initialize function if you don’t want the “bottom” part, which actually isn’t even a bottom because it’s at the same height as the other parts.

Modulescript: ReplicatedStorage.Modules.OccupiedGraph.OccupiedGraph 
local OccupiedGraphCell = require(script.Parent.OccupiedGraphCell)

local DEFAULT_OCCUPIED = true

local OccupiedGraph = {}
OccupiedGraph.__index = OccupiedGraph

local function createBottomPart(self)
	local part = Instance.new("Part")
	part.Name = "Bottom"
	part.Color = Color3.new(1, 0, 0)
	part.Anchored = true
	part.Size = Vector3.new(self.studWidth, .5, self.studLength)
	part.CFrame = self.cf
	part.Parent = self.parentFolder
end

local function createRootPart(self)
	local part = Instance.new("Part")
	part.Color = self.rootPartColor
	part.Size = Vector3.new(self.studWidth, self.studHeight, self.rootPartStudLength)
	--print(self.cf.LookVector ~= nil, self.rootPartStudLength)
	part.CFrame = self.cf + self.cf.LookVector * ((-self.studLength + self.rootPartStudLength) * .5)
	part.Parent = self.parentFolder
	return part
end

local function createCellPartFolder(self)
	local folder = Instance.new("Folder")
	folder.Name = "CellParts"
	folder.Parent = self.parentFolder
	return folder
end

local function createArrayOfCellArraysAndPartCellDictionary(self)
	--[[
	for k, v in pairs(self) do
		print(k, v)
	end
	--]]
	local numOfRows, smallerRowNumOfCells = self.numOfRows, self.smallerRowNumOfCells
	local arrayOfCellArrays = table.create(numOfRows)
	local partCellDictionary = {}
	for i1 = 1, numOfRows do
		local rowLength = smallerRowNumOfCells + i1 % 2
		local array = table.create(rowLength)
		for i2 = 1, rowLength do
			local cell = OccupiedGraphCell.new(self, i1, i2, DEFAULT_OCCUPIED) 
			array[i2] = cell
			partCellDictionary[cell.part] = cell
		end
		arrayOfCellArrays[i1] = array
	end
	return arrayOfCellArrays, partCellDictionary
end

local function initialize(self)
	self.rootPart = createRootPart(self)
	self.cellPartFolder = createCellPartFolder(self)
	self.arrayOfCellArrays, self.partCellDictionary = createArrayOfCellArraysAndPartCellDictionary(self)
	createBottomPart(self)
end

local function getNeighborIndicesValidAndInvalid(cell)
	local i1, i2 = cell.i1, cell.i2
	local adjacentRowFirstNeighborInd = i2 - i1 % 2
	return {
		{i1 - 1, adjacentRowFirstNeighborInd},
		{i1 - 1, adjacentRowFirstNeighborInd + 1},
		{i1, i2 - 1},
		{i1, i2 + 1},
		{i1 + 1, adjacentRowFirstNeighborInd},
		{i1 + 1, adjacentRowFirstNeighborInd + 1}
	}
end

local function resetCellColor(cell)
	cell:resetColor()
end

function OccupiedGraph.new(parentFolder, cf, sizeSettings, visualSettings)
	local studLength, studWidth, studHeight, rootPartStudLength, padding, shortRowNormalizedOffset, numOfRows, biggerRowNumOfCells = sizeSettings.studLength, sizeSettings.studWidth, sizeSettings.studHeight, sizeSettings.rootPartStudLength, sizeSettings.padding, sizeSettings.shortRowNormalizedOffset, sizeSettings.numOfRows, sizeSettings.biggerRowNumOfCells
	--[[
	for k, v in pairs(sizeSettings) do
		print(k, v)
	end
	print(padding, numOfRows, biggerRowNumOfCells)
	--]]
	if padding * numOfRows >= studLength or padding * biggerRowNumOfCells >= studWidth then
		error("too big padding")
	end
	if rootPartStudLength >= studLength then
		error("too big rootpart stud length")
	end
	
	local self = {}
	
	self.cf = cf
	
	-- size
	self.studLength = studLength
	self.studWidth = studWidth
	self.studHeight = studHeight
	self.padding = padding
	self.shortRowNormalizedOffset = shortRowNormalizedOffset
	self.rootPartStudLength = rootPartStudLength
	self.cellAreaStudLength = studLength - rootPartStudLength
	self.cellStudLength = self.cellAreaStudLength / numOfRows
	self.cellStudWidth = studWidth / biggerRowNumOfCells
	
	self.numOfRows = numOfRows
	self.biggerRowNumOfCells = biggerRowNumOfCells
	self.smallerRowNumOfCells = biggerRowNumOfCells - 1
	
	self.arrayOfCellArrays = nil
	self.partCellDictionary = nil
	
	--visual
	self.occupiedTransparency = visualSettings.occupiedTransparency
	self.unOccupiedTransparency = visualSettings.unOccupiedTransparency
	self.rootPartColor = visualSettings.rootPartColor
	self.defaultOccupiedColor = visualSettings.defaultOccupiedColor
	self.defaultUnOccupiedColor = visualSettings.defaultUnOccupiedColor
	
	self.parentFolder = parentFolder
	self.rootPart = nil
	self.cellPartFolder = nil
	
	initialize(self)
	return setmetatable(self, OccupiedGraph)
end

function OccupiedGraph:areIndicesValid(i1, i2)
	return i1 > 0 and i1 <= self.numOfRows and i2 > 0 and i2 <= self.smallerRowNumOfCells + i1 % 2
end

function OccupiedGraph:getCell(i1, i2)
	if not self:areIndicesValid(i1, i2) then
		error("invalid indices")
	end
	return self.arrayOfCellArrays[i1][i2]
end

function OccupiedGraph:getCellFromPart(part)
	return self.partCellDictionary[part]
end

function OccupiedGraph:forEachCell(funct)
	for i1 = 1, self.numOfRows do
		for i2, cell in ipairs(self.arrayOfCellArrays[i1]) do
			funct(cell)
		end
	end
end

function OccupiedGraph:getNeighborIndices(cell)
	local neighborIndices = {}
	for _, indices in ipairs(getNeighborIndicesValidAndInvalid(cell)) do
		if self:areIndicesValid(indices[1], indices[2]) then
			table.insert(neighborIndices, indices)
		end
	end
	return neighborIndices
end

function OccupiedGraph:getNeighbors(cell)
	local neighborIndices = self:getNeighborIndices(cell)
	local neighbors = table.create(#neighborIndices)
	for i, indices in ipairs(neighborIndices) do
		neighbors[i] = self:getCell(indices[1], indices[2])
	end
	return neighbors
end

function OccupiedGraph:isOccupiedCellConnectedToRoot(cell)
	if not cell.occupied then
		error("not defined for non-occupied cells")
	end
	
	if cell.i1 == 1 then
		return true
	end
	
	local neighbors = {}
	local alreadyChecked = {[cell] = true}

	for _, neighbor in ipairs(self:getNeighbors(cell)) do
		if not neighbor.occupied then
			continue
		end
		if neighbor.i1 == 1 then
			return true
		end
		table.insert(neighbors, neighbor)
		alreadyChecked[neighbor] = true
	end

	while #neighbors > 0 do
		local newNeighbors = {}
		for _, neighbor in ipairs(neighbors) do
			for _, newNeighbor in ipairs(self:getNeighbors(neighbor)) do
				if not newNeighbor.occupied or alreadyChecked[newNeighbor] then
					continue
				end
				if newNeighbor.i1 == 1 then
					return true
				end
				table.insert(newNeighbors, newNeighbor)
				alreadyChecked[newNeighbor] = true
			end
		end
		neighbors = newNeighbors
	end
	return false
end

function OccupiedGraph:resetAllCellColors()
	self:forEachCell(resetCellColor)
end

return OccupiedGraph
Modulescript: ReplicatedStorage.Modules.OccupiedGraph.OccupiedGraphCell 
local OccupiedGraphCell = {}
OccupiedGraphCell.__index = OccupiedGraphCell

local function occupy(self, part)
	self.occupied = true
	local graph = self.graph
	part.Transparency = graph.occupiedTransparency
	part.Color = graph.defaultOccupiedColor
	part.CanCollide = true
end

local function unOccupy(self, part)
	self.occupied = false
	local graph = self.graph
	part.Transparency = graph.unOccupiedTransparency
	part.Color = graph.defaultUnOccupiedColor
	part.CanCollide = false
end

local function createPart(self, graph, i1, i2, defaultOccupied)
	local part = Instance.new("Part")
	part.Name = "CellPart"
	part.Size = Vector3.new(graph.cellStudWidth - graph.padding, graph.studHeight, graph.cellStudLength - graph.padding)
	part.Anchored = true
	local initial = Vector3.new((-graph.studWidth - graph.cellStudWidth) * .5, 0, (graph.studLength + graph.cellStudLength) * .5 - graph.rootPartStudLength)
	local partPosOffset = Vector3.new((i2 + ((i1 + 1) % 2) * graph.shortRowNormalizedOffset) * graph.cellStudWidth, 0, -i1 * graph.cellStudLength)
	part.CFrame = graph.cf * CFrame.new(initial + partPosOffset)
	if defaultOccupied == true then
		occupy(self, part)
	else
		unOccupy(self, part)
	end
	part.Parent = graph.cellPartFolder
	return part
end

function OccupiedGraphCell.new(graph, i1, i2, defaultOccupied)
	local self = setmetatable({}, OccupiedGraphCell)
	self.graph = graph
	self.i1 = i1
	self.i2 = i2
	self.occupied = defaultOccupied
	self.part = createPart(self, graph, i1, i2, defaultOccupied)
	return self
end

function OccupiedGraphCell:occupy()
	occupy(self, self.part)
end

function OccupiedGraphCell:unOccupy()
	unOccupy(self, self.part)
end

function OccupiedGraphCell:setColor(color)
	self.part.Color = color
end

function OccupiedGraphCell:resetColor()
	self.part.Color = self.occupied and self.graph.defaultOccupiedColor or self.graph.defaultUnOccupiedColor
end

return OccupiedGraphCell
Modulescript: ReplicatedStorage.Modules.OccupiedGraph.OccupiedGraphSizeSettings 
local OccupiedGraphSizeSettings = {}
OccupiedGraphSizeSettings.__index = OccupiedGraphSizeSettings

function OccupiedGraphSizeSettings.new(studLength, studWidth, studHeight, rootPartStudLength, padding, shortRowNormalizedOffset, numOfRows, biggerRowNumOfCells)
	if shortRowNormalizedOffset < 0 or shortRowNormalizedOffset > 1 then
		error("Normalized offset must be between 0 and 1.")
	end
	
	local self = {}
	self.studLength = studLength
	self.studWidth = studWidth
	self.studHeight = studHeight
	self.rootPartStudLength = rootPartStudLength
	self.padding = padding
	self.shortRowNormalizedOffset = shortRowNormalizedOffset
	
	self.numOfRows = numOfRows
	self.biggerRowNumOfCells = biggerRowNumOfCells
	return setmetatable(self, OccupiedGraphSizeSettings)
end

return OccupiedGraphSizeSettings
Modulescript: ReplicatedStorage.Modules.OccupiedGraph.OccupiedGraphVisualSettings 
local OccupiedGraphVisualSettings = {}
OccupiedGraphVisualSettings.__index = OccupiedGraphVisualSettings

function OccupiedGraphVisualSettings.new(occupiedTransparency, unOccupiedTransparency, rootPartColor, defaultOccupiedColor, defaultUnOccupiedColor)
	local self = {}
	self.occupiedTransparency = occupiedTransparency
	self.unOccupiedTransparency = unOccupiedTransparency
	self.rootPartColor = rootPartColor
	self.defaultOccupiedColor = defaultOccupiedColor
	self.defaultUnOccupiedColor = defaultUnOccupiedColor
	return setmetatable(self, OccupiedGraphVisualSettings)
end

return OccupiedGraphVisualSettings
Modulescript: ReplicatedStorage.Modules.MouseRaycast 
local UserInputService = game:GetService("UserInputService")

local camera = workspace.CurrentCamera

local MouseRaycast = {}

function MouseRaycast.getRaycastResult(params, distance) -- these are optional, not necessary
	local mousePos = UserInputService:GetMouseLocation()
	local unitRay = camera:ViewportPointToRay(mousePos.X, mousePos.Y)
	return workspace:Raycast(unitRay.Origin, unitRay.Direction*(distance or 5000), params)
end

function MouseRaycast.getMouseTarget(params, distance)
	local result = MouseRaycast.getRaycastResult(params, distance)
	if result then
		return result.Instance
	end
	return nil
end

return MouseRaycast
Localscript: StarterPlayer.StarterPlayersScripts.OccupiedGraphTest 
local ReplicatedStorage = game:GetService("ReplicatedStorage")
local ContextActionService = game:GetService("ContextActionService")

local modules = ReplicatedStorage.Modules
local occupiedGraphModules = modules.OccupiedGraph

local OccupiedGraph = require(occupiedGraphModules.OccupiedGraph)
local OccupiedGraphSizeSettings = require(occupiedGraphModules.OccupiedGraphSizeSettings)
local OccupiedGraphVisualSettings = require(occupiedGraphModules.OccupiedGraphVisualSettings)

local MouseRayCast = require(modules.MouseRaycast)

local OCCUPIED_TRANSPARENCY = 0
local UNOCCUPIED_TRANSPARENCY = .75
local ROOT_PART_COLOR = Color3.new(1, 1, 0)
local DEFAULT_OCCUPIED_COLOR = Color3.new(0, 1, 1)
local DEFAULT_UNOCCUPIED_COLOR = Color3.new(1, 1, 1)

local STUD_LENGTH = 100
local STUD_WIDTH = 100
local STUD_HEIGHT = 2
local ROOT_PART_STUD_LENGTH = 10
local PADDING = 1
local SHORT_ROW_NORMALIZED_OFFSET = .25
local NUM_OF_ROWS = 9
local BIGGER_ROW_NUM_OF_CELLS = 10
local CF = CFrame.new(50, STUD_HEIGHT / 2, 50)

local parentFolder = Instance.new("Folder")
parentFolder.Name = "OccupiedGraph"
parentFolder.Parent = workspace


local sizeSettings = OccupiedGraphSizeSettings.new(STUD_LENGTH, STUD_WIDTH, STUD_HEIGHT, ROOT_PART_STUD_LENGTH, PADDING, SHORT_ROW_NORMALIZED_OFFSET, NUM_OF_ROWS, BIGGER_ROW_NUM_OF_CELLS)
local visualSettings = OccupiedGraphVisualSettings.new(OCCUPIED_TRANSPARENCY, UNOCCUPIED_TRANSPARENCY, ROOT_PART_COLOR, DEFAULT_OCCUPIED_COLOR, DEFAULT_UNOCCUPIED_COLOR)
local graph = OccupiedGraph.new(parentFolder, CF, sizeSettings, visualSettings)

local function colorNeighbors(cell)
	for _, neighbor in ipairs(graph:getNeighbors(cell)) do
		neighbor:setColor(Color3.new(0, 1, 0))
	end
end

local function colorBasedOnWhetherConnectedIfOccupied(cell)
	if not cell.occupied then
		return
	end
	cell:setColor(graph:isOccupiedCellConnectedToRoot(cell) and Color3.new(0, .7, 0) or Color3.new(1, .5, 0))
end

local function colorAllOccupiedBasedOnWhetherConnected()
	graph:forEachCell(colorBasedOnWhetherConnectedIfOccupied)
end

local function handleClick(_, inputState)
	if inputState ~= Enum.UserInputState.End then
		return
	end
	local mouseTarget = MouseRayCast.getMouseTarget()
	if mouseTarget == nil then
		return
	end
	local cell = graph:getCellFromPart(mouseTarget)
	if cell == nil then
		return
	end
	
	--[
	-- toggle occupied
	if cell.occupied then
		cell:unOccupy()
	else
		cell:occupy()
	end
	--]]
	
	-- cell colors
	graph:resetAllCellColors()
	--colorNeighbors(cell)
	colorAllOccupiedBasedOnWhetherConnected()
end

ContextActionService:BindAction("click", handleClick, false, Enum.UserInputType.MouseButton1)

Edit: I said that the while loop should end when there are no new neighbors that haven’t been checked. I forgot to mention that this is the ending condition when there’s no connection to the root, in which case the function returns false after the loop. Of course the while loop will also end if the function returns true which happens when a connection to the root is found. There’s a connection to the root if the cell itself is in the first row or it’s connected to an occupied cell that is in the first row.

1 Like
#3

WOW RoBoPoJu

I can’t thank you enough for the thoughtful reply and the sheer volume of work and expertise you poured into this response. I’m not sure what your hourly programming rate is but I’m guessing the bill is in the mail…

I was beginning to think I hadn’t described my issue well enough, or the problem simply wasn’t solvable, but you’ve solved for the adjacent part evaluation (and written a large portion of the rest of my game; creating all of the parts and property management). Again, thank you so much for all of this.

Full disclosure, I’m one of the few, true boomer aspiring developers here, and probably have no business learning this stuff. I failed out of computer science in the early 90s and have had a long career in finance; now picking this up as a hobby. I’ve been studying your scripts and working to understand the solution, and implement into my game.

Your solution is a much more efficient and elegant solution than mine: As mentioned a mostly hard coded process of cycling through each part (they’ve ended up being balls and not blocks), then first setting the balls in the first row that are connected directly to the source to ‘TopConnected’ then comparing all other balls to their adjacent balls and determining if it is connected to another TopConnected ball.

** I’m aware how off the formatting of this if statement is:

	local B = Set.Balls
	local Table = ""
	local function SetTable(ball)
		if ball == B.P0101 then Table = {B.P0102,B.P0201}
		elseif ball == B.P0102 then Table = {B.P0101,B.P0201,B.P0202,B.P0103}
		elseif ball == B.P0103 then Table = {B.P0102,B.P0202,B.P0203,B.P0104}
		elseif ball == B.P0104 then Table = {B.P0103,B.P0203,B.P0204,B.P0105}
		elseif ball == B.P0105 then Table = {B.P0104,B.P0204,B.P0205,B.P0106}
		elseif ball == B.P0106 then Table = {B.P0105,B.P0205,B.P0206,B.P0107}
		elseif ball == B.P0107 then Table = {B.P0106,B.P0206,B.P0207,B.P0108}
		elseif ball == B.P0108 then Table = {B.P0107,B.P0207}
		elseif ball == B.P0201 then Table = {B.P0101,B.P0102,B.P0202,B.P0301,B.P0302}
		elseif ball == B.P0202 then Table = {B.P0102,B.P0103,B.P0201,B.P0203,B.P0302,B.P0303}
		elseif ball == B.P0203 then Table = {B.P0103,B.P0104,B.P0202,B.P0204,B.P0303,B.P0304}
		elseif ball == B.P0204 then Table = {B.P0104,B.P0105,B.P0203,B.P0205,B.P0304,B.P0305}

…etc through the rest of the parts. Then cycling through each to determine if it is connected:

for i, ball in pairs(Set.Balls:GetChildren()) do -- check every ball, if it is occupied, set row 1 TopConnected values to true and all others to false.
		--if ball.Occupied.Value == true then
		if ball.Name == "P0101" or ball.Name == "P0102" or ball.Name == "P0103" or ball.Name == "P0104" or ball.Name == "P0105" or ball.Name == "P0106" or ball.Name == "P0107" or ball.Name == "P0108" or ball.Name == "P0109" or ball.Name == "P0110" or ball.Name == "P0111" then
			ball.TopConnected.Value = true
		else
			ball.TopConnected.Value = false
		end
	end
	for count = 1, 10, 1 do
		for i, ball in pairs(Set.Balls:GetChildren()) do -- one at a time, for every ball in the Balls folder do the below.
			if ball.Occupied.Value == true then
				SetTable(ball)

				for i, v in pairs (Table) do -- for each ball, after getting its table above, check its adjacents and set their top value to true if the ball was true.
					if v.TopConnected.Value == true and v.Occupied.Value == true then
						ball.TopConnected.Value = true
					end
				end
				for i, v in pairs (Table) do
					if ball.TopConnected.Value == true then
						v.TopConnected.Value = true
					end
				end
			end
		end -- ends the loop through each ball in balls folder

	end -- ends 10 cycle loop that is setting connected values

This has worked well in testing, but would still fail periodically when I had a ball that was connected to the top source through many other single balls. Only by having a larger number of iterations through the loop (currently 10 times) could I seem to catch all situations. Again. I’m sure this solution reeks of inexperience, but it works.

I’m going to continue to work with your scripts and implement – Marking as solution for now and I’m sure I’ll be back with questions. THANK YOU RoboJu.

1 Like