Factorio Forums

Posted: **Sun Feb 02, 2020 8:18 am**

Hey Factorio Team!

This topic connects to the Friday Facts #331. I'm currently finishing my computer science master specializing at route planning algorithms. It was quite interesting to read the post, since it answered a few questions that already came to my mind, but it also rose a few new ones.

Why A*? I see the heuristic helps already to significantly decrease the number of settled nodes. But why not directly to specially road-network tailored solutions like contraction hierarchies?
How does the graph representation of a rail network look like?
I'm not sure from those descriptions how you represent your rail network by now. But it seems that Issues 1, 2 and 3 could be sorted out if it was designed as follows: Nodes for each junction, block transition and station. Edges between nodes represent the number of segments between them. (Maybe some penalties added for example on block transitions...) The issue of the distance between a junction and a train stop would than naturally be resolved without any modifications to the algorithms. The issue of train positions on a segment would be resolved as it is in real applications like Google Maps (or Graphhopper if you like to view the source code for it). You simple start routing from the node that is closest to the train (e.g. euclidean distance).
Could (2.) also preempt the rise of some of the other issues you descriped as rising from the solution of the first 2 issues?

Posted: **Sun Feb 02, 2020 8:41 am**

butschde wrote: Sun Feb 02, 2020 8:18 am Why A*? I see the heuristic helps already to significantly decrease the number of settled nodes. But why not directly to specially road-network tailored solutions like contraction hierarchies?

Since Dijkstra is special case of A* with heuristic function h(x)=0, then by changing heuristic from "always 0" to "minimum distance to any given end", it is no longer Dijkstra (or am i wrong?).

butschde wrote: Sun Feb 02, 2020 8:18 am How does the graph representation of a rail network look like?

viewtopic.php?p=475372#p475372
Nodes are segments+direction. Usually there will be up to 2 nodes per segment if segment is bidirectional. In some extreme cases it is possible to have 6 nodes over given segment. Edges are transitions (up to 18 edges on a junction in case junction is of 3 segments to 3 segments, all bidirectional).

butschde wrote: Sun Feb 02, 2020 8:18 am if it was designed as follows: Nodes for each junction, block transition and station

This design would be useless. Nodes would then be required to have their own enter/exit direction and edges would be required to hold extra informations about which segment they are referring. 2 junctions may be connected with 3 distinct segments and you have to be able to distinguish which one is shortest to reconstruct path.

In case of map coloring problem, nodes are on countries and edges represent relation of being "adjacent to". You would not be trying to solve map coloring problem by simply placing nodes where 3 or more borders cross and edges where borders are, unless you are solving a problem of "how to get from one point on border to another point on another border always having both feets in different countries" (and even then, nodes would represent borders and edges would represent borders being in touch in one corner, so you could always start on node and have an goal as a node, unless you want to inject start and goal node, then border junctions as nodes would be fine)

butschde wrote: Sun Feb 02, 2020 8:18 am Could (2.) also preempt the rise of some of the other issues you descriped as rising from the solution of the first 2 issues?

This was simply due to wrong assumption. End reached check was performed with assumption we are at the end of node's underlying segment, while because of penalties added up to this point, virtual train would have been just at transition to the last segment.

Posted: **Mon Feb 03, 2020 8:54 am**

boskid wrote: Sun Feb 02, 2020 8:41 am
butschde wrote: Sun Feb 02, 2020 8:18 am if it was designed as follows: Nodes for each junction, block transition and station
This design would be useless. Nodes would then be required to have their own enter/exit direction and edges would be required to hold extra informations about which segment they are referring. 2 junctions may be connected with 3 distinct segments and you have to be able to distinguish which one is shortest to reconstruct path.

Do I understand that correct: The issue is that the outgoing rail segments that can be used are depending on which ingoing segment i were coming from?

Code: Select all

A===O====B
     \===C

So in this case you need to prevent that the Path (B,O,C) is used?

Posted: **Mon Feb 03, 2020 9:01 am**

butschde wrote: Mon Feb 03, 2020 8:54 am
Code: Select all
A===O====B
     \===C
So in this case you need to prevent that the Path (B,O,C) is used?

Path B-O-C is not possible in that scenario. There would be 6 nodes: AO, OA, BO, OB, CO, OC, and because of junction, there would be no edge going from BO -> OC (would require train to reverse and this is forbidden). In this case only edges would be: AO->OB, AO->OC, BO->OA and CO->OA.

So answer to this:

butschde wrote: Mon Feb 03, 2020 8:54 am Do I understand that correct: The issue is that the outgoing rail segments that can be used are depending on which ingoing segment i were coming from?

Yes. Not all segments on junction are valid as next step. Simply because reversing on junction is not allowed (would require a lot more complications like finding path that would fit whole train after junction and then requiring it to change direction after junction)

Factorio Forums

Train Path Finder

Train Path Finder

Re: Train Path Finder

Re: Train Path Finder

Re: Train Path Finder