workspace:GetBoundingBox() is not capturing all of the terrain in the game

NovelDev · January 15, 2025, 3:21am

NOTE: This is an offshoot from a previous topic about pathfinding. I decided to make a new topic for this specific issue because it’s very removed from the original discussion in the original topic.

I have a function generateMapGrid(), posted below:

local function generateMapGrid()
	local cframe, size = workspace:GetBoundingBox()
	local cellsX, cellsY, cellsZ = math.ceil(size.X / OCTREE_SIZE), math.ceil(size.Y / OCTREE_SIZE), math.ceil(size.Z / OCTREE_SIZE)
	local cellBounds, origin = OCTREE_SIZE * Vector3.new(cellsX, cellsY, cellsZ), cframe.Position
	for x = 1, cellsX do
		for y = 1, cellsY do
			for z = 1, cellsZ do
				local position = origin + Vector3.new(x, y, z) * OCTREE_SIZE - cellBounds * 0.5 - Vector3.one * OCTREE_SIZE * 0.5
				table.insert(roots, position)
				debugRootNode(position)
			end
		end
	end
end

The function is intended to encompass the entire map in as few 512x512x512 blocks as necessary to encompass it fully. The larger purpose is to space out the root nodes for an octree across a massive map so it can automatically generate a rough collision map for pathfinding. On two different maps I’ve tried this on, though, I’ve run into the same problem; the function will only encompass specific parts of the terrain and leave out the rest of it, as demonstrated below:

Notice in the bottom left corner how the massive chunk of terrain on the map is not covered with the green, translucent blocks (root notes). The image above has no BaseParts in the scan area. When I add BaseParts, it will include those, but not the extra terrain:

The two houses floating off to the side of the original chunk of terrain are dragging the coverage out to meet them, but not to the terrain off to the top right of the image. Here’s another image:

Hard to see, but there’s a house on the second chunk of terrain that the function is going out to meet, yet it isn’t encompassing the rest of the terrain surrounding it. Very frustrating.

I’ve narrowed down the problem to the :GetBoundingBox() function; it seems to think the latter terrain is not a part of the workspace’s physical makeup even though it was created in the same way as the terrain that is being captured in the bounding box. I have no idea what’s causing this and I don’t get any error messages or other indicators that something is failing except for print() messages returning values for the size of the bounding box that are obviously wrong.

Below I’ve included the place file for you to play around with. Hopefully you can get a better idea of what the problem is:
octree-spacing.rbxl (4.0 MB)

I’ll try to answer any other questions as well.

NovelDev · January 15, 2025, 6:35am

A quick update to the topic: I went in a different direction and tried working on a different aspect of the pathfinding using a similar implementation to generate a grid. I created an entirely new place file, used similar code, and ran into the same problem. Even without any BaseParts or terrain or anything at all that has a definite size (the workspace folder is just the objects for the camera and the terrain, the latter of which there is none), the function thinks the workspace has a bounding box of (2044, 252, 2044). If I try to insert a 100x100 baseplate at the origin, it continues to think it’s the previous, much larger size, even when nothing else exists in the workspace.

It doesn’t make sense how the workspace can have a set-in-stone physical size like this while having nothing in it; you can theoretically go in any direction forever, so why isn’t it much bigger? Here is the place file if you want to see for yourself:
empty-workspace-bounds.rbxl (54.0 KB)

EDIT: The workspace bounds of octree-spacing.rbxl (see OP) without anything in it is (2044, 512, 2044)

Mortai_Yt · January 15, 2025, 7:16am

Is this on the client or server? Is Workspace.StreamingEnabled on or off? (if on then that could be the issue)

NovelDev · January 15, 2025, 8:28am

This is server-side. Enabling/disabling StreamingEnabled seems to make no difference either way.

deleteables · January 15, 2025, 9:23am

Terrain’s size property is always locked at (2044, 252, 2044). The two bounding box methods on the workspace always see Terrain as that large cuboid, which is also a minimum bounding box in the case of your second place file.

I found a few painful ways of accurately getting the bounds of terrain:

NovelDev · January 17, 2025, 5:57am

I’m currently trying to implement the former. I got the DFS floodfill algorithm working in a place file of its own, but when I try to implement it into the larger system I’m trying to use it for, I get nothing but stack overflow errors.

