Lua中如何快速实现队列？

Question

Lua中如何快速实现队列？

luaqueuepath-findingbreadth-first-searchlua-table

9

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

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

以前我使用C ++中的队列实现了广度优先搜索。从我所读到的关于Lua的内容来看，使用表格实现的堆栈非常高效，因为元素在进行push（）（即table.insert）和pop（）（即table.remove）操作后不需要进行移位。然而，我推测，具有大容量的队列在Lua中可能非常低效，因为如果您想从表格的索引1插入/删除某些内容，则必须将表格中的所有其他元素向上或向下移动。

因此，我想问一些对Lua有经验的人一些简单的问题。这种语言中最简单和/或最快的队列实现是什么？在Lua中是否可能拥有快速的队列，还是通常认为Lua将始终被迫对队列操作（如pop（）或append（））进行“移位”？

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

- Shashank

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yu Hao · Accepted Answer

在Lua中，快速实现队列（实际上是双向队列）的方法可以参考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        -- 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