Hmm, one possible way to improve on the equal-distance issue is to make fewer of the paths exactly equal. For example, you could add a cost penalty for turning (and this could be really small too, like 0.001), with that the above example would only have 2 equal best paths (>>>^^^ and ^^^>>>), or maybe only 1 because the source and target belts have fixed direction too.
You could also add the turn penalty to the heuristic function, based on the minimum number of turns required. This could be based only on the direction of the target belt, and the current belt (and their coordinates)
- Same direction, and they are in the same "lane" (column or row), and target is in front of the current belt: min 0 turns >>>
- Same direction, not the same lane, in front: min 2 turns (have to do a lane change) >>>^>>>
- Same direction, target is behind: min 4 turns (need to do a 360 turn) >^<<<<v>>
- Right-angle, in front in both directions: min 1 turn >>>^^^
- Right-angle, behind (could be behind either or both directions) : min 3 turns >^<<<^^^ or >vvv>>>^
- Opposite direction: min 4 turns
If you do something like this, could you expose the turn penalty as a setting, so we can tweak it? And also the cost penalty for underground belts in case of "prefer overground" mode. Right now I think it is pretty high, but I'd prefer this to be also something like 0.01, so it'd go overground in long straight stretches, but it'd use undergrounds if it can save any travel distance.
