Skip to main content

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 Draw method 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 = number

An 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 = string

The 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 {
FilterList: {EntityId}?
CustomFilter: ((EntityId) → boolean)?
FilterType: Enum.RaycastFilterType?
}

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​

</>
LooseTightDoubleGrid.ShapeType: {
Circle: ShapeType,
Rect: ShapeType,
Point: ShapeType
}
  • Circle: Represents a circular entity.
  • Rect: Represents a rectangular entity.
  • Point: Represents a point entity.

Functions​

new​

</>
LooseTightDoubleGrid.new(config: {
Position: Vector2?,
Size: Vector2?,
CellSize: number?
}) → LTDG

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​

</>
for  id: EntityId  in  LooseTightDoubleGrid  do

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​

</>
LooseTightDoubleGrid:GetEntities() → {EntityId}

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​

</>
LooseTightDoubleGrid:InsertRect(
position: Vector2,
size: Vector2
) → EntityId

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​

</>
LooseTightDoubleGrid:InsertCircle(
position: Vector2,
radius: number
) → EntityId

Inserts a circular entity into the grid.

local entityId = grid:InsertCircle(Vector2.new(5, 5), 2)
print("Inserted Circle Entity ID:", entityId)

InsertPoint​

</>
LooseTightDoubleGrid:InsertPoint(position: Vector2) → EntityId

Inserts a point entity into the grid.

local entityId = grid:InsertPoint(Vector2.new(10, 10))
print("Inserted Point Entity ID:", entityId)

UpdateRect​

</>
LooseTightDoubleGrid:UpdateRect(
entityId: EntityId,
newPosition: Vector2,
newSize: Vector2
) → ()

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​

</>
LooseTightDoubleGrid:UpdateCircle(
entityId: EntityId,
newPosition: Vector2,
newRadius: number
) → ()

Updates the position and radius of a circular entity.

grid:UpdateCircle(entityId, Vector2.new(8, 8), 3)
print("Updated Circle Entity ID:", entityId)

UpdatePoint​

</>
LooseTightDoubleGrid:UpdatePoint(
entityId: EntityId,
newPosition: Vector2
) → ()

Updates the position of a point entity.

grid:UpdatePoint(entityId, Vector2.new(15, 15))
print("Updated Point Entity ID:", entityId)

Remove​

</>
LooseTightDoubleGrid:Remove(entityId: EntityId) → boolean

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​

</>
LooseTightDoubleGrid:Has(entityId: EntityId) → boolean

Checks if an entity exists in the grid.

local exists = grid:Has(entityId)
print("Entity exists:", exists)

GetEntitySize​

</>
LooseTightDoubleGrid:GetEntitySize(id: EntityId) → Vector2

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​

</>
LooseTightDoubleGrid:GetEntityPosition(id: EntityId) → Vector2

Returns the position of an entity. Errors if no entity with the id is in the grid.. 

local position = grid:GetEntityPosition(entityId)
print

GetEntityPositionAndSize​

</>
LooseTightDoubleGrid:GetEntityPositionAndSize(id: EntityId) → (
)

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​

</>
LooseTightDoubleGrid:GetEntityShape(id: EntityId) → ShapeType

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​

</>
LooseTightDoubleGrid:QueryRect(
pos: Vector2,
size: Vector2,
filterParams: FilterParams?
) → {EntityId}

Queries entities within a rectangular region.

local entityIds = grid:QueryRect(Vector2.new(10, 10), Vector2.new(6, 6))
print("Entities in Rect:", entityIds)

QueryCircle​

</>
LooseTightDoubleGrid:QueryCircle(
pos: Vector2,
radius: number,
filterParams: FilterParams?
) → {EntityId}

Queries entities within a circular region.

local entities = grid:QueryCircle(Vector2.new(15, 15), 5)
print("Entities in Circle:", entities)

QueryPoint​

</>
LooseTightDoubleGrid:QueryPoint(
pos: Vector2,
filterParams: FilterParams?
) → {EntityId}

Queries entities at a specific point.

local entitiesIds = grid:QueryPoint(Vector2.new(20, 20))
print("Entities at Point:", entitiesIds)

