Preventing obstacle traps in Crossy Road type map generation

Help and Feedback Scripting Support
#1

I am working currently on a game similar to crossy road and have the map generation side of it complete. It works fine and I’m wondering how I could add the map elements (trees, bushes, rocks, etc) spawn randomly while also not having RNG trap the player but make sure there is always a space for the player to move foreward.

One idea i had is with each floor piece could have an invisible part in the middle of each grid of the floor that would be able to spawn a random map obstacle depending on the floor type (eg: if ground type is grass then spawn either a tree, bush, or nothing). But the issue would still remain of making sure this doesn’t block the player from moving.

Script in ServerScriptService that generates a random map seed:

local ReplicatedStorage = game:GetService("ReplicatedStorage")
local Players = game:GetService("Players")

local startingRandom = 25267357

ReplicatedStorage.seed.Value = math.random() * startingRandom --numberValue being given a random number

Players.PlayerAdded:Connect(function(player)
	player:WaitForChild("PlayerGui"):WaitForChild("respawn").Frame.TextButton.MouseButton1Click:Connect(function()
		ReplicatedStorage.seed.Value = math.random() * startingRandom
	end)
end)

LocalScript in ReplicatedFirst that generates each floor piece randomly:

local Players = game:GetService("Players")
local Workspace = game:GetService("Workspace")
local ReplicatedStorage = game:GetService("ReplicatedStorage")
local RunService = game:GetService("RunService")

if not game:IsLoaded() then game.Loaded:Wait() end

local player = Players.LocalPlayer
local part = Workspace.startingEnvironment:WaitForChild("start") --the connecting piece from the starting floor that isnt random, where the next generated piece will connect
local random = Random.new(ReplicatedStorage.seed.Value)

local mapReset = part:Clone()
mapReset.Parent = ReplicatedStorage.mapReset

local models = ReplicatedStorage.models:GetChildren()
table.sort(models, function(a, b) return a.Name < b.Name end)

local debounce = true

