lua写四叉树碰撞算法

四叉树碰撞算法是一种常用的空间分割算法，可以有效地优化碰撞检测的性能。下面是使用Lua语言实现四叉树碰撞算法的基本步骤：

1. 定义四叉树节点

首先我们需要定义四叉树节点的数据结构，一个四叉树节点包含四个子节点和一个节点范围（即矩形区域）。可以使用Lua的table来表示节点。

local QuadNode = {
    children = {}, -- 子节点
    bounds = {},   -- 节点范围
    objects = {},  -- 包含的物体
}

2. 构建四叉树

接下来，我们需要构建四叉树。构建四叉树的过程就是不断地将物体插入到四叉树节点中，如果一个节点已经包含了足够数量的物体或者达到了最大深度，则需要将该节点分割成四个子节点。

function QuadNode:insert(obj)
    if #self.objects < MAX_OBJECTS or self.depth >= MAX_DEPTH then
        table.insert(self.objects, obj)
    else
        if not self.children[1] then self:split() end
        for i = 1, #self.children do
            if self.children[i]:contains(obj) then
                self.children[i]:insert(obj)
                break
            end
        end
    end
end

function QuadNode:split()
    local x, y, w, h = self.bounds.x, self.bounds.y, self.bounds.width, self.bounds.height
    local half_w, half_h = w / 2, h / 2
    self.children[1] = QuadNode:new(x, y, half_w, half_h, self.depth + 1)
    self.children[2] = QuadNode:new(x + half_w, y, half_w, half_h, self.depth + 1)
    self.children[3] = QuadNode:new(x, y + half_h, half_w, half_h, self.depth + 1)
    self.children[4] = QuadNode:new(x + half_w, y + half_h, half_w, half_h, self.depth + 1)
    for i = 1, #self.objects do
        local obj = self.objects[i]
        for j = 1, #self.children do
            if self.children[j]:contains(obj) then
                self.children[j]:insert(obj)
                break
            end
        end
    end
    self.objects = {}
end

3. 碰撞检测

最后，我们需要进行碰撞检测。对于一个物体，我们首先找到它所在的叶子节点，然后检测该节点中所有物体是否与该物体相交。如果相交，则进行进一步的检测。

function QuadNode:query(obj, results)
    if not results then results = {} end
    for i = 1, #self.objects do
        local other = self.objects[i]
        if obj ~= other and obj:intersects(other) then
            table.insert(results, other)
        end
    end
    if self.children[1] then
        for i = 1, #self.children do
            if self.children[i]:intersects(obj) then
                self.children[i]:query(obj, results)
            end
        end
    end
    return results
end

完整代码如下：

QuadNode = {
    MAX_OBJECTS = 10,
    MAX_DEPTH = 5,
}

function QuadNode:new(x, y, w, h, depth)
    local node = {
        children = {},
        bounds = {x = x, y = y, width = w, height = h},
        objects = {},
        depth = depth or 0,
    }
    setmetatable(node, {__index = QuadNode})
    return node
end

function QuadNode:insert(obj)
    if #self.objects < QuadNode.MAX_OBJECTS or self.depth >= QuadNode.MAX_DEPTH then
        table.insert(self.objects, obj)
    else
        if not self.children[1] then self:split() end
        for i = 1, #self.children do
            if self.children[i]:contains(obj) then
                self.children[i]:insert(obj)
                break
            end
        end
    end
end

function QuadNode:split()
    local x, y, w, h = self.bounds.x, self.bounds.y, self.bounds.width, self.bounds.height
    local half_w, half_h = w / 2, h / 2
    self.children[1] = QuadNode:new(x, y, half_w, half_h, self.depth + 1)
    self.children[2] = QuadNode:new(x + half_w, y, half_w, half_h, self.depth + 1)
    self.children[3] = QuadNode:new(x, y + half_h, half_w, half_h, self.depth + 1)
    self.children[4] = QuadNode:new(x + half_w, y + half_h, half_w, half_h, self.depth + 1)
    for i = 1, #self.objects do
        local obj = self.objects[i]
        for j = 1, #self.children do
            if self.children[j]:contains(obj) then
                self.children[j]:insert(obj)
                break
            end
        end
    end
    self.objects = {}
end

function QuadNode:contains(obj)
    local x, y, w, h = self.bounds.x, self.bounds.y, self.bounds.width, self.bounds.height
    local ox, oy, ow, oh = obj.x, obj.y, obj.width, obj.height
    return ox >= x and ox + ow <= x + w and oy >= y and oy + oh <= y + h
end

function QuadNode:intersects(obj)
    local x, y, w, h = self.bounds.x, self.bounds.y, self.bounds.width, self.bounds.height
    local ox, oy, ow, oh = obj.x, obj.y, obj.width, obj.height
    return x < ox + ow and x + w > ox and y < oy + oh and y + h > oy
end

function QuadNode:query(obj, results)
    if not results then results = {} end
    for i = 1, #self.objects do
        local other = self.objects[i]
        if obj ~= other and obj:intersects(other) then
            table.insert(results, other)
        end
    end
    if self.children[1] then
        for i = 1, #self.children do
            if self.children[i]:intersects(obj) then
                self.children[i]:query(obj, results)
            end
        end
    end
    return results
end

使用示例：

-- 创建四叉树
local tree = QuadNode:new(0, 0, 640, 480)

-- 插入物体
tree:insert({x=10, y=10, width=20, height=20})
tree:insert({x=30, y=30, width=20, height=20})
tree:insert({x=50, y=50, width=20, height=20})

-- 查询物体相交的物体
local results = tree:query({x=40, y=40, width=20, height=20})
for i = 1, #results do
    print('object', i, results[i].x, results[i].y)
end