6 added 13 characters in body edited Dec 7 '13 at 12:33 Engineer 26.8k33 gold badges5757 silver badges112112 bronze badges 3 cases can occur, where your entity is standing: exactly upon a node (no problem here) between 4 nodes (as per your example -- we need to fix) 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: exactly upon a node (no problem here) between 4 nodes (as per your example -- we need to fix) 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: exactly upon a node (no problem here) between 4 nodes (as per your example -- we need to fix) 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 edited Dec 7 '13 at 12:27 Engineer 26.8k33 gold badges5757 silver badges112112 bronze badges There are 3 cases that can occur, where your entity is standing: exactly upon a node (no problem here) between 4 nodes (as per your example -- we need to fix) 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: exactly upon a node (no problem here) between 4 nodes (as per your example -- we need to fix) 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: exactly upon a node (no problem here) between 4 nodes (as per your example -- we need to fix) 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 edited Dec 7 '13 at 12:22 Engineer 26.8k33 gold badges5757 silver badges112112 bronze badges There are 3 cases that can occur, where your entity is standing: exactly upon a node (no problem here) between 4 nodes (as per your example -- we need to fix) 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: exactly upon a node (no problem here) between 4 nodes (as per your example -- we need to fix) 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: exactly upon a node (no problem here) between 4 nodes (as per your example -- we need to fix) 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 edited Dec 7 '13 at 12:16 Engineer 26.8k33 gold badges5757 silver badges112112 bronze badges 2 added 32 characters in body edited Dec 7 '13 at 12:11 Engineer 26.8k33 gold badges5757 silver badges112112 bronze badges 1 answered Dec 7 '13 at 12:05 Engineer 26.8k33 gold badges5757 silver badges112112 bronze badges