local function dfs(pos)
	if table.find(posRecord, pos) then return end

	local min = pos - (Vector3.one * VOXEL_SIZE * 0.5)
	local max = pos + (Vector3.one * VOXEL_SIZE * 0.5)
	
	local materials, occupancies = workspace.Terrain:ReadVoxels(Region3.new(min, max), 4)
	local size = materials.Size

	local bounded = false
	for x = 1, size.X do
		for y = 1, size.Y do
			for z = 1, size.Z do
				local material = materials[x][y][z]
				local position = min + (Vector3.one * VOXEL_SIZE * 0.5) + (Vector3.new(x - 1, y - 1, z - 1) * VOXEL_SIZE)
				if (material ~= Enum.Material.Air and material ~= Enum.Material.Water) then
					bounded = true
				end
			end
		end
	end
	
	if bounded == true then
		--debugNode(pos, VOXEL_SIZE)
		table.insert(posRecord, pos)
		if min.X < boundsMin.X then boundsMin = Vector3.new(min.X, boundsMin.Y, boundsMin.Z) end
		if min.Y < boundsMin.Y then boundsMin = Vector3.new(boundsMin.X, min.Y, boundsMin.Z) end
		if min.Z < boundsMin.Z then boundsMin = Vector3.new(boundsMin.X, boundsMin.Y, min.Z) end
		if max.X > boundsMax.X then boundsMax = Vector3.new(max.X, boundsMax.Y, boundsMax.Z) end
		if max.Y > boundsMax.Y then boundsMax = Vector3.new(boundsMax.X, max.Y, boundsMax.Z) end
		if max.Z > boundsMax.Z then boundsMax = Vector3.new(boundsMax.X, boundsMax.Y, max.Z) end
		for i = 1, #TERRAIN_CELL_OFFSETS do dfs(pos + TERRAIN_CELL_OFFSETS[i] * VOXEL_SIZE) end
	end
end

VOXEL_SIZE is the size of the voxel scanning area and is set to 8 (I couldn’t get it to detect anything at size 4) and boundsMin and boundsMax are global variables that determine what the final min and max bounds of the “true bounding box” are. Updated place file below:
octree-spacing.rbxl (4.0 MB)
Is there anything here I could optimize? This is the first time I’ve ever tried implementing a floodfill algorithm, much less a 3D one. I’d rather not add task.wait() calls if I can afford it.

deleteables · January 17, 2025, 6:26am

The recursive call is what’s making the stack overflow. Try making dfs work on an array/set of cell positions that it fills up and processes.

I tried it. If you delay the execution of the main thread when it exceeds a timeout like 1/60 it won’t kill the script. I think the 8 VOXEL_SIZE is causing it to do this weird grid separation thing. Does the 0.5 you multiply with it in a few places have anything to do with the fact 8 worked for you but 4 didn’t?

NovelDev · January 17, 2025, 4:50pm

All the multiplication of VOXEL_SIZE with 0.5 does is set the maximum and minimum positions to create the region used by :ReadVoxels(). I pulled the basic framework for this script from another script I used to detect collision with terrain parts, which would add all of the 2x2 chunks of the 4x4 scan region to an array if it detected something. The line in the 3D for loop where position was defined and set ended up being useless, so I removed it.

I’m not entirely sure what you mean by this. The implementations online I used to guide my implementation all used recursive function calls, and the function is to get the bounding box of the entire map, so there’s no easy way of knowing how many cell positions there are or where they’re located before I run the algorithm. It’s only meant to run once, when the map is loaded, so it doesn’t need to run smoothly, but it shouldn’t kill the script. I could run separate parts in separate threads, but that might result in problems.

deleteables · January 17, 2025, 5:10pm

That makes sense.

I think the word “queue” or even an unsorted “pile” is a better word for what I meant. I rewrote that post a bit too much. I’m aware that the algorithm uses recursive function calls but there’s practical limits in Lua. Processing the cells from a pile or array doesn’t lose any information and isn’t my own bias, it’s just a way to emulate recursion without overflowing the stack. By using the heap instead.

Hopefully this worry is gone with my clarification above.

NovelDev · January 18, 2025, 3:46am

