How to use spatial hashing?

[Konjointed]

I’m trying to learn new ways to detect when the player is near stuff so I can let them interact with it and I discovered a method called spatial hashing which seems neat and is more efficient then what I used to do, however, it is quite confusing.

AFAIK it’s basically a grid of cells and you can put an object within a cell and then you can check for things within a cell (correct me if I’m wrong)

Here is my spatial hash class

function SpatialHash.new(cellSize)
	local self = {}
	
	local cellSize = cellSize
	local spatialHash = {}
	
	-- Calculate the hash key for the given position
	local function getHashKey(position)
		-- warn("Getting hash key")
		local x = math.floor(position.X / cellSize)
		local y = math.floor(position.Y / cellSize)
		local z = math.floor(position.Z / cellSize)
		return x.."_"..y.."_"..z
	end
	
	-- Calculate the cell coordinates for the given position
	function self.getCellCoords(position)
		-- warn("Getting cell coords")
		local x = math.floor(position.X / cellSize)
		local y = math.floor(position.Y / cellSize)
		local z = math.floor(position.Z / cellSize)
		return x, y, z
	end	

	-- Add an object to the spatial hash at the given position
	function self.addObject(object, position)
		warn("Adding object:",object)
		local key = getHashKey(position)

		if not spatialHash[key] then
			spatialHash[key] = {}
		end

		table.insert(spatialHash[key], object)
	end

	-- Get all objects in range of the given position
	function self.getObjectsInRange(position, range)
		local range = range / cellSize
		local x, y, z = self.getCellCoords(position)
		local objects = {}

		for i = -range, range do
			for j = -range, range do
				for k = -range, range do
					local key = (x + i) .. "_" .. (y + j) .. "_" .. (z + k)
					if spatialHash[key] then
						for _, object in ipairs(spatialHash[key]) do
							table.insert(objects, object)
						end
					end
				end
			end
		end

		return objects
	end
	
	return self
end

And here is my code that uses it

local chest = workspace.Chest
local item = workspace.Item
local cellSize = 15
local range = 15

local spatialHash = SpatialHash.new(cellSize)

spatialHash.addObject(chest, chest.Position)
spatialHash.addObject(item, item.Position)

game:GetService("RunService").Stepped:Connect(function()
	local x, y, z = spatialHash.getCellCoords(root.Position)
	visualizationPart.Position = Vector3.new(x * cellSize, y * cellSize, z * cellSize)
end)

while true do
	local objectsInRange = spatialHash.getObjectsInRange(root.Position, range)

	for _, object in pairs(objectsInRange) do
		print(object.Name .. " is within range of the player")
	end
	
	task.wait(1)
end

So the code does seem to work, however, I’m confused on how exactly the cell size and range is supposed to work I tried to make a visual part to try and help me understand, but I’m not sure if I did the math correctly because it looks a bit wonky.

[azqjanna]

This is technically a spatial hash but I think you’re confused because it doesn’t really give any advantages in this application. Concatenating the X Y and Z coordinate is a strong hash in that its not possible to have collisions, assuming the coordinates are integers of course. As such there isn’t really a need for a min / max range, and the cell size chosen will not effect performance.
Your comparison is not any less expensive that just comparing the coordinates of two objects rounded down, however. I think it would help if you looked at how an octree works, which is basically an extension of this with a tree structure. That application is extremely fast for a lot of kinds of checks, especially if one side of the collision never moves, like if its terrain.

[Konjointed]

So I ended up using this octree module and got it to work and it’s pretty neat, however, I’m a bit confused on I guess the usage.

At first I decided to make my octree and add objects all on the client since I’m trying to detect when the player is near things and so I can do things like add an outline and prompt, however, I realized it’s probably smarter for the server to handle creating and adding, but I’m confused on how I can use the octree on the client now. Would I just send information to the client?

[azqjanna]

It depends on the use case of the information that comes from the tree. If its for gameplay-critical logic it should of course be on the server. If the client also needs this information, it might be necessary for every client to also have a copy. Your job then is to make sure these octree stay the same.