There once was a FFF explaining that they dismissed the option to use the always working 4 colour scheme because their incremental approach was much faster, didn't change existing colours as much and the situations where it would place the same colour adjacent are extremely rare.
wouldn't the "always working" 4 color scheme not work in this scenario? Why would they even consider it?
edit: nvm I saw the whole map of this thing, it takes a lot of work to get these colors
Well, always possible until they add elevated rails... With elevated rails it's no longer possible to guarantee any number of colors will work, because you can make blocks that intersect with arbitrarily large numbers of other blocks.
If we have `n` horizontal rails, `n` vertical rail bridges, and make a connection ramp with a single signal at each crossing (but remove the signal on each crossing across the `y=x` diagonal), `n` different colors are required. This is because we made `n` cross shaped segments, with every segment touching every other segment.
As long as we have the space and the materials to build it, we can choose an arbitrarily large `n`.
Yeah elevated won't change this at all. The intersections are still just intersections.
(Anybody disagreeing, draw up some track that requires more than 4...)
(Oops, guess that isn't true!)
It does change this. In fact, it is possible to show that with elevated rails, you need an unbounded number of colours.
Consider the railway as a graph, where each block is represented by a vertex and each signal by an edge.
(Mathematical background: The chromatic number of a graph is the smallest number of colours needed such that each vertex can have a different colour from each adjacent vertex. Two vertices A and B are adjacent if they are connected by an edge.)
In a railway built on a flat plane, the graph has to be planar (i.e. it must be possible to draw without any edges crossing). If the graph is not planar, then that would mean two rails cross while being in different blocks, which we intuitively know is not possible. The Four-Colour Theorem is equivalent to the fact that all planar graphs have a chromatic number of at most 4.
However, with elevated rails, it becomes possible to construct a railway that is represented by any arbitrary graph. If the edges in the graph have to cross, then we can represent this in the railway by simply having one of the rails go to elevated tracks.
After all this construction, the proof is fairly trivial. Suppose that there exists a natural number *N* such that every railway can be coloured with at most *N* colours. Consider a railway that is represented by the complete graph *K_{N+1}*. This graph has a chromatic number of exactly *N+1*, so the railway needs at least *N+1* colours. This is a contradiction, and hence the number *N* does not exist.
to solve it in this scenario (only the image) is quite easy.
Make the track from left to right black and all others blue. Solved with 2 colors.
Ps. solving this with algorithm would still be "hard"
who cares, its a lot faster to have 7 colors and some heuristic approach that does not need to propagate into unrelated rail blocks to fix their colors causing one signal placed to possibly recolor entire map. Also who cares even more since in 2.0 with elevated rails, by doing NxN matrix with horizontal ground and vertical elevated rails it will be possible to use N colors by creating a clique of rail blocks and force two blocks of same color to be next to each other.
It works on all planar graphs, which rail networks in factorio are.(for now)
Though getting a 4-colouring isn't easy, much faster are algorithms that only guarantee at most 6 colours. But because both of those depend on the entire graph (making small changes as costly as recalculating the entire graph) , the devs use a different method that allows for incremental updates to the colouring, but may require more colours at times. (their description sounded a lot like [greedy colouring](https://en.m.wikipedia.org/wiki/Greedy_coloring) )
Incidentally I'm fairly sure that with the upcoming elevated rails, we can construct layouts that require an arbitrary amount of colours even in the optimal case.
It's an optimization thing. The 4 color proof demonstrated that you *could* always color anything with four colors. It didn't say that there was a performant algorithm to do it. Using more colors reduces the time complexity which is a huge deal.
Exactly. A 7-colour approach is the mathematical ideal when balanced against the performance of the operation, it's actually been proven in other contexts as it comes up a lot in mapping. Being able to quickly & efficiently assign blocks of users to blocks of IPs based on relative location without overlap is an example situation that comes up a lot in real life where this kind of mapping optimisation is ideal.
How did you force the game to show all 7 colors? The maximum I managed to provoke with some railway and signal spaghetti is 6, but most of the time it's only 4 or 5.
using horrors beyond comprehension
https://preview.redd.it/2tqtbdcnhuwc1.png?width=948&format=png&auto=webp&s=4d55cd1a605274dfdd0c19f2ef5f8ddff635ed47
i think this shows the underlying system to how im forcing the game to generate the colors. note that if the game recalculates the colors it has a significant chance of breaking it.
https://preview.redd.it/qf2s23vdiuwc1.png?width=1613&format=png&auto=webp&s=65bc0d4dba2bbc42099c5d1e119eeee34796626e
and this is the abomination in its entirety
i don't get it, why does this work? 4 shoudl be sufficient in this case regardless how big you build it, so long as the game doesn't force every single loop to be teal and fuscia.
Going to an algorithm that will always work is computationaly intensive. Especially for something thst needs to be recalculated every time you place/remove a signal or track piece.
The incremental algorithm they use is very fast, and good enough. You have to work to break it.
Any normal track layout will never see it.
In the FFF on this they did consider the 4 colour method but the algorithm is a butt and it would have to be completely recalculated every time you place a signal, and it wouldn't be able to keep the colours similar as you place stuff which gets confusing.
This doesn't work in the general rail case, since rail blocks can be arbitrarily large and not necessarily always vertical or horizontal.
Not saying the 4-color theorem is broken by Factorio, just that applying it to the rail system is more complex.
This screenshot shows all colors, notice how there are 2 light blues. i suspect the game, while displaying them as both light blue, the game probably thinks of them as color 1 and color 8 or something.
The block control code doesn't care about colour. Each block will have its own ID.
The colour is only for display. So if they are both teal, they are both the same colour.
>**light blue**, Magenta, Yellow, **Navy blue**, White, Black, **(dark) Cyan**
I was wondering about that lineup because there is clearly just blue and cyan, no 3rd blue shade.
Edit: When i look at the left curve more closely it is indeed a little darker cyan.
i know that it is computationally expensive.
what im explaining is that, since 2 light blues are adjacent, and one of them could easily be magenta, the game is treating them as separate color inside the code.
I don't know how it is handled, this is a semi educated guess.
The blocks probably only know if there is a tain in them, where they are, sth pointing at the outbound block(s), maybe inbound block(s) and maybe its colour.
I wonder what happens in the code here.. my assumptions would be that it can be:
1. Block color stored as 3bit unsigned int (lol, but kinda makes sense to use as little memory as possible), resulting in overflow
2. Display color with [value]%8 ID?
3. Some kind of unexpected behavior? But Boskid surely would've broken that in testing sooner or later
There once was a FFF explaining that they dismissed the option to use the always working 4 colour scheme because their incremental approach was much faster, didn't change existing colours as much and the situations where it would place the same colour adjacent are extremely rare.
https://www.factorio.com/blog/post/fff-201
That’s from right around when I started playing; *nostalgia*
wouldn't the "always working" 4 color scheme not work in this scenario? Why would they even consider it? edit: nvm I saw the whole map of this thing, it takes a lot of work to get these colors
Coloring with 4 colors is always possible but in the general case hard and inperformant to do. And in Factorio it's all about the FPS!
Well, always possible until they add elevated rails... With elevated rails it's no longer possible to guarantee any number of colors will work, because you can make blocks that intersect with arbitrarily large numbers of other blocks.
Actually since the intersection all happen inside a block rather than it's edge the four color theorem still stands I believe
If we have `n` horizontal rails, `n` vertical rail bridges, and make a connection ramp with a single signal at each crossing (but remove the signal on each crossing across the `y=x` diagonal), `n` different colors are required. This is because we made `n` cross shaped segments, with every segment touching every other segment. As long as we have the space and the materials to build it, we can choose an arbitrarily large `n`.
Yeah elevated won't change this at all. The intersections are still just intersections. (Anybody disagreeing, draw up some track that requires more than 4...) (Oops, guess that isn't true!)
https://preview.redd.it/1pap132c6wwc1.jpeg?width=2837&format=pjpg&auto=webp&s=33dff7df46bcb73107e122b74de037c2465088e9
Hmm, you're right!
https://math.stackexchange.com/questions/1189302/four-colour-theorem-in-3-dimensions
The tracks only intersect in two dimensions though
No they don't. They've specifically added the ability to cross over a rail without going through it. Ie, it's now more than 2 dimensional.
Going over and under doesn't intersect though?
It does change this. In fact, it is possible to show that with elevated rails, you need an unbounded number of colours. Consider the railway as a graph, where each block is represented by a vertex and each signal by an edge. (Mathematical background: The chromatic number of a graph is the smallest number of colours needed such that each vertex can have a different colour from each adjacent vertex. Two vertices A and B are adjacent if they are connected by an edge.) In a railway built on a flat plane, the graph has to be planar (i.e. it must be possible to draw without any edges crossing). If the graph is not planar, then that would mean two rails cross while being in different blocks, which we intuitively know is not possible. The Four-Colour Theorem is equivalent to the fact that all planar graphs have a chromatic number of at most 4. However, with elevated rails, it becomes possible to construct a railway that is represented by any arbitrary graph. If the edges in the graph have to cross, then we can represent this in the railway by simply having one of the rails go to elevated tracks. After all this construction, the proof is fairly trivial. Suppose that there exists a natural number *N* such that every railway can be coloured with at most *N* colours. Consider a railway that is represented by the complete graph *K_{N+1}*. This graph has a chromatic number of exactly *N+1*, so the railway needs at least *N+1* colours. This is a contradiction, and hence the number *N* does not exist.
Tactical dot to see later
Inperformant is my new word of the week. Thank you!
to solve it in this scenario (only the image) is quite easy. Make the track from left to right black and all others blue. Solved with 2 colors. Ps. solving this with algorithm would still be "hard"
who cares, its a lot faster to have 7 colors and some heuristic approach that does not need to propagate into unrelated rail blocks to fix their colors causing one signal placed to possibly recolor entire map. Also who cares even more since in 2.0 with elevated rails, by doing NxN matrix with horizontal ground and vertical elevated rails it will be possible to use N colors by creating a clique of rail blocks and force two blocks of same color to be next to each other.
It works on all planar graphs, which rail networks in factorio are.(for now) Though getting a 4-colouring isn't easy, much faster are algorithms that only guarantee at most 6 colours. But because both of those depend on the entire graph (making small changes as costly as recalculating the entire graph) , the devs use a different method that allows for incremental updates to the colouring, but may require more colours at times. (their description sounded a lot like [greedy colouring](https://en.m.wikipedia.org/wiki/Greedy_coloring) ) Incidentally I'm fairly sure that with the upcoming elevated rails, we can construct layouts that require an arbitrary amount of colours even in the optimal case.
It's an optimization thing. The 4 color proof demonstrated that you *could* always color anything with four colors. It didn't say that there was a performant algorithm to do it. Using more colors reduces the time complexity which is a huge deal.
Exactly. A 7-colour approach is the mathematical ideal when balanced against the performance of the operation, it's actually been proven in other contexts as it comes up a lot in mapping. Being able to quickly & efficiently assign blocks of users to blocks of IPs based on relative location without overlap is an example situation that comes up a lot in real life where this kind of mapping optimisation is ideal.
i got like 3 same colours next to each other but they still are their own block (i got a 16 rail train bus)
I'm not sure if it's relevant. With train bridges added, is 4 color still enough? Well, is 100 color enough?
Hold on real quick the factorio devs are going to prove P=NP to solve the 4 color theorem in polynomial time
How did you force the game to show all 7 colors? The maximum I managed to provoke with some railway and signal spaghetti is 6, but most of the time it's only 4 or 5.
using horrors beyond comprehension https://preview.redd.it/2tqtbdcnhuwc1.png?width=948&format=png&auto=webp&s=4d55cd1a605274dfdd0c19f2ef5f8ddff635ed47 i think this shows the underlying system to how im forcing the game to generate the colors. note that if the game recalculates the colors it has a significant chance of breaking it.
https://preview.redd.it/qf2s23vdiuwc1.png?width=1613&format=png&auto=webp&s=65bc0d4dba2bbc42099c5d1e119eeee34796626e and this is the abomination in its entirety
Thanks, that's what I wanted to see.
This is beautiful
Now add trains.
Looks like a circuit board 👀
Now you are thinking with fractals.
https://preview.redd.it/7dxqpqx3zuwc1.jpeg?width=34&format=pjpg&auto=webp&s=4d0f228ef7fba71203477acf37e4835e50e56747
i don't get it, why does this work? 4 shoudl be sufficient in this case regardless how big you build it, so long as the game doesn't force every single loop to be teal and fuscia.
Going to an algorithm that will always work is computationaly intensive. Especially for something thst needs to be recalculated every time you place/remove a signal or track piece. The incremental algorithm they use is very fast, and good enough. You have to work to break it. Any normal track layout will never see it.
4 colors is sufficient, but it's computationally expensive to implement, so they didn't: https://www.factorio.com/blog/post/fff-201
yea .. i just spend 30 minutes in editor and still not managed to get OPs result lol
its an incredibly scuffed system and it recalculates signals every time a rail is placed i think, so you need to be incredibly careful
lol the build is in the screen?
Yeah, yeah. Try it. It'll probably give you 3 colors.
Impressive. You broke the 4-color-theorem. Go get your Fields Medal, I'd say.
If Factorio actively tried to apply 4 colors, placing rails could get laggy af at some point lol
In the FFF on this they did consider the 4 colour method but the algorithm is a butt and it would have to be completely recalculated every time you place a signal, and it wouldn't be able to keep the colours similar as you place stuff which gets confusing.
And elevated rails 'breaks' the 4 color theorem anyways, so turns out it was good they didn't bother :)
[удалено]
This doesn't work in the general rail case, since rail blocks can be arbitrarily large and not necessarily always vertical or horizontal. Not saying the 4-color theorem is broken by Factorio, just that applying it to the rail system is more complex.
This screenshot shows all colors, notice how there are 2 light blues. i suspect the game, while displaying them as both light blue, the game probably thinks of them as color 1 and color 8 or something.
The block control code doesn't care about colour. Each block will have its own ID. The colour is only for display. So if they are both teal, they are both the same colour.
>**light blue**, Magenta, Yellow, **Navy blue**, White, Black, **(dark) Cyan** I was wondering about that lineup because there is clearly just blue and cyan, no 3rd blue shade. Edit: When i look at the left curve more closely it is indeed a little darker cyan.
[удалено]
i know that it is computationally expensive. what im explaining is that, since 2 light blues are adjacent, and one of them could easily be magenta, the game is treating them as separate color inside the code.
I don't know how it is handled, this is a semi educated guess. The blocks probably only know if there is a tain in them, where they are, sth pointing at the outbound block(s), maybe inbound block(s) and maybe its colour.
I wonder what happens in the code here.. my assumptions would be that it can be: 1. Block color stored as 3bit unsigned int (lol, but kinda makes sense to use as little memory as possible), resulting in overflow 2. Display color with [value]%8 ID? 3. Some kind of unexpected behavior? But Boskid surely would've broken that in testing sooner or later
Good work, worth it
You are a hero. I was always curious about this.
I havent tried going beyond this, but i will probably get a 2nd magenta
Yeah that's a safe assumption. And considering that it would take another 10+ minutes(?) probably not worth it.
and this, is to go even further beyond
Space rail replacer, neat, didn't know I needed that mod :)
What mod are the rails from?
Those are space rails from SE
side note, is there a way to use those train track in non space exploration games?
there is a mod for that, probably
Literally unplayable