I’m afraid I still don’t understand what you mean. Are you suggesting I enter all the scan areas into an array and then scan them for terrain afterward? I get that most implementations of a floodfill algorithm are working off a grid of pixels, but those examples all have predefined dimensions they’re working off of. In my current implementation, you have to process the cell to know whether or not to move on to the surrounding cells because the bounds of the map are theoretically infinite. If I were trying to find the possible dimensions to scan in before I did any processing, the script would probably time out.

deleteables · January 18, 2025, 3:54am

Right. When I process a valid cell, I add the surrounding cells to same queue that the current cell was in. They’ll get dropped if they’re invalid. There’s no prerequisite information that it needs other than knowing whether a cell was already dealt with.

NovelDev · January 19, 2025, 7:20am

I think I understand what you’re saying. I found some old experiments with pathfinding tutorials where two tables exist, toSearch and searched. You start off by adding one point to toSearch and then run a while loop of the function until toSearch is exhausted. Rather than using strictly recursive function calls, the function simply adds the cell to searched after searching it and removes it from toSearch. If it finds the cell is valid, it adds the neighbors to toSearch.

Unfortunately I tried all of this just now, and it doesn’t seem to have made much of a difference, as now the script times out rather then the stack overflowing.

-- . . .
local toSearch = {}
local searched = {}
local boundsMin, boundsMax = Vector3.one * math.huge, Vector3.one * -math.huge
-- . . .
-- recursive function for flood fill algorithm
local function dfs(pos)
	if table.find(searched, pos) then table.remove(toSearch, table.find(toSearch, pos)) return end

	local min = pos - (Vector3.one * VOXEL_SIZE * 0.5)
	local max = pos + (Vector3.one * VOXEL_SIZE * 0.5)
	
	local materials, occupancies = workspace.Terrain:ReadVoxels(Region3.new(min, max), 4)
	local size = materials.Size

	local bounded = false
	for x = 1, size.X do
		for y = 1, size.Y do
			for z = 1, size.Z do
				local material = materials[x][y][z]
				if (material ~= Enum.Material.Air and material ~= Enum.Material.Water) then
					bounded = true
				end
			end
		end
	end
	table.insert(searched, pos)
	table.remove(toSearch, table.find(toSearch, pos))
	if bounded == true then
		--debugNode(pos, VOXEL_SIZE)
		if min.X < boundsMin.X then boundsMin = Vector3.new(min.X, boundsMin.Y, boundsMin.Z) end
		if min.Y < boundsMin.Y then boundsMin = Vector3.new(boundsMin.X, min.Y, boundsMin.Z) end
		if min.Z < boundsMin.Z then boundsMin = Vector3.new(boundsMin.X, boundsMin.Y, min.Z) end
		if max.X > boundsMax.X then boundsMax = Vector3.new(max.X, boundsMax.Y, boundsMax.Z) end
		if max.Y > boundsMax.Y then boundsMax = Vector3.new(boundsMax.X, max.Y, boundsMax.Z) end
		if max.Z > boundsMax.Z then boundsMax = Vector3.new(boundsMax.X, boundsMax.Y, max.Z) end
		for i = 1, #TERRAIN_CELL_OFFSETS do table.insert(toSearch, (pos + TERRAIN_CELL_OFFSETS[i] * VOXEL_SIZE)) end
	end
end
-- generates an accurate bounding box that includes terrain
local function getTrueBoundingBox()
	table.insert(toSearch, Vector3.zero + Vector3.one * VOXEL_SIZE * 0.5)
	while #toSearch > 0 do dfs(toSearch[1]) end
	-- . . .
end

octree-spacing.rbxl (4.0 MB)

deleteables · January 19, 2025, 8:54am

I made a “cooldown” function in my version that yields temporarily after enough time has been spent running code. It’s something like:

local TIMEOUT = 1 / 60 -- you might be able to make this shorter
local latest = os.clock()

local function cooldown()
	if (os.clock() - latest) > TIMEOUT then
		task.wait() -- i did a convoluted thread delay thing before, ignore that
		latest = os.clock()
	end
end

You can either put a call to this in the while loop or dfs itself.

NovelDev · January 19, 2025, 12:47pm

