Friday Facts #113 - Better rail building

Regular reports on Factorio development.
Theace98
Burner Inserter
Burner Inserter
Posts: 11
Joined: Fri Oct 09, 2015 6:04 pm
Contact:

Re: Friday Facts #113 - Better rail building

Post by Theace98 » Fri Nov 20, 2015 9:38 pm

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.
I typically play Factorio, Minecraft, Rimworld, Starsector, Prison Architect and Stardrive 2. Oh and add XCOM, FTL and Homeworld. And Transport Tycoon...

Quite frankly, it's a miracle I get anything done.

AlexTheNotsogreat
Long Handed Inserter
Long Handed Inserter
Posts: 94
Joined: Thu May 14, 2015 12:54 am
Contact:

Re: Friday Facts #113 - Better rail building

Post by AlexTheNotsogreat » Fri Nov 20, 2015 9:42 pm

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

Theace98
Burner Inserter
Burner Inserter
Posts: 11
Joined: Fri Oct 09, 2015 6:04 pm
Contact:

Re: Friday Facts #113 - Better rail building

Post by Theace98 » Fri Nov 20, 2015 9:46 pm

AlexTheNotsogreat wrote:While it moving through that forest is very resource inefficient, it looks REALLY FREAKING COOL!
I'll admit that.
I typically play Factorio, Minecraft, Rimworld, Starsector, Prison Architect and Stardrive 2. Oh and add XCOM, FTL and Homeworld. And Transport Tycoon...

Quite frankly, it's a miracle I get anything done.

billw
Long Handed Inserter
Long Handed Inserter
Posts: 67
Joined: Tue May 27, 2014 10:27 am
Contact:

Re: Friday Facts #113 - Better rail building

Post by billw » Fri Nov 20, 2015 10:02 pm

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
Global Moderator
Global Moderator
Posts: 2757
Joined: Thu Dec 25, 2014 7:30 am
Contact:

Re: Friday Facts #113 - Better rail building

Post by daniel34 » Fri Nov 20, 2015 10:04 pm

Theace98 wrote: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?
kovarex wrote: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
Burner Inserter
Burner Inserter
Posts: 5
Joined: Tue Sep 09, 2014 3:22 pm
Contact:

Re: Friday Facts #113 - Better rail building

Post by Martoon » Fri Nov 20, 2015 10:24 pm

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.

User avatar
ssilk
Global Moderator
Global Moderator
Posts: 10469
Joined: Tue Apr 16, 2013 10:35 pm
Contact:

Re: Friday Facts #113 - Better rail building

Post by ssilk » Fri Nov 20, 2015 10:40 pm

This is what I always wished. :D
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?
Cool suggestion: Eatable MOUSE-pointers.
Have you used the Advanced Search today?
Need help, question? FAQ - Wiki - Forum help
I still like small signatures...

knexer
Manual Inserter
Manual Inserter
Posts: 2
Joined: Fri Nov 20, 2015 11:44 pm
Contact:

Re: Friday Facts #113 - Better rail building

Post by knexer » Fri Nov 20, 2015 11:50 pm

Martoon wrote: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
Fast Inserter
Fast Inserter
Posts: 211
Joined: Sat Apr 12, 2014 12:03 am

Re: Friday Facts #113 - Better rail building

Post by _aD » Sat Nov 21, 2015 12:39 am

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

ratchetfreak
Filter Inserter
Filter Inserter
Posts: 936
Joined: Sat May 23, 2015 12:10 pm
Contact:

Re: Friday Facts #113 - Better rail building

Post by ratchetfreak » Sat Nov 21, 2015 1:24 am

daniel34 wrote: 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
Inserter
Inserter
Posts: 31
Joined: Sat Nov 21, 2015 1:40 am
Contact:

Re: Friday Facts #113 - Better rail building

Post by Nidan » Sat Nov 21, 2015 2:38 am

knexer wrote:
Martoon wrote:
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?
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)
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.
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
Manual Inserter
Manual Inserter
Posts: 2
Joined: Fri Nov 20, 2015 11:44 pm
Contact:

Re: Friday Facts #113 - Better rail building

Post by knexer » Sat Nov 21, 2015 3:52 am

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
Inserter
Inserter
Posts: 31
Joined: Sat Nov 21, 2015 1:40 am
Contact:

Re: Friday Facts #113 - Better rail building

Post by Nidan » Sat Nov 21, 2015 4:57 am

knexer wrote:
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...

User avatar
Smarty
Global Moderator
Global Moderator
Posts: 816
Joined: Sat Oct 04, 2014 5:00 pm
Contact:

Re: Friday Facts #113 - Better rail building

Post by Smarty » Sat Nov 21, 2015 8:34 am

0.12.18 released today hu? :P

ikarikeiji
Long Handed Inserter
Long Handed Inserter
Posts: 92
Joined: Sun Jul 12, 2015 6:28 pm
Contact:

Re: Friday Facts #113 - Better rail building

Post by ikarikeiji » Sat Nov 21, 2015 11:53 am

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
Manual Inserter
Manual Inserter
Posts: 4
Joined: Tue May 26, 2015 7:00 am
Contact:

Re: Friday Facts #113 - Better rail building

Post by Legion1337 » Sat Nov 21, 2015 12:51 pm

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
Burner Inserter
Burner Inserter
Posts: 8
Joined: Mon Jun 02, 2014 6:50 pm
Contact:

Re: Friday Facts #113 - Better rail building

Post by nocturnalAndroid » Sat Nov 21, 2015 4:47 pm

From the post wrote: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
Inserter
Inserter
Posts: 42
Joined: Thu Sep 10, 2015 3:59 pm
Contact:

Re: Friday Facts #113 - Better rail building

Post by Silden » Sat Nov 21, 2015 4:57 pm

hitzu wrote: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
Global Moderator
Global Moderator
Posts: 2757
Joined: Thu Dec 25, 2014 7:30 am
Contact:

Re: Friday Facts #113 - Better rail building

Post by daniel34 » Sat Nov 21, 2015 5:04 pm

Silden wrote:
hitzu wrote: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.
kovarex wrote:
hitzu wrote: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
Burner Inserter
Burner Inserter
Posts: 6
Joined: Fri Nov 20, 2015 11:34 am
Contact:

Re: Friday Facts #113 - Better rail building

Post by kyborek » Sat Nov 21, 2015 5:16 pm

nocturnalAndroid wrote:
From the post wrote: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.

Post Reply

Return to “News”

Who is online

Users browsing this forum: No registered users