Distance formula to calculate speed between two points

[Vlad]

It's not quite on topic, but let me ask you smart guys;

This is the data:
A -> B
B -> C
C -> D
E -> C
A -> E
B -> A
C -> B
C -> A
A -> C

You see, if you wish to go from A to D you can go:
(1) A->B->C->D
(2) A->C->D
(3) many others involving cycles like A->C->B->A->C->D and so forth...

In any case, I have this system in MySQL:
{PrimKey, X, Y} where PrimKey is an integer, X and Y are the node values. For example A->B is {1, A, B}, then B->C becomes {2, B, C} and so forth.

This is graph theory, traversal of graphs but considering there are cycles this makes it a bit tricky.

I have to make a class i.e. "Map" to help me keep order of who comes and goes to who. This way if I want to go from A to D I can return a list where I get various paths leading to D without the backtracking (A->C->B->A->C->D e.g.) and it shouldn't stuck looping indefinitely.

Do you have some ideas how I should structure this class?

I was thinking something along the lines of:
class Map {
nodes = array();
addNode(node) {
addChild(getParent(node::letter), node) // find A in nodes then add this node as that parents child, if not then add the child as a new root-node with node::letter as index key
}
getRoutes(start, end) {
// traverse the nodes, find any paths starting at start and ending at end, paths not leading to the end are ignored, this I reckon will be a recursive function
}
}

Very rough, maybe someone has a better idea or a tip like example code they know of on the net. :P

[SDPhantom]

A method I could think of is to have it scan out, branching off every time it has a choice based on direction from the origin point. I've had experience in writing functions that run recursively though data without the need to call itself. This usually involves building and managing your own data in a stack-like data structure. You end up using more memory instead of increasing your call stack, which is the best way to avoid stack overflows. It'll take a while to write it all from scratch. I'm assuming this would be in PHP?

[Vlad]

Indeed, php.

[SDPhantom]

I'm looking into writing some code that'll allow you to add paths with a cost metric and the pathfinding AI will choose the lowest cost route. To conserve processing time, it'll "give up" on a path if its cost exceeds that of a route it already discovered.

This method will allow you to customize what you use for a path's cost metric, whether it's the copper cost, distance, or even number of hops. The first two should be easy to figure out, but to do hops, you'll need to set the cost of all paths to a single number greater than zero, like 1.

I may have the pathfinding AI accept a max cost argument that it'll automatically "give up" on if the cost is exceeded.

[SDPhantom]

I have a working prototype running and here's the debug info that it's printing.
The following calls were made to generate this.

addPath("A","B",1);
addPath("A","C",1);
addPath("A","E",1);
addPath("B","A",1);
addPath("B","C",1);
addPath("C","A",1);
addPath("C","B",1);
addPath("C","D",1);
addPath("E","C",1);

findRoute("B","E");

Path Data:

Create: A>B(1)
Add: A>C(1)
Add: A>E(1)
Create: B>A(1)
Add: B>C(1)
Create: C>A(1)
Add: C>B(1)
Add: C>D(1)
Create: E>C(1)

Array
(
    [A] => Array
        (
            [0] => Array
                (
                    [0] => B
                    [1] => 1
                )

            [1] => Array
                (
                    [0] => C
                    [1] => 1
                )

            [2] => Array
                (
                    [0] => E
                    [1] => 1
                )

        )

    [b] => Array
        (
            [0] => Array
                (
                    [0] => A
                    [1] => 1
                )

            [1] => Array
                (
                    [0] => C
                    [1] => 1
                )

        )

    [C] => Array
        (
            [0] => Array
                (
                    [0] => A
                    [1] => 1
                )

            [1] => Array
                (
                    [0] => B
                    [1] => 1
                )

            [2] => Array
                (
                    [0] => D
                    [1] => 1
                )

        )

    [E] => Array
        (
            [0] => Array
                (
                    [0] => C
                    [1] => 1
                )

        )

)

Routing Steps:

Routing B>E
Iterating Stack: 0@0=B>A 0+1=1
Push Stack 1
Iterating Stack: 1@0=A>B 1+1=2
Iterating Stack: 1@1=A>C 1+1=2
Push Stack 2
Iterating Stack: 2@0=C>A 2+1=3
Iterating Stack: 2@1=C>B 2+1=3
Iterating Stack: 2@2=C>D 2+1=3
Pop Stack 2
Iterating Stack: 1@2=A>E 1+1=2
Route Found

