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 reverse then
 323       if not pathcache_active[loc1] then pathcache_active[loc1] = new_pathcache_table() end
 324       if not pathcache_inactive[loc1] then pathcache_inactive[loc1] = new_pathcache_table() end
 325     else
 326       for _, v in ipairs(loctable) do
 327         if not pathcache_active[v] then pathcache_active[v] = new_pathcache_table() end
 328         if not pathcache_inactive[v] then pathcache_inactive[v] = new_pathcache_table() end
 329       end
 330     end
 331
 332     rvv = QuestHelper:CreateTable("route controller path shunt returnvalue")
 333     local rv = QH_Graph_Pathmultifind(loc1.loc, lt, reverse, true)
 334     QuestHelper: Assert(#lt == #rv)
 335
 336     -- We want to store the math.max(sqrt(#rv), 10) shortest paths
 337     local tostore = complete_pass and math.max(sqrt(#rv), 10) or #rv
 338     --print("would store", #rv, "am store", tostore)
 339     local linkity = QuestHelper:CreateTable("shortest path summary")
 340     for k, v in ipairs(rv) do
 341       local tk = QuestHelper:CreateTable("shortest path summary item")
 342       tk.k = k
 343       tk.v = v
 344       table.insert(linkity, tk)
 345
 346       rvv[k] = rv[k].d
 347     end
 348     table.sort(linkity, function(a, b) return a.v.d < b.v.d end)
 349     while #linkity > tostore do
 350       local rip = table.remove(linkity)
 351       QuestHelper:ReleaseTable(rip.v)
 352       QuestHelper:ReleaseTable(rip)
 353     end
 354
 355     for _, it in pairs(linkity) do
 356       local k, v = it.k, it.v
 357
 358       if not rv[k] then
 359         QuestHelper:TextOut(QuestHelper:StringizeTable(loc1.loc))
 360         QuestHelper:TextOut(QuestHelper:StringizeTable(lt[k]))
 361       end
 362       QuestHelper: Assert(rv[k], string.format("%d to %d", loc1.loc.p, loctable[k].loc.p))
 363       QuestHelper: Assert(rv[k].d)
 364
 365       -- We're only setting the inactive to give the garbage collector potentially a little more to clean up (i.e. the old path.)
 366       if not reverse then
 367         QuestHelper: Assert(pathcache_active[loc1])
 368         QuestHelper: Assert(pathcache_inactive[loc1])
 369         pathcache_active[loc1][loctable[k]] = rv[k]
 370         pathcache_inactive[loc1][loctable[k]] = rv[k]
 371       else
 372         pathcache_active[loctable[k]][loc1] = rv[k]
 373         pathcache_inactive[loctable[k]][loc1] = rv[k]
 374       end
 375     end
 376
 377     for _, v in ipairs(linkity) do
 378       -- we do not release v.v, since that's now stored in our path cache
 379       QuestHelper:ReleaseTable(v)
 380     end
 381     QuestHelper:ReleaseTable(linkity)
 382     QuestHelper:ReleaseTable(lt)
 383     QuestHelper:ReleaseTable(rv)  -- this had better be releasable
 384
 385     return rvv
 386   end
 387 )
 388
 389 local StartObjective = {desc = "Start", tracker_hidden = true} -- this should never be displayed
 390
 391 local lapa = GetTime()
 392 local passcount = 0
 393
 394 local lc, lx, ly, lrc, lrz
 395
 396 local last_playerpos = nil
 397
 398 local function ReleaseShard(ki, shard)
 399   for k, tv in pairs(shard) do
 400     if not pathcache_active[ki] or not pathcache_active[ki][k] then QuestHelper:ReleaseTable(tv) end
 401   end
 402   QuestHelper:ReleaseTable(shard)
 403 end
 404
 405 local function process()
 406
 407   local last_cull = 0
 408   local last_movement = 0
 409
 410   local first = true
 411   -- 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.
 412   while true do
 413     if last_cull + 120 < GetTime() then
 414       last_cull = GetTime()
 415
 416       for k, v in pairs(pathcache_inactive) do
 417         ReleaseShard(k, v)
 418       end
 419       QuestHelper:ReleaseTable(pathcache_inactive)
 420
 421       pathcache_inactive = pathcache_active
 422       pathcache_active = new_pathcache_table()
 423     end
 424
 425     if last_movement + 1 < GetTime() then
 426       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
 427       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
 428         --local t = GetTime()
 429         lc, lx, ly, lrc, lrz = c, x, y, rc, rz
 430
 431         local new_playerpos = {desc = "Start", why = StartObjective, loc = NewLoc(c, x, y, rc, rz), tracker_hidden = true, ignore = true}
 432         Route_Core_SetStart(new_playerpos)
 433         if last_path then last_path[1] = new_playerpos end
 434         --QuestHelper: TextOut(string.format("SS takes %f", GetTime() - t))
 435         ReplotPath()
 436
 437         if last_playerpos then
 438           -- if it's in active, then it must be in inactive as well, so we do our actual deallocation in inactive only
 439           if pathcache_active[last_playerpos] then QuestHelper:ReleaseTable(pathcache_active[last_playerpos]) pathcache_active[last_playerpos] = nil end
 440           for k, v in pairs(pathcache_active) do v[last_playerpos] = nil end
 441
 442           if pathcache_inactive[last_playerpos] then ReleaseShard(last_playerpos, pathcache_inactive[last_playerpos]) pathcache_inactive[last_playerpos] = nil end
 443           for k, v in pairs(pathcache_inactive) do if v[last_playerpos] then QuestHelper:ReleaseTable(v[last_playerpos]) v[last_playerpos] = nil end end
 444         end
 445
 446         last_playerpos = new_playerpos
 447
 448         last_movement = GetTime()
 449       end
 450     end
 451
 452     if not first then
 453       Route_Core_Process()
 454       QH_Timeslice_Doneinit()
 455
 456       -- Wackyland code here
 457       if QH_WACKYLAND then
 458         QH_Route_Filter_Rescan()
 459         QH_Route_TraverseClusters(function (clust) QH_Route_SetClusterPriority(clust, math.random(-2, 2)) end)
 460       end
 461     end
 462     first = false
 463
 464     passcount = passcount + 1
 465     if lapa + 60 < GetTime() then
 466       if debug_output then QuestHelper:TextOut(string.format("%d passes in the last minute, %d nodes", passcount, Route_Core_NodeCount())) end
 467       lapa = lapa + 60
 468       passcount = 0
 469     end
 470
 471     QH_Timeslice_Yield()
 472
 473     -- snag stuff so we don't accidentally end up changing pending in two things at once
 474     while #pending > 0 do
 475       local lpending = pending
 476       pending = {}
 477
 478       for k, v in ipairs(lpending) do
 479         v()
 480         QH_Timeslice_Yield()
 481       end
 482     end
 483   end
 484 end
 485
 486 QH_Timeslice_Add(process, "new_routing")