Lua код первопрохождения нуждается в оптимизации

Question

После работы на моем коде на некоторое время, оптимизируя наиболее очевидные вещи, я привел в этом:

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. Есть ли способ, которым я могу его оптимизировать, или, возможно, лучший метод, с которым я могу смотреть в подобном?

ОБНОВЛЕНИЕ: Я, наконец, решил уничтожить мой алгоритм из-за неэффективности и реализовал алгоритм Dijkstra для поиска пути. Для любого, кто интересуется исходным кодом, можно найти здесь: http://pastebin.com/Xivf9mwv

Answer 1

Вы знаете, что Roblox предоставляет вам PathfindingService? Он использует C-side A * pathing для вычисления довольно быстро. Я бы рекомендовал использовать его

http://wiki.roblox.com/index.php?title=API:Class/PathfindingService

Answer 2

Попробуйте перестроить свой алгоритм, чтобы использовать хвостовые вызовы. Это отличный механизм, доступный в Lua.

Хвост вызова - это тип рекурсии, в которой ваша функция возвращает вызов функции как последнее, что он делает. У Lua есть правильная реализация хвостовых вызовов, и она будет одевать эту рекурсию как «перейти» под сцену, так что ваш стек никогда не ударит.

Передача «путей», как один из аргументов FindPath, может помочь в этом.

Answer 3

Я видел вашу правку о вынужденном код, но только, чтобы помочь другим, спотыкаясь на этот вопрос:

• ipairs медленнее, чем пар, что медленнее, чем Численном -loop. Если производительность имеет значение, никогда не используйте ipairs, но используйте для i = 1, # tab loop
• Если вы хотите клонировать таблицу, используйте цикл for. Иногда у вас есть, чтобы использовать распаковку (возврат динамического количества задних нолей), но это не такой случай. Unpack также является медленной функцией.

Замена ipairs с парами или числовыми для петель и с помощью петли вместо распаковывать увеличит производительность много.

Если вы хотите, чтобы получить наименьшее значение в таблице, используйте этот код:

local lowestValue = values[1] 
for k,v in pairs(values) do 
    if v < lowestValue then 
     lowestValue = k,v 
    end 
end 

Это может быть переписан для вашего примера путь, как так:

local least = #path[1] 
for k,v in pairs(path) do 
    if #v < least then 
     least = v 
    end 
end 

Я должен признать, , вы очень изобретательны. Не многие люди будут использовать математику.min (unpack (tab)) (не считая того, что это плохо)