6 added 13 characters in body
source | link

3 cases can occur, where your entity is standing:

  1. exactly upon a node (no problem here)
  2. between 4 nodes (as per your example -- we need to fix)
  3. on the grid boundary between exactly 2 nodes (need to fix)

Given a choice of 2+ local candidates to start from, which do we gravitate toward, before proceeding on the Dijkstra-calculated path? Obviously, that which is furthest along the path.

target = ...;
nearest = getEuclideanNearestNode(map, entity); //this would return D in your case
pathList = dijkstra(map, nearest , target); //calculated path ordered from D to A
localCandidates = getGridNearestNodes(map, entity); //return 1, 2 or 4 nodes: any order

if localCandidates.length > 1
    bestStartingCandidateNode = undefined;

    for each node n in pathList //move toward end of list
        for each node c in localCandidates
            if c == n
                 //each time we find a candidate further along, we overwrite the old best
                bestStartingCandidateNode = c
                break; //inner loop only
        remove c from localCandidates

    entity.moveTo(bestStartingCandidateNode);
else
    bestStartingCandidateNode = localCandidates[0];

//now you may proceed along the (remainder of) the path

We have to start with some estimate of the ideal starting node -- that which is nearest as the crow flies (using Pythagoras). Then we get the Dijkstra path, starting at that guesstimate node. Beyond that, we deal with your specific problem: evaluate every surrounding node to see which of these is furthest along the Dijkstra path, and pick that one as the first to proceed from.

We have to first guesss and then later re-evaluate, because until our path is generated, we have no idea which direction it will take, and thus cannot yet pick a best local candidate!

3 cases can occur, where your entity is standing:

  1. exactly upon a node (no problem here)
  2. between 4 nodes (as per your example -- we need to fix)
  3. on the grid boundary between exactly 2 nodes (need to fix)

Given a choice of 2+ local candidates to start from, which do we gravitate toward, before proceeding on the Dijkstra-calculated path? Obviously, that which is furthest along the path.

target = ...;
nearest = getEuclideanNearestNode(map, entity); //this would return D in your case
pathList = dijkstra(map, nearest , target); //calculated path ordered from D to A
localCandidates = getGridNearestNodes(map, entity); //return 1, 2 or 4 nodes: any order

if localCandidates.length > 1
    bestStartingCandidateNode = undefined;

    for each node n in pathList //move toward end of list
        for each node c in localCandidates
            if c == n
                 //each time we find a candidate further along, we overwrite the old best
                bestStartingCandidateNode = c
                break;
        remove c from localCandidates

    entity.moveTo(bestStartingCandidateNode);
else
    bestStartingCandidateNode = localCandidates[0];

//now you may proceed along the (remainder of) the path

We have to start with some estimate of the ideal starting node -- that which is nearest as the crow flies (using Pythagoras). Then we get the Dijkstra path, starting at that guesstimate node. Beyond that, we deal with your specific problem: evaluate every surrounding node to see which of these is furthest along the Dijkstra path, and pick that one as the first to proceed from.

We have to first guesss and then later re-evaluate, because until our path is generated, we have no idea which direction it will take, and thus cannot yet pick a best local candidate!

3 cases can occur, where your entity is standing:

  1. exactly upon a node (no problem here)
  2. between 4 nodes (as per your example -- we need to fix)
  3. on the grid boundary between exactly 2 nodes (need to fix)

Given a choice of 2+ local candidates to start from, which do we gravitate toward, before proceeding on the Dijkstra-calculated path? Obviously, that which is furthest along the path.

target = ...;
nearest = getEuclideanNearestNode(map, entity); //this would return D in your case
pathList = dijkstra(map, nearest , target); //calculated path ordered from D to A
localCandidates = getGridNearestNodes(map, entity); //return 1, 2 or 4 nodes: any order

if localCandidates.length > 1
    bestStartingCandidateNode = undefined;

    for each node n in pathList //move toward end of list
        for each node c in localCandidates
            if c == n
                 //each time we find a candidate further along, we overwrite the old best
                bestStartingCandidateNode = c
                break; //inner loop only
        remove c from localCandidates

    entity.moveTo(bestStartingCandidateNode);
else
    bestStartingCandidateNode = localCandidates[0];

//now you may proceed along the (remainder of) the path