RunService.Heartbeat:Connect(function(deltaTime)
	for _,v in pairs(workspace:GetDescendants()) do
		if v:IsA("Texture") then
			v:Destroy()
		end
	end

	if not player.Character then return end
	if (part.Position - player.Character:GetPivot().Position).Magnitude > 200 then return end

	local model = models[random:NextInteger(1, #models)]:Clone()
	model:PivotTo(part.CFrame)
	model.start:Destroy()
	model.End.Transparency = 1
	model.Parent = workspace.environment.ground

	part:Destroy()
	part = model.End

	ReplicatedStorage.seed.Changed:Connect(function()
		if debounce then
			debounce = false
			print("respawning")
			task.wait(1.2)

			for _,x in pairs(Workspace.environment.ground:GetChildren())do
				x:Destroy()
			end

			part = ReplicatedStorage.mapReset["start"]:Clone()
			part.Parent = Workspace.startingEnvironment

			local modelReload = models[random:NextInteger(1, #models)]:Clone()
			modelReload:PivotTo(part.CFrame)
			modelReload.start:Destroy()
			modelReload.End.Transparency = 1
			modelReload.Parent = workspace.environment.ground

			part:Destroy()
			part = modelReload.End
			
			debounce = true
		end
	end)
end)
#2

You can use a breadth first search to ensure all empty floor tiles are connected. This’ll mean there are no enclosed areas. Here’s some code for it

-- does a flood fill from a floor tile and collects the whole region
local function bfsRegion(grid, visited, startY, startX)
	local queue = {}
	table.insert(queue, {startY, startX})
	visited[startY][startX] = true
	local region = {{startY, startX}}

	while #queue > 0 do
		local current = table.remove(queue, 1)
		local y, x = current[1], current[2]

		-- check the 4 directions (no diagonals)
		for _, offset in ipairs({{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) do
			local dy, dx = offset[1], offset[2]
			local ny, nx = y + dy, x + dx

			-- inside bounds check
			if ny >= 1 and ny <= #grid and nx >= 1 and nx <= #grid[1] then
				-- unvisited floor tiles only
				if not visited[ny][nx] and grid[ny][nx] == "." then
					visited[ny][nx] = true
					table.insert(queue, {ny, nx})
					table.insert(region, {ny, nx})
				end
			end
		end
	end

	return region
end

-- finds all disconnected floor regions
local function findRegions(grid)
	local visited = {}
	for y = 1, #grid do
		visited[y] = {}
		for x = 1, #grid[1] do
			visited[y][x] = false
		end
	end

	local regions = {}
	for y = 1, #grid do
		for x = 1, #grid[1] do
			if grid[y][x] == "." and not visited[y][x] then
				-- new region found
				table.insert(regions, bfsRegion(grid, visited, y, x))
			end
		end
	end

	return regions
end

-- simple manhattan distance between two points
local function distance(p1:number, p2:number)
	return math.abs(p1[1] - p2[1]) + math.abs(p1[2] - p2[2])
end

-- carves an L-shaped tunnel through walls between two points
local function carvePath(grid, a, b)
	local y1, x1 = a[1], a[2]
	local y2, x2 = b[1], b[2]

	-- go vertically first
	for y = math.min(y1, y2), math.max(y1, y2) do
		if grid[y][x1] == "#" then
			grid[y][x1] = "."
		end
	end

	-- then horizontally
	for x = math.min(x1, x2), math.max(x1, x2) do
		if grid[y2][x] == "#" then
			grid[y2][x] = "."
		end
	end
end

-- repeatedly connects closest regions until only one is left
local function connectAllRegions(grid)
	local regions = findRegions(grid)

	while #regions > 1 do
		local r1 = regions[1]
		local r2 = regions[2]

		-- find nearest pair of tiles between r1 and r2
		local minDist = math.huge
		local bestPair = nil
		for _, p1 in ipairs(r1) do
			for _, p2 in ipairs(r2) do
				local d = distance(p1, p2)
				if d < minDist then
					minDist = d
					bestPair = {p1, p2}
				end
			end
		end

		-- dig a path between them
		carvePath(grid, bestPair[1], bestPair[2])

		-- recalculate all regions after merge
		regions = findRegions(grid)
	end

	return grid
end

-- test grid with multiple disconnected floor regions
local myGrid = {
	{"#", "#", "#", "#", "#", "#", "#", "#", "#"},
	{"#", ".", ".", "#", "#", "#", ".", ".", "#"},
	{"#", ".", "#", "#", "#", "#", "#", ".", "#"},
	{"#", "#", "#", ".", ".", ".", "#", ".", "#"},
	{"#", "#", "#", ".", "#", ".", "#", "#", "#"},
	{"#", "#", "#", ".", ".", ".", "#", "#", "#"},
	{"#", ".", ".", "#", "#", "#", ".", ".", "#"},
	{"#", ".", "#", "#", "#", "#", "#", ".", "#"},
	{"#", "#", "#", "#", "#", "#", "#", "#", "#"},
}

-- print original grid
for _, row in ipairs(myGrid) do
	print(table.concat(row, " "))
end
print()

-- connect all the floor regions into one big one
local result = connectAllRegions(myGrid)

-- print updated grid
for _, row in ipairs(result) do
	print(table.concat(row, " "))
end

--[[
  19:20:16.413  # # # # # # # # #  -  Edit
  19:20:16.413  # . . # # # . . #  -  Edit
  19:20:16.413  # . # # # # # . #  -  Edit
  19:20:16.413  # # # . . . # . #  -  Edit
  19:20:16.413  # # # . # . # # #  -  Edit
  19:20:16.413  # # # . . . # # #  -  Edit
  19:20:16.413  # . . # # # . . #  -  Edit
  19:20:16.413  # . # # # # # . #  -  Edit
  19:20:16.413  # # # # # # # # #  -  Edit
  19:20:16.414    -  Edit
  19:20:16.414  # # # # # # # # #  -  Edit
  19:20:16.414  # . . . . . . . #  -  Edit
  19:20:16.414  # . # . # # # . #  -  Edit
  19:20:16.414  # # # . . . # . #  -  Edit
  19:20:16.414  # # # . # . # # #  -  Edit
  19:20:16.414  # # # . . . # # #  -  Edit
  19:20:16.414  # . . . # . . . #  -  Edit
  19:20:16.414  # . # # # # # . #  -  Edit
  19:20:16.414  # # # # # # # # #  -  Edit
]]

It ensures there are no isolated islands by connecting them together