Array
(
    [0] => 2
    [1] => B
    [2] => A
    [3] => E
)

Pop Stack 1
Iterating Stack: 0@1=B>C 0+1=1
Push Stack 1
Iterating Stack: 1@0=C>A 1+1=2
Cost Exceeded
Iterating Stack: 1@1=C>B 1+1=2
Cost Exceeded
Iterating Stack: 1@2=C>D 1+1=2
Cost Exceeded
Pop Stack 1
Pop Stack 0

Returned Route:

Array
(
    [0] => B
    [1] => A
    [2] => E
)

[SDPhantom]

Polished off a few checks and removed the debug code. Here's the prototype.

PHP Code:

$paths=array();

function addPath($src,$dst,$cost=1){
    global $paths;

    if($src==$dst || $cost<0) return NULL;
    if($paths[$src]){
        foreach($paths[$src] as $i) if($i[0]==$dst) return false;
    }else
        $paths[$src]=array();

    $paths[$src][]=array($dst,$cost);
    return true;
}

function findRoute($src,$dst,$maxcost=NULL,$maxhops=NULL){
    global $paths;

    if(!$paths[$src]) return NULL;

    $found=false;
    foreach($paths as $i) foreach($i as $j) if($j[0]==$dst){$found=true;break;}
    if(!$found) return false;

    $pstack=array(array($src,0,0));
    while(($id=count($pstack)-1)>=0){
        $ptr=&$pstack[$id];
        if($node=$paths[$ptr[0]][$ptr[1]++]){
            $cost=$ptr[2]+$node[1];
            if($maxcost===NULL || $cost<=$maxcost){
                if($node[0]==$dst){
                    $maxcost=$cost;
                    $route=array();
                    foreach($pstack as $i) $route[]=$i[0];
                    $route[]=$dst;
                    array_pop($pstack);
                }elseif($paths[$node[0]] && ($maxhops===NULL || ($id+1)<$maxhops)){
                    $unique=true;
                    foreach($pstack as $i) if($i[0]==$node[0]){$unique=false;break;}
                    if($unique)
                        array_push($pstack,array($node[0],0,$cost));
                }
            }
        }else
            array_pop($pstack);
    }

    return $route?$route:false;
} 


Notes:
addPath() returns true on success, false on duplicates, and NULL on error.
findRoute() returns an array on success, false if no path found, and NULL on error.

[Vlad]

Wow SDPhantom, you really put effort into this code, thanks!

I got the basic idea, just trying to sort off cycles now, as it gets stuck looping in a circle thinking it goes forward. I need to add a "visited" check to skip going where we've already been I reckon.

[SDPhantom]

Strange, can you post a copy of the paths you're registering? When it checks a path, it looks back into the stack to see if the node isn't already in there. With a bigger data set, it would often recheck paths again when going back up the stack. You can try setting the maxcost to limit how far it runs away with this.

[Vlad]

http://pastebin.com/e0LfewY1

For example if I do this:
findRoute(2, 15);

The output of the id is this:

0>1>1>2>2>2>3>3>3>3>4>4>4>4>5>5>5>5>5>6>6>7>7>7>6>5>6>6>6>6>5>4>5>6>7>7>7>7>7>7>8>8>8>8>7>6>6>5>5>4>5>6>6>6>7>7>8>9>9>10>10>11>11>11>12>12>12>12>13>13>14>14>14>14>15>15>16>16>16>16>16>17>17>18>19>20>20>21>21>22>22>23>24>25>25>26>26>26>26>27>27>27>28>28>28>29>29>29>30>31>31>31>31>30>30>29>28>27>27>28>29>29>30>31>31>31>31>30>30>30>29>28>28>28>27>...

It keeps repeating after the dots... going back to 26 then up to 31 and back to 26, e.g. It's a bit odd indeed, are you getting that too?

[SDPhantom]

The stack ID only reflects the size of the stack at the time, it'll always be going up and down until it's all done. It's pretty much equal to how many hops it's at in its current path.

