LooseTightDoubleGrid
The LooseTightDoubleGrid is a spatial partitioning structure designed to efficiently manage and query entities in a 2D space.
It is particularly useful for scenarios where entities with highly dynamic sizes need to be inserted, updated, removed, or queried based on their spatial
relationships, such as in games, simulations, or physics engines.
Features
- Insertion: Supports inserting circular, rectangular, and point entities into the grid.
- Updates: Allows updating the position and size of entities.
- Removal: Entities can be removed from the grid.
- Queries: Supports querying entities within rectangular, circular, and point regions. Additional query methods for rotated rectangles and polygons are planned but not yet implemented.
- Debugging: Includes a
Drawmethod to visualize the grid and its entities in the 3D workspace.
Scenarios
The LooseTightDoubleGrid is ideal for:
- Collision Detection: Quickly finding potential collisions between entities in a 2D space.
- Spatial Queries: Efficiently retrieving entities within a specific region.
- Dynamic Environments: Managing entities that frequently move or change size.
Example Usage
local grid = LooseTightDoubleGrid.new({
Position = Vector2.new(0, 0),
Size = Vector2.new(32, 32),
CellSize = 4
})
-- Insert a rectangle
local rectId = grid:InsertRect(Vector2.new(10, 10), Vector2.new(5, 5))
-- Query entities in a region
local entities = grid:QueryRect(Vector2.new(10, 10), Vector2.new(6, 6))
print("Entities in region:", entities)
-- Update the rectangle's position
grid:UpdateRect(rectId, Vector2.new(15, 15), Vector2.new(5, 5))
-- Remove the rectangle
local success = grid:Remove(rectId)
print("Did find and remove?", success)
How it works - (Info for Nerds)
Internally the grid is divided into two layers:
- Tight Grid: A fixed grid where each cell contains references to overlapping loose cells.
- Loose Grid: A grid where each cell has a larger boundary than the corresponding tight cell, allowing entities to span multiple cells.
Entities are stored in the loose grid, and their spatial relationships are managed using axis-aligned bounding boxes (AABBs). The tight grid helps narrow down the search space during queries, improving performance.
Vector2
Although the documentation specifies Vector2 for positions and sizes,
the system will take any table with X and Y properties.
Types
EntityId
type EntityId = numberAn identifier for an entity in the grid. This is a unique number assigned to each entity upon insertion into the grid. Ids are not unique between different grids, so they should be used only within the context of a single grid instance.
ShapeType
type ShapeType = stringThe type of shape for an entity in the grid. Use the ShapeType enum for comparisions as the raw values are subject to change.
FilterParams
interface FilterParams {}Controls the filtering of entities during queries. You can use either a list of entity IDs or a custom filter function to specify which entities to include or exclude from the query results.
The FilterType determines whether the filter is inclusive or exclusive. Uses RaycastFilterType for consistency with Roblox's raycasting system.
Properties
ShapeType
- Circle: Represents a circular entity.
- Rect: Represents a rectangular entity.
- Point: Represents a point entity.
Functions
new
Creates a new instance of LooseTightDoubleGrid with the given configuration.
- Position is the center origin of the grid. (Default:
Vector2.new(0, 0)) - Size is the number of cells in the x and y directions. (Default:
Vector2.new(32, 32)) - CellSize is the size of each cell in studs. Adjust this number based on the average sizes of your provided entities in order to optimize performance. (Default:
4)
local grid = LooseTightDoubleGrid.new({
Position = Vector2.new(0, 0),
Size = Vector2.new(32, 32),
CellSize = 4
})
iterating over LooseTightDoubleGrid
Iterates over the entities in the grid.
local grid = LooseTightDoubleGrid.new()
grid:InsertRect(Vector2.new(10, 10), Vector2.new(5, 5))
for id in grid do
print(grid:GetPosition(id)) -- Prints the position of each entity in the grid
end
GetEntities
Gets an array of all currently registered entity IDs in the grid.
If you need to iterate over the grid then you should use the __iter metamethod instead.
InsertRect
Inserts a rectangular entity into the grid.
-- Example Code for generating some parts and registering them in the grid
local function V3ToV2(v3: Vector3): Vector2
return Vector2.new(v3.X, v3.Z)
end
local IdToPart = {}
for i = 1, 10 do
local part = Instance.new("Part")
part.Size = Vector3.new(math.random(1, 5), 1, math.random(1, 5))
part.Position = Vector3.new(math.random(-20, 20), 1, math.random(-20, 20))
part.Anchored = true
part.Parent = workspace
local entityId = grid:InsertRect(V3ToV2(part.Position), V3ToV2(part.Size))
-- Some potential ways you could identify the connection between the part and the entityId:
IdToPart[entityId] = part -- A: store the part in a table for later reference
part:SetAttribute("EntityId", entityId) -- B: store the entity ID in the part's attribute for lookup
print("Inserted Rect Entity ID:", entityId)
end
InsertCircle
Inserts a circular entity into the grid.
local entityId = grid:InsertCircle(Vector2.new(5, 5), 2)
print("Inserted Circle Entity ID:", entityId)
InsertPoint
Inserts a point entity into the grid.
local entityId = grid:InsertPoint(Vector2.new(10, 10))
print("Inserted Point Entity ID:", entityId)
UpdateRect
Updates the position and size of a rectangular entity.
grid:UpdateRect(entityId, Vector2.new(12, 12), Vector2.new(5, 7))
print("Updated Rect Entity ID:", entityId)
UpdateCircle
Updates the position and radius of a circular entity.
grid:UpdateCircle(entityId, Vector2.new(8, 8), 3)
print("Updated Circle Entity ID:", entityId)
UpdatePoint
Updates the position of a point entity.
grid:UpdatePoint(entityId, Vector2.new(15, 15))
print("Updated Point Entity ID:", entityId)
Remove
Removes an entity from the grid. Return true if the entity was found and removed. Return false if the entity was not found.
local entityId = grid:InsertRect(Vector2.new(10, 10), Vector2.new(5, 5))
local didRemove = grid:Remove(entityId)
Has
Checks if an entity exists in the grid.
local exists = grid:Has(entityId)
print("Entity exists:", exists)
GetEntitySize
Returns the size of an entity. Errors if no entity with the id is in the grid.
local size = grid:GetEntitySize(entityId)
print("Entity Size:", size)
GetEntityPosition
Returns the position of an entity. Errors if no entity with the id is in the grid..
local position = grid:GetEntityPosition(entityId)
print
GetEntityPositionAndSize
Gets the position and size of an entity.
Faster than calling GetEntityPosition and GetEntitySize separately.
Errors if no entity with the id is in the grid.
local position, size = grid:GetEntityPositionAndSize(entityId)
print("Entity Position:", position, "Size:", size)
GetEntityShape
Returns the shape type of an entity. Errors if no entity with the id is in the grid.
local shapeType = grid:GetEntityShape(entityId)
print("Entity Shape Type:", shapeType)
QueryRect
Queries entities within a rectangular region.
local entityIds = grid:QueryRect(Vector2.new(10, 10), Vector2.new(6, 6))
print("Entities in Rect:", entityIds)
QueryCircle
Queries entities within a circular region.
local entities = grid:QueryCircle(Vector2.new(15, 15), 5)
print("Entities in Circle:", entities)
QueryPoint
Queries entities at a specific point.
local entitiesIds = grid:QueryPoint(Vector2.new(20, 20))
print("Entities at Point:", entitiesIds)
QueryClosestToPoint
Queries the closest entity to a given point. Closeness is determined by the distance to the edge of the entity's shape.
This method searches for the entity that is closest to the specified point in the grid. It considers all shapes (circles, rectangles, and points) and uses a two-tier comparison:
- Primary Metric: Distance to the edge of the shape.
- Secondary Metric: Distance to the center of the shape (used to break ties when the point is inside multiple shapes).
Under this two-tier metric, the method will return an entity if the point is inside the entity, even if another
entities's center is technically closer to the point. Point entities are treated as circles with a radius of 0.
The method uses an expanding search algorithm, starting from the tight cell containing the point and gradually expanding outward until the closest entity is found.
-- Insert some entities
local rectId = grid:InsertRect(Vector2.new(10, 10), Vector2.new(5, 5))
local circleId = grid:InsertCircle(Vector2.new(15, 15), 3)
local pointId = grid:InsertPoint(Vector2.new(20, 20))
-- Query the closest entity to a point
local closestEntityId = grid:QueryClosestToPoint(Vector2.new(12, 12))
print("Closest Entity ID:", closestEntityId)
Raycast
LooseTightDoubleGrid:Raycast() → {Distance: number,}?
Performs a raycast through the grid, checking for intersections with entities.
The ray starts at origin and travels in the direction. The magnitude of
the direction vector determines the length of the ray.
Returns the closest intersection, including the hit position, normal, distance,
and the intersected entity ID. If nothing was hit then it returns nil.
local id1 = grid:InsertRect(Vector2.new(5, 0), Vector2.new(2, 2))
local id2 = grid:InsertCircle(Vector2.new(8, 0), 1)
local hit = grid:Raycast(Vector2.new(0, 0), Vector2.new(10, 0), {
FilterList = {id1}, -- ignore the rect
FilterType = Enum.RaycastFilterType.Exclude,
})
if hit then
print("Hit entity:", hit.EntityId)
end
Draw
debugRenders the grid and its entities for debugging purposes. Subsequent calls will destroy the previous render model.
local renderModel = grid:Draw()
print("Render Model:", renderModel)