pathfinding.lua

   1 QuestHelper_File["pathfinding.lua"] = "Development Version"
   2
   3 local IRONFORGE_PORTAL = {25,0.255,0.084, "Ironforge portal site"}
   4 local STORMWIND_CITY_PORTAL = {36,0.387,0.802, "Stormwind City portal site"}
   5 local DARNASSUS_PORTAL = {21,0.397,0.824, "Darnassus portal site"}
   6 local EXODAR_PORTAL = {12,0.476,0.598, "Exodar portal site"}
   7
   8 local SHATTRATH_CITY_PORTAL = {60,0.530,0.492, "Shattrath City portal site"}
   9 local MOONGLADE_PORTAL = {20,0.563,0.320, "Moonglade portal site"}
  10
  11 local SILVERMOON_CITY_PORTAL = {52,0.583,0.192, "Silvermoon City portal site"}
  12 local UNDERCITY_PORTAL = {45,0.846,0.163, "Undercity portal site"}
  13 local ORGRIMMAR_PORTAL = {1,0.386,0.859, "Orgrimmar portal site"}
  14 local THUNDER_BLUFF_PORTAL = {23,0.222,0.168, "Thunder Bluff portal site"}
  15
  16 local static_horde_routes =
  17   {
  18    {{7, 0.505, 0.124}, {38, 0.313, 0.303}, 210}, -- Durotar <--> Grom'gol Base Camp
  19    {{38, 0.316, 0.289}, {43, 0.621, 0.591}, 210}, -- Grom'gol Base Camp <--> Tirisfal Glades
  20    {{43, 0.605, 0.587}, {7, 0.509, 0.141}, 210}, -- Tirisfal Glades <--> Durotar
  21    {{45, 0.549, 0.11}, {52, 0.495, 0.148}, 5}, -- Undercity <--> Silvermoon City
  22
  23    {{60, 0.592, 0.483}, SILVERMOON_CITY_PORTAL, 5, true, nil, "SILVERMOON_CITY_PORTAL"}, -- Shattrath City --> Silvermoon City
  24    {{60, 0.528, 0.531}, THUNDER_BLUFF_PORTAL, 5, true, nil, "THUNDER_BLUFF_PORTAL"}, -- Shattrath City --> Thunder Bluff
  25    {{60, 0.522, 0.529}, ORGRIMMAR_PORTAL, 5, true, nil, "ORGRIMMAR_PORTAL"}, -- Shattrath City --> Orgrimmar
  26    {{60, 0.517, 0.525}, UNDERCITY_PORTAL, 5, true, nil, "UNDERCITY_PORTAL"} -- Shattrath City --> Undercity
  27   }
  28
  29 local static_alliance_routes =
  30   {
  31    {{36, 0.639, 0.083}, {25, 0.764, 0.512}, 120}, -- Deeprun Tram
  32    {{51, 0.044, 0.569}, {16, 0.323, 0.441}, 210}, --Menethil Harbor <--> Auberdine
  33    {{10, 0.718, 0.565}, {51, 0.047, 0.636}, 210}, -- Theramore Isle <--> Menethil Harmor
  34
  35    {{60, 0.558, 0.366}, STORMWIND_CITY_PORTAL, 5, true, nil, "STORMWIND_CITY_PORTAL"}, -- Shattrath City --> Stormwind City
  36    {{60, 0.563, 0.37}, IRONFORGE_PORTAL, 5, true, nil, "IRONFORGE_PORTAL"}, -- Shattrath City --> Ironforge
  37    {{60, 0.552, 0.364}, DARNASSUS_PORTAL, 5, true, nil, "DARNASSUS_PORTAL"}, -- Shattrath City --> Darnassus
  38    {{60, 0.596, 0.467}, EXODAR_PORTAL, 5, true, nil, "EXODAR_PORTAL"} -- Shattrath City --> Exodar
  39   }
  40
  41 local static_shared_routes =
  42   {
  43    {{11, 0.638, 0.387}, {38, 0.257, 0.73}, 210}, -- Ratchet <--> Booty Bay
  44    {{40, 0.318, 0.503}, {32, 0.347, 0.84}, 130}, -- Burning Steppes <--> Searing Gorge
  45
  46    -- More Alliance routes than anything, but without them theres no valid path to these areas for Horde characters.
  47    {{24, 0.559, 0.896}, {21, 0.305, 0.414}, 5}, -- Rut'Theran Village <--> Darnassus
  48    {{16, 0.332, 0.398}, {24, 0.548, 0.971}, 210}, -- Auberdine <--> Rut'Theran Village
  49    {{16, 0.306, 0.409}, {3, 0.2, 0.546}, 210}, -- Auberdine <--> Azuremyst Isle
  50
  51    -- Route to new zone. Not valid, exists only to keep routing from exploding if you don't have the flight routes there.
  52    {{41, 0.5, 0.5}, {64, 0.5, 0.5}, 7200} -- Eversong Woods <--> Sunwell
  53   }
  54
  55 -- Darkportal is handled specially, depending on whether or not you're level 58+ or not.
  56 local dark_portal_route = {{33, 0.587, 0.599}, {56, 0.898, 0.502}, 5}
  57
  58 local static_zone_transitions =
  59   {
  60    {2, 11, 0.687, 0.872}, -- Ashenvale <--> The Barrens
  61    {2, 6, 0.423, 0.711}, -- Ashenvale <--> Stonetalon Mountains
  62    {2, 15, 0.954, 0.484}, -- Ashenvale <--> Azshara
  63    {2, 16, 0.289, 0.144}, -- Ashenvale <--> Darkshore
  64    {2, 13, 0.557, 0.29}, -- Ashenvale <--> Felwood
  65    {21, 24, 0.894, 0.358}, -- Darnassus <--> Teldrassil
  66    {22, 11, 0.697, 0.604}, -- Mulgore <--> The Barrens
  67    {22, 23, 0.376, 0.33}, -- Mulgore <--> Thunder Bluff
  68    {22, 23, 0.403, 0.193}, -- Mulgore <--> Thunder Bluff
  69    {3, 12, 0.247, 0.494}, -- Azuremyst Isle <--> The Exodar
  70    {3, 12, 0.369, 0.469}, -- Azuremyst Isle <--> The Exodar
  71    {3, 9, 0.42, 0.013}, -- Azuremyst Isle <--> Bloodmyst Isle
  72    {4, 6, 0.539, 0.032}, -- Desolace <--> Stonetalon Mountains
  73    {4, 17, 0.428, 0.976}, -- Desolace <--> Feralas
  74    {5, 18, 0.865, 0.115}, -- Silithus <--> Un'Goro Crater
  75    {7, 11, 0.341, 0.424}, -- Durotar <--> The Barrens
  76    {7, 1, 0.455, 0.121}, -- Durotar <--> Orgrimmar
  77    {8, 18, 0.269, 0.516}, -- Tanaris <--> Un'Goro Crater
  78    {8, 14, 0.512, 0.21}, -- Tanaris <--> Thousand Needles
  79    {10, 11, 0.287, 0.472}, -- Dustwallow Marsh <--> The Barrens
  80    {10, 11, 0.563, 0.077}, -- Dustwallow Marsh <--> The Barrens
  81    {11, 14, 0.442, 0.915}, -- The Barrens <--> Thousand Needles
  82    {13, 19, 0.685, 0.06}, -- Felwood <--> Winterspring
  83    {13, 20, 0.669, -0.063}, -- Felwood <--> Moonglade
  84    {1, 11, 0.118, 0.69}, -- Orgrimmar <--> The Barrens
  85    {17, 14, 0.899, 0.46}, -- Feralas <--> Thousand Needles
  86    {6, 11, 0.836, 0.973}, -- Stonetalon Mountains <--> The Barrens
  87    {26, 48, 0.521, 0.7}, -- Alterac Mountains <--> Hillsbrad Foothills
  88    {26, 35, 0.173, 0.482}, -- Alterac Mountains <--> Silverpine Forest
  89    {26, 50, 0.807, 0.347}, -- Alterac Mountains <--> Western Plaguelands
  90    {39, 51, 0.454, 0.89}, -- Arathi Highlands <--> Wetlands
  91    {39, 48, 0.2, 0.293}, -- Arathi Highlands <--> Hillsbrad Foothills
  92    {27, 29, 0.49, 0.071}, -- Badlands <--> Loch Modan
  93    {27, 32, -0.005, 0.636}, -- Badlands <--> Searing Gorge
  94    {33, 46, 0.519, 0.051}, -- Blasted Lands <--> Swamp of Sorrows
  95    {40, 30, 0.79, 0.842}, -- Burning Steppes <--> Redridge Mountains
  96    {47, 31, 0.324, 0.363}, -- Deadwind Pass <--> Duskwood
  97    {47, 46, 0.605, 0.41}, -- Deadwind Pass <--> Swamp of Sorrows
  98    {28, 25, 0.534, 0.349}, -- Dun Morogh <--> Ironforge
  99    {28, 29, 0.863, 0.514}, -- Dun Morogh <--> Loch Modan
 100    {28, 29, 0.844, 0.31}, -- Dun Morogh <--> Loch Modan
 101    {31, 37, 0.801, 0.158}, -- Duskwood <--> Elwynn Forest
 102    {31, 37, 0.15, 0.214}, -- Duskwood <--> Elwynn Forest
 103    {31, 38, 0.447, 0.884}, -- Duskwood <--> Stranglethorn Vale
 104    {31, 38, 0.209, 0.863}, -- Duskwood <--> Stranglethorn Vale
 105    {31, 30, 0.941, 0.103}, -- Duskwood <--> Redridge Mountains
 106    {31, 49, 0.079, 0.638}, -- Duskwood <--> Westfall
 107    {34, 50, 0.107, 0.726}, -- Eastern Plaguelands <--> Western Plaguelands
 108    {34, 44, 0.625, 0.03}, -- Eastern Plaguelands <--> Ghostlands
 109    {37, 36, 0.321, 0.493}, -- Elwynn Forest <--> Stormwind City
 110    {37, 49, 0.202, 0.804}, -- Elwynn Forest <--> Westfall
 111    {37, 30, 0.944, 0.724}, -- Elwynn Forest <--> Redridge Mountains
 112    {41, 52, 0.567, 0.494}, -- Eversong Woods <--> Silvermoon City
 113    {41, 44, 0.486, 0.916}, -- Eversong Woods <--> Ghostlands
 114    {35, 43, 0.678, 0.049}, -- Silverpine Forest <--> Tirisfal Glades
 115    {42, 50, 0.217, 0.264}, -- The Hinterlands <--> Western Plaguelands
 116    {43, 45, 0.619, 0.651}, -- Tirisfal Glades <--> Undercity
 117    {43, 50, 0.851, 0.703}, -- Tirisfal Glades <--> Western Plaguelands
 118    {38, 49, 0.292, 0.024}, -- Stranglethorn Vale <--> Westfall
 119    {48, 35, 0.137, 0.458}, -- Hillsbrad Foothills <--> Silverpine Forest
 120    {48, 42, 0.899, 0.253}, -- Hillsbrad Foothills <--> The Hinterlands
 121    {29, 51, 0.252, 0}, -- Loch Modan <--> Wetlands
 122
 123    -- These are just guesses, since I haven't actually been to these areas.
 124    {58, 60, 0.783, 0.545}, -- Nagrand <--> Shattrath City
 125    {60, 55, 0.782, 0.492}, -- Shattrath City <--> Terokkar Forest
 126    {54, 59, 0.842, 0.284}, -- Blade's Edge Mountains <--> Netherstorm
 127    {54, 57, 0.522, 0.996}, -- Blade's Edge Mountains <--> Zangarmarsh
 128    {54, 57, 0.312, 0.94}, -- Blade's Edge Mountains <--> Zangarmarsh
 129    {56, 55, 0.353, 0.901}, -- Hellfire Peninsula <--> Terokkar Forest
 130    {56, 57, 0.093, 0.519}, -- Hellfire Peninsula <--> Zangarmarsh
 131    {58, 55, 0.8, 0.817}, -- Nagrand <--> Terokkar Forest
 132    {58, 57, 0.343, 0.159}, -- Nagrand <--> Zangarmarsh
 133    {58, 57, 0.754, 0.331}, -- Nagrand <--> Zangarmarsh
 134    {53, 55, 0.208, 0.271}, -- Shadowmoon Valley <--> Terokkar Forest
 135    {55, 57, 0.341, 0.098}, -- Terokkar Forest <--> Zangarmarsh
 136   }
 137
 138 local walkspeed_multiplier = 1/7 -- Every yard walked takes this many seconds.
 139
 140 QuestHelper.prepared_objectives = {}
 141 QuestHelper.named_nodes = {}
 142
 143 local function cont_dist(a, b)
 144   local x, y = a.x-b.x, a.y-b.y
 145   return math.sqrt(x*x+y*y)
 146 end
 147
 148 function QuestHelper:ComputeRoute(p1, p2)
 149   if not p1 or not p2 then QuestHelper:Error("Boom!") end
 150   local graph = self.world_graph
 151
 152   graph:PrepareSearch()
 153
 154   local l = p2[2]
 155   local el = p2[1]
 156   for i, n in ipairs(el) do
 157     n.e, n.w = l[i], 1
 158     n.s = 3
 159   end
 160
 161   l = p1[2]
 162   for i, n in ipairs(p1[1]) do
 163     graph:AddRouteStartNode(n, l[i], el)
 164   end
 165
 166   local e = graph:DoRouteSearch(el)
 167
 168   assert(e)
 169
 170   local d = e.g+e.e
 171
 172   if p1[1] == p2[1] then
 173     local x, y = p1[3]-p2[3], p1[4]-p2[4]
 174     local d2 = math.sqrt(x*x+y*y)
 175     if d2 < d then
 176       d = d2
 177       e = nil
 178     end
 179   end
 180
 181   return e, d
 182 end
 183
 184 function QuestHelper:ComputeTravelTime(p1, p2)
 185   if not p1 or not p2 then QuestHelper:Error("Boom!") end
 186   local graph = self.world_graph
 187
 188   graph:PrepareSearch()
 189
 190   local l = p2[2]
 191   local el = p2[1]
 192   for i, n in ipairs(el) do
 193     n.e, n.w = l[i], 1
 194     assert(n.e)
 195     n.s = 3
 196   end
 197
 198   l = p1[2]
 199   for i, n in ipairs(p1[1]) do
 200     graph:AddStartNode(n, l[i], el)
 201   end
 202
 203   local e = graph:DoSearch(el)
 204
 205   assert(e)
 206
 207   local d = e.g+e.e
 208
 209   if p1[1] == p2[1] then
 210     local x, y = p1[3]-p2[3], p1[4]-p2[4]
 211     d = math.min(d, math.sqrt(x*x+y*y))
 212   end
 213
 214   return d
 215 end
 216
 217 function QuestHelper:CreateGraphNode(c, x, y, n)
 218   local node = self.world_graph:CreateNode()
 219
 220   if y then
 221     node.c = c
 222     node.x = x
 223     node.y = y
 224     node.name = n
 225   else
 226     local cont, zone = unpack(QuestHelper_ZoneLookup[c[1]])
 227     node.c = cont
 228     node.x, node.y = self.Astrolabe:TranslateWorldMapPosition(cont, zone, c[2], c[3], cont, 0)
 229     node.x = node.x * self.continent_scales_x[node.c]
 230     node.y = node.y * self.continent_scales_y[node.c]
 231     node.name = c[5] or QuestHelper_NameLookup[c[1]]
 232   end
 233
 234   node.w = 1
 235   return node
 236 end
 237
 238 function QuestHelper:CreateAndAddZoneNode(z, c, x, y)
 239   local node = self:CreateGraphNode(c, x, y)
 240
 241   -- Not going to merge nodes.
 242   --[[local closest, travel_time = nil, 0
 243
 244   for i, n in ipairs(z) do
 245     local t = math.sqrt((n.x-node.x)*(n.x-node.x)+(n.y-node.y)*(n.y-node.y))
 246     if not closest or t < travel_time then
 247       closest, travel_time = n, t
 248     end
 249   end
 250
 251   if closest and travel_time < 10 then
 252     closest.x = (closest.x * closest.w + node.x)/(closest.w+1)
 253     closest.y = (closest.y * closest.w + node.y)/(closest.w+1)
 254     closest.w = closest.w + 1
 255     self.world_graph:DestroyNode(node)
 256     return closest
 257   else]]
 258     table.insert(z, node)
 259     return node
 260   --end
 261 end
 262
 263 function QuestHelper:CreateAndAddStaticNodePair(data)
 264   local node1, node2
 265
 266   if data[5] and self.named_nodes[data[5]] then
 267     node1 = self.named_nodes[data[5]]
 268   else
 269     node1 = self:CreateAndAddZoneNode(self.zone_nodes[data[1][1]], data[1])
 270     if data[5] then self.named_nodes[data[5]] = node1 end
 271   end
 272
 273   if data[6] and self.named_nodes[data[6]] then
 274     node2 = self.named_nodes[data[6]]
 275   else
 276     node2 = self:CreateAndAddZoneNode(self.zone_nodes[data[2][1]], data[2])
 277     if data[6] then self.named_nodes[data[6]] = node2 end
 278   end
 279
 280   node1.name = node1.name or "route to "..QuestHelper_NameLookup[data[2][1]]
 281   node2.name = node2.name or "route to "..QuestHelper_NameLookup[data[1][1]]
 282
 283   node1:Link(node2, data[3])
 284
 285   if not data[4] then -- If data[4] is true, then this is a one-way trip.
 286     node2:Link(node1, data[3])
 287   end
 288
 289   self:yieldIfNeeded(0.1)
 290   return node1, node2
 291 end
 292
 293 function QuestHelper:GetNodeByName(name, fallback_data)
 294   local node = self.named_nodes[name]
 295   if not node and fallback_data then
 296     node = self:CreateAndAddZoneNode(self.zone_nodes[fallback_data[1]], fallback_data)
 297     self.named_nodes[name] = node
 298   end
 299   return node
 300 end
 301
 302 local function nodeLeavesContinent(node, c)
 303   if node.c == c then
 304     for n, d in pairs(node.n) do
 305       if n.c ~= c then
 306         return true
 307       end
 308     end
 309   end
 310   return false
 311 end
 312
 313 local function isGoodPath(start_node, end_node, i, j)
 314   -- Checks to make sure a path doesn't leave the continent only to reenter it.
 315   while true do
 316     if end_node.p then
 317       if end_node.c == i then
 318         return false
 319       end
 320       end_node = end_node.p
 321       if end_node.c == j then
 322         return false
 323       end
 324     else
 325       return end_node == start_node
 326     end
 327   end
 328 end
 329
 330 local function shouldLink(a, b)
 331   -- TODO: Need to have objectives not create links to unreachable nodes.
 332   return a ~= b
 333   --[[
 334   if a == b then
 335     return false
 336   else
 337     for id in pairs(a.id_from) do
 338       if not b.id_to[id] then
 339         for id in pairs(b.id_to) do
 340           if not a.id_from[id] then
 341             return true
 342           end
 343         end
 344       end
 345     end
 346
 347     return false
 348   end]]
 349 end
 350
 351 local function getNPCNode(npc)
 352   local npc_objective = QuestHelper:GetObjective("monster", npc)
 353   if npc_objective:Known() then
 354     npc_objective:PrepareRouting()
 355     local p = npc_objective:Position()
 356     local node = nil
 357
 358     if p then
 359       node = QuestHelper:CreateAndAddZoneNode(p[1], p[1].c, p[3], p[4])
 360     end
 361
 362     npc_objective:DoneRouting()
 363     return node
 364   end
 365   return nil
 366 end
 367
 368 function QuestHelper:CreateAndAddTransitionNode(z1, z2, pos)
 369   local node = self:CreateGraphNode(pos)
 370
 371   local closest, travel_time = nil, 0
 372
 373   for i, n in ipairs(z1) do
 374     local t = math.sqrt((n.x-node.x)*(n.x-node.x)+(n.y-node.y)*(n.y-node.y))
 375     if not closest or t < travel_time then
 376       closest, travel_time = n, t
 377     end
 378   end
 379
 380   if z1 ~= z2 then
 381     for i, n in ipairs(z2) do
 382       local t = math.sqrt((n.x-node.x)*(n.x-node.x)+(n.y-node.y)*(n.y-node.y))
 383       if not closest or t < travel_time then
 384         closest, travel_time = n, t
 385       end
 386     end
 387   end
 388
 389   if closest and travel_time < 10 then
 390     --QuestHelper:TextOut("Node already exists at "..closest.x..", "..closest.y..", name="..(closest.name or "nil"))
 391     closest.x = (closest.x * closest.w + node.x)/(closest.w+1)
 392     closest.y = (closest.y * closest.w + node.y)/(closest.w+1)
 393     closest.w = closest.w + 1
 394     local z1_has, z2_has = false, false
 395
 396     -- Just because the node already exists, doesn't mean its already in both lists!
 397
 398     for i, n in ipairs(z1) do
 399       if n == closest then
 400         z1_has = true
 401         break
 402       end
 403     end
 404
 405     if z1 ~= z2 then
 406       for i, n in ipairs(z2) do
 407         if n == closest then
 408           z2_has = true
 409           break
 410         end
 411       end
 412     else
 413       z2_has = true
 414     end
 415
 416     if not z1_has then table.insert(z1, closest) end
 417     if not z2_has then table.insert(z2, closest) end
 418
 419     self.world_graph:DestroyNode(node)
 420     self:yieldIfNeeded(0.2)
 421     return closest
 422   else
 423     table.insert(z1, node)
 424     if z1 ~= z2 then table.insert(z2, node) end
 425     self:yieldIfNeeded(0.1)
 426     return node
 427   end
 428 end
 429
 430 function QuestHelper:ReleaseObjectivePathingInfo(o)
 431   if o.setup then
 432     for z, pl in pairs(o.p) do
 433       self:ReleaseTable(o.d[z])
 434
 435       for i, p in ipairs(pl) do
 436         self:ReleaseTable(p[2])
 437         self:ReleaseTable(p)
 438       end
 439
 440       self:ReleaseTable(pl)
 441     end
 442
 443     self:ReleaseTable(o.d)
 444     self:ReleaseTable(o.p)
 445     self:ReleaseTable(o.nm)
 446     self:ReleaseTable(o.nm2)
 447     self:ReleaseTable(o.nl)
 448
 449     local cache = o.distance_cache
 450     for k, v in pairs(cache) do
 451       self:ReleaseTable(v)
 452       cache[k] = nil
 453     end
 454     self:ReleaseTable(cache)
 455
 456     o.d, o.p, o.nm, o.nm2, o.nl = nil, nil, nil, nil, nil
 457     o.distance_cache = nil
 458     o.pos, o.sop = nil, nil -- ResetPathing will preserve these values if needed.
 459     o.setup = nil
 460   end
 461 end
 462
 463 function QuestHelper:SetupTeleportInfo(info, can_create)
 464   self:TeleportInfoClear(info)
 465
 466   if QuestHelper_Home then
 467     local node = self:GetNodeByName("HOME_PORTAL", can_create and QuestHelper_Home)
 468     if node then
 469       local cooldown = self:ItemCooldown(6948)
 470       if cooldown then
 471         self:SetTeleportInfoTarget(info, node, GetTime()-60*60+cooldown, 60*60, 10)
 472       end
 473     else
 474       self.defered_graph_reset = true
 475     end
 476   end
 477
 478   -- TODO: Compact this. . . and find a better way to tell if the player has a spell.
 479
 480   if GetSpellTexture("Teleport: Darnassus") then
 481     local node = self:GetNodeByName("DARNASSUS_PORTAL", can_create and DARNASSUS_PORTAL)
 482     if node then self:SetTeleportInfoTarget(info, node, 0, 0, 10, 17031) else self.defered_graph_reset = true end
 483   end
 484
 485   if GetSpellTexture("Teleport: Exodar") then
 486     local node = self:GetNodeByName("EXODAR_PORTAL", can_create and EXODAR_PORTAL)
 487     if node then self:SetTeleportInfoTarget(info, node, 0, 0, 10, 17031) else self.defered_graph_reset = true end
 488   end
 489
 490   if GetSpellTexture("Teleport: Ironforge") then
 491     local node = self:GetNodeByName("IRONFORGE_PORTAL", can_create and IRONFORGE_PORTAL)
 492     if node then self:SetTeleportInfoTarget(info, node, 0, 0, 10, 17031) else self.defered_graph_reset = true end
 493   end
 494
 495   if GetSpellTexture("Teleport: Moonglade") then
 496     local node = self:GetNodeByName("MOONGLADE_PORTAL", can_create and MOONGLADE_PORTAL)
 497     if node then self:SetTeleportInfoTarget(info, node, 0, 0, 10) else self.defered_graph_reset = true end
 498   end
 499
 500   if GetSpellTexture("Teleport: Orgrimmar") then
 501     local node = self:GetNodeByName("ORGRIMMAR_PORTAL", can_create and ORGRIMMAR_PORTAL)
 502     if node then self:SetTeleportInfoTarget(info, node, 0, 0, 10, 17031) else self.defered_graph_reset = true end
 503   end
 504
 505   if GetSpellTexture("Teleport: Shattrath") then
 506     local node = self:GetNodeByName("SHATTRATH_CITY_PORTAL", can_create and SHATTRATH_CITY_PORTAL)
 507     if node then self:SetTeleportInfoTarget(info, node, 0, 0, 10, 17031) else self.defered_graph_reset = true end
 508   end
 509
 510   if GetSpellTexture("Teleport: Silvermoon") then
 511     local node = self:GetNodeByName("SILVERMOON_CITY_PORTAL", can_create and SILVERMOON_CITY_PORTAL)
 512     if node then self:SetTeleportInfoTarget(info, node, 0, 0, 10, 17031) else self.defered_graph_reset = true end
 513   end
 514
 515   if GetSpellTexture("Teleport: Stormwind") then
 516     local node = self:GetNodeByName("STORMWIND_CITY_PORTAL", can_create and STORMWIND_CITY_PORTAL)
 517     if node then self:SetTeleportInfoTarget(info, node, 0, 0, 10, 17031) else self.defered_graph_reset = true end
 518   end
 519
 520   if GetSpellTexture("Teleport: Thunder Bluff") then
 521     local node = self:GetNodeByName("THUNDER_BLUFF_PORTAL", can_create and THUNDER_BLUFF_PORTAL)
 522     if node then self:SetTeleportInfoTarget(info, node, 0, 0, 10, 17031) else self.defered_graph_reset = true end
 523   end
 524
 525   if GetSpellTexture("Teleport: Undercity") then
 526     local node = self:GetNodeByName("UNDERCITY_PORTAL", can_create and UNDERCITY_PORTAL)
 527     if node then self:SetTeleportInfoTarget(info, node, 0, 0, 10, 17031) else self.defered_graph_reset = true end
 528   end
 529
 530   self:SetTeleportInfoReagent(info, 17031, self:CountItem(17031))
 531 end
 532
 533 function QuestHelper:ResetPathing()
 534   for key in pairs(self.named_nodes) do
 535     self.named_nodes[key] = nil
 536   end
 537
 538   -- Objectives may include cached information that depends on the world graph.
 539   local i = 1
 540
 541   while i <= #self.prepared_objectives do
 542     local o = self.prepared_objectives[i]
 543
 544     if o.setup_count == 0 then
 545       table.remove(self.prepared_objectives, i)
 546       self:ReleaseObjectivePathingInfo(o)
 547     else
 548       -- Routing should reset the positions of objectives in the route after the reset is complete.
 549       o.pos = nil
 550       self:ReleaseObjectivePathingInfo(o)
 551       i = i + 1
 552     end
 553   end
 554
 555   local to_readd = self.prepared_objectives
 556   self.prepared_objectives = self.old_prepared_objectives or {}
 557   self.old_prepared_objectives = to_readd
 558
 559   local zone_nodes = self.zone_nodes
 560   if not zone_nodes then
 561     zone_nodes = {}
 562     self.zone_nodes = zone_nodes
 563   end
 564
 565   local flight_master_nodes = self.flight_master_nodes
 566   if not flight_master_nodes then
 567     flight_master_nodes = {}
 568     self.flight_master_nodes = flight_master_nodes
 569   else
 570     for key in pairs(flight_master_nodes) do
 571       flight_master_nodes[key] = nil
 572     end
 573   end
 574
 575   self.world_graph:Reset()
 576   self:yieldIfNeeded(0.1)
 577
 578   local continent_scales_x, continent_scales_y = self.continent_scales_x, self.continent_scales_y
 579   if not continent_scales_x then
 580     continent_scales_x = {}
 581     continent_scales_y = {}
 582     self.continent_scales_x = continent_scales_x
 583     self.continent_scales_y = continent_scales_y
 584   end
 585
 586   for c=1,select("#", GetMapContinents()) do
 587     if not continent_scales_x[c] then
 588       local _, x, y = self.Astrolabe:ComputeDistance(c, 0, 0.25, 0.25, c, 0, 0.75, 0.75)
 589
 590       continent_scales_x[c] = x*walkspeed_multiplier*2
 591       continent_scales_y[c] = y*walkspeed_multiplier*2
 592     end
 593   end
 594
 595   for i, name in pairs(QuestHelper_NameLookup) do
 596     local z = zone_nodes[i]
 597     if not z then
 598       z = {}
 599       zone_nodes[i] = z
 600       z.i, z.c, z.z = i, unpack(QuestHelper_ZoneLookup[i])
 601     else
 602       for key in pairs(z) do
 603         z[key] = nil
 604       end
 605       z.i, z.c, z.z = i, unpack(QuestHelper_ZoneLookup[i])
 606     end
 607   end
 608
 609   self:SetupTeleportInfo(self.teleport_info, true)
 610   self:yieldIfNeeded(0.1)
 611
 612   --[[for node, info in pairs(self.teleport_info.node) do
 613     self:TextOut("You can teleport to "..(node.name or "nil").. " in "..self:TimeString(info[1]+info[2]-GetTime()))
 614   end]]
 615
 616   if self.faction == 1 then
 617     for i, data in ipairs(static_alliance_routes) do
 618       self:CreateAndAddStaticNodePair(data)
 619     end
 620   elseif self.faction == 2 then
 621     for i, data in ipairs(static_horde_routes) do
 622       self:CreateAndAddStaticNodePair(data)
 623     end
 624   end
 625
 626   for i, data in ipairs(static_shared_routes) do
 627     self:CreateAndAddStaticNodePair(data)
 628   end
 629
 630   if self.player_level >= 58 then
 631     dark_portal_route[3] = 5
 632   else
 633     -- If you can't take the route yet, we'll still add it and just pretend it will take a really long time.
 634     dark_portal_route[3] = 86400
 635   end
 636
 637   self:CreateAndAddStaticNodePair(dark_portal_route)
 638
 639   local st = self:CreateTable()
 640
 641   for i, data in pairs(static_zone_transitions) do
 642     st[1], st[2], st[3] = data[1], data[3], data[4]
 643
 644     self:CreateAndAddTransitionNode(zone_nodes[data[1]],
 645                                     zone_nodes[data[2]],
 646                                     st).name = QHFormat("ZONE_BORDER", QuestHelper_NameLookup[data[1]], QuestHelper_NameLookup[data[2]])
 647   end
 648
 649   self:ReleaseTable(st)
 650
 651   -- Create and link the flight route nodes.
 652   local flight_times = self.flight_times
 653   if not flight_times then
 654     self:buildFlightTimes()
 655     flight_times = self.flight_times
 656   end
 657
 658   for start, list in pairs(flight_times) do
 659     for dest, duration in pairs(list) do
 660       local a_npc, b_npc = self:getFlightInstructor(start), self:getFlightInstructor(dest)
 661
 662       if a_npc and b_npc then
 663         local a, b = flight_master_nodes[start], flight_master_nodes[dest]
 664
 665         if not a then
 666           a = getNPCNode(a_npc)
 667           if a then
 668             flight_master_nodes[start] = a
 669             a.name = (select(3, string.find(start, "^(.*),")) or start).." flight point"
 670           end
 671         end
 672
 673         if not b then
 674           b = getNPCNode(b_npc)
 675           if b then
 676             flight_master_nodes[dest] = b
 677             b.name = (select(3, string.find(dest, "^(.*),")) or dest).." flight point"
 678           end
 679         end
 680
 681         if a and b then
 682           a:Link(b, duration+5)
 683         end
 684       end
 685     end
 686     self:yieldIfNeeded(0.1)
 687   end
 688
 689   -- id_from, id_to, and id_local will be used in determining whether there is a point to linking nodes together.
 690   for i, n in ipairs(self.world_graph.nodes) do
 691     n.id_from = self:CreateTable()
 692     n.id_to = self:CreateTable()
 693     n.id_local = self:CreateTable()
 694   end
 695
 696   -- Setup the local ids a node exists in.
 697   for i, list in pairs(zone_nodes) do
 698     for _, n in ipairs(list) do
 699       n.id_local[i] = true
 700       n.id_to[i] = true
 701       n.id_from[i] = true
 702     end
 703   end
 704
 705   -- Figure out where each node can come from or go to.
 706   for i, list in pairs(zone_nodes) do
 707     for _, node in ipairs(list) do
 708       for n in pairs(node.n) do
 709         for id in pairs(n.id_local) do node.id_to[id] = true end
 710         for id in pairs(node.id_local) do n.id_from[id] = true end
 711       end
 712     end
 713   end
 714
 715   -- We'll treat 0 as a special id for where ever it is the player happens to be.
 716   for node in pairs(self.teleport_info.node) do
 717     node.id_from[0] = true
 718   end
 719
 720   -- Will go through each zone and link all the nodes we have so far with every other node.
 721   for _, list in pairs(zone_nodes) do
 722     for i = 1,#list do
 723       for j = 1,#list do
 724         if shouldLink(list[i], list[j]) then
 725           list[i]:Link(list[j], cont_dist(list[i], list[j]))
 726         end
 727       end
 728     end
 729   end
 730
 731   self:yieldIfNeeded(0.1)
 732
 733   -- We don't need to know where the nodes can go or come from now.
 734   for i, n in ipairs(self.world_graph.nodes) do
 735     self:ReleaseTable(n.id_from)
 736     self:ReleaseTable(n.id_to)
 737     self:ReleaseTable(n.id_local)
 738     n.id_from, n.id_to, n.id_local = nil, nil, nil
 739   end
 740
 741   -- TODO: This is a work around until I fix shouldLink
 742   for start, list in pairs(flight_times) do
 743     for dest, duration in pairs(list) do
 744       local a, b = flight_master_nodes[start], flight_master_nodes[dest]
 745       if a and b then
 746         a:Link(b, duration+5)
 747       end
 748     end
 749   end
 750
 751   self:yieldIfNeeded(0.1)
 752   -- self.world_graph:SanityCheck()
 753
 754   -- Remove objectives again, since we created some for the flight masters.
 755   while true do
 756     local o = table.remove(self.prepared_objectives)
 757     if not o then break end
 758
 759     self:ReleaseObjectivePathingInfo(o)
 760
 761     if o.setup_count > 0 then
 762       -- There's a chance an objective could end up in the list twice, but we'll deal with that by not actually
 763       -- adding locations for it if it's already setup.
 764       table.insert(to_readd, o)
 765     end
 766   end
 767
 768   while true do
 769     local obj = table.remove(to_readd)
 770     if not obj then break end
 771
 772     if not obj.setup then -- In case the objective was added multiple times to the to_readd list.
 773       obj.d = QuestHelper:CreateTable()
 774       obj.p = QuestHelper:CreateTable()
 775       obj.nm = QuestHelper:CreateTable()
 776       obj.nm2 = QuestHelper:CreateTable()
 777       obj.nl = QuestHelper:CreateTable()
 778       obj.distance_cache = QuestHelper:CreateTable()
 779       obj:AppendPositions(obj, 1, nil)
 780       obj:FinishAddLoc()
 781     end
 782   end
 783
 784   if self.i then
 785     self.pos[1] = self.zone_nodes[self.i]
 786     for i, n in ipairs(self.pos[1]) do
 787       local a, b = n.x-self.pos[3], n.y-self.pos[4]
 788       self.pos[2][i] = math.sqrt(a*a+b*b)
 789     end
 790   end
 791
 792   -- And if all went according to plan, we now have a graph we can follow to get from anywhere to anywhere.
 793
 794   if self.graph_walker then
 795     self.graph_walker:GraphChanged()
 796   end
 797 end