We have to start with some estimate of the ideal starting node -- that which is nearest as the crow flies (using Pythagoras). Then we get the Dijkstra path, starting at that guesstimate node. Beyond that, we deal with your specific problem: evaluate every surrounding node to see which of these is furthest along the Dijkstra path, and pick that one as the first to proceed from.

We have to first guesss and later re-evaluate, because until our path is generated, we have no idea which direction it will take, and thus cannot yet pick a best local candidate!

5 edited body
source | link

There are 3 cases that can occur, where your entity is standing:

  1. exactly upon a node (no problem here)
  2. between 4 nodes (as per your example -- we need to fix)
  3. on the grid boundary between exactly 2 nodes (need to fix)

Given a choice of a number (2+) of candidate starting nodes2+ local candidates to start from, how wewhich do we decide which one to gravitate toward, before proceeding on the Dijkstra-calculated path? Obviously, that which is furthest along the path.

target = ...;
nearest = getEuclideanNearestNode(map, entity); //this would return D in your case
pathList = dijkstra(map, nearest , target); //calculated path ordered from D to A
localCandidates = getGridNearestNodes(map, entity); //return 1, 2 or 4 nodes: any order

if localCandidates.length > 1
    bestStartingCandidateNode = undefined;

    for each node n in pathList //move toward end of list
        for each node c in localCandidates
            if c == n
                 //each time we find a candidate further along, we overwrite the old best
                bestStartingCandidateNode = c
                break;
        remove c from localCandidates

    entity.moveTo(bestStartingCandidateNode);
else
    bestStartingCandidateNode = localCandidates[0];

//now you may proceed along the (remainder of) the path

We are just evaluatinghave to start with some estimate of the ideal starting node -- that which is nearest as the crow flies (using Pythagoras). Then we get the Dijkstra path, starting at that guesstimate node. Beyond that, we deal with your specific problem: evaluate every localsurrounding node to see which of these is furtherfurthest along the Dijkstra path, then pickingand pick that one as the first to proceed from.

We have to first guesss and then later re-evaluate, because until our path is generated, we have no idea which direction it will take, and thus cannot yet pick a best local candidate!

There are 3 cases that can occur, where your entity is standing:

  1. exactly upon a node (no problem here)
  2. between 4 nodes (as per your example -- we need to fix)
  3. on the grid boundary between exactly 2 nodes (need to fix)

Given a choice of a number (2+) of candidate starting nodes, how we do we decide which one to gravitate toward, before proceeding on the Dijkstra-calculated path?

target = ...;
nearest = getEuclideanNearestNode(map, entity); //this would return D in your case
pathList = dijkstra(map, nearest , target); //calculated path ordered from D to A
localCandidates = getGridNearestNodes(map, entity); //return 1, 2 or 4 nodes: any order

if localCandidates.length > 1
    bestStartingCandidateNode = undefined;

    for each node n in pathList //move toward end of list
        for each node c in localCandidates
            if c == n
                 //each time we find a candidate further along, we overwrite the old best
                bestStartingCandidateNode = c
                break;
        remove c from localCandidates

    entity.moveTo(bestStartingCandidateNode);
else
    bestStartingCandidateNode = localCandidates[0];

//now you may proceed along the (remainder of) the path

We are just evaluating every local node to see which is further along the Dijkstra path, then picking that one as the first to proceed from.

3 cases can occur, where your entity is standing:

  1. exactly upon a node (no problem here)
  2. between 4 nodes (as per your example -- we need to fix)
  3. on the grid boundary between exactly 2 nodes (need to fix)

Given a choice of 2+ local candidates to start from, which do we gravitate toward, before proceeding on the Dijkstra-calculated path? Obviously, that which is furthest along the path.

target = ...;
nearest = getEuclideanNearestNode(map, entity); //this would return D in your case
pathList = dijkstra(map, nearest , target); //calculated path ordered from D to A
localCandidates = getGridNearestNodes(map, entity); //return 1, 2 or 4 nodes: any order

if localCandidates.length > 1
    bestStartingCandidateNode = undefined;

    for each node n in pathList //move toward end of list
        for each node c in localCandidates
            if c == n
                 //each time we find a candidate further along, we overwrite the old best
                bestStartingCandidateNode = c
                break;
        remove c from localCandidates

    entity.moveTo(bestStartingCandidateNode);
