Friday Facts #113 - Better rail building

[Theace98]

GAH! Starsector 0.7A release AND factorio 0.12 stable-ish? Which do I play first? But still well done on reaching a stable, time to do an update, always fun to play factorio, even if the music sounds like I'm playing xenonaunts.

As for the rail through the forest? I have a easy approach. It's called personal roboport and a deconstruction planner. Those pesky forests don't know what hit em when construction robots tear them to piece. Far faster than an axe and more material efficient than that route.

[AlexTheNotsogreat]

While it moving through that forest is very resource inefficient, it looks REALLY FREAKING COOL!

[Theace98]

While it moving through that forest is very resource inefficient, it looks REALLY FREAKING COOL!

I'll admit that.

[billw]

Looks amazing, I bet it was fun to code as well. Any chance it can be extended to provide some more of the extra features the automatic rail layer provides? Track doubling is a must, as if the point of this is to make large rail systems easier, what large rail system doesn't use doubled track? Although I guess you could place another auto track with adjacent start and end points, but it may be the case that the previous rail didn't leave space in the right places to run another parallel line.
Another one would be automatic placement of signals, and perhaps power poles.

[daniel34]

As for the rail through the forest? I have a easy approach. It's called personal roboport and a deconstruction planner. Those pesky forests don't know what hit em when construction robots tear them to piece. Far faster than an axe and more material efficient than that route.

Did you read this reply from kovarex?

It will probably work the same way as blueprints. When you hold shift, trees get ignored.

Just today I had to lay a rail through a big forest (limiting myself to vanilla) and had to constantly switch between deconstruction planner, straight rail and curved rail. This rail building method is much more efficient than I imagined when I heard the devs are redoing rails. This is just awesome.

For me Factorio is like an almost fully released (for my time spent / fun I had with it even AAA+) game that continues to improve in quality. I haven't seen such a rail laying mechanism in any game before and I really, really like that the devs explain the technical background behind each of these features every week. I just wish the devs of other early access (*) games that I have on steam would be as forthcoming and community-oriented as the Factorio team.

(*) Like mentioned above, for me Factorio has progressed to be far more than just "early access".

[Martoon]

In the next example, the first solution found is not optimal, as the curves can be straightened, so extra steps of the algorithm is needed to find a better solution.

I take it the heuristic function is not quite admissible (i.e., the cost-to-goal estimate can sometimes be slightly higher than the actual cost to goal)? It guess it's not strictly a traditional A* search.

[ssilk]

This is what I always wished.
What I still don't get is: if there is only one type of rail left (which is very good), and if it works like blueprint, how could the character build curves without bots?
Other question is with signals etc. Will there be autoplacing of signal (a signal after X segments)? Autoplacing of poles? Will there be the possibility to lay 2 lanes at once (2x1-way tracks)?

And a bit off-topic: The features of the rail-layer mod are long. For example that it can use blueprints. Or laying tracks over water (using concrete). Will there be something like this?

[knexer]

kovarex wrote:
In the next example, the first solution found is not optimal, as the curves can be straightened, so extra steps of the algorithm is needed to find a better solution.

I take it the heuristic function is not quite admissible (i.e., the cost-to-goal estimate can sometimes be slightly higher than the actual cost to goal)? It guess it's not strictly a traditional A* search.

I was wondering about this as well; it's very surprising given that Euclidean distance is admissible here. I think it might instead be a consequence of searching from both ends and meeting in the middle - looking at the given example of a suboptimal chosen path, each half of the path is definitely the right thing for the A* to be checking first, assuming it's using a variant of Euclidean-distance-to-target as its heuristic.

In other words, the algorithm found the shortest path from A->B->C (or really, A->B and C->B, but paths are reversible in this context), for some B that's not guaranteed to be on a globally shortest path from A->C.

Bidirectional A* is slightly more subtle than this - IIRC the constraints on the heuristic functions are stronger (fortunately Euclidean distance should still meet them in this case) and the stop criteria are different. However, I'm super curious as to the extent to which this algorithm's answers are 'good enough' or can be corrected with inexpensive and simple heuristics to be 'good enough'. What do the extra steps look like?

[_aD]

Oh wow that looks brilliant! I hadn't even wanted auto rail laying until I saw how great it looked :-)

[ratchetfreak]

Just today I had to lay a rail through a big forest (limiting myself to vanilla) and had to constantly switch between deconstruction planner, straight rail and curved rail. This rail building method is much more efficient than I imagined when I heard the devs are redoing rails. This is just awesome.

Make a blueprint of a piece of track and you won't need to switch to the deconstruction planner, just need to switch between blueprints

[Nidan]

In the next example, the first solution found is not optimal, as the curves can be straightened, so extra steps of the algorithm is needed to find a better solution.

I take it the heuristic function is not quite admissible (i.e., the cost-to-goal estimate can sometimes be slightly higher than the actual cost to goal)? It guess it's not strictly a traditional A* search.

I was wondering about this as well; it's very surprising given that Euclidean distance is admissible here. I think it might instead be a consequence of searching from both ends and meeting in the middle - looking at the given example of a suboptimal chosen path, each half of the path is definitely the right thing for the A* to be checking first, assuming it's using a variant of Euclidean-distance-to-target as its heuristic.

In other words, the algorithm found the shortest path from A->B->C (or really, A->B and C->B, but paths are reversible in this context), for some B that's not guaranteed to be on a globally shortest path from A->C.

