I am making a game using Lua and I need to use Breadth-first search to implement a fast path-finding algorithm which finds the shortest path between the enemy AI and the player.
I will have up to 3 enemies using this algorithm at once and map is a 2-dimensional tile-based maze. I have already implemented collision detection so now all that is left to do is get a way for the enemies to find the shortest path to the player in a way that can be done quickly and and preferably about 80-90 times per second per enemy.
When I previously implemented breadth-first search, I used a queue in C++. From what I have read about Lua, stack implementations using tables are very efficient since the elements don't need to be shifted after push()
(AKA table.insert) and pop()
(table.remove) operations. However, I have theorized that queues with large sizes can be very inefficient in Lua, because if you want to insert/remove something from index 1 of a table, all other elements in the table must be shifted either upward or downward in the table.
Thus, I would like to ask some simple questions for those experienced in Lua. What is the simplest and/or fastest implementation of a queue in this language? Is it even possible to have a fast queue in Lua or is it just generally accepted that Lua will always be forced to "shift" all elements for a queue operation such as pop()
or append()
?
EDIT: I understand that the underlying implementation of "shifting elements" in Lua tables is written in C and is therefore quite optimized. I just would like to know if I have any better options for queues before I begin to write a simple table implementation.
A fast implementation of queue(actually double queue) in Lua is done by the book Programming in Lua:
List = {}
function List.new ()
return {first = 0, last = -1}
end
It can insert or remove an element at both ends in constant time, the key is to store both first
and 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