Thought this problem looked like a lot of fun, so I wanted to come up with a solution. Originally I was thinking the same thing as @azqjanna
However, the graph is actually not entirely necessary, it’s more of an optimization to the problem. A simpler brute force method exists where you can simply check the distance from each border cell on an island to all other border cells on all other islands to find the nearest island and the shortest bridge simultaneously.
This method would be slow on a large map, but for a map of the size you’ve provided the problem should be pretty trivial. However, this is where the graph could come in. Say you had 100 islands with 5,000 border tiles, with the brute force method that would be 5,000 ^ 2 (25,000,000) tests to find all of the closest islands and their bridges. That’s likely going to be problematic depending on your use-case.
For a graph solution you could start by defining each island as a vertex on the graph, and for each vertex connect all other vertices to it via edges. Once you’ve done that you could find the minimum spanning tree of the graph via Prim’s, Kruskal’s, or Tarjan’s algorithm. Once you’ve found your minimum spanning tree you can do the same distance test as before on each of the border cells, but this time only to the islands connected to each other. This should vastly simplify the problem.
I went ahead and wrote out the brute force method and created a way to visualize it. On my PC it takes about 0.5ms to find all of the islands, water bodies, and find the nearest connection points between the islands. That said, unless your use-case is significantly more complex I really don’t think this needs further optimization.
local map_array = {
{0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1},
{0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1},
{0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0},
{0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0},
{1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0},
{1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1},
}
local height = #map_array;
local width = #map_array[1];
local body_types = {
[0] = 'Water',
[1] = 'Land',
};
local land_bodies = {};
local water_bodies = {};
local _considered_cells = {};
local function get_cell(x: number, y: number)
return map_array[y] and map_array[y][x];
end
local function get_body(x: number, y: number, body)
local center_cell = get_cell(x, y);
local body_type = body_types[center_cell];
local body = body or {
Type = body_type,
Cells = {},
BorderCells = {},
TotalPosition = Vector2.zero,
};
_considered_cells[x.. ',' ..y] = true;
local value = Vector2.new(x, y);
table.insert(body.Cells, value);
body.TotalPosition += value;
local function check_adjacent(x2, y2)
if (x2 <= 0 or x2 > width or y2 <= 0 or y2 > height) then
return; -- Out of map bounds.
end
local adjacent_cell = get_cell(x2, y2);
local adjacent_type = body_types[adjacent_cell];
if (adjacent_type ~= body_type) then
body.BorderCells[x.. ',' ..y] = value;
end
if (_considered_cells[x2.. ',' ..y2]) then
return;
end
if (adjacent_type == body_type) then
get_body(x2, y2, body);
end
end
check_adjacent(x - 1, y);
check_adjacent(x, y - 1);
check_adjacent(x + 1, y);
check_adjacent(x, y + 1);
return body;
end
local function get_bodies()
local bodies = {};
water_bodies = {};
land_bodies = {};
for x = 1, width do
for y = 1, height do
if (not _considered_cells[x.. ',' ..y]) then
local body = get_body(x, y);
body.Position = body.TotalPosition / #body.Cells;
table.insert(bodies, body);
if (body.Type == 'Water') then
table.insert(water_bodies, body);
else
table.insert(land_bodies, body);
end
end
end
end
return bodies;
end
local start_clock = os.clock();
local bodies = get_bodies();
local island_linkages = {};
local function get_closest_island_cell(island)
local closest_p1 = nil;
local closest_p2 = nil;
local nearest_island = nil;
local shortest_distance = 0;
for _, other_island in land_bodies do
if (other_island == island) then
continue;
end
if (island_linkages[other_island] and island_linkages[other_island].NearestIsland == island) then
continue;
end
for _, p1 in island.BorderCells do
for _, p2 in other_island.BorderCells do
local dist = (p1 - p2).Magnitude;
if (dist < shortest_distance or not closest_p1) then
closest_p1 = p1;
closest_p2 = p2;
shortest_distance = dist;
nearest_island = other_island;
end
end
end
end
island_linkages[island] = { From = closest_p1, To = closest_p2, NearestIsland = nearest_island };
return closest_p1, closest_p2, nearest_island;
end
for _, island in land_bodies do
get_closest_island_cell(island);
end
local finish_clock = os.clock() - start_clock;
print('Finished island generation. Took ' ..(finish_clock * 1000).. ' milliseconds. Got ' ..#land_bodies.. ' islands and ' ..#water_bodies.. ' oceans.');
-- Visualization stuff below.
local land_part = workspace.Land;
local water_part = workspace.Water;
local marker_part = workspace.Marker;
local edge_indicator = workspace.EdgeIndicator;
land_part.Parent = nil;
water_part.Parent = nil;
marker_part.Parent = nil;
edge_indicator.Parent = nil;
local visual_cells = {};
for _, body in pairs(bodies) do
for _, position in body.Cells do
local p = land_part;
if (body.Type == 'Water') then
p = water_part;
end
local border_cell = body.BorderCells[position.X.. ',' ..position.Y];
p = p:Clone();
p.Position = Vector3.new(position.X * 2, 0, position.Y * 2);
if (border_cell) then
print('is border cell')
p.Color = Color3.new(p.Color.R + 0.1, p.Color.G + 0.1, p.Color.B + 0.1);
end
p.Parent = workspace;
visual_cells[position.X.. ',' ..position.Y] = p;
end
local m = marker_part:Clone();
m.Position = Vector3.new(body.Position.X * 2, 1, body.Position.Y * 2);
m.Parent = workspace;
end
for island, linkage in island_linkages do
if (not linkage.NearestIsland) then
continue;
end
local ind = edge_indicator:Clone();
local a1 = Instance.new('Attachment');
a1.Parent = workspace.Terrain;
a1.WorldCFrame = CFrame.new(linkage.From.X * 2, 1, linkage.From.Y * 2);
local a2 = Instance.new('Attachment');
a2.Parent = workspace.Terrain;
a2.WorldCFrame = CFrame.new(linkage.To.X * 2, 1, linkage.To.Y * 2);
ind.Attachment0 = a1;
ind.Attachment1 = a2;
ind.Parent = workspace;
local c1 = visual_cells[linkage.From.X.. ',' ..linkage.From.Y];
local c2 = visual_cells[linkage.To.X.. ',' ..linkage.To.Y];
if (c1 and c2) then
c1.Color = Color3.new(0, 1, 0);
c2.Color = Color3.new(1, 0, 0);
end
end
Should you want only straight bridges you can add a test to get_closest_island_cell to ignore any cells that don’t fit p1.X == p2.X or p1.Y == p2.Y and it should provide only straight line bridges.
