title: Pathfinding algorithm for trains
body: <p>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.</p>
  
  <p>I need to get a list of rails so the train can follow. Now, the problem is how do I get the list.</p>
  
  <ul>
  <li>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.</li>
  <li>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.</li>
  </ul>
  
  <p>The thing is that there are cases in which the train must go through a rail multiple times to reach its destination.</p>
  
  <p>Any ideas?</p>
  
  <p>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.</p>
  
  <p><img src="https://i.stack.imgur.com/s08Zj.jpg" alt="A-&gt;B"></p>
  
  <p><img src="https://i.stack.imgur.com/yYDPG.jpg" alt="enter image description here"></p>
  
  <p>And obviously, you need to come from 2 black to get to 3 red. You can't just go 1black->2red->1red->3red.</p>