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