[SDPhantom]

I looked at the DBC data over and discovered that no paths lead to #15. I added in a check for this before it starts pathing and an additional maxhops argument. I would suggest using it to cut down on processing time. You may use NULL to bypass the maxcost argument.

For example, this'll trace an alliance route from Booty Bay to Light's Hope Chapel with a max of 10 hops.

findNode(19,67,NULL,10);

The code in my previous post has been updated with these changes.

PS: You should only load in paths accessible to a specific faction to help in processing if by chance it's queried for a route cross faction. It can also wander over into cross faction routes if it hits shared paths. It seems the value following the unknown horde/alliance IDs is indeed a 3-bit faction flag. Bit 1 is alliance and bit 2 is horde. I see bit 3 set in a few paths, but it's unknown what that means at this point.

[Vlad]

Hmm, really? Maybe I used a node no longer accessible, should have used the lighthope chapel one, sorry for my mistake too, kind of set you on the wrong path.

Yes, you are right about the faction thing, should not mix them up.

*Edit*

Very nice mate, couldn't have done this all by myself -tough I should, had graph theory in Java a year ago.

Anyway, got it working on my end as well, made a class for it and it only reads in paths that are accessible for the faction when I am flying around in my virtual WoW.

*Edit 2*

I ran some calculations for 10 paths from Stormwind, the results were (time in HH:MM:SS):

Stormwind, Elwynn -> Sentinel Hill, Westfall takes 00:01:11
Stormwind, Elwynn -> Lakeshire, Redridge takes 00:01:50
Stormwind, Elwynn -> Ironforge, Dun Morogh takes 00:03:32
Stormwind, Elwynn -> Menethil Harbor, Wetlands takes 00:05:28
Stormwind, Elwynn -> Thelsamar, Loch Modan takes 00:05:13
Stormwind, Elwynn -> Darkshire, Duskwood takes 00:01:53
Stormwind, Elwynn -> Refuge Pointe, Arathi takes 00:06:53
Stormwind, Elwynn -> Booty Bay, Stranglethorn takes 00:03:15
Stormwind, Elwynn -> Aerie Peak, The Hinterlands takes 00:07:29
Stormwind, Elwynn -> Nethergarde Keep, Blasted Lands takes 00:02:53

Checking the InFlight data that contains the proper times (+-1/2 seconds difference, since latency has something to say on the arrival time as well), in any case these were the differences in seconds:

Stormwind, Elwynn -> Sentinel Hill, Westfall takes (71-73) -2
Stormwind, Elwynn -> Lakeshire, Redridge takes (110-113) = -3
Stormwind, Elwynn -> Ironforge, Dun Morogh takes (212-215) = -3
Stormwind, Elwynn -> Menethil Harbor, Wetlands takes (328-233) = 95
Stormwind, Elwynn -> Thelsamar, Loch Modan takes (313-212) = 101
Stormwind, Elwynn -> Darkshire, Duskwood takes (113-116) = -3
Stormwind, Elwynn -> Refuge Pointe, Arathi takes (413-375) = 38
Stormwind, Elwynn -> Booty Bay, Stranglethorn takes (195-198) = -3
Stormwind, Elwynn -> Aerie Peak, The Hinterlands takes (449-412) = 37
Stormwind, Elwynn -> Nethergarde Keep, Blasted Lands takes (173-176) = -3

Those that are heavily out of mark like Menethil Harbor, Thelsamar, Refuge Pointe, Aerie Peak, those I think are because of my coding of the faction check, if not then something else must have gone wrong, since the others are up to 3 seconds quicker than what InFlight says the times are, 3 seconds is not bad at all considering it's all calculated trough formulas and not stopwatch.

With some fine tuning like adding delay because of the "wobble" effect (large angles, high distances, create a slight deviation in the distance calculation, this is not yet addressed in the code), and proper faction checks to allow neutral paths when flying as any faction but restrict the path finding to either Alliance or Horde and avoid mixing those.

Perhaps these huge deviations may be due to result of flights going quicker than the constant speed I calculate with (30+1/3), maybe those paths used quicker flight speeds, so this also has to be added in the code.

