routing_controller.lua

   1 QuestHelper_File["routing_controller.lua"] = "Development Version"
   2 QuestHelper_Loadtime["routing_controller.lua"] = GetTime()
   3
   4 local debug_output = (QuestHelper_File["routing_controller.lua"] == "Development Version")
   5
   6 local Route_Core_Process = QH_Route_Core_Process
   7
   8 local Route_Core_NodeCount = QH_Route_Core_NodeCount
   9
  10 local Route_Core_Init = QH_Route_Core_Init
  11 local Route_Core_SetStart = QH_Route_Core_SetStart
  12
  13 local Route_Core_ClusterAdd = QH_Route_Core_ClusterAdd
  14 local Route_Core_ClusterRemove = QH_Route_Core_ClusterRemove
  15 local Route_Core_ClusterRequires = QH_Route_Core_ClusterRequires
  16 local Route_Core_DistanceClear = QH_Route_Core_DistanceClear
  17
  18 local Route_Core_IgnoreNode = QH_Route_Core_IgnoreNode
  19 local Route_Core_UnignoreNode = QH_Route_Core_UnignoreNode
  20 local Route_Core_IgnoreCluster = QH_Route_Core_IgnoreCluster
  21 local Route_Core_UnignoreCluster = QH_Route_Core_UnignoreCluster
  22
  23 local Route_Core_GetClusterPriority = QH_Route_Core_GetClusterPriority
  24 local Route_Core_SetClusterPriority = QH_Route_Core_SetClusterPriority
  25
  26 local Route_Core_TraverseNodes = QH_Route_Core_TraverseNodes
  27 local Route_Core_TraverseClusters = QH_Route_Core_TraverseClusters
  28 local Route_Core_IgnoredReasons_Cluster = QH_Route_Core_IgnoredReasons_Cluster
  29 local Route_Core_IgnoredReasons_Node = QH_Route_Core_IgnoredReasons_Node
  30 local Route_Core_Ignored_Cluster = QH_Route_Core_Ignored_Cluster
  31 local Route_Core_Ignored_Cluster_Active = QH_Route_Core_Ignored_Cluster_Active
  32
  33 local Route_Core_EarlyExit = QH_Route_Core_EarlyExit
  34
  35 QH_Route_Core_Process = nil
  36 QH_Route_Core_Init = nil
  37 QH_Route_Core_SetStart = nil
  38 QH_Route_Core_NodeObsoletes = nil
  39 QH_Route_Core_NodeRequires = nil
  40 QH_Route_Core_DistanceClear = nil
  41 QH_Route_Core_IgnoreNode = nil
  42 QH_Route_Core_UnignoreNode = nil
  43 QH_Route_Core_IgnoreCluster = nil
  44 QH_Route_Core_UnignoreCluster = nil
  45 QH_Route_Core_GetClusterPriority = nil
  46 QH_Route_Core_SetClusterPriority = nil
  47 QH_Route_Core_TraverseNodes = nil
  48 QH_Route_Core_TraverseClusters = nil
  49 QH_Route_Core_IgnoredReasons_Cluster = nil
  50 QH_Route_Core_IgnoredReasons_Node = nil
  51 QH_Route_Core_Ignored_Cluster = nil
  52 QH_Route_Core_Ignored_Cluster_Active = nil
  53 QH_Route_Core_EarlyExit = nil
  54
  55 local pending = {}
  56 local rescan_it_all = false
  57
  58 local weak_key = {__mode="k"}
  59
  60 local function new_pathcache_table(conservative)
  61   return setmetatable(conservative and {} or QuestHelper:CreateTable("controller cache"), weak_key)
  62 end
  63
  64 -- Every minute or two, we dump the inactive and move active to inactive. Every time we touch something, we put it in active.
  65 local pathcache_active = new_pathcache_table()
  66 local pathcache_inactive = new_pathcache_table()
  67
  68 local function pcs(tpcs)
  69   local ct = 0
  70   for _, v in pairs(tpcs) do
  71     for _, t in pairs(v) do
  72       ct = ct + 1
  73     end
  74   end
  75   return ct
  76 end
  77
  78 function QH_PrintPathcacheSize()
  79   QuestHelper:TextOut(string.format("Active pathcache: %d", pcs(pathcache_active)))
  80   QuestHelper:TextOut(string.format("Inactive pathcache: %d", pcs(pathcache_inactive)))
  81 end
  82 function QH_ClearPathcache(conservative)
  83   local ps = pcs(pathcache_inactive)
  84   pathcache_active = new_pathcache_table(conservative)
  85   pathcache_inactive = new_pathcache_table(conservative)
  86   return ps
  87 end
  88
  89 local notification_funcs = {}
  90
  91 function QH_Route_RegisterNotification(func)
  92   table.insert(notification_funcs, func)
  93 end
  94
  95 local hits = 0
  96 local misses = 0
  97
  98 local function GetCachedPath(loc1, loc2)
  99   -- If it's in active, it's guaranteed to be in inactive.
 100   if not pathcache_inactive[loc1] or not pathcache_inactive[loc1][loc2] then
 101     -- Not in either, time to create
 102     misses = misses + 1
 103     local nrt = QH_Graph_Pathfind(loc1.loc, loc2.loc, false, true)
 104     QuestHelper: Assert(nrt)
 105     if not pathcache_active[loc1] then pathcache_active[loc1] = new_pathcache_table() end
 106     if not pathcache_inactive[loc1] then pathcache_inactive[loc1] = new_pathcache_table() end
 107     pathcache_active[loc1][loc2] = nrt
 108     pathcache_inactive[loc1][loc2] = nrt
 109     return nrt
 110   else
 111     hits = hits + 1
 112     if not pathcache_active[loc1] then pathcache_active[loc1] = new_pathcache_table() end
 113     pathcache_active[loc1][loc2] = pathcache_inactive[loc1][loc2]
 114     return pathcache_active[loc1][loc2]
 115   end
 116 end
 117
 118 local last_path = nil
 119 local cleanup_path = nil
 120
 121 local function ReplotPath(progress)
 122   if not last_path then return end  -- siiigh
 123
 124   local real_path = QuestHelper:CreateTable("path")
 125   hits = 0
 126   misses = 0
 127
 128   local distance = 0
 129   for k, v in ipairs(last_path) do
 130     QH_Timeslice_Yield()
 131     --QuestHelper: Assert(not v.condense_type) -- no
 132     v.distance = distance -- I'm not a huge fan of mutating things like this, but it is safe, and these nodes are technically designed to be modified during runtime anyway
 133     table.insert(real_path, v)
 134
 135     if last_path[k + 1] then
 136       local nrt = GetCachedPath(last_path[k], last_path[k + 1])
 137       distance = distance + nrt.d
 138       QuestHelper: Assert(nrt)
 139
 140       -- The "condense" is kind of weird - we're actually condensing descriptions, but we condense to the *last* item. Urgh.
 141       local condense_start = nil
 142       local condense_class = nil
 143       local condense_to = nil
 144
 145       -- ugh this is just easier
 146       local function condense_doit()
 147         --print("start condense doit, was", real_path[condense_start].map_desc[1])
 148         for i = condense_start, #real_path do
 149           real_path[i].map_desc = condense_to
 150         end
 151         --print("end condense doit, now", real_path[condense_start].map_desc[1])
 152         condense_start, condense_class, condense_to = nil, nil, nil
 153       end
 154
 155       if #nrt > 0 then for _, wp in ipairs(nrt) do
 156         QuestHelper: Assert(wp.c)
 157
 158         --print(wp.condense_class)
 159         if condense_class and condense_class ~= wp.condense_class then condense_doit() end
 160
 161         local pathnode = QuestHelper:CreateTable("pathnode")
 162         pathnode.loc = QuestHelper:CreateTable("pathnode.loc")
 163         pathnode.loc.x = wp.x
 164         pathnode.loc.y = wp.y
 165         pathnode.loc.c = wp.c
 166         pathnode.ignore = true
 167         pathnode.map_desc = wp.map_desc
 168         pathnode.map_desc_chain = last_path[k + 1]
 169         pathnode.local_allocated = true
 170         pathnode.cluster = last_path[k + 1].cluster
 171         table.insert(real_path, pathnode) -- Technically, we'll end up with the distance to the next objective. I'm okay with this.
 172
 173         if not condense_class and wp.condense_class then
 174           condense_start, condense_class = #real_path, wp.condense_class
 175         end
 176         if condense_class then
 177           condense_to = wp.map_desc
 178         end
 179       end end
 180
 181       if condense_class then condense_doit() end -- in case we have stuff left over
 182     end
 183
 184     if progress then progress:SetPercentage(k / #last_path) end
 185   end
 186
 187   for _, v in pairs(notification_funcs) do
 188     QH_Timeslice_Yield()
 189     v(real_path)
 190   end
 191
 192   -- I hate having to do this, I feel like I'm just begging for horrifying bugs
 193   if cleanup_path then
 194     for k, v in ipairs(cleanup_path) do
 195       if v.local_allocated then
 196         QuestHelper:ReleaseTable(v.loc)
 197         QuestHelper:ReleaseTable(v)
 198       end
 199     end
 200
 201     QuestHelper:ReleaseTable(cleanup_path)
 202     cleanup_path = nil
 203   end
 204
 205   cleanup_path = real_path
 206
 207   QH_Timeslice_Yield()
 208 end
 209
 210 local filters = {}
 211
 212 function QH_Route_RegisterFilter(filter)
 213   QuestHelper: Assert(not filters[filter.name])
 214   QuestHelper: Assert(filter)
 215   filters[filter.name] = filter
 216 end
 217
 218 -- we deal very badly with changing the requirement links after things are set up, so right now we're just relying on the fact that everything is unchanging afterwards
 219 -- this is one reason the API is not considered stable :P
 220 local function ScanNode(node, ...)
 221   local stupid_lua = {...}
 222   Route_Core_EarlyExit()
 223   table.insert(pending, function ()
 224     for k, v in pairs(filters) do
 225       if v:Process(node, unpack(stupid_lua)) then
 226         Route_Core_IgnoreNode(node, v)
 227       else
 228         Route_Core_UnignoreNode(node, v)
 229       end
 230     end
 231   end)
 232 end
 233
 234 local function ScanCluster(clust)
 235   Route_Core_EarlyExit()
 236   table.insert(pending, function ()
 237     for _, v in ipairs(clust) do
 238       ScanNode(v)
 239     end
 240   end)
 241 end
 242
 243 local show_debug_commands = false
 244
 245 function QH_Route_Filter_Rescan_Now()
 246   Route_Core_TraverseNodes(function (...)
 247     ScanNode(...)
 248   end)
 249 end
 250
 251 function QH_Route_Filter_Rescan(name, suppress_earlyexit)
 252   if not suppress_earlyexit then Route_Core_EarlyExit() --[[print("ee rscn", (debugstack(2, 1, 0):gsub("\n...", "")))]] end
 253   QuestHelper: Assert(not name or filters[name] or name == "user_manual_ignored")
 254   table.insert(pending, function ()
 255     if show_debug_commands then print("delayed qrfr") end
 256     QH_Route_Filter_Rescan_Now() -- yeah, so we're really rescanning every node, aren't we. laaaazy
 257   end)
 258 end
 259
 260 function QH_Route_IgnoreNode(node, reason)
 261   Route_Core_EarlyExit() --print("ee in")
 262   table.insert(pending, function () if show_debug_commands then print("delayed qrin") end Route_Core_IgnoreNode(node, reason) end)
 263 end
 264
 265 function QH_Route_UnignoreNode(node, reason)
 266   Route_Core_EarlyExit() --print("ee uin")
 267   table.insert(pending, function () if show_debug_commands then print("delayed qrun") end Route_Core_UnignoreNode(node, reason) end)
 268 end
 269
 270 function QH_Route_ClusterAdd(clust)
 271   for _, v in ipairs(clust) do
 272     QuestHelper: Assert(v.cluster == clust)
 273   end
 274   Route_Core_EarlyExit() --print("ee ca")
 275   table.insert(pending, function () if show_debug_commands then print("delayed qrca1") end Route_Core_ClusterAdd(clust) end)
 276   rescan_it_all = true
 277 end
 278
 279 function QH_Route_ClusterRemove(clust)
 280   Route_Core_EarlyExit() --print("ee cre")
 281   table.insert(pending, function () if show_debug_commands then print("delayed qrcrm") end Route_Core_ClusterRemove(clust) end)
 282 end
 283
 284 function QH_Route_ClusterRequires(a, b)
 285   Route_Core_EarlyExit() --print("ee cr")
 286   table.insert(pending, function () if show_debug_commands then print("delayed qrcrq") end Route_Core_ClusterRequires(a, b) end)
 287 end
 288
 289 function QH_Route_IgnoreCluster(clust, reason)
 290   Route_Core_EarlyExit() --print("ee ic")
 291   table.insert(pending, function () if show_debug_commands then print("delayed qric") end Route_Core_IgnoreCluster(clust, reason) end)
 292 end
 293
 294 function QH_Route_UnignoreCluster(clust, reason)
 295   Route_Core_EarlyExit() --print("ee uic")
 296   table.insert(pending, function () if show_debug_commands then print("delayed qruc") end Route_Core_UnignoreCluster(clust, reason) end)
 297 end
 298
 299 function QH_Route_SetClusterPriority(clust, pri)
 300   QuestHelper: Assert(clust)
 301   Route_Core_EarlyExit() --print("ee scp")
 302   table.insert(pending, function () if show_debug_commands then print("delayed qrscp") end Route_Core_SetClusterPriority(clust, pri) end)
 303 end
 304
 305 local pending_recalc = false
 306 function QH_Route_FlightPathRecalc()
 307   if not pending_recalc then
 308     pending_recalc = true
 309     Route_Core_EarlyExit() --print("ee recalc")
 310     table.insert(pending, function () if show_debug_commands then print("delayed qrfpr") end pending_recalc = false QH_redo_flightpath() pathcache_active = new_pathcache_table() pathcache_inactive = new_pathcache_table() Route_Core_DistanceClear() ReplotPath() end)
 311   end
 312 end
 313 QH_Route_FlightPathRecalc() -- heh heh
 314
 315 -- Right now we just defer to the existing ones
 316 function QH_Route_TraverseNodes(func)
 317   return Route_Core_TraverseNodes(func)
 318 end
 319 function QH_Route_TraverseClusters(func)
 320   return Route_Core_TraverseClusters(func)
 321 end
 322 function QH_Route_IgnoredReasons_Cluster(clust, func)
 323   return Route_Core_IgnoredReasons_Cluster(clust, func)
 324 end
 325 function QH_Route_IgnoredReasons_Node(node, func)
 326   return Route_Core_IgnoredReasons_Node(node, func)
 327 end
 328 function QH_Route_Ignored_Cluster(clust)
 329   return Route_Core_Ignored_Cluster(clust)
 330 end
 331 function QH_Route_Ignored_Cluster_Active(clust)
 332   return Route_Core_Ignored_Cluster_Active(clust)
 333 end
 334 function QH_Route_GetClusterPriority(clust)
 335   return Route_Core_GetClusterPriority(clust)
 336 end
 337
 338
 339
 340 Route_Core_Init(
 341   function(path, progress)
 342     last_path = path
 343     ReplotPath(progress)
 344   end,
 345   function(loc1, loctable, reverse, complete_pass)
 346     if #loctable == 0 then return QuestHelper:CreateTable("null response") end
 347
 348     QH_Timeslice_Yield()
 349
 350     QuestHelper: Assert(loc1)
 351     QuestHelper: Assert(loc1.loc)
 352
 353     local lt = QuestHelper:CreateTable("route controller path shunt loctable")
 354     for _, v in ipairs(loctable) do
 355       QuestHelper: Assert(v.loc)
 356       table.insert(lt, v.loc)
 357     end
 358     QuestHelper: Assert(#loctable == #lt)
 359
 360     local rvv
 361
 362     if not reverse then
 363       if not pathcache_active[loc1] then pathcache_active[loc1] = new_pathcache_table() end
 364       if not pathcache_inactive[loc1] then pathcache_inactive[loc1] = new_pathcache_table() end
 365     else
 366       for _, v in ipairs(loctable) do
 367         if not pathcache_active[v] then pathcache_active[v] = new_pathcache_table() end
 368         if not pathcache_inactive[v] then pathcache_inactive[v] = new_pathcache_table() end
 369       end
 370     end
 371
 372     rvv = QuestHelper:CreateTable("route controller path shunt returnvalue")
 373     local rv = QH_Graph_Pathmultifind(loc1.loc, lt, reverse, true)
 374     QuestHelper: Assert(#lt == #rv)
 375
 376     -- We want to store the math.max(sqrt(#rv), 10) shortest paths
 377     local tostore = complete_pass and math.max(sqrt(#rv), 10) or #rv
 378     --print("would store", #rv, "am store", tostore)
 379     local linkity = QuestHelper:CreateTable("shortest path summary")
 380     for k, v in ipairs(rv) do
 381       local tk = QuestHelper:CreateTable("shortest path summary item")
 382       tk.k = k
 383       tk.v = v
 384       table.insert(linkity, tk)
 385
 386       rvv[k] = rv[k].d
 387     end
 388     table.sort(linkity, function(a, b) return a.v.d < b.v.d end)
 389     while #linkity > tostore do
 390       local rip = table.remove(linkity)
 391       QuestHelper:ReleaseTable(rip.v)
 392       QuestHelper:ReleaseTable(rip)
 393     end
 394
 395     for _, it in pairs(linkity) do
 396       local k, v = it.k, it.v
 397
 398       if not rv[k] then
 399         QuestHelper:TextOut(QuestHelper:StringizeTable(loc1.loc))
 400         QuestHelper:TextOut(QuestHelper:StringizeTable(lt[k]))
 401       end
 402       QuestHelper: Assert(rv[k], string.format("%d to %d", loc1.loc.p, loctable[k].loc.p))
 403       QuestHelper: Assert(rv[k].d)
 404
 405       -- We're only setting the inactive to give the garbage collector potentially a little more to clean up (i.e. the old path.)
 406       if not reverse then
 407         QuestHelper: Assert(pathcache_active[loc1])
 408         QuestHelper: Assert(pathcache_inactive[loc1])
 409         pathcache_active[loc1][loctable[k]] = rv[k]
 410         pathcache_inactive[loc1][loctable[k]] = rv[k]
 411       else
 412         QuestHelper: Assert(loctable[k])
 413         QuestHelper: Assert(pathcache_active[loctable[k]])
 414         QuestHelper: Assert(pathcache_inactive[loctable[k]])
 415         pathcache_active[loctable[k]][loc1] = rv[k]
 416         pathcache_inactive[loctable[k]][loc1] = rv[k]
 417       end
 418     end
 419
 420     for _, v in ipairs(linkity) do
 421       -- we do not release v.v, since that's now stored in our path cache
 422       QuestHelper:ReleaseTable(v)
 423     end
 424     QuestHelper:ReleaseTable(linkity)
 425     QuestHelper:ReleaseTable(lt)
 426     QuestHelper:ReleaseTable(rv)  -- this had better be releasable
 427
 428     return rvv
 429   end
 430 )
 431
 432 local StartObjective = {desc = "Start", tracker_hidden = true} -- this should never be displayed
 433
 434 local lapa = GetTime()
 435 local passcount = 0
 436
 437 local lc, lx, ly, lrc, lrz
 438
 439 local last_playerpos = nil
 440
 441 local function ReleaseShard(ki, shard)
 442   for k, tv in pairs(shard) do
 443     if not pathcache_active[ki] or not pathcache_active[ki][k] then QuestHelper:ReleaseTable(tv) end
 444   end
 445   QuestHelper:ReleaseTable(shard)
 446 end
 447
 448 local function process()
 449
 450   local last_cull = 0
 451   local last_movement = 0
 452
 453   local first = true
 454   -- Order here is important. We don't want to update the location, then wait for a while as we add nodes. We also need the location updated before the first nodes are added. This way, it all works and we don't need anything outside the loop.
 455   while true do
 456     if last_cull + 120 < GetTime() then
 457       last_cull = GetTime()
 458
 459       for k, v in pairs(pathcache_inactive) do
 460         ReleaseShard(k, v)
 461       end
 462       QuestHelper:ReleaseTable(pathcache_inactive)
 463
 464       pathcache_inactive = pathcache_active
 465       pathcache_active = new_pathcache_table()
 466     end
 467
 468     if last_movement + 1 < GetTime() then
 469       local c, x, y, rc, rz = QuestHelper.routing_ac, QuestHelper.routing_ax, QuestHelper.routing_ay, QuestHelper.routing_c, QuestHelper.routing_z  -- ugh we need a better solution to this, but with this weird "planes" hybrid there just isn't one right now
 470       if c and x and y and rc and rz and (c ~= lc or x ~= lx or y ~= ly or rc ~= lrc or rz ~= lrz) then
 471         --local t = GetTime()
 472         lc, lx, ly, lrc, lrz = c, x, y, rc, rz
 473
 474         local new_playerpos = {desc = "Start", why = StartObjective, loc = NewLoc(c, x, y, rc, rz), tracker_hidden = true, ignore = true}
 475         Route_Core_SetStart(new_playerpos)
 476         if last_path then last_path[1] = new_playerpos end
 477         --QuestHelper: TextOut(string.format("SS takes %f", GetTime() - t))
 478         ReplotPath()
 479
 480         if last_playerpos then
 481           -- if it's in active, then it must be in inactive as well, so we do our actual deallocation in inactive only
 482           if pathcache_active[last_playerpos] then QuestHelper:ReleaseTable(pathcache_active[last_playerpos]) pathcache_active[last_playerpos] = nil end
 483           for k, v in pairs(pathcache_active) do v[last_playerpos] = nil end
 484
 485           if pathcache_inactive[last_playerpos] then ReleaseShard(last_playerpos, pathcache_inactive[last_playerpos]) pathcache_inactive[last_playerpos] = nil end
 486           for k, v in pairs(pathcache_inactive) do if v[last_playerpos] then QuestHelper:ReleaseTable(v[last_playerpos]) v[last_playerpos] = nil end end
 487         end
 488
 489         last_playerpos = new_playerpos
 490
 491         last_movement = GetTime()
 492       end
 493     end
 494
 495     if not first then
 496       Route_Core_Process()
 497       QH_Timeslice_Doneinit()
 498
 499       -- Wackyland code here
 500       if QH_WACKYLAND then
 501         QH_Route_Filter_Rescan()
 502         QH_Route_TraverseClusters(function (clust) QH_Route_SetClusterPriority(clust, math.random(-2, 2)) end)
 503       end
 504     end
 505     first = false
 506
 507     passcount = passcount + 1
 508     if lapa + 60 < GetTime() then
 509       if debug_output then QuestHelper:TextOut(string.format("%d passes in the last minute, %d nodes", passcount, Route_Core_NodeCount())) end
 510       lapa = lapa + 60
 511       passcount = 0
 512     end
 513
 514     QH_Timeslice_Yield()
 515
 516     -- snag stuff so we don't accidentally end up changing pending in two things at once
 517     while #pending > 0 do
 518       local lpending = pending
 519       pending = {}
 520
 521       for k, v in ipairs(lpending) do
 522         v()
 523         QH_Timeslice_Yield()
 524       end
 525     end
 526
 527     if rescan_it_all then
 528       rescan_it_all = false
 529       assert(#pending == 0) -- assert that everything is consistent after the scan
 530       QH_Route_Filter_Rescan_Now()
 531     end
 532   end
 533 end
 534
 535 QH_Timeslice_Add(process, "new_routing")