【高级技巧】四叉树入门：大量怪物的邻近查询

local function newQuad(x, y, size, depth)
    return { x = x, y = y, size = size, depth = depth,
        items = {}, kids = nil }
end
local function quadInsert(node, it)
    if node.kids then
        local half = node.size / 2
        local cx = it.x < node.x + half and 0 or 1
        local cy = it.y < node.y + half and 0 or 1
        quadInsert(node.kids[cy * 2 + cx + 1], it)
        return
    end
    node.items[#node.items + 1] = it
    if #node.items > 8 and node.depth < 6 then
        quadSplit(node)
    end
end
local function quadSplit(node)
    local half = node.size / 2
    node.kids = {
        newQuad(node.x, node.y, half, node.depth + 1),
        newQuad(node.x + half, node.y, half, node.depth + 1),
        newQuad(node.x, node.y + half, half, node.depth + 1),
        newQuad(node.x + half, node.y + half, half, node.depth + 1),
    }
    local items = node.items
    node.items = {}
    for _, it in ipairs(items) do
        quadInsert(node, it)
    end
end

local function quadQuery(node, cx, cy, r, out)
    if cx + r < node.x or cx - r > node.x + node.size
        or cy + r < node.y or cy - r > node.y + node.size then
        return
    end
    for _, it in ipairs(node.items) do
        local dx, dy = it.x - cx, it.y - cy
        if dx * dx + dy * dy <= r * r then
            out[#out + 1] = it
        end
    end
    if node.kids then
        for _, k in ipairs(node.kids) do
            quadQuery(k, cx, cy, r, out)
        end
    end
end