Support on Optimizing Voxel-Based Flood Fill Algorithm

Help and Feedback Scripting Support
, ,
1

Hello! I’m currently working on a simple mining game, and am currently trying to generate caves. The functions below handle all the logic that goes into it, mainly the caveGen() function, which uses a flood fill algorithm. Unfortunately it’s pretty unoptimized and I have absolutely no clue how to improve it, I’m fairly new to this kind of algorithm. It takes a while for the server to process, way too long compared to what I’ve seen other games pull off.

Let me know if I need to supply any more information. The isCave() function just returns a set math.noise() function. I’m looking to optimize how it loops through all the positions.

local generatingCave = false
local function caveGen(Pos)
	generatingCave = true
	
	local queue = {}
	local isChecked = {}
	local lastLen = 0
	
	table.insert(queue, Pos)
	
	while #queue ~= 0 do
		local Point = queue[1]
		table.remove(queue, 1)
		if table.find(isChecked, Point) == nil then
			table.insert(isChecked, Point)
			if isCave(Point) then
				for _,v in Helper.adjacent(Point) do
					if not table.find(isChecked, v) then
						table.insert(queue, v)
					end
				end
			end
		end
		task.wait()
	end

	generatingCave = false
	return isChecked
end

local function fabricateOre(Ore, Pos : Vector3)
	if isCave(Pos) then
		print("Is a cave!")
		local CaveArray = caveGen(Pos)
		for _,v in CaveArray do
			if isCave(v) then
				table.insert(PositionArray, v)
				for _,w in Helper.adjacent(v) do
					if not table.find(PositionArray, w) and w.Y <= 0 and not isCave(w) then
						fabricateOre(randomPick(w.Y), w)
					end
				end
			else
				print("What are you doing here.")
			end
		end
		for _,w in Helper.adjacent(Pos) do
			if not table.find(PositionArray, w) and w.Y <= 0 and not isCave(w) then
				fabricateOre(randomPick(w.Y), w)
			end
		end
		print("FINSIHED!")
	end
	local ActualOre = OreStorage:FindFirstChild(Ore)
	table.insert(PositionArray, Pos)
	local NewOre = ActualOre:Clone()
	NewOre.Position = Helper.convertFrom(Pos)
	NewOre.Parent = Ores
end

Edit: I’d like to append some more information. It seems after testing it can actually be really quick, or at least as quick as realistic. But I still think it’s likely tanking server performance every time one generates. Here’s an example of what the caves look like when finished.

image
image1536×969 127 KB

3 Likes
2

You might use Ore: string

I think function fabricateOre is being overused alot

I see like code if it is not right then repeat until it is right

3

I’m not sure what you mean here. Ore is a string. FabricateOre is supposed to be used a lot, as that is how the game works. I don’t know what you mean by the last part.

4 
		for _,v in CaveArray do
			if isCave(v) then
				table.insert(PositionArray, v)
				for _,w in Helper.adjacent(v) do
					if not table.find(PositionArray, w) and w.Y <= 0 and not isCave(w) then
						fabricateOre(randomPick(w.Y), w) -- over use
					end
				end
			else
				print("What are you doing here.")
			end
		end
		for _,w in Helper.adjacent(Pos) do
			if not table.find(PositionArray, w) and w.Y <= 0 and not isCave(w) then
				fabricateOre(randomPick(w.Y), w) -- over use
			end
		end
		print("FINSIHED!")
	end
5

This is intentional behavior. It generates ores around the perimeter of the cave.

6

this could be probably (the issue) ? (since being overused, it is also overusing Clone() and table.insert, i think)

	local ActualOre = OreStorage:FindFirstChild(Ore)
	table.insert(PositionArray, Pos)
	local NewOre = ActualOre:Clone()
	NewOre.Position = Helper.convertFrom(Pos)
	NewOre.Parent = Ore
end
7

Placing the ores is not the optimization concern. I want support with how to optimize and improve the flood fill algorithm. Not this.

1 Like
8

table.find searches up to the entire table every time it runs which can be terribly inefficient, you can use dictionaries instead.

Roblox supports vector3 as the dictionary key, so you can do isChecked[point] = true and to check it just do if not isChecked[point] then

1 Like
10

Scratch that, was my fault. I’ll try and implement this for the used positions system too. Have you got any more feedback for how I could further optimize this?

11

you should also have a total blocks checked integer variable and do task.wait() every time it exceeds a set value and then set it to zero when it does or use modulus operator instead, this will evenly distribute processing power over time which will maximize generation speed. if you can post generation times and total blocks in the cave then that would be nice.

1 Like
12

I’ve changed the code significantly since last post, but it’s still about the same thing. I think I’ve done what you mean by the modulus idea? It just does a task.wait() every 1,000 iterations. You can find out the generation times yourself by entering the test game I made just now, link below.

Currently the game does lock-up when a cave is being generated, for safety. I tried to make it so that you could mine while a cave is being generated, but it causes way too much inconsistency and is probably a realm of complexity I don’t understand yet. As a result, nobody in the server can mine while a cave is being generated. It doesn’t bother me personally too much though, and it’s better than the game just breaking, or not having caves at all.

