1
\$\begingroup\$

I am having trouble understanding how to implement dijkstra's algorithm for a path finding assignment, here's what the layout looks like: layout_

Each node has a List of neighbours which are found using raycasting. Now the issue i am having is how to weight each node.... I understand Dijkstras maintains a list of visited nodes and an open list. I just don't understand how to weight them individually based on where i want to go.

Right now i'm weighting them all by a distance of 1. But this seems to be incredibly redundant and is going to take an extremely long time to find the shortest path because it's going to check every possibility of a paths to the endNode....

Can someone help me understand the logic of how to implement dijkstra's algorithm in this environment?

\$\endgroup\$
  • 1
    \$\begingroup\$ 1. In pathfinding you are actually weighting the edges not the nodes. 2. Dijkstra's algorithm visits every possible node so it takes long. Use the A* algorithm for faster pathfinding. \$\endgroup\$ – dari Feb 16 '16 at 20:26
2
\$\begingroup\$

To answer your questions one by one:

Each node has a List of neighbours which are found using raycasting. Now the issue i am having is how to weight each node.... I understand Dijkstras maintains a list of visited nodes and an open list. I just don't understand how to weight them individually based on where i want to go

because you found those node by raycasting, in order to find the shortest path the weight of edges must be naturally equal to distance(or multiple of) between those nodes and not influenced by the goal node. Dijskras algorithm does not care what the goal node is - the output of the algorithm is w-distance(weighted distance, in your case just the "distance") from one node to every other.

Right now i'm weighting them all by a distance of 1.

that is partially correct way because it is a multiple of distance between adjacent nodes - assuming they are on grid and it is not diagonal distance, which would be sqrt(2).

But this seems to be incredibly redundant and is going to take an extremely long time to find the shortest path because it's going to check every possibility of a paths to the endNode....

Profile first, judge speed after. Dijsktra runs in ~n^2, raycasting all vs all will cast n^2 rays and check up all objects in scene each, moreover contrary to the pathfinding algorithm there is quite complicated math behind it that takes time.
To speed things up there is for example very popular A* algorithm, however I would not be surprised if it were actually slower than Dijkstra for input with few number of nodes(<1000?) just because it is more complicated algorithm.
You can imagine(very simplified!) Dijkstra as filling the map with water from start node(that does not stop until all map is full), A* is analogy with the map tilted towards goal node.
Alternatively, you can use Floyd-Warshals algorithm which runs in n^3 and computes shortest path "all vs all". This way, you can run the computation "offline" before game is loaded, effectively reducing time to ~zero. Note: because paths are pre-computated, it will not handle moving obstacles.

\$\endgroup\$
  • \$\begingroup\$ ooops missed the part about "assignment", probably should not have answered this. However what is done is done, hope at least this answer will help others looking for explanation and short state-of-the-art of pathfinding. \$\endgroup\$ – wondra Feb 16 '16 at 23:04

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.