# 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

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

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

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.

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.