So, this is one of the big things I've been wanting to add for a long time. Basically, Questie should eventually be able to calculate the most efficient path to complete your current quests, and to pick up new ones along the way. While taking into account the world terrain, not a simple distance calculation. We all know the wow world isn't 2D. This requires using true pathfinding (mangos server for now) to generate a database of step costs between all objectives.

This issue is to consolidate information related to this enhancement as it is worked on.

Challenges:

• An external pathfinding system to calculate step costs between each objective
• An efficient way to store step cost data for each possible objective combination per zone.
• An A* implementation in vanilla-wow compatible Lua

The pathfinding system is already done, I've successfully hacked into the mangoszero server core, and am able to query it's recast/detour instance for any arbitrary path, via a TCP socket.

I believe step costs can be stored by giving each objective a coordinate in n-dimensional space using Eigendecomposition of Gramian matrices made from the distance matrices calculated by mangos server

The problem is, I'm not so good at advanced math and I can't find any code examples of "Eigendecomposition of Gramian matrices". If anyone here is familiar with the math, your help would be an asset.

It's possible this doesn't even solve the problem of "calculate the coordinates for a set of arbitrary points where only their distance between each other is known"

Turns out this is exactly what we needed.

http://stackoverflow.com/a/17177833

http://dev.heuristiclab.com/trac.fcgi/browser/branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior.Analyzers/3.3/DistanceMatrixToPoints.cs?rev=10416

I've successfully generated the data for Elwynn and it used only 2 dimensions so I was able to plot the data:

Took about an hour to generate the distance map, so not too bad.

https://github.com/vhallac/Routes/blob/master/TSP.lua

Hey @AeroScripts ,

Is this still on the radar? Similar to #1565 & #1559 -- this feature would be great, but complicated. You'd want to factor in mountains and walls and such, also probably give people the option to map the optimal route to pick up and well as complete quests. Understandable if it's more trouble than it's worth. (=

@namreeb has been helping with this recently, getting pretty close to completion I'll post back here when he finishes it

Been looking in to this a bit more recently, might be a thing soon but no promises. It's tough because generating the distance matrix for each zone takes a long time

Thankfully python has a class for dealing with this already, put a small example together for future reference

from sklearn.manifold import MDS
import math
import numpy as np

TEST_COUNT = 1000

mds = MDS(n_components=2, dissimilarity='precomputed')
points = np.random.uniform(-300, 300, (TEST_COUNT, 2)) # fill array with random values 
distanceMatrix = np.zeros((TEST_COUNT, TEST_COUNT)) 

def dist(a, b):
	dx = abs(a[0]-b[0])
	dy = abs(a[1]-b[1])
	return math.sqrt(dx*dx + dy*dy)

#calculate distance between all points
for i in range(TEST_COUNT):
	for e in range(TEST_COUNT):
		distanceMatrix[i, e] = dist(points[i], points[e])

#generate new matrix based on distances
mat = mds.fit_transform(distanceMatrix)

#print results (error should be near zero)
print("True\t\tcalculated\terror")
for i in range(32):
	r = dist(points[0], points[i])
	f = dist(mat[0], mat[i])
	print("%f\t%f\t%f" % (r, f, abs(r-f)))

Feeds into #2498