1
\$\begingroup\$

I'm using Dijkstra algorithm to find shortest path and I'm drawing this path on the screen. As the character object moves on, path updates itself(shortens as the object approaches the target and gets longer as the object moves away from it.) I tried to visualize my problem.

This is the beginning state. 'A' node is the target, path is the blue and the object is the green one.

enter image description here

I draw this path, from object to the closest node. In this case my problem occurs. Because 'D' node is more closer to the object than 'C' node, something like this happens:

enter image description here

So, how can i decide that the object passed the 'D' node? Path should be look like this:

enter image description here

One thing comes to my mind is that I use some distance variables between the two closest nodes in the route path. (In this example these are 'C' and 'D' nodes.) As the object approaches 'C' and moves away from the 'D' node at the same time, this means character passed the 'D'.

However, I think there are some standardized and easy ways to solve this. What approach should I take?

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

If you correctly implement Dijkstra algorithm, it should work correctly. You are not just looking for the nearest node current. You have to consider other paths too. I'll try to explain:

The nearest point from start is D, so D is your next candidate. Distance from start to C is less than distance from start to D + distance from D to C. So, your path is now start-C instead of start-D-C, but you still have start-D-C memorized somewhere so you'll later check which path is more favorable. Start-C-B is more favorable than start-D-B and start-D-C-B so we're taking start-C-B. And you repeat this all the time until you find your target node.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.