Is A* suitable for this particular case?

Question

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.

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:

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?

Answer 1

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.