graph.lua

   1 local floor = math.floor
   2
   3 local function Graph_Search(self, first, last)
   4   if first ~= last then
   5     local open = self.open
   6     while #open > 0 do table.remove(open) end
   7     for _, n in ipairs(self.nodes) do n.s = 0 end
   8
   9     table.insert(open, first)
  10
  11     first.g = 0
  12     first.s = 2
  13
  14     while #open > 0 do
  15       local current = table.remove(open)
  16
  17       if current == last then
  18         first.p = nil
  19         return true
  20       end
  21
  22       current.s = 2
  23       local cd = current.g
  24
  25       for n, d in pairs(current.n) do
  26         if n.s == 0 then
  27           -- Haven't visited this node yet.
  28           local g = cd+d
  29           n.g = g
  30           n.s = 1
  31           n.p = current
  32
  33           local mn, mx = 1, #open+1
  34
  35           while mn ~= mx do
  36             local m = floor((mn+mx)*0.5)
  37
  38             if open[m].g > g then
  39               mn = m+1
  40             else
  41               mx = m
  42             end
  43           end
  44
  45           table.insert(open, mn, n)
  46         elseif n.s == 1 then
  47           local g = cd+d
  48           if g < n.g then
  49             n.g = g
  50             n.p = current
  51             local mn, mx = 1, #open
  52
  53             while mn ~= mx do
  54               local m = floor((mn+mx)*0.5)
  55               if open[m].g > g then
  56                 mn = m+1
  57               else
  58                 mx = m
  59               end
  60             end
  61
  62             while open[mn] ~= n do
  63               mn = mn + 1
  64             end
  65             mx = #open
  66             table.remove(open, mn)
  67
  68             while mn ~= mx do
  69               local m = floor((mn+mx)*0.5)
  70
  71               if open[m].g > g then
  72                 mn = m+1
  73               else
  74                 mx = m
  75               end
  76             end
  77
  78             table.insert(open, mn, n)
  79           end
  80         end
  81       end
  82     end
  83   end
  84   last.p = nil
  85   return first == last
  86 end
  87
  88 local function sanity(list, node)
  89   local last = nil
  90   local contains = false
  91   for i, n in ipairs(list) do
  92     if not (not last or last >= n.g) then
  93       for i, n in ipairs(list) do
  94         QuestHelper:TextOut(i..") "..n.g)
  95       end
  96       QuestHelper:Error("Order "..i.."/"..#list.." ("..n.g..")")
  97     end
  98     assert(not last or last >= n.g)
  99     last = n.g
 100     if n == node then
 101       contains = true
 102     end
 103   end
 104   if node and not contains then QuestHelper:Error("Missing") end
 105 end
 106
 107 local function Graph_Node_Link(self, next_node, distance)
 108   if type(distance) ~= "number" or distance < 0 then QuestHelper:Error("Boom!") end
 109   if self ~= next_node then
 110     self.n[next_node] = distance
 111     table.insert(next_node.r, self)
 112   end
 113 end
 114
 115 local function Graph_CreateNode(self)
 116   local node = QuestHelper:CreateTable()
 117   node.Link = Graph_Node_Link
 118   node.n = QuestHelper:CreateTable()
 119   node.r = QuestHelper:CreateTable()
 120   table.insert(self.nodes, node)
 121   return node
 122 end
 123
 124 local function Graph_DestroyNode(self, node)
 125   for i = 1,#self.nodes do
 126     if self.nodes[i] == node then
 127       table.remove(self.nodes, i)
 128       QuestHelper:ReleaseTable(node.n)
 129       QuestHelper:ReleaseTable(node.r)
 130       QuestHelper:ReleaseTable(node)
 131       break
 132     end
 133   end
 134 end
 135
 136 local function Graph_Reset(self)
 137   while #self.nodes > 0 do
 138     local node = table.remove(self.nodes)
 139     QuestHelper:ReleaseTable(node.n)
 140     QuestHelper:ReleaseTable(node.r)
 141     QuestHelper:ReleaseTable(node)
 142   end
 143 end
 144
 145 local function Graph_AddRouteStartNode(self, n, g, end_list)
 146   local open = self.open
 147
 148   n.p = nil
 149
 150   if n.s == 3 then
 151     n.s = 4
 152   elseif n.s == 0 then
 153     n.s = 1
 154   else
 155     local og = n.g
 156     if g < og then
 157       local mn, mx = 1, #open
 158
 159       while mn ~= mx do
 160         local m = floor((mn+mx)*0.5)
 161         if open[m].g > og then
 162           mn = m+1
 163         else
 164           mx = m
 165         end
 166       end
 167
 168       while open[mn] ~= n do
 169         mn = mn + 1
 170       end
 171
 172       table.remove(open, mn)
 173     else
 174       return -- Don't want to insert the node a second time.
 175     end
 176   end
 177
 178   local mn, mx = 1, #open+1
 179
 180   while mn ~= mx do
 181     local m = floor((mn+mx)*0.5)
 182
 183     if open[m].g > g then
 184       mn = m+1
 185     else
 186       mx = m
 187     end
 188   end
 189
 190   table.insert(open, mn, n)
 191
 192   n.g = g
 193 end
 194
 195 local function Graph_DoRouteSearch(self, end_list)
 196   local open = self.open
 197   local end_count = #end_list
 198
 199   while #open > 0 do
 200     local current = table.remove(open)
 201
 202     if current.s == 3 or current.s == 4 then
 203       current.s = 2
 204       return current
 205     end
 206
 207     current.s = 2
 208
 209     local cd = current.g
 210
 211     for n, d in pairs(current.n) do
 212       if n.s == 0 or n.s == 3 then
 213         -- Haven't visited this node yet.
 214         local g = cd+d
 215         n.p = current
 216         n.g = g
 217
 218         n.s = n.s == 3 and 4 or 1
 219
 220         local mn, mx = 1, #open+1
 221
 222         while mn ~= mx do
 223           local m = floor((mn+mx)*0.5)
 224
 225           if open[m].g > g then
 226             mn = m+1
 227           else
 228             mx = m
 229           end
 230         end
 231
 232         table.insert(open, mn, n)
 233       elseif n.s == 1 or n.s == 4 then
 234         local g = cd+d
 235         local og = n.g
 236         if g < og then
 237           n.p = current
 238
 239           local mn, mx = 1, #open
 240
 241           while mn ~= mx do
 242             local m = floor((mn+mx)*0.5)
 243             if open[m].g > og then
 244               mn = m+1
 245             else
 246               mx = m
 247             end
 248           end
 249
 250           while open[mn] ~= n do
 251             mn = mn + 1
 252           end
 253
 254           mx = #open
 255
 256           table.remove(open, mn)
 257
 258           while mn ~= mx do
 259             local m = floor((mn+mx)*0.5)
 260
 261             if open[m].g > g then
 262               mn = m+1
 263             else
 264               mx = m
 265             end
 266           end
 267
 268           n.g = g
 269           table.insert(open, mn, n)
 270         end
 271       end
 272     end
 273   end
 274 end
 275
 276 local function Graph_PrepareSearch(self)
 277   local open = self.open
 278   for n in pairs(open) do open[n] = nil end
 279   for _, n in pairs(self.nodes) do
 280     n.s = 0
 281   end
 282 end
 283
 284 local function Graph_AddStartNode(self, n, g, end_list)
 285   local open = self.open
 286
 287   n.p = n
 288
 289   if n.s == 3 then
 290     n.s = 4
 291   elseif n.s == 0 then
 292     n.s = 1
 293   else
 294     local og = n.g
 295     if g < og then
 296       local mn, mx = 1, #open
 297
 298       while mn ~= mx do
 299         local m = floor((mn+mx)*0.5)
 300         if open[m].g > og then
 301           mn = m+1
 302         else
 303           mx = m
 304         end
 305       end
 306
 307       while open[mn] ~= n do
 308         mn = mn + 1
 309       end
 310
 311       table.remove(open, mn)
 312     else
 313       return -- Don't want to insert the node a second time.
 314     end
 315   end
 316
 317   local mn, mx = 1, #open+1
 318
 319   while mn ~= mx do
 320     local m = floor((mn+mx)*0.5)
 321
 322     if open[m].g > g then
 323       mn = m+1
 324     else
 325       mx = m
 326     end
 327   end
 328
 329   table.insert(open, mn, n)
 330
 331   n.g = g
 332 end
 333
 334 local function Graph_DoSearch(self, end_list)
 335   local open = self.open
 336   local end_count = #end_list
 337
 338   while #open > 0 do
 339     local current = table.remove(open)
 340
 341     if current.s == 3 or current.s == 4 then
 342       current.s = 2
 343       return current
 344     end
 345
 346     current.s = 2
 347
 348     local cd = current.g
 349
 350     for n, d in pairs(current.n) do
 351       if n.s == 0 or n.s == 3 then
 352         -- Haven't visited this node yet.
 353         local g = cd+d
 354         n.g = g
 355         n.p = current.p
 356
 357         n.s = n.s == 3 and 4 or 1
 358
 359         local mn, mx = 1, #open+1
 360
 361         while mn ~= mx do
 362           local m = floor((mn+mx)*0.5)
 363
 364           if open[m].g > g then
 365             mn = m+1
 366           else
 367             mx = m
 368           end
 369         end
 370
 371         table.insert(open, mn, n)
 372       elseif n.s == 1 or n.s == 4 then
 373         local g = cd+d
 374         local og = n.g
 375         if g < og then
 376           n.p = current.p
 377
 378           local mn, mx = 1, #open
 379
 380           while mn ~= mx do
 381             local m = floor((mn+mx)*0.5)
 382             if open[m].g > og then
 383               mn = m+1
 384             else
 385               mx = m
 386             end
 387           end
 388
 389           while open[mn] ~= n do
 390             mn = mn + 1
 391           end
 392
 393           mx = #open
 394
 395           table.remove(open, mn)
 396
 397           while mn ~= mx do
 398             local m = floor((mn+mx)*0.5)
 399
 400             if open[m].g > g then
 401               mn = m+1
 402             else
 403               mx = m
 404             end
 405           end
 406
 407           n.g = g
 408           table.insert(open, mn, n)
 409         end
 410       end
 411     end
 412   end
 413 end
 414
 415 local removed = {}
 416
 417 local function Graph_DoFullSearch(self, end_list)
 418   local open = self.open
 419   local end_count = #end_list
 420
 421   while #open > 0 do
 422     local current = table.remove(open)
 423
 424     if current.s == 3 or current.s == 4 then
 425       if end_count == 1 then
 426         for i = 1,#removed do
 427           table.insert(end_list, table.remove(removed))
 428         end
 429         return
 430       end
 431
 432       for i = 1,end_count do
 433         if end_list[i] == current then
 434           table.insert(removed, table.remove(end_list, i))
 435           break
 436         end
 437       end
 438
 439       end_count = end_count - 1
 440     end
 441
 442     current.s = 2
 443
 444     local cd = current.g
 445
 446     for n, d in pairs(current.n) do
 447       if n.s == 0 or n.s == 3 then
 448         -- Haven't visited this node yet.
 449         local g = cd+d
 450         n.g = g
 451         n.p = current.p
 452
 453         n.s = n.s == 3 and 4 or 1
 454
 455         local mn, mx = 1, #open+1
 456
 457         while mn ~= mx do
 458           local m = floor((mn+mx)*0.5)
 459
 460           if open[m].g > g then
 461             mn = m+1
 462           else
 463             mx = m
 464           end
 465         end
 466
 467         table.insert(open, mn, n)
 468       elseif n.s == 1 or n.s == 4 then
 469         local g = cd+d
 470         local og = n.g
 471         if g < og then
 472           n.p = current.p
 473
 474           local mn, mx = 1, #open
 475
 476           while mn ~= mx do
 477             local m = floor((mn+mx)*0.5)
 478             if open[m].g > og then
 479               mn = m+1
 480             else
 481               mx = m
 482             end
 483           end
 484
 485           while open[mn] ~= n do
 486             mn = mn + 1
 487           end
 488
 489           mx = #open
 490
 491           table.remove(open, mn)
 492
 493           while mn ~= mx do
 494             local m = floor((mn+mx)*0.5)
 495
 496             if open[m].g > g then
 497               mn = m+1
 498             else
 499               mx = m
 500             end
 501           end
 502
 503           n.g = g
 504           table.insert(open, mn, n)
 505         end
 506       end
 507     end
 508   end
 509
 510   for i, n in ipairs(end_list) do
 511     QuestHelper:TextOut(i..") Failed to reach: "..n.name..", s="..n.s)
 512   end
 513
 514   for i = 1,#removed do
 515     table.insert(end_list, table.remove(removed))
 516   end
 517
 518   for i, n in ipairs(end_list) do
 519     QuestHelper:TextOut(i..") End node: "..n.name..", s="..n.s)
 520   end
 521
 522   QuestHelper:Error("Boom!")
 523
 524   for i = 1,#removed do
 525     table.insert(end_list, table.remove(removed))
 526   end
 527 end
 528
 529 local function propLinks(node)
 530   if node.s ~= 1 then
 531     node.s = 1
 532     for n in pairs(node.n) do
 533       propLinks(n)
 534     end
 535   end
 536 end
 537
 538 function Graph_SanityCheck(self)
 539   for i = 1,#self.nodes do
 540     for _, n in ipairs(self.nodes) do
 541       n.s = 0
 542     end
 543
 544     propLinks(self.nodes[i])
 545
 546     for _, n in ipairs(self.nodes) do
 547       if n.s ~= 1 then
 548         QuestHelper:TextOut((n.name or "unknown").." isn't reachable from "..(self.nodes[i].name or "unknown"))
 549       end
 550     end
 551   end
 552 end
 553
 554 function QuestHelper:CreateGraph()
 555   local graph = self:CreateTable()
 556   graph.nodes = self:CreateTable()
 557   graph.end_nodes = self:CreateTable()
 558   graph.open = self:CreateTable()
 559
 560   graph.CreateNode = Graph_CreateNode
 561   graph.DestroyNode = Graph_DestroyNode
 562   graph.Reset = Graph_Reset
 563
 564   graph.PrepareSearch = Graph_PrepareSearch
 565
 566   graph.AddRouteStartNode = Graph_AddRouteStartNode
 567   graph.DoRouteSearch = Graph_DoRouteSearch
 568   graph.Search = Graph_Search
 569   graph.SanityCheck = Graph_SanityCheck
 570
 571   -- These don't deal with finding paths and instead only care about finding distances.
 572   graph.AddStartNode = Graph_AddStartNode
 573   graph.DoSearch = Graph_DoSearch
 574   graph.DoFullSearch = Graph_DoFullSearch
 575
 576   return graph
 577 end
 578
 579 function QuestHelper:ReleaseGraph(graph)
 580   graph:Reset()
 581   self:ReleaseTable(graph.nodes)
 582   self:ReleaseTable(graph.end_nodes)
 583   self:ReleaseTable(graph.open)
 584   self:ReleaseTable(graph)
 585 end
 586
 587 QuestHelper.world_graph = QuestHelper:CreateGraph()