-- Copyright (C) 2010 Tyson Brown
-- 
-- This file is part QuestHelper2, an AddOn for World of Warcraft.
-- 
-- QuestHelper2 is free software: you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation, either version 3 of the License, or
-- (at your option) any later version.
-- 
-- QuestHelper2 is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
-- 
-- You should have received a copy of the GNU General Public License
-- along with QuestHelper2. If not, see <http://www.gnu.org/licenses/>.

if LibDebug then LibDebug() end
local shared = select(2, ...)

-- This file is in charge of maintaining a list of objectives, in the order they should be completed in.
-- It is the route the player should follow.

-- Some functions I like to keep close to my heart.
local insert, wipe, unpack, next, pairs, ipairs, random, floor = table.insert, table.wipe, unpack, next, pairs, ipairs, math.random, math.floor

-- This is the route, as it should appear on the map.
local route = {}
shared.route = route

-- This is the list that route is derived from; it includes several of the most recently disabled objectives,
-- so that their positions in the route can be restored should they get re-enabled.
local sorted_route = {}

-- The disabled objectives that we're continuing to keep in sorted_route are kept in here.
local recently_disabled_objectives_set = {}

-- They also appear in this list, sorted by how recently they were used. When the list grows too large, we'll
-- remove the older objectives.
local recently_disabled_objectives_list = {}

-- This is set to true an objective is added, removed, or modified, and is to inform the
-- routing thread that it needs to recheck its assumptions regarding the route.
local route_objectives_changed = false

-- If set to true, routing may violate priority order in exchange for
-- shorter paths.
local relaxed_priorities = false

-- This is set to true when a pathing object changes, as is a flag to the
-- routing thread that it needs to clean its cache of node distances.
local pathing_changed = false

-- Set to true by forceFullUpdate().
local full_update = false

-- A list of callbacks to invoke when the primary objective is changed.
local on_primary_objective_changed = {}

-- Just what is the primary objective, anyway?
local primary_objective = nil

-- Yields if more than 2ms have elapsed since its last call.
local start_time, real_yield = GetTime(), coroutine.yield
local function conditionalYield()
  if GetTime()-start_time > 0.0015 then
    real_yield(0)
    start_time = GetTime()
  end
end

local function simpleYield()
  real_yield(0)
end

-- A dummy function for not yielding. In fact, it does yield, but not very often.
local no_yield_count = 0
local function noYield()
  if no_yield_count == 20 then
    no_yield_count = 0
    real_yield(0)
  else
    no_yield_count = no_yield_count + 1
  end
end

-- Set to either conditionalYield or noYield depending on whether full_update has been set to true.
local yield = simpleYield

local function forceFullUpdate()
  full_update = true
  yield = noYield
end

function shared.onPrimaryObjectiveChanged(cb, ...)
  cb = shared.callback(cb, ...)
  table.insert(on_primary_objective_changed, cb)
  cb(primary_objective)
end

--[===[@debug@
shared.onPrimaryObjectiveChanged(function (obj)
  print("Primary objective is now: "..(obj and obj.text or "unset"))
end)
--@end-debug@]===]

-- A list of callbacks to invoke when the route gets changed.
local on_route_changed = {}

-- Give anyone that wants to know when the route changes a way of knowing.
function shared.onRouteChanged(cb)
  table.insert(on_route_changed, cb)
  cb(route)
end

local objective_priority = {}
local function objectiveCmp(a, b) return objective_priority[a] < objective_priority[b] end

-- This returns objective if it is obtainable, or the first obtainable objective in sorted_route that is
-- a dependency of objective.
local function firstUsableDependency(objective)
  if objective.enabled and objective.obtainable and objective.has_locations then
    return objective
  end
  
  local list = {}
  
  for dep in objective:fwdDependencies() do
    insert(list, dep)
  end
  
  sort(list, objectiveCmp)
  
  for i, dep in ipairs(list) do
    local result = firstUsableDependency(dep)
    if result then return result end
  end
