pathfinding.lua

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