Lua中队列的快速实现？

2013-9-17 8:25:16
收藏：0
阅读：101
评论：1

我正在使用Lua制作游戏，需要使用广度优先搜索来实现一种快速的路径搜索算法，以找到敌人AI和玩家之间的最短路径。

我将同时使用多达3个敌人使用此算法，地图是一个二维基于瓷砖的迷宫。我已经实现了碰撞检测，现在所剩的就是让敌人找到通向玩家的最短路径，以一种可以快速完成且每个敌人每秒可以完成80-90次的方式。

以前我实现广度优先搜索时在C++中使用了队列。从我所了解的有关Lua的信息来看，使用表格的栈实现非常高效，因为在push()（也称为table.insert）和pop()（table.remove）操作之后，元素不需要进行移位。但是，我推理大型大小的队列在Lua中可能非常低效，因为如果您想从表的索引1处插入/删除内容，则必须将表中的所有其他元素向上或向下移位。

因此，我想向那些经验丰富的Lua人员提出一些简单的问题。这种语言中最简单和/或最快的队列实现是什么？在Lua中是否可能拥有快速队列，或者通常认为Lua总是被迫对于类似于pop()或append()的队列操作“移动”所有元素？

编辑：我了解，在Lua表格中“移动元素”的底层实现是用C编写的，因此非常优化。我只想知道在开始编写简单的表格实现之前，是否有更好的队列选项。

点赞
用户1009479
用户1009479

Lua书籍Programming in Lua提供了队列（实际上是双端队列）的快速实现：

List = {}
function List.new ()
  return {first = 0, last = -1}
end

该队列可以在常数时间内插入或删除两端的元素，关键是要存储first和last。

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        -- 允许垃圾回收
  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         -- 允许垃圾回收
  list.last = last - 1
  return value
end
2013-09-17 07:41:53

作者:

用户2653390

用户2653390
推荐文章