How to use spatial hashing?

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

	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
	-- 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

	-- 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] = {}

		table.insert(spatialHash[key], object)

	-- 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)

		return objects
	return self

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.addObject(chest, chest.Position)
spatialHash.addObject(item, item.Position)

	local x, y, z = spatialHash.getCellCoords(root.Position)
	visualizationPart.Position = * cellSize, y * cellSize, z * cellSize)

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")

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.

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.

1 Like

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?

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.

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