This was my "report" on the matter for now, when this is done I'll share my code for anyone to use that needs to calculate taxi flight times. :P

[Seerah]

Do your calculations account for when the taxi circles before landing?

[Vlad]

Yes it should, hard to tell atm because I need to implement the various speeds on some flightpaths, hehe.

For many regular gryphon based flightpaths with regular speeds the calculations return answers within 3 seconds of the InFlight data, I guess the last 3 seconds are due to latency; it takes a up to a second to start flying and landing and some minor delays due to wobble effect or when jumping from a node to node in general.

I think Ironforge may be the cause of the weird timers on my end, probably because the game does not fly in the city when flying on a connected path, it skips some nodes that I include in the calculations most likely, need to research more.

[Seerah]

Ah, yes, that would definitely be a contributing factor. SW, too.

[Vlad]

Something I noticed about GetUnitSpeed:

The API returns different values but very small changes, decimals only.

Still, at long paths this may change the time up to 10 seconds at worst, maybe this has something to do with lag compensation?

I.e. if the average player ms is 500 then the game would make up for the time lost in between node connections (i.e. sw->goldshire->redrige), each "->" jump would need to be confirmed with the server so if the mount visually flies quicker and the client comes at the last node and requests the next path, it has accounted for the slight delay ocuring so you wouldn't loose time.

Somehow it doesn't make any sense because the location of the player is anyway decided by the server, that explains why I've sometimes seen me land earlier than I should by having my flight just teleport me the last 40 yards instead of flying and landing like it should have.

The gryphons (creature 541) flies between 30.1 to 30.4 so any decimals in between, very weird and hard to account for when flying, thus even tracking the time with a stopwatch would always return 1-3 seconds differences between flights due to this randomness...

Still, some seconds off the mark is not a big deal considering you still know you got over 13 minutes of flying if you want to fly from Booty Bay to Eastern Plaguelands.

[Saiket]

I spent a weekend trying to figure out the flight-path mechanics, and while I did come pretty close to accurately modeling them, I'm stumped by a few issues. Since I doubt I'll make anymore progress without a big time commitment, here's what I've found so far:

1. WoW smooths the paths between TaxiPathNode points using splines—specifically, Catmull-Rom splines. I wrote a test addon so I could experimentally compare expected and measured flightpaths, and Catmull-Rom seems 100% accurate.

   
   Cyan line is the expected path, red line is the measured path, alternating yellow and purple sets of dots mark joined path splines' control points, yellow gridlines are map chunk boundaries, and the red crosshair centers on the player.

2. For multi-part flights, WoW takes the shortest combination of paths, unless a direct route is available. The "length" of a path is the length of the Catmull-Rom spline in 3D space, found through integration.

   

3. Where two paths join together, WoW seems to dynamically strip away spline control points between them that would make too sharp a turn. I didn't attempt to reverse engineer the algorithm, since it would just be a bunch of guesswork and tweaking without WoW's source code available. My test addon defines a function GetSkippedNodes in case anyone wants to attempt to implement this properly. For now, it returns placeholder values 1,1 to skip one innermost point from each joined path. Here are a few examples where paths join incorrectly:

   
   While I was taking screenshots for this post, I noticed that last example where WoW actually makes a tight turn. Who knows.

4. I couldn't find any way to estimate flight-path speeds. It's definitely not constant across all paths, and instead seems to be determined by the node you depart from. The NPC ID of your flight-path mount (from TaxiNodes) works the same way, but I don't know if your mount affects your speed here. Even if it does, I couldn't find a lookup for NPC speed in my cache files or the DBCs.
   
   I have noticed that flight-path speed appears to vary, but GetUnitSpeed doesn't reflect it. I assume any visual speed change is just rubber-banding when you periodically synchronize your flight-path progress with the server.

Overall it's still pretty inaccurate because of lag, unknown speed, and the path joint issue. Oh well, it was still a fun project.

My test mod is attached if anyone wants to play with it. "/taxi" opens the grid, and you can navigate around sort of like Google Maps. If you talk with a flight master while the grid is open, hovering over nodes will plot their expected paths.

[Vlad]

Very informative post, thanks for sharing your findings!

Very interesting, catmull-rom splines, haven't heard of that until now, gotta look into this!