# Recursing Too Deep

I’ve been working on a somewhat primitive infinite mining game project with a friend, and I recently implemented a basic form of cave generation.

It, for the most part, works just fine except with extremely large caves hitting the recursion limit, that and some… ‘minor’ performance issues on bigger caves.

Anyway, ideally I would be able to generate the whole cave to completion for any size, but I’m not exactly sure how i’d complete that, any thoughts?

Related Generation Code:

``````--[[
some reference
self.MinedVectors = {}:: {[Vector3]: boolean}
self.GeneratedVectors = {}:: {[Vector3]: BasePart}
Blockspace is defined as (Rounded to floor):
((Position - self.OreParams.GenerationCenter)/OreSize) * Vector3.new(1, -1, 1)
]]

function OreHandler:GetGenerationTable(BlockspaceVector: Vector3)
return {
BlockspaceVector + Vector3.new(1,0,0);
BlockspaceVector + Vector3.new(-1,0,0);

BlockspaceVector + Vector3.new(0,1,0);
BlockspaceVector + Vector3.new(0,-1,0);

BlockspaceVector + Vector3.new(0,0,1);
BlockspaceVector + Vector3.new(0,0,-1);
}
end

function OreHandler:IsCaveBlock(BlockspaceVector: Vector3)
local CaveRandom = math.noise((BlockspaceVector.X + math.random())/GameSettings.CAVE_RESOLUTION, BlockspaceVector.Y/GameSettings.CAVE_RESOLUTION, BlockspaceVector.Z/GameSettings.CAVE_RESOLUTION)
return CaveRandom > GameSettings.CAVE_THRASH and BlockspaceVector.Y > GameSettings.CAVE_MINHEIGHT
end

function OreHandler:Break(Player: Player, BlockspaceVector: Vector3, CaveBreak: boolean)
local TryGeneration = self:GetGenerationTable(BlockspaceVector)

local MinedVectors = self.MinedVectors
local GeneratedVectors = self.GeneratedVectors
local ActiveOre = self.GeneratedVectors[BlockspaceVector] :: ActiveOre

MinedVectors[BlockspaceVector] = true

for _, NewVector in TryGeneration do
if MinedVectors[NewVector] then
continue
end

if GeneratedVectors[NewVector] then
continue
end

if NewVector.Y <= 0 then
continue
end

self:GenerateAt(NewVector, Player)
end
... -- unrelated code
end

function OreHandler:GenerateAt(BlockspaceVector: Vector3, PlayerBroke: boolean): BasePart
return
end

local OreTable = self:GetRandomOre(BlockspaceVector.Y):: OreDictionary.Ore
if not OreTable then
return false
end

local NewOre = {
DictionaryReference = OreTable.Name;
}:: ActiveOre

self.GeneratedVectors[BlockspaceVector] = NewOre
local IsCaveBlock = self:IsCaveBlock(BlockspaceVector)

if IsCaveBlock then
local TempStopPart
if PlayerBroke then
TempStopPart = Instance.new("Part")
InstanceFuncs:Populate(TempStopPart, {
Position = self:ToWorldSpace(BlockspaceVector);
Anchored = true;
Size = GameSettings.ORE_SIZE;
Parent = GameSettings.ORE_CONTAINER
})
end

local CaveGenStart = os.clock()

self:Break(nil, BlockspaceVector, true)

local CaveGenEnd = os.clock() - CaveGenStart

if TempStopPart then
TempStopPart:Destroy()
print(`Cavegen Time: {CaveGenEnd*1000}ms`)
end

end

... --unrelated code
end``````

Right now you’re calling GenerateAt() which in turn calls Break() again, which can go back and forth hitting the recursion limit. I don’t know how your code works exactly so I can’t go into more detail, but you need to replace calling self:Break(nil, BlockspaceVector, true) in GenerateAt() with some other code to avoid calling Break() back and forth.

That’s… how the caves are generated.
It calls `IsCaveBlock()` on itself to figure out if its supposed to be air, and then breaks itself to create the blocks around it which do the same.

Maybe breaking this recursion temporarily after a certain amount of calls by incrementing a variable on every call will help? By adding an extra if-condition in Break() which checks and returns if the call limit is exceeded. You do this while keeping track of where you left off, and then you continue with the recursion again by calling a new Break()

I also wanted to ask, how many blocks are there? The recursion limit is 20k when I looked it up. Maybe the problem is because of an infinite loop somewhere which can happen if none of the if-conditions in Break() applies.

As already stated, the recursion limit is pretty deep so unless your map is massive, you probably shouldn’t be hitting it.

But eventually it might be a problem. As such I don’t recommend recursion for this type of problem. I think I have kind of an idea of how your system works, but it’s not super solid. It seems that break is basically finding all of it’s neighbors and calling generate for them. Then generate is calling break which causes a very large recursive chain. Two things. First is that each block has it’s neighbors neighbor unless you are specifically filtering that out which means that unless you are careful, you’ve created an infinite loop.

Secondly, you shouldn’t be making this recursive if there are no hard limits on how much this can be called. To get around doing this recursively take this example

``````local function GenerateAt(original, ...)
local unprocessedBlocks = {original}
local processedBlocks = {} --keep track of every block you've already visited so you don't accidentally visit them multiple times
while #unprocessedBlocks > 0 do
local currentBlock = table.remove(unprocessedBlocks)
processedBlocks[currentBlock] = true --Mark that this one has been seen

--This part is basically equivalent to your break function and can be split out so long as it retains access to the data it needs
for _, neighbor in ipairs(getBlocksNeighbors(currentBlock) do
if processedBlocks[neighbor] then continue end --We've already processed this block, so skip it
table.insert(unprocessedBlocks, neighbor) --Make the loop longer because we have new blocks to calculate
end
end
end
``````
1 Like

Thanks for your advice! This is exactly what I was looking for. I also ended up making a simple chunkloading bit to make absolutely sure that no crashes happen.

``````function OreHandler:GenerateCave(SeedBlockspaceVector: Vector3)
local Queue = {SeedBlockspaceVector}
local Visited = {}
local Boundary = {}

local MinedVectors = self.MinedVectors

local DirtyYieldCount = 1
local DirtyYieldThreshold = 1000 --Stops particularly massive caves from causing a script exhaustion

self.CurrentlyProcessingCave = true

print(`Filling neighbors queue...`)
while #Queue > 0 do
local ProccessingVector = Queue[#Queue]
table.remove(Queue, #Queue)

Visited[ProccessingVector] = true

for _, Neighbor in self:GetGenerationTable(ProccessingVector) do
if Visited[Neighbor] then
continue
end

if self:IsCaveBlock(Neighbor) then
MinedVectors[Neighbor] = true
table.insert(Queue, Neighbor)
else
table.insert(Boundary, Neighbor)
end
end

DirtyYieldCount += 1

if DirtyYieldCount > DirtyYieldThreshold then
print(`Current Cave Boundary: {#Boundary} Blocks`)
DirtyYieldCount = 1
end
end

print(`Final Cave Boundary: {#Boundary} Blocks`)

print(`Chunking...`)
local Chuncks = {}
local BlockIndex = 1
for Index=1, math.ceil(#Boundary/self.OreParams.ChunckSize) do
Chuncks[Index] = {}

for ChunkIndex=1, self.OreParams.ChunckSize do
Chuncks[Index][BlockIndex] = Boundary[BlockIndex]
BlockIndex += 1
end

end

print(`Creating chuncks...`)
for _, Chunck in Chuncks do
for _, Block in Chunck do
self:GenerateAt(Block, false)
end