Skip to main content

Quadtree

A sparse spatial index for storing objects by 2D position.

The quadtree divides space into progressively smaller regions and stores nodes in the smallest region that contains their position. That makes spatial queries like radius searches and nearest-node lookups substantially cheaper than scanning an entire list.

Quadtree example gif 

local Quadtree = require(path.to.quadtree)

local tree = Quadtree.new(128)
local node = tree:CreateNode(Vector2.new(10, 20), {
	Name = "SpawnPoint",
})

for entry in tree:ForEachInRadius(Vector2.new(0, 0), 64) do
	print(entry.Object.Name)
end
Vector3 Support

Internally, this implementation accepts both Vector2 and Vector3 inputs. When a Vector3 is provided, the Y component is ignored and the node is indexed using its X/Z coordinates.

Types​

Vector​

</>
type Vector = Vector2 | Vector3

Internally only Vector2 is used for positions, but Vector3 is accepted as input and will be converted to Vector2 by dropping the Y component.

Node<T>​

</>
type Node<T> = {
Position: Vector2,
Object: T
}

A node stored inside the quadtree.

Position is always normalized to Vector2. Object is the payload you store in the tree. These fields are public for read-only access and should not be mutated manually. 

local node = tree:CreateNode(Vector2.new(12, 4), "Coin")
print(node.Position, node.Object)

Functions​

new​

Constructor
</>
Quadtree.new(topRegionSize: number?) → Quadtree<T>

Creates a new quadtree instance.

topRegionSize controls the size of the root-level grid cells. Larger values mean fewer top regions, while smaller values create a denser top-level grid. 

local tree = Quadtree.new(256)
topRegionSize

If your objects are generally clustered together, a smaller topRegionSize can help reduce the number of nodes per region and speed up queries. By default, it's 512, which means each top-level region covers a 512x512 area. Adjust this based on your expected spatial distribution for better performance.

CreateNode​

</>
Quadtree:CreateNode(
position: Vector,
object: T
) → Node<T>

Creates and inserts a node into the quadtree.

local node = tree:CreateNode(Vector2.new(32, 16), "Pickup")

RemoveNode​

</>
Quadtree:RemoveNode(node: Node<T>) → boolean

Removes a node from the quadtree if present.

local didRemove = tree:RemoveNode(node)

ChangeNodePosition​

</>
Quadtree:ChangeNodePosition(
node: Node<T>,
position: Vector
) → ()

Changes a node's position and updates region membership.

tree:ChangeNodePosition(node, Vector2.new(100, 0))

ClearAllNodes​

</>
Quadtree:ClearAllNodes() → ()

Clears all regions and nodes from the quadtree.

GetAllNodes​

</>
Quadtree:GetAllNodes() → {Node<T>}

Returns a flat array of all nodes.

local all = tree:GetAllNodes()
for _, node in ipairs(all) do
	print(node.Object)
end

CountNodes​

</>
Quadtree:CountNodes() → number

Returns the current node count.

SearchRadius​

</>
Quadtree:SearchRadius(
position: Vector,
radius: number
) → {Node<T>}

Returns nodes strictly within the given radius of position.

local nearbyNodes = tree:SearchRadius(Vector2.new(0, 0), 32)

ForEachInRadius​

</>
Quadtree:ForEachInRadius(
position: Vector,
radius: number
) → () → Node<T>?

Returns an iterator for nodes strictly within radius.

for node in tree:ForEachInRadius(Vector2.new(0, 0), 32) do
	print(node.Object)
end

ForEachNode​

</>
Quadtree:ForEachNode() → () → Node<T>?

Returns an iterator across all nodes.

for node in tree:ForEachNode() do
	print(node.Object)
end

FindFirstNode​

</>
Quadtree:FindFirstNode(object: T) → Node<T>?

Returns the first node whose Object equals object.

local node = tree:FindFirstNode("SpawnPoint")
if node then
	print(node.Position)
end

GetNearest​