Edit: Did some more testing and uhh, sometimes it does like to timeout if it’s a really big cave. Might just have to make the modulo smaller. Or reduce the threshold for cave size.

image
image830×144 69.8 KB

local generatingCave = false
local function caveGen(Pos)
	local queue = {}
	local isChecked = {}
	local isCaveSpot = {}
	local lastLen = 0
	local i = 0

	table.insert(queue, Pos)

	while #queue ~= 0 do
		local Point = queue[1]
		table.remove(queue, 1)
		if not isChecked[Point] then
			isChecked[Point] = true
			if isCave(Point) then
				table.insert(isCaveSpot, Point)
				for _,v in Helper.adjacent(Point) do
					if not isChecked[v] then
						table.insert(queue, v)
					end
				end
			end
		end
		i += 1
		if i % 1000 == 1 or IsStudio then
			task.wait()
		end
	end

	return isCaveSpot
end

local function fabricateOre(Ore, Pos : Vector3)
	local ActualOre = OreStorage:FindFirstChild(Ore)
	table.insert(PositionArray, Pos)
	local NewOre = ActualOre:Clone()
	NewOre.Position = Helper.convertFrom(Pos)
	NewOre.Parent = Ores
end

local function caveHandle(pos)
	if generatingCave then return end
	generatingCave = true
	print("generating")
	local CaveArray = caveGen(pos)
	for _,v in CaveArray do
		if isCave(v) then
			table.insert(PositionArray, v)
			for _,w in Helper.adjacent(v) do
				if not table.find(PositionArray, w) and w.Y <= 0 and not isCave(w) then
					fabricateOre(randomPick(w.Y), w)
				end
			end
		end
	end
	for _,w in Helper.adjacent(pos) do
		if not table.find(PositionArray, w) and w.Y <= 0 and not isCave(w) then
			fabricateOre(randomPick(w.Y), w)
		end
	end
	print("FINSIHED!")
	generatingCave = false
end

local function generateMine()
	Seed = math.random(-10000,10000)
	for _,v in Ores:GetChildren() do
		v:Destroy()
	end
	for i=(Origin.X)-10,(Origin.X)+10,1 do
		for j=(Origin.Z)-10,(Origin.Z)+10,1 do
			fabricateOre(randomPick(0, true), Vector3.new(i,0,j))
		end
	end
end

local counter = 0
local function destroyOre(P : Player, Target : BasePart)
	if generatingCave then return end
	if Target ~= nil then
		for _,pos in Helper.adjacent(Helper.convertTo(Target.Position)) do
			if not table.find(PositionArray, pos) and pos.Y <= 0 then
				if isCave(pos) then
					caveHandle(pos)
				end
				fabricateOre(randomPick(pos.Y), pos)
			end
		end
		Target.Parent = TempMined
		task.delay(.5, function()
			Target:Destroy()
		end)
		Data.awardOre(P, Target.Name, 1)
	end
end
13

this isn’t really opmitzening it at all but you can put

while #queue ~= 0 do
		local Point = queue[1]
		table.remove(queue, 1)
		if table.find(isChecked, Point) == nil then
			table.insert(isChecked, Point)
			if isCave(Point) then
				for _,v in Helper.adjacent(Point) do
					if not table.find(isChecked, v) then
						table.insert(queue, v)
					end
				end
			end
		end
		task.wait()
	end

into a task.spawn to make it run without waiting for the other stuff in the while do loop to finish

so…

while #queue ~= 0 do
task.spawn(function()
		local Point = queue[1]
		table.remove(queue, 1)
		if table.find(isChecked, Point) == nil then
			table.insert(isChecked, Point)
			if isCave(Point) then
				for _,v in Helper.adjacent(Point) do
					if not table.find(isChecked, v) then
						table.insert(queue, v)
					end
				end
			end
		end
       end)
		task.wait()
	end

sorry the code isn’t formatted this won’t help performance in fact it might even use more data for the new scope (I hope scope is the right word).

14

it should be i % 1000 == 0, not i % 1000 == 1
you should be fine with much much larger intervals, 5000-10000+

the biggest source of lag is going to be placing the actual block parts, many mining games have part caching, greedy meshing systems, chunk systems and interval loading blocks in a chunk to keep the experience smooth and fast.

you should benchmark sections of your script by comparing the difference in time from os.clock()

1 Like
15

It shouldn’t necessarily matter whether it’s 1 or 0 though, I’ll change it anyways but modulo just returns the remainder.

I might benchmark it at some point, I still got a lot of other things I need to make. I ended up adding the modulo system to the block placing as well. I noticed the timeout issue only happened when it had already placed a ton of blocks.

16

Making it a task spawn would be unideal. If I want the caves to happen but still let people mine, I would need to also add measures and checks to make sure people don’t mine into a cave that’s already being generated, and that’s a lot of logic I can’t say I’m bothered enough to figure out..

1 Like