0
\$\begingroup\$

I have a 2D map of nodes a train could travel. They are not in a grid. The node positions are placed by a designer and exported to a JSON file which the game loads to display the node positions on the map texture/sprite.

I'm tying to implement pathfinding for the train. The user can select a node and set a waypoint to that node. The game should find the shortest path and take that (avoiding locked nodes).

The way the nodes are set up right now is that each node has other neighbour nodes. There's the condept of a 'link' which connects two nodes. Nodes do not store any neighbour information in them, instead they're stored in the links which are stored separately (a list of links, each link contain two integers representing the linked nodes' ids)

The train has no restriction on its movement it could move from A->B or B->A, only restriction is that it doesn't move to the previous node it came from. So going from A->B, when asking B of its neighbours, we exclude A and look at the other neighbours.

enter image description here

I hope that's enough context to answer my question: Is A* applicable to me? If so, I'm not really sure how to write a function to generate weights/costs on nodes. I just can't seem to answer the question of: What's the total distance between A->B in order to assign costs/distances? Because there could be more than one path to go from A->B, which requires path-finding in itself (see the infinite loop in my logic?). If A* is not the best here, what is?

[EDIT] Replying to Matt's answer. I thought of using distances to calculate the weights/costs but take this example for instance:

enter image description here

Where's at 'P' trying to go to 'T'. Edge/link 'A' is shorter than 'E' but if we take the 'A' route it would be longer in the long run. I would have to travel both the paths to determine which distance is shorter, otherwise how do I know? am I missing/misunderstanding something here?

Another question is, how do I track paths/links/nodes that I shouldn't visit anymore? I can't just mark a node as 'visited' once I visit it the first time because there could be a branch in there and I have to visit it twice to know which one is shorter, correct?

[EDIT] I guess in the first case^, it would be benefecial to also do the pathfinding backwards from 'T' to 'P' then pick which ever is the shortest between going P->T and T->A?

\$\endgroup\$
  • 1
    \$\begingroup\$ Why the downvote? \$\endgroup\$ – vexe Jan 3 '17 at 22:19
  • \$\begingroup\$ The downvote button tooltip says "This question does not show any research effort" as one reason to use it. I think that applies in this case, because this is a textbook application of the A* algorithm. You can find this algorithm explained in detail in dozens of high-quality guides a Google search away. You can even walk through the algorithm's steps yourself on the example graph to understand exactly how it behaves in such cases. \$\endgroup\$ – DMGregory Jan 3 '17 at 22:27
  • \$\begingroup\$ I did research. I just never implemented it before. The more I read the more I got confused, I got the impression that data has to be grid-based, I ithought it would only take the shortest and not discard any, that's why I asked. \$\endgroup\$ – vexe Jan 3 '17 at 22:33
  • \$\begingroup\$ ...literally typing "a star algorithm" into Google brings up a Wikipedia summary with a non-grid example above all other results. Personally, I'd consider that a reasonably low bar for research effort in game development. Other users may feel similarly or differently - that's what the voting system exists to tally. \$\endgroup\$ – DMGregory Jan 3 '17 at 22:42
1
\$\begingroup\$

A* can be used to solve this problem. The search starts from your start node, and then scores all adjacent nodes. The cost of each adjacent node is the actual cost of getting to that node (the link distance) plus an estimate of how far you have left to go. This estimate must not overestimate the true cost - for this problem, you can use the straight-line distance between points.

Now you have a cost for all nodes adjacent to the start node. Pick the lowest-cost node, and repeat, scoring all nodes adjacent to that one (score = the running total of the link distance + distance remaining estimate). If you want to speed up the search, disallow backtracking. Keep doing this, and you will find the optimal path from A to B.

For your example in the bottom half of the question, keep in mind that A* has no way of knowing the optimal path a priori, so it will likely explore routes that are later discarded. In fact, you may wind up exploring every possible path and finding the optimal one last. All A* guarantees is that you WILL find the optimal path, not that you will find it quickly. The search relies on heuristics, which usually speeds things up, but it isn't guaranteed.

From a programming point of view, one way to implement A* is using two lists of nodes, called the open list and the closed list. The open list is your "frontier" of visited nodes that you haven't expanded yet - that is, you haven't looked at where you can get to from there. The closed list is nodes you have visited and expanded. The open list starts with the start node, and the closed list starts empty. Take the lowest-scoring node on the open list, expand it, and add all adjacent neighbors to the open list. If a node is on the closed list, don't re-open it, and if it's already on the open list, keep the new one if you have found a better (lower-scoring) path. Then move the current node to the closed list. Repeat until you expand the destination node and move it to the closed list. You only have to expand each node once, since you only keep the shortest path to any particular node.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. Could you check my edit at the bottom of the question? (Made another edit) \$\endgroup\$ – vexe Jan 3 '17 at 21:53
  • \$\begingroup\$ Thanksf or the extra info. 1- I'm assuming the solution has to be recursive? 2- In the example I posted above, will A* find both that paths that lead from A to T and only pick the shortest one? How does that work with what you said "Repeat until you expand the destination node and move it to the closed list", doesn't that mean once we find the destination once we stop? \$\endgroup\$ – vexe Jan 3 '17 at 22:07
  • \$\begingroup\$ 1 - no, you can write A* in an iterative, rather than recursive form. 2 - Remember that we're always expanding whichever node has the least sum of distance + estimate, and our estimates can never exceed the true distance. The destination node has an estimate of 0 (since it is the destination). That means, if it has the least sum of every node in our list, then the distance we've found to it must be shorter than every path we haven't yet explored. (If one of those paths could be shorter, then that node's distance + estimate would have to be smaller, meaning we'd have chosen it instead) \$\endgroup\$ – DMGregory Jan 3 '17 at 22:15
  • \$\begingroup\$ So, just to make sure I understand the numbers, going from point A to B trying to reach T, FinalCost(A, B) = LineDistance(A, B) + LineDistance(A, T)? \$\endgroup\$ – vexe Jan 3 '17 at 22:28
  • 1
    \$\begingroup\$ At any step, A* guesses at the true cost of the path between A and T. This is expressed as BestGuess(A, T) = LinkDistance(A, B) + LineDistance(B, T). LinkDistance is the actual cost of traversing from A to B along the tracks, and LineDistance is the straight-line guess of the remaining distance from B to T. For your other note, you stop once you move the destination off the open list, not when it goes on the open list - at that point there's still a chance you could find a shorter path from other nodes adjacent to the destination. \$\endgroup\$ – Nuclear Wang Jan 3 '17 at 22:33

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.