优化空间网格中对象移动的Diff更新算法

当空间网格中的对象发生移动、缩放甚至瞬移时，暴力移除原区域所有单元格再添加新区域的做法效率极低。我们可以通过计算原区域与新区域的差异部分，仅对需要变更的单元格操作，大幅提升性能。

核心思路 #

1. 计算原区域与新区域的重叠区域：这部分单元格无需变更，直接跳过处理
2. 计算需要移除对象的区域：原区域减去重叠区域（即原区域中不在新区域里的部分）
3. 计算需要添加对象的区域：新区域减去重叠区域（即新区域中不在原区域里的部分）

坐标定义说明 #

• 移动前对象边界：l0（左）、r0（右）、t0（上）、b0（下）
• 移动后对象边界：l1（左）、r1（右）、t1（上）、b1（下）
• 注：假设坐标为网格单元格索引，且满足l <= r、t <= b

算法步骤 #

1. 计算重叠区域边界

local overlap_l = math.max(l0, l1)
local overlap_r = math.min(r0, r1)
local overlap_t = math.max(t0, t1)
local overlap_b = math.min(b0, b1)

如果overlap_l > overlap_r或overlap_t > overlap_b，说明新旧区域无重叠，直接移除整个原区域、添加整个新区域即可。

2. 处理需要移除的单元格（原区域 - 重叠区域）

分四个矩形区域遍历：

• 原区域顶部：从t0到overlap_t - 1，左右范围l0到r0
• 原区域底部：从overlap_b + 1到b0，左右范围l0到r0
• 原区域左侧：从overlap_t到overlap_b，左右范围l0到overlap_l - 1
• 原区域右侧：从overlap_t到overlap_b，左右范围overlap_r + 1到r0

对每个区域内的单元格，执行移除对象操作。

3. 处理需要添加的单元格（新区域 - 重叠区域）

同样分四个矩形区域遍历：

• 新区域顶部：从t1到overlap_t - 1，左右范围l1到r1
• 新区域底部：从overlap_b + 1到b1，左右范围l1到r1
• 新区域左侧：从overlap_t到overlap_b，左右范围l1到overlap_l - 1
• 新区域右侧：从overlap_t到overlap_b，左右范围overlap_r + 1到r1

对每个区域内的单元格，执行添加对象操作。

Lua 实现代码 #

-- 假设网格结构为 grid[y][x]，存储对应单元格的对象集合
-- 从单元格(x,y)中移除目标对象
local function remove_from_cell(grid, x, y, obj)
    local cell = grid[y] and grid[y][x]
    if cell then
        -- 根据实际存储结构调整，这里假设用数组存储对象
        for i, v in ipairs(cell) do
            if v == obj then
                table.remove(cell, i)
                break
            end
        end
    end
end

-- 向单元格(x,y)中添加目标对象
local function add_to_cell(grid, x, y, obj)
    if not grid[y] then grid[y] = {} end
    if not grid[y][x] then grid[y][x] = {} end
    table.insert(grid[y][x], obj)
end

-- 核心更新函数：处理对象移动/缩放后的网格更新
local function update_object_in_grid(grid, obj, l0, r0, t0, b0, l1, r1, t1, b1)
    -- 计算重叠区域边界
    local ol = math.max(l0, l1)
    local or_ = math.min(r0, r1)
    local ot = math.max(t0, t1)
    local ob = math.min(b0, b1)

    -- 处理需要移除的区域
    -- 1. 原区域顶部
    for y = t0, ot - 1 do
        for x = l0, r0 do
            remove_from_cell(grid, x, y, obj)
        end
    end
    -- 2. 原区域底部
    for y = ob + 1, b0 do
        for x = l0, r0 do
            remove_from_cell(grid, x, y, obj)
        end
    end
    -- 3. 原区域左侧（仅当重叠区域存在时处理）
    if ot <= ob then
        for y = ot, ob do
            for x = l0, ol - 1 do
                remove_from_cell(grid, x, y, obj)
            end
        end
    end
    -- 4. 原区域右侧（仅当重叠区域存在时处理）
    if ot <= ob then
        for y = ot, ob do
            for x = or_ + 1, r0 do
                remove_from_cell(grid, x, y, obj)
            end
        end
    end

    -- 处理需要添加的区域
    -- 1. 新区域顶部
    for y = t1, ot - 1 do
        for x = l1, r1 do
            add_to_cell(grid, x, y, obj)
        end
    end
    -- 2. 新区域底部
    for y = ob + 1, b1 do
        for x = l1, r1 do
            add_to_cell(grid, x, y, obj)
        end
    end
    -- 3. 新区域左侧（仅当重叠区域存在时处理）
    if ot <= ob then
        for y = ot, ob do
            for x = l1, ol - 1 do
                add_to_cell(grid, x, y, obj)
            end
        end
    end
    -- 4. 新区域右侧（仅当重叠区域存在时处理）
    if ot <= ob then
        for y = ot, ob do
            for x = or_ + 1, r1 do
                add_to_cell(grid, x, y, obj)
            end
        end
    end
end

注意事项 #

• 可根据实际网格存储结构（比如哈希表、稀疏数组）调整remove_from_cell和add_to_cell函数
• 若对象边界是连续坐标（非离散单元格索引），需先转换为对应的单元格范围再执行算法
• 瞬移场景下（无重叠区域），代码会自动处理为移除整个原区域、添加整个新区域，无需额外判断

内容的提问来源于stack exchange，提问作者kikito