pathfinding.lua

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