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