else
    bestStartingCandidateNode = localCandidates[0];

//now you may proceed along the (remainder of) the path

We have to start with some estimate of the ideal starting node -- that which is nearest as the crow flies (using Pythagoras). Then we get the Dijkstra path, starting at that guesstimate node. Beyond that, we deal with your specific problem: evaluate every surrounding node to see which of these is furthest along the Dijkstra path, and pick that one as the first to proceed from.

We have to first guesss and then later re-evaluate, because until our path is generated, we have no idea which direction it will take, and thus cannot yet pick a best local candidate!

4 edited body
source | link

There are 3 cases that can occur, where your entity is standing:

  1. exactly upon a node (no problem here)
  2. between 4 nodes (as per your example -- we need to fix)
  3. on the grid boundary between exactly 2 nodes (need to fix)

Given a choice of a number (2+) of candidate starting nodes, how we do we decide which one to gravitate toward, before proceeding on the Dijkstra-calculated path?

target = ...;
nearest = getEuclideanNearestNode(map, entity); //this would return D in your case
pathList = dijkstra(map, nearest , target); //calculated path ordered from D to A
localCandidates = getSurroundingNodesgetGridNearestNodes(map, entity); //return 1, 2 or 4 nodes: any order

if localCandidates.length > 1
    bestStartingCandidateNode = undefined;

    for each node n in pathList //move toward end of list
        for each node c in localCandidates
            if c == n
                 //each time we find a candidate further along, we overwrite the old best
                bestStartingCandidateNode = c
                break;
        remove c from localCandidates

    entity.moveTo(bestStartingCandidateNode);
else
    bestStartingCandidateNode = localCandidates[0];

//now you may proceed along the (remainder of) the path

We are just evaluating every local node to see which is further along the Dijkstra path, then picking that one as the first to proceed from.

There are 3 cases that can occur, where your entity is standing:

  1. exactly upon a node (no problem here)
  2. between 4 nodes (as per your example -- we need to fix)
  3. on the grid boundary between exactly 2 nodes (need to fix)

Given a choice of a number (2+) of candidate starting nodes, how we do we decide which one to gravitate toward, before proceeding on the Dijkstra-calculated path?

target = ...;
nearest = getEuclideanNearestNode(map, entity); //this would return D in your case
pathList = dijkstra(map, nearest , target); //calculated path ordered from D to A
localCandidates = getSurroundingNodes(map, entity); //return 1, 2 or 4 nodes: any order

if localCandidates.length > 1
    bestStartingCandidateNode = undefined;

    for each node n in pathList //move toward end of list
        for each node c in localCandidates
            if c == n
                 //each time we find a candidate further along, we overwrite the old best
                bestStartingCandidateNode = c
                break;
        remove c from localCandidates

    entity.moveTo(bestStartingCandidateNode);
else
    bestStartingCandidateNode = localCandidates[0];

//now you may proceed along the (remainder of) the path

We are just evaluating every local node to see which is further along the Dijkstra path, then picking that one as the first to proceed from.

There are 3 cases that can occur, where your entity is standing:

  1. exactly upon a node (no problem here)
  2. between 4 nodes (as per your example -- we need to fix)
  3. on the grid boundary between exactly 2 nodes (need to fix)

Given a choice of a number (2+) of candidate starting nodes, how we do we decide which one to gravitate toward, before proceeding on the Dijkstra-calculated path?

target = ...;
nearest = getEuclideanNearestNode(map, entity); //this would return D in your case
pathList = dijkstra(map, nearest , target); //calculated path ordered from D to A
localCandidates = getGridNearestNodes(map, entity); //return 1, 2 or 4 nodes: any order

if localCandidates.length > 1
    bestStartingCandidateNode = undefined;

    for each node n in pathList //move toward end of list
        for each node c in localCandidates
            if c == n
                 //each time we find a candidate further along, we overwrite the old best
                bestStartingCandidateNode = c
                break;
        remove c from localCandidates

    entity.moveTo(bestStartingCandidateNode);
else
    bestStartingCandidateNode = localCandidates[0];

//now you may proceed along the (remainder of) the path

We are just evaluating every local node to see which is further along the Dijkstra path, then picking that one as the first to proceed from.

3 deleted 14 characters in body
source | link
2 added 32 characters in body
source | link
1
source | link