</>
Quadtree:GetNearest(
position: Vector,
radius: number,
maxNodes: number?
) → {Node<T>}

Returns nearest nodes sorted by ascending distance.

local nearestNodes = tree:GetNearest(Vector2.new(0, 0), 64, 5)

iterating over Quadtree​

metamethod
</>
for  Node<T>  in  Quadtree  do

Metamethod alias for ForEachNode, enabling direct iteration over the quadtree.

Show raw api
{
    "functions": [
        {
            "name": "new",
            "desc": "Creates a new quadtree instance.\n\n`topRegionSize` controls the size of the root-level grid cells. Larger values\nmean fewer top regions, while smaller values create a denser top-level grid.\n\n```lua\nlocal tree = Quadtree.new(256)\n```\n\n:::tip topRegionSize\nIf your objects are generally clustered together, a smaller `topRegionSize`\ncan help reduce the number of nodes per region and speed up queries. By default, \nit's 512, which means each top-level region covers a 512x512 area. Adjust this \nbased on your expected spatial distribution for better performance.\n:::",
            "params": [
                {
                    "name": "topRegionSize",
                    "desc": "",
                    "lua_type": "number?"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "Quadtree<T>"
                }
            ],
            "function_type": "static",
            "tags": [
                "Constructor"
            ],
            "source": {
                "line": 385,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "CreateNode",
            "desc": "Creates and inserts a node into the quadtree.\n\n\n```lua\nlocal node = tree:CreateNode(Vector2.new(32, 16), \"Pickup\")\n```",
            "params": [
                {
                    "name": "position",
                    "desc": "",
                    "lua_type": "Vector"
                },
                {
                    "name": "object",
                    "desc": "",
                    "lua_type": "T"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "Node<T>"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 409,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "RemoveNode",
            "desc": "Removes a node from the quadtree if present.\n\n\n```lua\nlocal didRemove = tree:RemoveNode(node)\n```",
            "params": [
                {
                    "name": "node",
                    "desc": "",
                    "lua_type": "Node<T>"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "boolean"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 437,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "ChangeNodePosition",
            "desc": "Changes a node's position and updates region membership.\n\n\n```lua\ntree:ChangeNodePosition(node, Vector2.new(100, 0))\n```",
            "params": [
                {
                    "name": "node",
                    "desc": "",
                    "lua_type": "Node<T>"
                },
                {
                    "name": "position",
                    "desc": "",
                    "lua_type": "Vector"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "()"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 486,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "ClearAllNodes",
            "desc": "Clears all regions and nodes from the quadtree.",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "()"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 537,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "GetAllNodes",
            "desc": "Returns a flat array of all nodes.\n\n```lua\nlocal all = tree:GetAllNodes()\nfor _, node in ipairs(all) do\n\tprint(node.Object)\nend\n```",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{Node<T>}"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 558,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "CountNodes",
            "desc": "Returns the current node count.",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 580,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "SearchRadius",
            "desc": "Returns nodes strictly within the given radius of position.\n\n```lua\nlocal nearbyNodes = tree:SearchRadius(Vector2.new(0, 0), 32)\n```",
            "params": [
                {
                    "name": "position",
                    "desc": "",
                    "lua_type": "Vector"
                },
                {
                    "name": "radius",
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{Node<T>}"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 596,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "ForEachInRadius",
            "desc": "Returns an iterator for nodes strictly within radius.\n\n```lua\nfor node in tree:ForEachInRadius(Vector2.new(0, 0), 32) do\n\tprint(node.Object)\nend\n```",
            "params": [
                {
                    "name": "position",
                    "desc": "",
                    "lua_type": "Vector"
                },
                {
                    "name": "radius",
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "() -> Node<T>?"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 627,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "ForEachNode",
            "desc": "Returns an iterator across all nodes.\n\n```lua\nfor node in tree:ForEachNode() do\n\tprint(node.Object)\nend\n```",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "() -> Node<T>?"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 656,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "FindFirstNode",
            "desc": "Returns the first node whose Object equals object.\n\n```lua\nlocal node = tree:FindFirstNode(\"SpawnPoint\")\nif node then\n\tprint(node.Position)\nend\n```",
            "params": [
                {
                    "name": "object",
                    "desc": "",
                    "lua_type": "T"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "Node<T>?"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 686,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "GetNearest",
            "desc": "Returns nearest nodes sorted by ascending distance.\n\n```lua\nlocal nearestNodes = tree:GetNearest(Vector2.new(0, 0), 64, 5)\n```",
            "params": [
                {
                    "name": "position",
                    "desc": "",
                    "lua_type": "Vector"
                },
                {
                    "name": "radius",
                    "desc": "",
                    "lua_type": "number"
                },
                {
                    "name": "maxNodes",
                    "desc": "",
                    "lua_type": "number?"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{Node<T>}"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 708,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "_getRegion",
            "desc": "",
            "params": [
                {
                    "name": "self",
                    "desc": "",
                    "lua_type": "QuadtreeInternal<T>"
                },
                {
                    "name": "maxLevel",
                    "desc": "",
                    "lua_type": "number"
                },
                {
                    "name": "position",
                    "desc": "",
                    "lua_type": "Vector2"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "Region<T>\n"
                }
            ],
            "function_type": "static",
            "private": true,
            "source": {
                "line": 729,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "__iter",
            "desc": "Metamethod alias for ***ForEachNode***, enabling direct iteration over the quadtree.",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "Node<T>"
                }
            ],
            "function_type": "method",
            "tags": [
                "metamethod"
            ],
            "source": {
                "line": 789,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        }
    ],
    "properties": [],
    "types": [
        {
            "name": "Vector",
            "desc": "Internally only Vector2 is used for positions, but Vector3 is accepted as input and will be converted to Vector2 by dropping the Y component.",
            "lua_type": "Vector2 | Vector3",
            "source": {
                "line": 44,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "Node<T>",
            "desc": "A node stored inside the quadtree.\n\n`Position` is always normalized to Vector2. `Object` is the payload you store in\nthe tree. These fields are public for read-only access and should not be mutated\nmanually.\n\n\n```lua\nlocal node = tree:CreateNode(Vector2.new(12, 4), \"Coin\")\nprint(node.Position, node.Object)\n```",
            "lua_type": "{Position: Vector2, Object: T}",
            "source": {
                "line": 211,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        },
        {
            "name": "NodeInternal<T>",
            "desc": "Internal node metadata used by the implementation.\n\nThis is the public node shape plus the owning region reference.",
            "lua_type": "Node<T> & {Region: Region<T>?}",
            "private": true,
            "source": {
                "line": 225,
                "path": "lib/quadtree/src/quadtree.luau"
            }
        }
    ],
    "name": "Quadtree",
    "desc": "A sparse spatial index for storing objects by 2D position.\n\nThe quadtree divides space into progressively smaller regions and stores nodes\nin the smallest region that contains their position. That makes spatial queries\nlike radius searches and nearest-node lookups substantially cheaper than scanning\nan entire list.\n\n![Quadtree example gif](../quadtree/quadtreeExample.gif)\n\n```lua\nlocal Quadtree = require(path.to.quadtree)\n\nlocal tree = Quadtree.new(128)\nlocal node = tree:CreateNode(Vector2.new(10, 20), {\n\tName = \"SpawnPoint\",\n})\n\nfor entry in tree:ForEachInRadius(Vector2.new(0, 0), 64) do\n\tprint(entry.Object.Name)\nend\n```\n\n:::tip Vector3 Support\nInternally, this implementation accepts both Vector2 and Vector3 inputs. When a\nVector3 is provided, the Y component is ignored and the node is indexed using\nits X/Z coordinates.\n:::",
    "source": {
        "line": 34,
        "path": "lib/quadtree/src/quadtree.luau"
    }
}