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     if last_path[k + 1] then
 135       local nrt = GetCachedPath(last_path[k], last_path[k + 1])
 136       distance = distance + nrt.d
 137       QuestHelper: Assert(nrt)
 138
 139       -- The "condense" is kind of weird - we're actually condensing descriptions, but we condense to the *last* item. Urgh.
 140       local condense_start = nil
 141       local condense_class = nil
 142       local condense_to = nil
 143
 144       -- ugh this is just easier
 145       local function condense_doit()
 146         --print("start condense doit, was", real_path[condense_start].map_desc[1])
 147         for i = condense_start, #real_path do
 148           real_path[i].map_desc = condense_to
 149         end
 150         --print("end condense doit, now", real_path[condense_start].map_desc[1])
 151         condense_start, condense_class, condense_to = nil, nil, nil
 152       end
 153
 154       if #nrt > 0 then for _, wp in ipairs(nrt) do
 155         QuestHelper: Assert(wp.c)
 156
 157         --print(wp.condense_class)
 158         if condense_class and condense_class ~= wp.condense_class then condense_doit() end
 159
 160         local pathnode = QuestHelper:CreateTable("pathnode")
 161         pathnode.loc = QuestHelper:CreateTable("pathnode.loc")
 162         pathnode.loc.x = wp.x
 163         pathnode.loc.y = wp.y
 164         pathnode.loc.c = wp.c
 165         pathnode.ignore = true
 166         pathnode.map_desc = wp.map_desc
 167         pathnode.map_desc_chain = last_path[k + 1]
 168         pathnode.local_allocated = true
 169         pathnode.cluster = last_path[k + 1].cluster
 170         table.insert(real_path, pathnode) -- Technically, we'll end up with the distance to the next objective. I'm okay with this.
 171
 172         if not condense_class and wp.condense_class then
 173           condense_start, condense_class = #real_path, wp.condense_class
 174         end
 175         if condense_class then
 176           condense_to = wp.map_desc
 177         end
 178       end end
 179
 180       if condense_class then condense_doit() end -- in case we have stuff left over
 181     end
 182
 183     if progress then progress:SetPercentage(k / #last_path) end
 184   end
 185
 186   for _, v in pairs(notification_funcs) do
 187     QH_Timeslice_Yield()
 188     v(real_path)
 189   end
 190
 191   -- I hate having to do this, I feel like I'm just begging for horrifying bugs
 192   if cleanup_path then
 193     for k, v in ipairs(cleanup_path) do
 194       if v.local_allocated then
 195         QuestHelper:ReleaseTable(v.loc)
 196         QuestHelper:ReleaseTable(v)
 197       end
 198     end
 199
 200     QuestHelper:ReleaseTable(cleanup_path)
 201     cleanup_path = nil
 202   end
 203
 204   cleanup_path = real_path
 205
 206   QH_Timeslice_Yield()
 207 end
 208
 209 local filters = {}
 210
 211 function QH_Route_RegisterFilter(filter)
 212   QuestHelper: Assert(not filters[filter.name])
 213   QuestHelper: Assert(filter)
 214   filters[filter.name] = filter
 215 end
 216
 217 -- 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
 218 -- this is one reason the API is not considered stable :P
 219 local function ScanNode(node, ...)
 220   local stupid_lua = {...}
 221   Route_Core_EarlyExit()
 222   table.insert(pending, function ()
 223     for k, v in pairs(filters) do
 224       if v:Process(node, unpack(stupid_lua)) then
 225         Route_Core_IgnoreNode(node, v)
 226       else
 227         Route_Core_UnignoreNode(node, v)
 228       end
 229     end
 230   end)
 231 end
 232
 233 local function ScanCluster(clust)
 234   Route_Core_EarlyExit()
 235   table.insert(pending, function ()
 236     for _, v in ipairs(clust) do
 237       ScanNode(v)
 238     end
 239   end)
 240 end
 241
 242 local show_debug_commands = false
 243
 244 function QH_Route_Filter_Rescan_Now()
 245   Route_Core_TraverseNodes(function (...)
 246     ScanNode(...)
 247   end)
 248 end
 249
 250 function QH_Route_Filter_Rescan(name, suppress_earlyexit)
 251   if not suppress_earlyexit then Route_Core_EarlyExit() --[[print("ee rscn", (debugstack(2, 1, 0):gsub("\n...", "")))]] end
 252   QuestHelper: Assert(not name or filters[name] or name == "user_manual_ignored")
 253   table.insert(pending, function ()
 254     if show_debug_commands then print("delayed qrfr") end
 255     QH_Route_Filter_Rescan_Now() -- yeah, so we're really rescanning every node, aren't we. laaaazy
 256   end)
 257 end
 258
 259 function QH_Route_IgnoreNode(node, reason)
 260   Route_Core_EarlyExit() --print("ee in")
 261   table.insert(pending, function () if show_debug_commands then print("delayed qrin") end Route_Core_IgnoreNode(node, reason) end)
 262 end
 263
 264 function QH_Route_UnignoreNode(node, reason)
 265   Route_Core_EarlyExit() --print("ee uin")
 266   table.insert(pending, function () if show_debug_commands then print("delayed qrun") end Route_Core_UnignoreNode(node, reason) end)
 267 end
 268
 269 function QH_Route_ClusterAdd(clust)
 270   for _, v in ipairs(clust) do
 271     QuestHelper: Assert(v.cluster == clust)
 272   end
 273   Route_Core_EarlyExit() --print("ee ca")
 274   table.insert(pending, function () if show_debug_commands then print("delayed qrca1") end Route_Core_ClusterAdd(clust) end)
 275   rescan_it_all = true
 276 end
 277
 278 function QH_Route_ClusterRemove(clust)
 279   Route_Core_EarlyExit() --print("ee cre")
 280   table.insert(pending, function () if show_debug_commands then print("delayed qrcrm") end Route_Core_ClusterRemove(clust) end)
 281 end
 282
 283 function QH_Route_ClusterRequires(a, b)
 284   Route_Core_EarlyExit() --print("ee cr")
 285   table.insert(pending, function () if show_debug_commands then print("delayed qrcrq") end Route_Core_ClusterRequires(a, b) end)
 286 end
 287
 288 function QH_Route_IgnoreCluster(clust, reason)
 289   Route_Core_EarlyExit() --print("ee ic")
 290   table.insert(pending, function () if show_debug_commands then print("delayed qric") end Route_Core_IgnoreCluster(clust, reason) end)
 291 end
 292
 293 function QH_Route_UnignoreCluster(clust, reason)
 294   Route_Core_EarlyExit() --print("ee uic")
 295   table.insert(pending, function () if show_debug_commands then print("delayed qruc") end Route_Core_UnignoreCluster(clust, reason) end)
 296 end
 297
 298 function QH_Route_SetClusterPriority(clust, pri)
 299   QuestHelper: Assert(clust)
 300   Route_Core_EarlyExit() --print("ee scp")
 301   table.insert(pending, function () if show_debug_commands then print("delayed qrscp") end Route_Core_SetClusterPriority(clust, pri) end)
 302 end
 303
 304 local pending_recalc = false
 305 function QH_Route_FlightPathRecalc()
 306   if not pending_recalc then
 307     pending_recalc = true
 308     Route_Core_EarlyExit() --print("ee recalc")
 309     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)
 310   end
 311 end
 312 QH_Route_FlightPathRecalc() -- heh heh
 313
 314 -- Right now we just defer to the existing ones
 315 function QH_Route_TraverseNodes(func)
 316   return Route_Core_TraverseNodes(func)
 317 end
 318 function QH_Route_TraverseClusters(func)
 319   return Route_Core_TraverseClusters(func)
 320 end
 321 function QH_Route_IgnoredReasons_Cluster(clust, func)
 322   return Route_Core_IgnoredReasons_Cluster(clust, func)
 323 end
 324 function QH_Route_IgnoredReasons_Node(node, func)
 325   return Route_Core_IgnoredReasons_Node(node, func)
 326 end
 327 function QH_Route_Ignored_Cluster(clust)
 328   return Route_Core_Ignored_Cluster(clust)
 329 end
 330 function QH_Route_Ignored_Cluster_Active(clust)
 331   return Route_Core_Ignored_Cluster_Active(clust)
 332 end
 333 function QH_Route_GetClusterPriority(clust)
 334   return Route_Core_GetClusterPriority(clust)
 335 end
 336
 337
 338
 339 Route_Core_Init(
 340   function(path, progress)
 341     last_path = path
 342     ReplotPath(progress)
 343   end,
 344   function(loc1, loctable, reverse, complete_pass)
 345     if #loctable == 0 then return QuestHelper:CreateTable("null response") end
 346
 347     QH_Timeslice_Yield()
 348
 349     QuestHelper: Assert(loc1)
 350     QuestHelper: Assert(loc1.loc)
 351
 352     local lt = QuestHelper:CreateTable("route controller path shunt loctable")
 353     for _, v in ipairs(loctable) do
 354       QuestHelper: Assert(v.loc)
 355       table.insert(lt, v.loc)
 356     end
 357     QuestHelper: Assert(#loctable == #lt)
 358
 359     local rvv
 360
 361     if not reverse then
 362       if not pathcache_active[loc1] then pathcache_active[loc1] = new_pathcache_table() end
 363       if not pathcache_inactive[loc1] then pathcache_inactive[loc1] = new_pathcache_table() end
 364     else
 365       for _, v in ipairs(loctable) do
 366         if not pathcache_active[v] then pathcache_active[v] = new_pathcache_table() end
 367         if not pathcache_inactive[v] then pathcache_inactive[v] = new_pathcache_table() end
 368       end
 369     end
 370
 371     rvv = QuestHelper:CreateTable("route controller path shunt returnvalue")
 372     local rv = QH_Graph_Pathmultifind(loc1.loc, lt, reverse, true)
 373     QuestHelper: Assert(#lt == #rv)
 374
 375     -- We want to store the math.max(sqrt(#rv), 10) shortest paths
 376     local tostore = complete_pass and math.max(sqrt(#rv), 10) or #rv
 377     --print("would store", #rv, "am store", tostore)
 378     local linkity = QuestHelper:CreateTable("shortest path summary")
 379     for k, v in ipairs(rv) do
 380       local tk = QuestHelper:CreateTable("shortest path summary item")
 381       tk.k = k
 382       tk.v = v
 383       table.insert(linkity, tk)
 384
 385       rvv[k] = rv[k].d
 386     end
 387     table.sort(linkity, function(a, b) return a.v.d < b.v.d end)
 388     while #linkity > tostore do
 389       local rip = table.remove(linkity)
 390       QuestHelper:ReleaseTable(rip.v)
 391       QuestHelper:ReleaseTable(rip)
 392     end
 393
 394     for _, it in pairs(linkity) do
 395       local k, v = it.k, it.v
 396
 397       if not rv[k] then
 398         QuestHelper:TextOut(QuestHelper:StringizeTable(loc1.loc))
 399         QuestHelper:TextOut(QuestHelper:StringizeTable(lt[k]))
 400       end
 401       QuestHelper: Assert(rv[k], string.format("%d to %d", loc1.loc.p, loctable[k].loc.p))
 402       QuestHelper: Assert(rv[k].d)
 403
 404       -- We're only setting the inactive to give the garbage collector potentially a little more to clean up (i.e. the old path.)
 405       if not reverse then
 406         QuestHelper: Assert(pathcache_active[loc1])
 407         QuestHelper: Assert(pathcache_inactive[loc1])
 408         pathcache_active[loc1][loctable[k]] = rv[k]
 409         pathcache_inactive[loc1][loctable[k]] = rv[k]
 410       else
 411         QuestHelper: Assert(loctable[k])
 412         QuestHelper: Assert(pathcache_active[loctable[k]])
 413         QuestHelper: Assert(pathcache_inactive[loctable[k]])
 414         pathcache_active[loctable[k]][loc1] = rv[k]
 415         pathcache_inactive[loctable[k]][loc1] = rv[k]
 416       end
 417     end
 418
 419     for _, v in ipairs(linkity) do
 420       -- we do not release v.v, since that's now stored in our path cache
 421       QuestHelper:ReleaseTable(v)
 422     end
 423     QuestHelper:ReleaseTable(linkity)
 424     QuestHelper:ReleaseTable(lt)
 425     QuestHelper:ReleaseTable(rv)  -- this had better be releasable
 426
 427     return rvv
 428   end
 429 )
 430
 431 local StartObjective = {desc = "Start", tracker_hidden = true} -- this should never be displayed
 432
 433 local lapa = GetTime()
 434 local passcount = 0
 435
 436 local lc, lx, ly, lrc, lrz
 437
 438 local last_playerpos = nil
 439
 440 local function ReleaseShard(ki, shard)
 441   for k, tv in pairs(shard) do
 442     if not pathcache_active[ki] or not pathcache_active[ki][k] then QuestHelper:ReleaseTable(tv) end
 443   end
 444   QuestHelper:ReleaseTable(shard)
 445 end
 446
 447 local function process()
 448
 449   local last_cull = 0
 450   local last_movement = 0
 451
 452   local first = true
 453   -- 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.
 454   while true do
 455     if last_cull + 120 < GetTime() then
 456       last_cull = GetTime()
 457
 458       for k, v in pairs(pathcache_inactive) do
 459         ReleaseShard(k, v)
 460       end
 461       QuestHelper:ReleaseTable(pathcache_inactive)
 462
 463       pathcache_inactive = pathcache_active
 464       pathcache_active = new_pathcache_table()
 465     end
 466
 467     if last_movement + 1 < GetTime() then
 468       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
 469       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
 470         --local t = GetTime()
 471         lc, lx, ly, lrc, lrz = c, x, y, rc, rz
 472
 473         local new_playerpos = {desc = "Start", why = StartObjective, loc = NewLoc(c, x, y, rc, rz), tracker_hidden = true, ignore = true}
 474         Route_Core_SetStart(new_playerpos)
 475         if last_path then last_path[1] = new_playerpos end
 476         --QuestHelper: TextOut(string.format("SS takes %f", GetTime() - t))
 477         ReplotPath()
 478
 479         if last_playerpos then
 480           -- if it's in active, then it must be in inactive as well, so we do our actual deallocation in inactive only
 481           if pathcache_active[last_playerpos] then QuestHelper:ReleaseTable(pathcache_active[last_playerpos]) pathcache_active[last_playerpos] = nil end
 482           for k, v in pairs(pathcache_active) do v[last_playerpos] = nil end
 483
 484           if pathcache_inactive[last_playerpos] then ReleaseShard(last_playerpos, pathcache_inactive[last_playerpos]) pathcache_inactive[last_playerpos] = nil end
 485           for k, v in pairs(pathcache_inactive) do if v[last_playerpos] then QuestHelper:ReleaseTable(v[last_playerpos]) v[last_playerpos] = nil end end
 486         end
 487
 488         last_playerpos = new_playerpos
 489
 490         last_movement = GetTime()
 491       end
 492     end
 493
 494     if not first then
 495       Route_Core_Process()
 496       QH_Timeslice_Doneinit()
 497
 498       -- Wackyland code here
 499       if QH_WACKYLAND then
 500         QH_Route_Filter_Rescan()
 501         QH_Route_TraverseClusters(function (clust) QH_Route_SetClusterPriority(clust, math.random(-2, 2)) end)
 502       end
 503     end
 504     first = false
 505
 506     passcount = passcount + 1
 507     if lapa + 60 < GetTime() then
 508       if debug_output then QuestHelper:TextOut(string.format("%d passes in the last minute, %d nodes", passcount, Route_Core_NodeCount())) end
 509       lapa = lapa + 60
 510       passcount = 0
 511     end
 512
 513     QH_Timeslice_Yield()
 514
 515     -- snag stuff so we don't accidentally end up changing pending in two things at once
 516     while #pending > 0 do
 517       local lpending = pending
 518       pending = {}
 519
 520       for k, v in ipairs(lpending) do
 521         v()
 522         QH_Timeslice_Yield()
 523       end
 524     end
 525
 526     if rescan_it_all then
 527       rescan_it_all = false
 528       assert(#pending == 0) -- assert that everything is consistent after the scan
 529       QH_Route_Filter_Rescan_Now()
 530     end
 531   end
 532 end
 533
 534 QH_Timeslice_Add(process, "new_routing")