QueryClosestToPoint​

</>
LooseTightDoubleGrid:QueryClosestToPoint(
point: Vector2,
filterParams: FilterParams?
) → EntityId?

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(
origin: Vector2,
direction: Vector2,
filterParams: FilterParams?
) → {
Normal: Vector2,
Position: Vector2,
Distance: number,
EntityId: EntityId,
}?

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​

debug
</>
LooseTightDoubleGrid:Draw() → Instance

Renders the grid and its entities for debugging purposes. Subsequent calls will destroy the previous render model. 

local renderModel = grid:Draw()
print("Render Model:", renderModel)
Show raw api
{
    "functions": [
        {
            "name": "__iter",
            "desc": "Iterates over the entities in the grid.\n```lua\nlocal grid = LooseTightDoubleGrid.new()\n\ngrid:InsertRect(Vector2.new(10, 10), Vector2.new(5, 5))\n\nfor id in grid do\n    print(grid:GetPosition(id)) -- Prints the position of each entity in the grid\nend\n```",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "id: EntityId"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 216,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "new",
            "desc": "Creates a new instance of LooseTightDoubleGrid with the given configuration.\n\n- **Position** is the center origin of the grid. *(Default: `Vector2.new(0, 0)`)*\n- **Size** is the number of cells in the x and y directions. *(Default: `Vector2.new(32, 32)`)*\n- **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`)*\n\n```lua\nlocal grid = LooseTightDoubleGrid.new({\n    Position = Vector2.new(0, 0),\n    Size = Vector2.new(32, 32),\n    CellSize = 4\n})\n```",
            "params": [
                {
                    "name": "config",
                    "desc": "",
                    "lua_type": "{\r\n    Position: Vector2?,\r\n    Size: Vector2?,\r\n    CellSize: number?\r\n}"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "LTDG\r\n"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 249,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "GetEntities",
            "desc": "Gets an array of all currently registered entity IDs in the grid.\n\nIf you need to iterate over the grid then you should use the `__iter` metamethod instead.",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{EntityId}\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 310,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "GetRow",
            "desc": "Gets the row index from a given world y-coordinate.",
            "params": [
                {
                    "name": "y",
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "returns": [],
            "function_type": "method",
            "private": true,
            "source": {
                "line": 323,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "GetCol",
            "desc": "Gets the column index from a given world x-coordinate.\n\n```lua\nlocal col = grid:GetCol(15)\nprint(\"Column:\", col)\n```",
            "params": [
                {
                    "name": "x",
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "returns": [],
            "function_type": "method",
            "private": true,
            "source": {
                "line": 343,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "InsertRect",
            "desc": "Inserts a rectangular entity into the grid.\n\n```lua\n-- Example Code for generating some parts and registering them in the grid\nlocal function V3ToV2(v3: Vector3): Vector2\n    return Vector2.new(v3.X, v3.Z)\nend\n\nlocal IdToPart = {}\nfor i = 1, 10 do\n    local part = Instance.new(\"Part\")\n    part.Size = Vector3.new(math.random(1, 5), 1, math.random(1, 5))\n    part.Position = Vector3.new(math.random(-20, 20), 1, math.random(-20, 20))\n    part.Anchored = true\n    part.Parent = workspace\n\n    local entityId = grid:InsertRect(V3ToV2(part.Position), V3ToV2(part.Size))\n\n    -- Some potential ways you could identify the connection between the part and the entityId:\n    IdToPart[entityId] = part -- A: store the part in a table for later reference\n    part:SetAttribute(\"EntityId\", entityId) -- B: store the entity ID in the part's attribute for lookup\n\n    print(\"Inserted Rect Entity ID:\", entityId)\nend\n```",
            "params": [
                {
                    "name": "position",
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "name": "size",
                    "desc": "",
                    "lua_type": "Vector2"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "EntityId\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 385,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "InsertCircle",
            "desc": "Inserts a circular entity into the grid.\n\n```lua\nlocal entityId = grid:InsertCircle(Vector2.new(5, 5), 2)\nprint(\"Inserted Circle Entity ID:\", entityId)\n```",
            "params": [
                {
                    "name": "position",
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "name": "radius",
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "EntityId\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 422,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "InsertPoint",
            "desc": "Inserts a point entity into the grid.\n\n```lua\nlocal entityId = grid:InsertPoint(Vector2.new(10, 10))\nprint(\"Inserted Point Entity ID:\", entityId)\n```",
            "params": [
                {
                    "name": "position",
                    "desc": "",
                    "lua_type": "Vector2"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "EntityId\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 456,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "_UpdateEntity",
            "desc": "Updates an entity's position and bounding box in the grid.",
            "params": [
                {
                    "name": "entityId",
                    "desc": "",
                    "lua_type": "EntityId"
                },
                {
                    "name": "newPos",
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "name": "L",
                    "desc": "",
                    "lua_type": "number"
                },
                {
                    "name": "B",
                    "desc": "",
                    "lua_type": "number"
                },
                {
                    "name": "R",
                    "desc": "",
                    "lua_type": "number"
                },
                {
                    "name": "T",
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "returns": [],
            "function_type": "method",
            "private": true,
            "source": {
                "line": 487,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "UpdateRect",
            "desc": "Updates the position and size of a rectangular entity.\n\n```lua\ngrid:UpdateRect(entityId, Vector2.new(12, 12), Vector2.new(5, 7))\nprint(\"Updated Rect Entity ID:\", entityId)\n```",
            "params": [
                {
                    "name": "entityId",
                    "desc": "",
                    "lua_type": "EntityId"
                },
                {
                    "name": "newPosition",
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "name": "newSize",
                    "desc": "",
                    "lua_type": "Vector2"
                }
            ],
            "returns": [],
            "function_type": "method",
            "source": {
                "line": 520,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "UpdateCircle",
            "desc": "Updates the position and radius of a circular entity.\n\n```lua\ngrid:UpdateCircle(entityId, Vector2.new(8, 8), 3)\nprint(\"Updated Circle Entity ID:\", entityId)\n```",
            "params": [
                {
                    "name": "entityId",
                    "desc": "",
                    "lua_type": "EntityId"
                },
                {
                    "name": "newPosition",
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "name": "newRadius",
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "returns": [],
            "function_type": "method",
            "source": {
                "line": 547,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "UpdatePoint",
            "desc": "Updates the position of a point entity.\n\n```lua\ngrid:UpdatePoint(entityId, Vector2.new(15, 15))\nprint(\"Updated Point Entity ID:\", entityId)\n```",
            "params": [
                {
                    "name": "entityId",
                    "desc": "",
                    "lua_type": "EntityId"
                },
                {
                    "name": "newPosition",
                    "desc": "",
                    "lua_type": "Vector2"
                }
            ],
            "returns": [],
            "function_type": "method",
            "source": {
                "line": 572,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "Remove",
            "desc": "Removes an entity from the grid.\nReturn true if the entity was found and removed.\nReturn false if the entity was not found.\n\n```lua\nlocal entityId = grid:InsertRect(Vector2.new(10, 10), Vector2.new(5, 5))\n\nlocal didRemove = grid:Remove(entityId)\n```",
            "params": [
                {
                    "name": "entityId",
                    "desc": "",
                    "lua_type": "EntityId"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "boolean\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 600,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "Has",
            "desc": "Checks if an entity exists in the grid.\n\n```lua\nlocal exists = grid:Has(entityId)\nprint(\"Entity exists:\", exists)\n```",
            "params": [
                {
                    "name": "entityId",
                    "desc": "",
                    "lua_type": "EntityId"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "boolean\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 622,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "GetEntitySize",
            "desc": "Returns the size of an entity.\nErrors if no entity with the id is in the grid.\n\n```lua\nlocal size = grid:GetEntitySize(entityId)\nprint(\"Entity Size:\", size)\n```",
            "params": [
                {
                    "name": "id",
                    "desc": "",
                    "lua_type": "EntityId"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "Vector2\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 636,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "GetEntityPosition",
            "desc": "Returns the position of an entity.\nErrors if no entity with the id is in the grid..\n\n```lua\nlocal position = grid:GetEntityPosition(entityId)\nprint",
            "params": [
                {
                    "name": "id",
                    "desc": "",
                    "lua_type": "EntityId"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "Vector2\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 657,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "GetEntityPositionAndSize",
            "desc": "Gets the position and size of an entity.\nFaster than calling `GetEntityPosition` and `GetEntitySize` separately.\nErrors if no entity with the id is in the grid.\n\n```lua\nlocal position, size = grid:GetEntityPositionAndSize(entityId)\nprint(\"Entity Position:\", position, \"Size:\", size)\n```",
            "params": [
                {
                    "name": "id",
                    "desc": "",
                    "lua_type": "EntityId"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "desc": "",
                    "lua_type": "Vector2"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 680,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "GetEntityShape",
            "desc": "Returns the shape type of an entity.\nErrors if no entity with the id is in the grid.\n\n```lua\nlocal shapeType = grid:GetEntityShape(entityId)\nprint(\"Entity Shape Type:\", shapeType)\n```",
            "params": [
                {
                    "name": "id",
                    "desc": "",
                    "lua_type": "EntityId"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "ShapeType\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 703,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "_QueryRegion",
            "desc": "Queries entities within a specified rectangular region bounds.",
            "params": [
                {
                    "name": "qL",
                    "desc": "",
                    "lua_type": "number"
                },
                {
                    "name": "qB",
                    "desc": "",
                    "lua_type": "number"
                },
                {
                    "name": "qR",
                    "desc": "",
                    "lua_type": "number"
                },
                {
                    "name": "qT",
                    "desc": "",
                    "lua_type": "number"
                },
                {
                    "name": "queryShapeType",
                    "desc": "",
                    "lua_type": "ShapeType?"
                },
                {
                    "name": "filterParams",
                    "desc": "",
                    "lua_type": "FilterParams?"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{ EntityId }\r\n"
                }
            ],
            "function_type": "method",
            "private": true,
            "source": {
                "line": 716,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "QueryRect",
            "desc": "Queries entities within a rectangular region.\n\n```lua\nlocal entityIds = grid:QueryRect(Vector2.new(10, 10), Vector2.new(6, 6))\nprint(\"Entities in Rect:\", entityIds)\n```",
            "params": [
                {
                    "name": "pos",
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "name": "size",
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "name": "filterParams",
                    "desc": "",
                    "lua_type": "FilterParams?"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{ EntityId }\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 841,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "QueryCircle",
            "desc": "Queries entities within a circular region.\n\n```lua\nlocal entities = grid:QueryCircle(Vector2.new(15, 15), 5)\nprint(\"Entities in Circle:\", entities)\n```",
            "params": [
                {
                    "name": "pos",
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "name": "radius",
                    "desc": "",
                    "lua_type": "number"
                },
                {
                    "name": "filterParams",
                    "desc": "",
                    "lua_type": "FilterParams?"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{ EntityId }\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 863,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "QueryPoint",
            "desc": "Queries entities at a specific point.\n\n```lua\nlocal entitiesIds = grid:QueryPoint(Vector2.new(20, 20))\nprint(\"Entities at Point:\", entitiesIds)\n```",
            "params": [
                {
                    "name": "pos",
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "name": "filterParams",
                    "desc": "",
                    "lua_type": "FilterParams?"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{ EntityId }\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 877,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "QueryClosestToPoint",
            "desc": "Queries the closest entity to a given point. Closeness is determined by the distance to the edge of the entity's shape.\n\nThis method searches for the entity that is closest to the specified point in the grid. \nIt considers all shapes (circles, rectangles, and points) and uses a two-tier comparison:\n- **Primary Metric**: Distance to the edge of the shape.\n- **Secondary Metric**: Distance to the center of the shape (used to break ties when the point is inside multiple shapes).\n\nUnder this two-tier metric, the method will return an entity if the point is inside the entity, even if another\nentities's center is technically closer to the point. `Point` entities are treated as circles with a radius of 0.\n\nThe method uses an expanding search algorithm, starting from the tight cell containing the point and gradually expanding outward until the closest entity is found.\n\n```lua\n-- Insert some entities\nlocal rectId = grid:InsertRect(Vector2.new(10, 10), Vector2.new(5, 5))\nlocal circleId = grid:InsertCircle(Vector2.new(15, 15), 3)\nlocal pointId = grid:InsertPoint(Vector2.new(20, 20))\n\n-- Query the closest entity to a point\nlocal closestEntityId = grid:QueryClosestToPoint(Vector2.new(12, 12))\nprint(\"Closest Entity ID:\", closestEntityId)\n```",
            "params": [
                {
                    "name": "point",
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "name": "filterParams",
                    "desc": "",
                    "lua_type": "FilterParams?"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "EntityId?\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 924,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "Raycast",
            "desc": "Performs a raycast through the grid, checking for intersections with entities.\nThe ray starts at `origin` and travels in the `direction`. The magnitude of\nthe direction vector determines the length of the ray.\n\nReturns the closest intersection, including the hit position, normal, distance,\nand the intersected entity ID. If nothing was hit then it returns `nil`.\n\n```lua\nlocal id1 = grid:InsertRect(Vector2.new(5, 0), Vector2.new(2, 2))\nlocal id2 = grid:InsertCircle(Vector2.new(8, 0), 1)\n\nlocal hit = grid:Raycast(Vector2.new(0, 0), Vector2.new(10, 0), {\n    FilterList = {id1}, -- ignore the rect\n    FilterType = Enum.RaycastFilterType.Exclude,\n})\nif hit then\n    print(\"Hit entity:\", hit.EntityId)\nend\n```",
            "params": [
                {
                    "name": "origin",
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "name": "direction",
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "name": "filterParams",
                    "desc": "",
                    "lua_type": "FilterParams?"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{\r\n        Normal: Vector2,\r\n        Position: Vector2,\r\n        Distance: number,\r\n        EntityId: EntityId,\r\n    }?\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 1156,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "QueryRotatedRect",
            "desc": "Gets all the entities that overlap with a rotated rectangular region.\n\n```lua\ngrid:QueryRotatedRect(Vector2.new(30, 30), Vector2.new(10, 5), 45)\n```",
            "params": [
                {
                    "name": "pos",
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "name": "size",
                    "desc": "",
                    "lua_type": "Vector2"
                },
                {
                    "name": "angle",
                    "desc": "",
                    "lua_type": "number"
                },
                {
                    "name": "filterParams",
                    "desc": "",
                    "lua_type": "FilterParams?"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{ EntityId }\r\n"
                }
            ],
            "function_type": "method",
            "errors": [
                {
                    "lua_type": "Not implemented.",
                    "desc": ""
                }
            ],
            "private": true,
            "unreleased": true,
            "source": {
                "line": 1401,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "QueryPolygon",
            "desc": "Queries entities within a polygonal region. The given polygon must be an array of Vector2 points\nthat define the vertices of the polygon in **counter clockwise order**.\n\n```lua\ngrid:QueryPolygon({Vector2.new(0, 0), Vector2.new(0, 10), Vector2.new(5, 5)})\n```",
            "params": [
                {
                    "name": "polygon",
                    "desc": "",
                    "lua_type": "{Vector2}"
                },
                {
                    "name": "filterParams",
                    "desc": "",
                    "lua_type": "FilterParams?"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{ EntityId }\r\n"
                }
            ],
            "function_type": "method",
            "errors": [
                {
                    "lua_type": "Not implemented.",
                    "desc": ""
                }
            ],
            "private": true,
            "unreleased": true,
            "source": {
                "line": 1418,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "Draw",
            "desc": "Renders the grid and its entities for debugging purposes.\nSubsequent calls will destroy the previous render model.\n\n```lua\nlocal renderModel = grid:Draw()\nprint(\"Render Model:\", renderModel)\n```",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "Instance\r\n"
                }
            ],
            "function_type": "method",
            "tags": [
                "debug"
            ],
            "source": {
                "line": 1437,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        }
    ],
    "properties": [
        {
            "name": "ShapeType",
            "desc": "- **Circle**: Represents a circular entity.\n- **Rect**: Represents a rectangular entity.\n- **Point**: Represents a point entity.",
            "lua_type": "{Circle: ShapeType, Rect: ShapeType, Point: ShapeType}",
            "source": {
                "line": 227,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        }
    ],
    "types": [
        {
            "name": "EntityId",
            "desc": "An identifier for an entity in the grid. This is a unique number assigned to each entity upon insertion into the grid.\nIds are not unique between different grids, so they should be used only within the context of a single grid instance.",
            "lua_type": "number",
            "source": {
                "line": 74,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "ShapeType",
            "desc": "The type of shape for an entity in the grid.\nUse the ShapeType enum for comparisions as the raw values are subject to change.",
            "lua_type": "string",
            "source": {
                "line": 81,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        },
        {
            "name": "FilterParams",
            "desc": "Controls the filtering of entities during queries.\nYou 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.\n\nThe `FilterType` determines whether the filter is inclusive or exclusive. Uses RaycastFilterType for consistency with Roblox's raycasting system.",
            "fields": [
                {
                    "name": "FilterList",
                    "lua_type": "{ EntityId }?",
                    "desc": ""
                },
                {
                    "name": "CustomFilter",
                    "lua_type": "((EntityId) -> boolean)?",
                    "desc": ""
                },
                {
                    "name": "FilterType",
                    "lua_type": "Enum.RaycastFilterType?",
                    "desc": ""
                }
            ],
            "source": {
                "line": 98,
                "path": "lib/loosetightdoublegrid/src/init.luau"
            }
        }
    ],
    "name": "LooseTightDoubleGrid",
    "desc": "The `LooseTightDoubleGrid` is a spatial partitioning structure designed to efficiently manage and query entities in a 2D space. \nIt is particularly useful for scenarios where entities with highly dynamic sizes need to be inserted, updated, removed, or queried based on their spatial \nrelationships, such as in games, simulations, or physics engines.\n\n## Features\n- **Insertion**: Supports inserting circular, rectangular, and point entities into the grid.\n- **Updates**: Allows updating the position and size of entities.\n- **Removal**: Entities can be removed from the grid.\n- **Queries**: Supports querying entities within rectangular, circular, and point regions. \n  Additional query methods for rotated rectangles and polygons are planned but not yet implemented.\n- **Debugging**: Includes a `Draw` method to visualize the grid and its entities in the 3D workspace.\n\n## Scenarios\nThe `LooseTightDoubleGrid` is ideal for:\n- **Collision Detection**: Quickly finding potential collisions between entities in a 2D space.\n- **Spatial Queries**: Efficiently retrieving entities within a specific region.\n- **Dynamic Environments**: Managing entities that frequently move or change size.\n\n## Example Usage\n```lua\nlocal grid = LooseTightDoubleGrid.new({\n    Position = Vector2.new(0, 0),\n    Size = Vector2.new(32, 32),\n    CellSize = 4\n})\n\n-- Insert a rectangle\nlocal rectId = grid:InsertRect(Vector2.new(10, 10), Vector2.new(5, 5))\n\n-- Query entities in a region\nlocal entities = grid:QueryRect(Vector2.new(10, 10), Vector2.new(6, 6))\nprint(\"Entities in region:\", entities)\n\n-- Update the rectangle's position\ngrid:UpdateRect(rectId, Vector2.new(15, 15), Vector2.new(5, 5))\n\n-- Remove the rectangle\nlocal success = grid:Remove(rectId)\nprint(\"Did find and remove?\", success)\n```\n\n:::info How it works - (Info for Nerds)\nInternally the grid is divided into two layers:\n- **Tight Grid**: A fixed grid where each cell contains references to overlapping loose cells.\n- **Loose Grid**: A grid where each cell has a larger boundary than the corresponding tight cell, allowing entities to span multiple cells.\n\nEntities are stored in the loose grid, and their spatial relationships are managed using axis-aligned bounding boxes (AABBs). \nThe tight grid helps narrow down the search space during queries, improving performance.\n:::\n:::tip Vector2\nAlthough the documentation specifies `Vector2` for positions and sizes,\nthe system will take any table with `X` and `Y` properties.\n:::",
    "source": {
        "line": 59,
        "path": "lib/loosetightdoublegrid/src/init.luau"
    }
}