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
if self:HasVectorAlreadyBeenUsed(BlockspaceVector) then
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
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
task.wait()
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
task.wait()
end
self.CurrentlyProcessingCave = false
end
I tried pushing it to it’s limits and it works surprisingly well.
