Looping through a 2D array to check grid connections

Help and Feedback Scripting Support
1

I have a game where players can place buildings on a grid and then their building placements are saved in a 2D array.

An example of a two by two grid would look like 
Grid = {
	{{visual = script.Parent["1,1"], buildingId = "Road"}, {visual = script.Parent["1,2"], buildingId = "Road"}},
	{{visual = script.Parent["2,1"], buildingId = "Road"}, {visual = script.Parent["2,2"], buildingId = "House"}
}

This all works well but I need a way to go through one of these 2D arrays and check that all of the roads are connected to each other. I’ve tried checking that there are only two endpoints but that makes it so that players can only have one straight road which isn’t ideal.

1 Like
2
  1. Start at any road.
  2. Add this road to a set of “visited” roads.
  3. For each unvisted neighbor of this road, repeat steps 2 and 3

When you’re done (i.e. you have no more neighbors to check), check whether you’ve visited all the roads.

2 Likes
3

You can use Depth-first search algorithm here.

STEPS:
1: Start
2: Pick the first road in the 2D array
3: If i and j are valid and the element passed is a road, and its not visited, add it to visited
4. Repeat step 3 with the element’s 4 neighbors
5. Stop

Example:

local roads = {
	{ 0, 1, 0, 0, 1 }, -- =|--=
	{ 0, 1, 0, 0, 0 }, -- -|---
	{ 1, 1, 1, 1, 1 }, -- ====-
	{ 0, 0, 0, 0, 1 }, -- ----|
	{ 1, 0, 1, 1, 1 }, -- =-==|
} -- Connected: (1, 2), (2, 2), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 5), (5, 3), (5, 4), (5, 5)

local function getStr(i, j)
	return ("%i_%i"):format(i, j);
end

local function getFirstRoad()
	for i,row in ipairs(roads) do
		for j,col in ipairs(row) do
			if col == 1 then
				return i, j;
			end
		end
	end
end

local function checkConnected()
	
	local visited = {};
	
	local function dfs(i, j)
		if i < 1 or j < 1 or i > #roads or j > #roads[1] then return; end
		if table.find(visited, getStr(i, j)) then return; end
		if roads[i][j] ~= 1 then return; end
		
		table.insert(visited, getStr(i, j));

		dfs(i - 1, j);
		dfs(i + 1, j);
		dfs(i, j - 1);
		dfs(i, j + 1);
	end
	
	
	dfs(getFirstRoad());
	
	for i = 1, #roads, 1 do
		local row = roads[i];
		for j = 1, #row, 1 do
			if table.find(visited, getStr(i, j)) then
				print(("(%i, %i) is connected"):format(i, j));
			end
		end
	end
end

checkConnected();

image

1 Like