end

local function updatePrimaryObjective()
  local chosen_objective
  
  for i, obj in ipairs(sorted_route) do
    objective_priority[obj] = i
  end
  
  for i, obj in ipairs(sorted_route) do
    if obj.enabled then
      chosen_objective = firstUsableDependency(obj)
      if chosen_objective then
        break
      end
    end
  end
  
  table.wipe(objective_priority)
  
  if chosen_objective ~= primary_objective then
    -- The chosen objective differs from what it was previously.
    primary_objective = chosen_objective
    
    shared.invokeCallbackList(on_primary_objective_changed, primary_objective)
  end
end

-- This regenerates route from shared_route, and invokes all the callbacks in on_route_changed if the
-- new route differs.
local function cleanRoute()
  -- TODO: Verify objective order satisfies objective dependencies.
  
  -- This first pass is just to make sure that the new route would differ from what it currently is.
  local j=0
  local mismatch = false
  
  for i, obj in ipairs(sorted_route) do
    if obj.enabled then
      j = j + 1
      if route[j] ~= obj then
        mismatch = true
        break
      end
    end
  end
  
  if j == #route and not mismatch then
    -- The publicly exposed route wouldn't change; so return without doing anything further.
    return
  end
  
  table.wipe(route)
  j=0
  
  for i, obj in ipairs(sorted_route) do
    if obj.enabled then
      j = j + 1
      route[j] = obj
    end
  end
  
  shared.invokeCallbackList(on_route_changed, route)
  
  updatePrimaryObjective()
end

--[===[@debug@
-- Make sure that the objectives in the route only appear once.
local function sanityCheck(msg, route)
  local seen = {}
  for i, obj in ipairs(route) do
    if seen[obj] then error(msg..": "..obj.text.." is at index "..seen[obj].." and "..i) end
    seen[obj] = i
  end
end
--@end-debug@]===]

local sorted_route_objectives = {}
local proposed_route_objectives = {}

local function proposeNewRoute(proposed_route)
  --[===[@debug@
  sanityCheck("OriginalCheck", sorted_route)
  sanityCheck("ProposedCheck", proposed_route)
  --@end-debug@]===]
  
  for i, objective in ipairs(sorted_route) do
    sorted_route_objectives[objective] = true
  end
  
  local i, objective = 1, proposed_route[1]
  while objective do
    if not sorted_route_objectives[objective] then
      -- This objective has been removed between when the routing code started calculating a route and now.
      table.remove(proposed_route, i)
    else
      proposed_route_objectives[objective] = true
      i = i + 1
    end
    
    objective = proposed_route[i]
  end
  
  -- We can't simply replace sorted_route with proposed_route, we need to make sure that sorted_route continues to contain all the objectives it
  -- previously did, just in the order suggested by proposed_route.
  -- We do this by searching for sequences of objectives in sorted_route that don't appear in proposed_route, and inserting that into
  -- into proposed_route just before the objective that appears after that sequence, or at the end of proposed_route if the sequence has no
  -- objectives following it.
  i, objective = 1, sorted_route[1]
  while objective do
    if not proposed_route_objectives[objective] then
      -- We found an objective in sorted_route that isn't in proposed_route.
      local j, end_objective = i+1, sorted_route[i+1]
      
      -- Search forward until we found a variable that is in proposed_route.
      while end_objective do
        if proposed_route_objectives[end_objective] then
          -- Found it.
          break
        end
        
        -- Try the next objective.
        j, end_objective = j+1, sorted_route[j+1]
      end
      
      -- At this point, [i,j) is the sequence of objectives that are missing from proposed_route.
      -- We'll search for element j in sorted_route in proposed_route, and insert the elements into proposed_route before that point.
      
      if end_objective then
        -- Insert [i,j) before end_objective in proposed_route.
        for insert_point,obj in pairs(proposed_route) do
          if obj == end_objective then
            -- Found the insertion point, do the inserting.
            for k=i,j-1 do insert(proposed_route, insert_point+(k-i), sorted_route[k]) end
            break
          end
        end
      else
        -- Insert [i,j) at the end of proposed_route.
        for k=i,j-1 do insert(proposed_route, sorted_route[k]) end
      end
      
      -- Continue our search from this point.
      i = j
    end
    
    -- ... and on to the next objective.
    i, objective = i + 1, sorted_route[i+1]
  end
  
  --[===[@debug@
  sanityCheck("MergeCheck", proposed_route)
  --@end-debug@]===]
  
  -- proposed_route has now been merged with sorted_route,
  -- wipe the sorted_route table and copy everything from proposed_route into it.
  wipe(sorted_route)
  wipe(sorted_route_objectives)
  wipe(proposed_route_objectives)
  
  for i, objective in ipairs(proposed_route) do
    sorted_route[i] = objective
  end
  
  shared.callOnce(cleanRoute)
