I was having trouble finding a path. Well, I was actually having trouble programming the path finding algorithm for the railroad game. I’ve never written something like this and what I threw together originally was just wrong.
There are a few requirements that exist in this game that affect the path finding. Beyond the obvious requirement of getting to a destination, the train must not go around in circles if there is a loop of track. The train must also know about going through switchbacks. That is, passing a switch and then backing through it. Ideally, the train should also take the shortest path to the destination.
My original code was just wrong. I set a flag for every segment of track and then make sure that I never touch the same segment twice. I then look at every segment connected to every other segment, starting with the location of the train. This didn’t work. The reason may be obvious but it was not obvious to me until I started to think about it in depth. the code was mostly right but I was very wrong with the anti-looping mechanism.
The new code keeps a stack of segment pointers and uses this to ensure that it never touches the same segment twice. This is different than keeping a flag in each segment because once I leave a segment during the processing, it is popped off the stack. I can then reuse it for a different path. For example, below is a picture of some track segments that need to be processed for path finding:
If the train is on or to the left of the segment numbered 1 and needs to end up on or after the segment numbered 3 then I should ideally check the path through segments 2 and 4. If I flagged 3 as having been touched once it was found through segment 2 then I could never find it through segment 4.
The solution was to use the stack. The algorithm finds segment 1 and pushes that onto the stack. It then checks segments 2 and 4 but the code is recursive and for each of 2 and 4, it will look ahead further. In order, the code finds the path 123 then finds 143. because of the stack, it finds segment 3 more than once. The code also tries 124 and 142 but once those paths are examined, they come to an end at segment 1 which is already on the stack for those paths.
This works well and I can compare the distance of each different path that does reach the final segment and pick the shortest. the stack handling keeps any track loops like 124 from looping endlessly while still allowing segments to be found as parts of different paths.
I plan on adding some extra code to somehow give a penalty for switchbacks. if the train needed to go through segment 1 then 2 then 4 to get to some destination then the train can do that automatically. It just passes the turnout to segment 4 and then backs onto that segment. Given two paths to a destination, I’d rather avoid a switchback if another path exists. in fact, it’s a train and having the locomotive push the train is also less desirable to pulling the train. Pushing is a little less safe and clearly harder for the engineer to see what’s in “front” of him.
The next problem to solve is when the train ends up parked over a turnout that needs to be taken to get tot he next destination. After that, I need waypoints to control movement that don’t stop the train, just direct it to a specific path.