我正在使用Lua进行游戏,我需要使用广度优先搜索来实现快速路径搜索算法,该算法找到敌人AI和玩家之间的最短路径.
我将同时使用此算法最多3个敌人,并且地图是基于2维拼图的迷宫.我已经实现了碰撞检测,所以现在剩下要做的就是让敌人找到一条通往玩家最短路径的方法,这种方式可以快速完成,最好每个敌人每秒约80-90次.
当我之前实现广度优先搜索时,我在C中使用了一个队列.从我读到的关于Lua的内容来看,使用表的堆栈实现非常有效,因为在push()(AKA table.insert)和pop()(table.remove)操作之后不需要移动元素.但是,我认为在Lua中大型队列的效率非常低,因为如果要在表的索引1中插入/删除某些内容,则表中的所有其他元素必须向上或向下移动.
因此,我想问一些Lua经验丰富的简单问题.在这种语言中,最简单和/或最快的队列实现是什么？是否有可能在Lua中拥有一个快速队列,或者只是普遍接受Lua总是被迫“移动”所有元素以进行队列操作,例如pop()或append()？
编辑：我理解Lua表中“移位元素”的底层实现是用C语言编写的,因此非常优化.在开始编写简单的表实现之前,我只想知道是否有更好的队列选项.
解决方法
Lua中的队列(实际上是双队列)的快速实现由书
Programming in Lua完成：
List = {}
function List.new ()
return {first = 0,last = -1}
end
它可以在恒定时间内插入或移除两端的元素,关键是存储第一个和最后一个.
function List.pushleft (list,value)
local first = list.first - 1
list.first = first
list[first] = value
end
function List.pushright (list,value)
local last = list.last + 1
list.last = last
list[last] = value
end
function List.popleft (list)
local first = list.first
if first > list.last then error("list is empty") end
local value = list[first]
list[first] = nil -- to allow garbage collection
list.first = first + 1
return value
end
function List.popright (list)
local last = list.last
if list.first > last then error("list is empty") end
local value = list[last]
list[last] = nil -- to allow garbage collection
list.last = last - 1
return value
end