end

shared.onObjectiveEnabled(function (objective)
  route_objectives_changed = true
  forceFullUpdate()
  
  if recently_disabled_objectives_set[objective] then
    -- We've haven't actually removed the objective in question, yet.
    
    recently_disabled_objectives_set[objective] = nil
    
    for i, obj in ipairs(recently_disabled_objectives_list) do
      if obj == objective then
        table.remove(recently_disabled_objectives_list, i)
        break
      end
    end
  else
    -- TODO: Pick a good starting index for the objective.
    table.insert(sorted_route, 1, objective)
  end
  
  if objective == primary_objective then
    -- The objective was disabled and re-enabled before cleanRoute was invoked,
    -- so re-announce it again as if it were modified.
    shared.invokeCallbackList(on_primary_objective_changed, primary_objective)
  end
  
  shared.callOnce(cleanRoute)
  
  forceFullUpdate()
end)

shared.onObjectiveModified(function (objective, affects_routing)
  if affects_routing then
    route_objectives_changed = true
  end
  
  if objective == primary_objective then
    -- The primary objective has changed in some way;
    -- re-announce it.
    shared.invokeCallbackList(on_primary_objective_changed, primary_objective)
  else
    -- Double check the primary objective in a moment, the change to it may
    -- affect which one should be chosen.
    -- cleanRoute() may also invoke updatePrimaryObjective, but only if the order
    -- of the objectives has changed; not if the individual objectives were modified.
    shared.callOnce(updatePrimaryObjective)
  end
  
  -- Force the route to be rechecked, in case some dependencies were changed.
  shared.callOnce(cleanRoute)
  
  forceFullUpdate()
end)

shared.onObjectiveDisabled(function (objective)
  route_objectives_changed = true
  -- Add the disabled objective to the list of disabled objectives.
  recently_disabled_objectives_set[objective] = true
  table.insert(recently_disabled_objectives_list, 1, objective)
  
  -- If the list of disabled objectives is starting to look a little big,
  -- start removing the oldest objectives.
  while #recently_disabled_objectives_list > 25 do
    local removed_objective = table.remove(recently_disabled_objectives_list)
    recently_disabled_objectives_set[removed_objective] = nil
    
    for i, obj in ipairs(sorted_route) do
      if obj == removed_objective then
        table.remove(sorted_route, i)
        break
      end
    end
  end
  
  shared.callOnce(cleanRoute)
  
  forceFullUpdate()
end)

local function pathingChanged()
  pathing_changed = true
end

shared.onMapLinkDisabled(pathingChanged)
shared.onMapLinkEnabled(pathingChanged)
shared.onMapPatherModified(pathingChanged)

-- An empty table, generally used so I can iterate through a table that may not exist.
local empty = {}

-- A function that always returns 1; thus function is used to multipy node scores when
-- using exploitation, and alternatively, math.random is used when exploration is to be used instead.
local function one()
  return 1