Bidirectional A* is slightly more subtle than this - IIRC the constraints on the heuristic functions are stronger (fortunately Euclidean distance should still meet them in this case) and the stop criteria are different. However, I'm super curious as to the extent to which this algorithm's answers are 'good enough' or can be corrected with inexpensive and simple heuristics to be 'good enough'. What do the extra steps look like?

Using Euclidean distance for the estimate is fine, and imho the best thing you should use in this case. Also A* doesn't have any nasty side effects when used bidirectional. To answer the question: You don't need any extra steps, A* (and Dijkstra) are designed in a way that the very first solution found is the best. However kovarex's wording and the picture suggest that the current implementation optimizes "pieces of track placed" counting both straights and curves as a single piece and thus favoring "curvy straights" (four pieces of curve cover the same distance as 14 straights) as shown in the picture. Better metrics would be "number of (new) rail items required for building" (i.e. counting a curve as 4 instead of 1) or actual track length (straights as 2 tiles, diagonals as sqrt(2), curves as approx. 7.85)

In the next example, the first solution found is not optimal, as the curves can be straightened, so extra steps of the algorithm is needed to find a better solution.

This sentence, especially the bold part is a dead giveaway that the implementation is wrong, in this case because you're optimizing the wrong thing.

[knexer]

A* (and Dijkstra) are designed in a way that the very first solution found is the best.

Correct; but this doesn't apply to the bidirectional variants of either algorithm. The last scanned node of the first complete path needn't be on a global optimal path at all. Instead, once those path trees have met, you can bound how far away you are from an optimal solution, then search until those bounds are met and take the overall best solution you saw. (This might be those 'extra steps' kovarex mentioned?)

See lecture notes (warning: pdf): http://www.cs.princeton.edu/courses/arc ... rithms.pdf

[Nidan]

A* (and Dijkstra) are designed in a way that the very first solution found is the best.

Correct; but this doesn't apply to the bidirectional variants of either algorithm. The last scanned node of the first complete path needn't be on a global optimal path at all. Instead, once those path trees have met, you can bound how far away you are from an optimal solution, then search until those bounds are met and take the overall best solution you saw. (This might be those 'extra steps' kovarex mentioned?)

See lecture notes (warning: pdf): http://www.cs.princeton.edu/courses/arc ... rithms.pdf

Yeah, the point where I went wrong was assuming A* has a trivial bidirectional variant. I've dug up my own university's slides on that topic, but yours do a better job at explaining things.
Conclusion: I messed up. kovarex's A* implementation and metric are fine (for the unidirectional case). To fix the bidirectional problem see the pdf mentioned above. If you prefer German, see slides 52 to 55 of http://i11www.iti.uni-karlsruhe.de/_med ... esung6.pdf (pdf, ~5MB), but the one from Princeton seems to explain things better.

Intuition says you want to explore towards the closest point of the opposite wavefront instead towards the opposite root, but I don't see that in the slides, so don't quote me on that. Also it's getting late over here...

[Smarty]

0.12.18 released today hu?

[ikarikeiji]

Please keep the ability to manually place, without bots/blueprints, both straight and curve rails as we can at the moment.

Also to be able to drag straight rail without invoking the pathfinding, so that we can still build really long straights.

Maybe making the straight rail act as it already does, and the curve rail act as your planner item, would work best? So that if you just click with a curve rail it places it with specified rotation as it works at the moment, but if you click and drag with curve rail it invokes the pathfinding. Because dragging straight rail in the current version makes sense, but dragging curve rail doesn't.

[Legion1337]

Two points:
As an programmer myself I really appreciate the techtalk in the Friday Facts. Keep going like this

But as an gamer I have to admince that since many months there isn't enough new - not even with mods for me to play factorio again.
Is there any way or option which I missed to further enjoy factorio?

[nocturnalAndroid]

Once the first solution is found(start and goal searches meet with opposite directions), the search continues for a little while, as better solutions might exist.

This might be a silly question, shouldn't weighting straight tiles less (say according to length, or even a bit more biased toward straight tracks) solve this? Obviously, having not built this, I have no idea of the intricacies of the problem, but I'm genuinely interested.

[Silden]

One question: why this algorithm avoid trees? If it works like a blueprint doesn't it should just lay tracks on top of the trees marking them to be removed?

I'd like an option to choose which, sometimes I want the trees, sometimes they come down.

[daniel34]

One question: why this algorithm avoid trees? If it works like a blueprint doesn't it should just lay tracks on top of the trees marking them to be removed?

I'd like an option to choose which, sometimes I want the trees, sometimes they come down.

One question: why this algorithm avoid trees? If it works like a blueprint doesn't it should just lay tracks on top of the trees marking them to be removed?

It will probably work the same way as blueprints. When you hold shift, trees get ignored.

[kyborek]

Once the first solution is found(start and goal searches meet with opposite directions), the search continues for a little while, as better solutions might exist.

This might be a silly question, shouldn't weighting straight tiles less (say according to length, or even a bit more biased toward straight tracks) solve this? Obviously, having not built this, I have no idea of the intricacies of the problem, but I'm genuinely interested.

I was thinking exactly the same. The only reason i can think of for such solution is the one where prefering curves and then counting a bit more after solution is found is on average faster than preferring straight rails that lead to nowhere. Such issue should still be solved by A* algorithm anyway but i don't know how does the both-way variant work.