Did you manage to get your version to actually complete scanning? The implementation I used here is starting to make me think I’m working in the wrong direction. I have two blocks of terrain, one that’s 2048 x 512 x 2048 and another that’s 2048 x 1024 x 2048. With a voxel size of 8, that means upwards of +12.5 million potential calculations. I lowered the time all the way down to a cooldown every 10 seconds (which was cutting it close) and there was still no end in sight.

octree-spacing.rbxl (4.0 MB)

If I’m running this once at the beginning of every game, I can’t afford to have the load time be more than 20 seconds absolute tops. That’s also including the actual collision detection scan included in the other topic mentioned in OP, which takes a while, too.

EDIT: I just tested it with a voxel size of 64; the scan does eventually conclude, and the results are correct, but I would still like to try to make the system more efficient because I plan for the maps to be much larger than the example that I’m using (2048 x 4096 x 1024).

Cxsnls · January 19, 2025, 1:29pm

Hey, I just got a notification that my post was linked and I think I can be of some help here. If I understand correctly, you’re trying to make a pathfinding algorithm using octrees and you need the terrain’s size to determine the size of those?

NovelDev · January 19, 2025, 1:35pm

I need the terrain’s size so that I can figure out how large the map is (in conjunction with workspace:GetBoundingBox() for base parts) so I can most efficiently space out root nodes (the nodes where the octree starts from) across the map, which would be used to generate a collision map of all of the surfaces, which in turn would be used as a flow-field pathfinding grid for AI. I’m keeping the root nodes a consistent size of 512^3 for now, but the code allows for me to make them bigger or smaller. I’m not trying to use the map’s bounding box to determine the size of the root nodes, if that’s what you’re asking.

Cxsnls · January 19, 2025, 1:38pm

Okay, so I see that you’ve already tested with a voxel size of 64 but according to my calculations the biggest number you can call ReadVoxels with is a region of 160^3. I’ve also done some tests afterwards and the lower the number of total calls (regardless of region size), the faster it goes. I’m not very sure how your implementation is, but if you need the number to be a divisor of 512, you can try 128^3.

NovelDev · January 19, 2025, 5:15pm

I tested 128^3 on the largest map I planned to scan (6144 x 512 x 6144), and it takes 15-25 seconds to work. It’s much better than before but I was hoping for faster. Are there any other optimizations that can be made to the script?

Cxsnls · January 19, 2025, 7:56pm

Well, that depends on your usecase. Do you just need the XZ size of the map, or do you need the Y dimension too? Also, are your maps more or less squares/rectangles or do they have any weird lines sticking out? In addition to this, is the bottom part more or less flat?

To reduce response times, I’ll write a few of my ideas:
If you have a map with a flat bottom and no weird line stuff, what you can do is this:
Instead of scanning the whole map, just scan in each direction. If you do this, you can reduce 9216 calls to just 100 calls.
If you don’t have a map with a flat bottom and a bunch line stuff, do the same as before, but when you reach an empty space, scan that whole section. If you don’t find anything else, then that’s the last piece of terrain in that direction. If you find other things, continue calling ReadVoxels in the position of that piece of terrain until it ends and repeat. I’m not sure how well this will work, really. Picture to explain:

This might sound a bit hacky, but you could also switch to raycasts (like my original solution). It should be a lot faster.

Anyways, I don’t mean to have you redo everything you’ve done so far, but I’d really really switch to raycasts if I were you.

NovelDev · January 21, 2025, 2:15am

I don’t know whether this is what you were advising, but I changed the script so that, rather than adding all of the searched node’s neighbors to the queue after processing, it would only add those neighbors that could potentially increase the max region bounds or decrease the minimum region bounds. Using just this qualifier, I managed to cut the number of calls in half from +12k to just about 6k. The process now takes roughly 9 seconds instead of 20. Considering I should be using a depth-first search for this process, I don’t know why I didn’t start with this as part of the script.

It should be mentioned I tried to reduce this further by adding only those with bounds that strictly exceeded the established bounds (min < boundsMin rather than <= and vice versa) but the script wouldn’t properly search all of the cells it needed to to find the accurate bounds of the map. I don’t know what would be causing this, but it’s running out of cells to search long before it should. If I can get the entire search down to five seconds, I’ll be satisfied. Maybe that involves doing a breadth-first search instead?