如何使用Lua在2D游戏中快速排序精灵?

我在开发一个2D游戏,使用lua脚本编写所有游戏逻辑。现在遇到一个问题是排序太慢了。有人可以帮我改善一下吗?

这是关于zobject列表的代码:

local c = class("ZList") -- class是用来生成一个“Class”的函数

function c:insert(v) -- 每个v(值或对象)都有一个z字段
    if v.z == nil then v.z = -1 end
    if self.head == nil then
        self.head = {val=v, nxt=nil}
    else
        local p = self.head
        local pp = p --pp是指向前一节点的指针
        while v.z and p and p.val.z and p.val.z <= v.z do
            pp = p
            p = p.nxt
        end
        if p == self.head then
            self.head = {val=v, nxt=p}
        else
            pp.nxt = {val=v, nxt=p}
        end
    end
end

function c:delete(v)
    local p = self.head
    local pp
    while p and p.val ~= v do
        pp = p
        p = p.nxt
    end

    if p ~= nil then
        if p == self.head then
            self.head = p.nxt
        else
            pp.nxt = p.nxt
        end
    end
end

___ 更新 ___

感谢Nicol和所有回复我的人!我按照你们的建议做了以下修改:使用table.insert和table.sort,并使用一个静态列表,不需要排序。以下是我的最终代码:

    local remove_list
    sort(Graphics.viewports, comp)
    for _, viewport in pairs(Graphics.viewports) do
        if viewport.visible then
            remove_list = {}
            if not viewport.static then sort(viewport.sprites, comp) end
            for k, sprite in pairs(viewport.sprites) do
                if not sprite:paint() then
                    table.insert(remove_list,1, k)
                end
            end
            for _, k in pairs(remove_list) do
                table.remove(viewport.sprites, k)
            end
        end
    end
点赞
用户734069
用户734069

停止将您的精灵放入链接列表中。将它们放入常规列表中。插入时间不会像链接列表的内存分配一样伤害您。只需使用常规 Lua 列表,使用 table.insert 等函数即可。

或者,您真的 需要 对所有精灵进行排序吗?最可能的情况(当然是取决于具体情况),您只需要按图层绘制它们:首先是所有的 0 层(以任意顺序),然后是所有的 1 层,依此类推。

2012-06-20 01:57:34
用户513763
用户513763

为什么不使用内置的 table.sort 呢?使用它有两个选项:

  1. 在调用时指定排序函数:table.sort(table,comp),其中 comp(a,b) 是一个返回 true 如果 a 小于 b 的函数。

  2. 为你的 sprite 类实现一个 __lt metamethod,实现 < 操作。

table.sort 显然使用快速排序算法的变体(根据 lua-users wiki 上的 LuaSorting)。

2012-06-20 05:55:56