9

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

我一次最多可以有 3 个敌人使用这个算法，并且地图是一个基于瓷砖的二维迷宫。我已经实现了碰撞检测，所以现在剩下要做的就是让敌人找到到玩家的最短路径，这种方法可以快速完成，最好是每个敌人每秒大约 80-90 次。

当我之前实现广度优先搜索时，我在 C++ 中使用了一个队列。push()根据我对 Lua 的了解，使用表的堆栈实现非常有效，因为在(AKA table.insert) 和pop()(table.remove) 操作之后不需要移动元素。但是，我认为在 Lua 中大尺寸的队列可能效率很低，因为如果你想从表的索引 1 中插入/删除某些东西，表中的所有其他元素都必须在表中向上或向下移动。

因此，我想问一些有 Lua 经验的人一些简单的问题。这种语言中最简单和/或最快的队列实现是什么？是否有可能在 Lua 中有一个快速队列，或者只是普遍认为 Lua 总是被迫“移动”所有元素以进行队列操作，例如pop()or append()？

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

4

1 回答 1

15

Lua 中队列（实际上是双队列）的快速实现由《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        -- 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
于 2013-09-17T07:41:53.233 回答