Pathfinding algorithm for trains

Question

I'm trying to find a solution for pathfinding in a trains game where there are different kinds of bifurcations. I want the train to go from one rail to another, everything is implemented except the pathfinding.

I need to get a list of rails so the train can follow. Now, the problem is how do I get the list.

• I've tried A*, didn't work because it stops searching if the node (rail) is already visited. This is a problem, because maybe the way to reach a point is by travelling through the longest route.
• Tried flood fill, this time made it not stop searching if already visited, the problem is how do I reconstruct the path and how does it choose that it can't go backwards again.

The thing is that there are cases in which the train must go through a rail multiple times to reach its destination.

Any ideas?

Starting point is A, end B. As you see the green path is the way it should travel. The balck circle are the rails which the train will step more than once, in this case 2 times.

B">

And obviously, you need to come from 2 black to get to 3 red. You can't just go 1black->2red->1red->3red.

Answer 1

Looking at this picture

It appears your problem would be represented well by a directed graph. Give each stop and each junction two nodes in the graph, one for each direction of the train. Dijkstra's algorithm works perfectly on directed graphs, so once you have the problem in that form, the rest is easy.

So for example, in the picture above, starting from A, we move to junction 1. From there, there's only one place to move to, junction 2, so there'd be an arrow from A --> junction 1 and an arrow from junction 1 --> junction 2. Regardless of which choice you make, you end up at junction 1, but moving in the other direction, so we create a separate node from there. From there, you have the option of going to A or B.

Notice that I removed one of the J1's, since it is superfluous (there's only one place to go).

If the train can stop and turn around at stops like A, we can connect those two nodes by edges in both directions, or just combine them into one node.

You can give the edges weights to specify distances.

Answer 2

Flood fill should really do the thing (I used it in a similar case) - but you only need to work with switches and segments carefully.

Algorithms should be allowed to pass the same segment in different direction, but not in the same. I.e. each segment really should be regarded as two separate.

to reconstruct the path you should assign numbers to segments while flooding them, so that each reached from N-1 is marked with N - then while move backward, tracking segments should be done so that numbers steadily decrease by one.

It is really kind of BFS.