Поработав некоторое время над своим кодом, оптимизировав самые очевидные вещи, я получил следующее:
function FindPath(start, finish, path)
--Define a table to hold the paths
local paths = {}
--Make a default argument
path = path or {start}
--Loop through connected nodes
for i,v in ipairs(start:GetConnectedParts()) do
--Determine if backtracking
local loop = false
for i,vv in ipairs(path) do
if v == vv then
loop = true
end
end
if not loop then
--Make a path clone
local npath = {unpack(path)}
npath[#npath+1] = v
if v == finish then
--If we reach the end add the path
return npath
else
--Otherwise add the shortest part extending from this node
paths[#paths+1] = FindPath(v, finish, npath) --NOTED HERE
end
end
end
--Find and return the shortest path
if #paths > 0 then
local lengths = {}
for i,v in ipairs(paths) do
lengths[#lengths+1] = #v
end
local least = math.min(unpack(lengths))
for i,v in ipairs(paths) do
if #v == least then
return v
end
end
end
end
Проблема в том, что указанная строка получает какую-то ошибку тайм-аута игрового сценария (что, как я полагаю, происходит из-за массовой рекурсии без выхода). Я также чувствую, что как только эта проблема будет решена, она, вероятно, будет довольно медленной даже в масштабе доски pacman. Есть ли способ, которым я могу его оптимизировать, или, возможно, лучший метод, который я могу изучить, подобный этому?
ОБНОВЛЕНИЕ: я, наконец, решил отказаться от своего алгоритма из-за его неэффективности и реализовал алгоритм Дейкстры для поиска пути. Для всех, кто интересуется исходным кодом, его можно найти здесь: http://pastebin.com/Xivf9mwv
