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) *, -1, 1)

function OreHandler:GetGenerationTable(BlockspaceVector: Vector3)
	return {
		BlockspaceVector +,0,0);
		BlockspaceVector +,0,0);

		BlockspaceVector +,1,0);
		BlockspaceVector +,-1,0);

		BlockspaceVector +,0,1);
		BlockspaceVector +,0,-1);

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

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
		if GeneratedVectors[NewVector] then
		if NewVector.Y <= 0 then

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

function OreHandler:GenerateAt(BlockspaceVector: Vector3, PlayerBroke: boolean): BasePart
	if self:HasVectorAlreadyBeenUsed(BlockspaceVector) then

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

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

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

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

		local CaveGenStart = os.clock()
		self:Break(nil, BlockspaceVector, true)
		local CaveGenEnd = os.clock() - CaveGenStart

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


	... --unrelated code

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
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
			if self:IsCaveBlock(Neighbor) then
				MinedVectors[Neighbor] = true
				table.insert(Queue, Neighbor)
				table.insert(Boundary, Neighbor)
		DirtyYieldCount += 1
		if DirtyYieldCount > DirtyYieldThreshold then
			print(`Current Cave Boundary: {#Boundary} Blocks`)
			DirtyYieldCount = 1
	print(`Final Cave Boundary: {#Boundary} Blocks`)
	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
	print(`Creating chuncks...`)
	for _, Chunck in Chuncks do
		for _, Block in Chunck do
			self:GenerateAt(Block, false)
	self.CurrentlyProcessingCave = false

I tried pushing it to it’s limits and it works surprisingly well.


This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.