end

local function routingThreadEntry()
  local calcDistance = shared.calculateTravelTime
  
  -- !!! Some constants for tuning how this thing works.
  
  -- How many ants are simulated.
  local max_ants = 20
  
  -- An ant walking over a trail decays the pheromone on that trail by this factor.
  local pheromone_decay = 0.999
  
  -- This decay is applied to all edges after all ants are done their traveling, to simulate
  -- evaporation of the pheromone trails.
  local pheromone_offline_decay = 0.99
  
  -- If the pathfinding system fails to find a path between two nodes,
  -- use this value in the calculations instead.
  local huge_distance = 3600
  
  -- The probability of using exploitation.
  local greed_prob = 0.7
  
  --!!! These variables are shared between multiple passes, and are only
  --!!! to be modified when the objectives the route is to be generated from are modified.
  
  -- Note: Node 0 represents the player.
  local node_count = 0
  
  -- Maps an old node to a new node; used to salvage values
  -- from node_{distance,pheromone}_cache when regenerating everything.
  local old_node_to_node = {}
  
  -- Node location values are encoded as the half open range [node_id*6, node_id*6+6)
  local node_location, old_node_location = {}, {}
  
  -- Maps a node to a set of nodes, all nodes in the group should be enabled or disabled
  -- at the same time.
  local node_group = {}
  
  -- A special group for representing the player.
  local player_group = {0}
  
  -- Maps a group to an objective, and back again.
  local group_to_objective = {}
  local objective_to_group, objective_to_old_group = {}, {}
  
  -- The number of dependencies each group has. (nil = 0)
  local group_dep_count = {}
  
  -- A set of groups that depend on a group, nil if no groups depend on the group.
  -- When a node is completed:
  --  * Every node in that node's group is disabled.
  --  * For each group that depends on the completed nodes group, we decreased the 'group_incomplete_dep_count' for that group.
  --  * If the count is decreased to 0, every node in that group is enabled.
  local group_rdeps = {}
  
  -- The priority of a node group (Only used if relaxed_priorities is enabled)
  local group_priority = {}
  
  -- A set of nodes that are enabled by default.
  local default_enabled_nodes = {}
  
  --!!! While these variables do get modified, during each pass, they are shared between multiple passes.
  
  -- Cached distances are encoded as node1+node2*node_count. If the result is nil, the distance is caluclated and
  -- stored in this table for future reference.
  local node_distance_cache, old_node_distance_cache = {}, {}
  
  -- Same format as node_distance_cache; missing values are assumed to be 1.
  -- Routing is performed using ant colony optimization, so the 'pheromone' here represents some
  -- measure of how enticing a path is to a simulated ant.
  local node_pheromone_cache, old_node_pheromone_cache = {}, {}
  
  -- Instead of simulating all the ants in parallel, I simulate them in serial, and the best path
  -- found so far is placed in these variables.
  local best_path, best_path_len = {}, nil
  
  -- The path of the currently simulated ant, if it ends up being better than best_path, it is swapped with best_path.
  local current_path, current_path_len = {}, nil
  
  -- This is the length if the best route we've ever found, minus the distance from the player to the first node.
  local used_route_len = nil
  
  -- This is the first node in the used route with a location; we calculate the distances from the player to this
  -- node and add it to used_route_len to determine the total length of the used route to determine when we find something better.
  local used_route_first_node = nil
  
  --!!! These variables are specific to the generation of the path being traveled by the current ant.
  
  local group_incomplete_dep_count = {}
  local enabled_nodes = {}
  
  -- This function is used for calculating the distance between nodes.
  local function dist_normal(src_node, dest_node)
    local edge = src_node+dest_node*node_count
    local distance = node_distance_cache[edge]
    
    if not distance then
      local area, level, x, y, ex, ey = unpack(node_location, src_node*6, src_node*6+5)
      local dst_area, dst_level, dst_x, dst_y, dst_ex, dst_ey = unpack(node_location, dest_node*6, dest_node*6+5)
      
      assert(area) -- The first node must have a location.
      
      if dst_area then -- The second node however doesn't.
        distance = calcDistance(area, level, x, y, ex, ey, dst_area, dst_level, dst_x, dst_y, dst_ex, dst_ey) or huge_distance
        yield()
      else
        -- Destination has no position.
        distance = 0
      end
      
      node_distance_cache[edge] = distance
    end
    
    return distance, edge
  end
  
  -- This function scales distances by the difference in priority between the
  -- groups of the two nodes.
  local function dist_priority(src_node, dest_node)
    local g1, g2 = node_group[src_node], node_group[dest_node]
    
    return 2^(group_priority[node_group[dest_node]] - group_priority[node_group[src_node]]) * dist_normal(src_node, dest_node)
  end
  
  -- This is set to either dist_normal or dist_priority, depending on whether relaxed_priorities is enabled.
  local dist
  
  -- And now, for the main loop.
  while true do
    if full_update then
      assert(yield == noYield)
      full_update = false
    else
      yield = simpleYield
    end
    
    if route_objectives_changed then
      route_objectives_changed = false
      
      dist = relaxed_priorities and dist_priority or dist_normal
      
      -- If the objectives change, then it's not fair to compare with the length of the currently used route,
      -- as they aren't composed of the same elements.
      used_route_len, used_route_first_node = nil, nil
      
      local old_node_count = node_count
      
      -- node 0 represents the player's position, so we really have 1 node right off the bat.
      node_count = 1
      
      table.wipe(node_group)
      table.wipe(group_priority)
      
      node_group[0] = player_group
      group_priority[player_group] = 0
      
      
      node_location, old_node_location = old_node_location, node_location
      objective_to_group, objective_to_old_group = objective_to_old_group, objective_to_group
      
      wipe(group_to_objective)
      
      --[===[@debug@
      sanityCheck("SeedCheck", sorted_route)
      --@end-debug@]===]
      
      local priority_to_group_set = {}
      
      assert(not next(node_location))
      assert(not next(objective_to_group))
      
      -- Create node groups to represent each objective, and create
      -- nodes to represent the locations where that objective can be completed.
      for i, objective in ipairs(sorted_route) do
        if objective.enabled then
          local group, old_group = {}, objective_to_old_group[objective]
          
          group_priority[group] = objective.priority
          
          local priority_group_set = priority_to_group_set[objective.priority]
          
          if not priority_group_set then
            priority_group_set = {}
            priority_to_group_set[objective.priority] = priority_group_set
          end
          
          priority_group_set[group] = true
          
          group_to_objective[group] = objective
          objective_to_group[objective] = group
          
          for area, level, x, y, ex, ey in objective:iterate() do
            node_group[node_count] = group
            group[node_count] = true
            
            if old_group then
              for old_node in pairs(old_group) do
                local offset = old_node*6
                if area  == old_node_location[offset  ] and
                   level == old_node_location[offset+1] and
                   x     == old_node_location[offset+2] and
                   y     == old_node_location[offset+3] and
                   ex    == old_node_location[offset+4] and
                   ey    == old_node_location[offset+5] then
                  old_node_to_node[old_node] = node_count
                end
              end
            end
            
            local offset = node_count*6
            
            node_location[offset], node_location[offset+1], node_location[offset+2],
            node_location[offset+3], node_location[offset+4], node_location[offset+5] =
              area, level, x, y, ex, ey
            
            node_count = node_count+1
          end
          
          if not next(group) then
            -- The objective has no locations, create a node that doesn't have a position.
            -- The routing code assumes that such a node can be completed anywhere.
            node_group[node_count] = group
            group[node_count] = true
            
            -- Don't bother to fill old_node_location; this nodes entry should already be nil.
            assert(node_location[node_count*6] == nil)
            
            node_count = node_count + 1
          end
        end
      end
      
      wipe(old_node_location)
      wipe(objective_to_old_group)
      wipe(group_dep_count)
      wipe(group_rdeps)
      
      -- Figure out each node group relates to one another.
      for group, objective in pairs(group_to_objective) do
        local rdep_set = {}
        
        for dep in objective:revDependencies() do
          local dep_group = assert(objective_to_group[dep])
          
          if not rdep_set[dep_group] then
            assert(group ~= dep_group)
            rdep_set[dep_group] = true
            group_dep_count[dep_group] = (group_dep_count[dep_group] or 0) + 1
          end
        end
        
        if not relaxed_priorities then
          -- If priorities aren't relaxed, treat high priority node groups
          -- as dependencies of low priority node groups.
          
          for priority, priority_group_set in pairs(priority_to_group_set) do
            if objective.priority < priority then
              -- This group has a higher priority than all the other groups in the set,
              -- make the groups in the set depend on this one so that this one will be
              -- completed first.
              
              for dep_group in pairs(priority_group_set) do
                assert(group ~= dep_group)
                
                if not rdep_set[dep_group] then
                  rdep_set[dep_group] = true
                  group_dep_count[dep_group] = (group_dep_count[dep_group] or 0) + 1
                end
              end
            end
          end
        end
        
        if next(rdep_set) then
          group_rdeps[group] = rdep_set
        end
      end
      
      wipe(default_enabled_nodes)
      
      -- Discover any groups that don't have any dependencies, and add their nodes
      -- to the default_enabled_nodes set.
      for group in pairs(group_to_objective) do
        if not group_dep_count[group] then
          for node in pairs(group) do
            default_enabled_nodes[node] = true
          end
        end
      end
      
      node_distance_cache, old_node_distance_cache = old_node_distance_cache, node_distance_cache
      node_pheromone_cache, old_node_pheromone_cache = old_node_pheromone_cache, node_pheromone_cache
      
      if pathing_changed then
        -- The cached distances may have changed; don't salvage them.
        pathing_changed = false
      else
        -- Attempt to salvage distances from node_distance_cache
        for old_edge, distance in pairs(old_node_distance_cache) do
          local new_node_1, new_node_2 = old_node_to_node[old_edge%old_node_count], old_node_to_node[floor(old_edge / old_node_count)]
          if new_node_1 and new_node_2 then
            local new_edge = new_node_1 + new_node_2 * node_count
            node_distance_cache[new_edge] = distance
          end
        end
      end
      
      -- Attempt to salvage pheromone from node_pheromone_cache
      for old_edge, pheromone in pairs(old_node_pheromone_cache) do
        local new_node_1, new_node_2 = old_node_to_node[old_edge%old_node_count], old_node_to_node[floor(old_edge / old_node_count)]
        if new_node_1 and new_node_2 then
          local new_edge = new_node_1 + new_node_2 * node_count
          node_pheromone_cache[new_edge] = pheromone
        end
      end
      
      wipe(old_node_distance_cache)
      wipe(old_node_pheromone_cache)
      wipe(old_node_to_node)
      
      -- Recalculating all that was a good amount of work, so let us yield for a moment.
      yield()
    end
    
    local area, level, x, y, ex, ey = shared.whereAmI()
    
    -- The routing code only works correctly if we know the player's position...
    -- and of course has objectives to find a route between.
    if area and node_count > 1 then
      if pathing_changed then
        pathing_changed = false
        wipe(node_distance_cache)
        
        node_location[0], node_location[1], node_location[2], node_location[3], node_location[4], node_location[5] =
          area, level, x, y, ex, ey
      else
        if area  ~= node_location[0] or
           level ~= node_location[1] or
           x     ~= node_location[2] or
           y     ~= node_location[3] or
           ex    ~= node_location[4] or
           ey    ~= node_location[5] then
          -- The player's position has changed.
          
          node_location[0], node_location[1], node_location[2], node_location[3], node_location[4], node_location[5] =
            area, level, x, y, ex, ey
          
          -- Remove all edges involving node 0 (the player's position) from the distance cache.
          -- Assumptions: node 0 doesn't have an edge to itself; no edges link to node 0.
          for i = node_count,(node_count-1)*node_count,node_count do
            node_distance_cache[i] = nil
          end
        end
      end
      
      -- Starting over, no best path this session.
      best_path_len = nil
      
      -- Simulating some number of ants running through this mess of edges.
      for i = 1,max_ants do
        wipe(current_path)
        current_path_len = 0
        
        wipe(enabled_nodes)
        wipe(group_incomplete_dep_count)
        for node in pairs(default_enabled_nodes) do enabled_nodes[node] = true end
        for group, count in pairs(group_dep_count) do group_incomplete_dep_count[group] = count end
        
        -- Node 0 represents the players current position.
        local previous_node = 0
        
        -- While there are enabled nodes...
        while next(enabled_nodes) do
          local area, level, x, y, ex, ey = unpack(node_location, previous_node*6, previous_node*6+5)
          
          local chosen_node, chosen_node_score, chosen_node_distance
          local method = random() <= greed_prob and one or random
          
          for node in pairs(enabled_nodes) do
            local distance, edge = dist(previous_node, node)
            
            local score = distance/(node_pheromone_cache[edge] or 1)*method()
            
            if not chosen_node or score < chosen_node_score then
              chosen_node, chosen_node_score, chosen_node_distance = node, score, distance
            end
          end
          
          -- Add the chosen node to the path.
          current_path_len = current_path_len + chosen_node_distance
          insert(current_path, chosen_node)
          
          local chosen_group = node_group[chosen_node]
          
          -- Remove all the nodes from the chosen nodes group.
          for node in pairs(chosen_group) do
            enabled_nodes[node] = nil
          end
          
          for group in pairs(group_rdeps[chosen_group] or empty) do
            local count = assert(group_incomplete_dep_count[group])
            if count == 1 then
              -- This group no longer has any incomplete dependencies.
              group_incomplete_dep_count[group] = nil
              
              -- This group has no more incomplete dependencies; enable its nodes.
              for node in pairs(group) do
                enabled_nodes[node] = true
              end
            else
              -- There are still some incomplete dependencies, but at least it's now one less than it was.
              group_incomplete_dep_count[group] = count - 1
            end
          end
          
          -- Decay the pheromone along the edge that was just transversed.
          local edge = previous_node+chosen_node*node_count
          node_pheromone_cache[edge] = (node_pheromone_cache[edge] or 1)*pheromone_decay + (1-pheromone_decay)
          
          if chosen_node_distance > 0 then
            -- Only replace the previous node if the chosen node has a position,
            -- presumably if the distances is 0, then either the current node didn't have a position,
            -- or both nodes are in same location and it doesn't matter which one we used, so
            -- we continue to use the previous node in that case.
            previous_node = chosen_node
          end
          
          yield()
        end
        
        if not best_path_len or current_path_len < best_path_len then
          best_path, best_path_len, current_path = current_path, current_path_len, best_path
        end
      end
      
      -- I'm recycling the 'current_path' variable to hold the set of transversed edges.
      wipe(current_path)
      
      -- Add pheromone to the best trail, by an amount inversely proportional to its length.
      
      -- scholarpedia doesn't say to add the offline decay coefficent to this, but I am do it anyway
      -- because I'm pretty sure not doing this would cause unvisited edges to converge to a value of 0,
      -- and I'm pretty sure I want them to converge to a value of 1.
      -- Why? Because dividing by a value that is slowly converging toward 0 is probably a bad idea,
      -- and secondly, I'd need to populate node_pheromone_cache with values for all the edges, rather
      -- than just the ones that have been visited.
      local added_pheromone = 600/best_path_len + (1 - pheromone_offline_decay)
      
      local previous_node = 0
      for i, node in ipairs(best_path) do
        local edge = previous_node+node*node_count
        
        current_path[edge] = true
        
        node_pheromone_cache[edge] = (node_pheromone_cache[edge] or 1)*pheromone_offline_decay + added_pheromone
        
        previous_node = node
      end
      
      -- For edges that weren't visited. Again, scholarpedia says this should be 0, but as I said before,
      -- I want these to converge to 1 rather than 0.
      added_pheromone = 1 - pheromone_offline_decay
      
      for edge, pheromone in pairs(node_pheromone_cache) do
        if not current_path[edge] then
          -- This edge wasn't used in the best path; decay it.
          node_pheromone_cache[edge] = pheromone*pheromone_offline_decay + added_pheromone
        end
      end
      
      yield()
      
      local replace_current_route = false
      
      if used_route_len then
        replace_current_route = best_path_len < used_route_len + (used_route_first_node and dist(0, used_route_first_node) or 0)
      else
        -- We have nothing to compare the route we just created, so assume our route is better by default.
        replace_current_route = true
      end
      
      if replace_current_route then
        used_route_first_node = nil
        
        -- Find the first node that has a usable location.
        for i, node in pairs(best_path) do
          if node_location[node*6] then
            used_route_first_node = node
            break
          end
        end
        
        -- Subtract the distance from the player to the first node and use that as the distance;
        -- we'll recalcuate the distance to the player and add it back each time we check to see if we've
        -- found a better route to account for the player moving around.
        used_route_len = best_path_len - (used_route_first_node and dist(0, used_route_first_node) or 0)
        
        -- And now I'm recycling the 'current_path' variable to hold resulting route.
        wipe(current_path)
        
        for i, node in ipairs(best_path) do
          local objective = group_to_objective[node_group[node]]
          
          objective:setRouteLocation(unpack(node_location, node*6, node*6+5))
          
          insert(current_path, objective)
        end
        
        proposeNewRoute(current_path)
        yield()
      end
    else
      -- We don't know the player's position, so we can't calculate a route.
      -- Since we can't do anything useful, yield for a longer duration than usual.
      real_yield(5)
    end
  end
end

local routing_thread = nil

local routing_enabled, in_combat, serializing = false, InCombatLockdown(), false
local registered = false

local function updateRoutingThread()
  if routing_enabled and not in_combat and not serializing then
    if not routing_thread then
      routing_thread = coroutine.wrap(routingThreadEntry)
    end
    
    if not registered then
      registered = true
      shared.onDelay(0, routing_thread)
    end
  else
    if registered then
      registered = false
      shared.cancelDelayed(routing_thread)
    end
  end
end

shared.onSerializeStart(function ()
  serializing = true
  updateRoutingThread()
end)

shared.onSerializeStop(function ()
  serializing = false
  updateRoutingThread()
end)

shared.onCombatEnter(function ()
  in_combat = true
  updateRoutingThread()
end)

shared.onCombatLeave(function ()
  in_combat = false
  updateRoutingThread()
end)

shared.onSetting("routing_enabled", function (enabled)
  routing_enabled = enabled
  updateRoutingThread()
end)

shared.onSetting("routing_relaxed_priorities", function (enabled)
  relaxed_priorities = enabled
  route_objectives_changed = true
end)

shared.onLoad(function ()
  local route = _G.QuestHelper2_SavedRoute or {}
  
  local generated_route = {}
  
  for i, id in ipairs(route) do
    local obj = shared.lookupObjective(id)
    if obj then
      table.insert(generated_route, obj)
    end
  end
  
  proposeNewRoute(generated_route)
end)

shared.onSave(function ()
  local route = {}
  _G.QuestHelper2_SavedRoute = route
  
  for i, obj in pairs(sorted_route) do
    local id = obj.unique_id
    
    if id then
      table.insert(route, id)
    end
  end
end)
