Friday Facts #198 - Rail segment visualisation

[polatrite@gmail.com]

In terms of graphical clutter with rail indicators, I've often thought the signal placement indicator (the large green square with rounded edges, and a line attaching to the track) is quite overkill for that purpose. This graph could be substantially muted, even as far as grayscale colors.

Mooncat mentioned tinting the rails, and I think this would be a brilliant solution. The rails are already a neutral color, so applying coloration to them could convey the message (these are different blocks) without being too flamboyant.

[silverkitty23]

4-colour theorem says that you should only need four different (hopefully harmonising) colours to display any such rail-markers.

while this is technically true, that doesn't mean there's an efficient algorithm for using only 4 colors. it's much easier to throw more colors at the problem

[Voltara]

Anyway, how did you compute the 9% probability. Using formula from http://preshing.com/20110504/hash-colli ... abilities/: (1-exp((-20*19)/(2*2^32))) multiplied by number of players I can get approx. 4.2%. Am I doing something wrong (yeah, probabilities are tricky)?

I was wondering the same thing:

Code: Select all

$ bc -ql
players=10^6
blueprints=20
checksums=2^32
100 * (1 - e(players * -blueprints * (blueprints - 1) / checksums / 2))
4.32736004523505534000

When in doubt, simulate. I wrote a program that simulates 1 million users with 20 random blueprints (by computing CRC32 of randomly generated strings), and prints the percentage of trials that result in at least one collision. So far it has run 525 trials, and the results are in line with the 4.3% estimate:

Code: Select all

...
24/520 (4.615%)
24/521 (4.607%)
24/522 (4.598%)
25/523 (4.780%)
25/524 (4.771%)
25/525 (4.762%)

[Xtrafresh]

Perhaps highlighting the rails and dividing lines?

rail block vis example.png

Another vote for this!
I'd only need it to be visible when i'm working on the rails, so when i'm holding either signals or rails. Highlighting a section (by brightness) on mouse over while holding these would also be nice

[doppelEben]

Maybe make it visible if one builds a signal?

I'm one of the lesser ones with 600h gameplay and still dont be sure how signals work and have to try-and-fail each time I build up my railsystem

really looking forward for release

[svercer]

Devs, draknor is absolutely right about CRC32 not being a good choice, and it has little to do with hash output size. All of the math posted above and in the FFF is based on an incorrect assumption: that every hash value has an equal probability of being selected. This is not the case for CRC32. The numbers presented are lower bounds on the collision probability; the actual probability is much higher (probably).

Using CRC here is like... using .jpg for storing sprites instead of a bitmap format. "What's the matter, they're both images, right? An image is an image. .jpg instead of .png is no big deal." Same way, "What's the matter, a hash is a hash, right? CRC32 instead of SHA is no big deal." CRC is explicitly not intended to be used the way you're using it. It's meant as an error detection code, which is entirely different than a probabilistically-unique hash.

It probably doesn't matter if you choose the perfect hash function; MD5 might be fine here or even Murmur hash or City hash. The important thing is that you choose at least what Wikipedia calls a "non-cryptographic hash function" (i.e., one designed for hash tables, which excludes all varieties of CRC and checksum), but there's also no reason not to choose a cheap "cryptographic hash function" like SHA. (However, you might have to consider security implications. I'm not sure how blueprints and multiplayer works, but what happens if someone finds a collision with a very common blueprint — say a standard 4x4 belt balancer — and saves it to a server? Would the collided blueprint no longer be able to be used on that server?)

(Edit to add:) By the way, the reason this doesn't contradict Voltara's empirical study above is that Voltara was using randomly generated strings instead of an actual set of 20 million unique but meaningful (i.e., nonrandom) blueprints. This wouldn't matter if we were testing the collision probability of, say, SHA-1, because we already know that SHA1 produces uniformly-random output. This is not valid reasoning for CRC and thus Voltara's experiment, while interesting, was therefore not a valid predictor of real-world behavior. Because CRC is not a cryptographic hash function, nor is it meant to be, the randomness of the input can "leak through" to the output, or rather, the non-randomness of real-world blueprints can "leak through" to produce biased CRC output behavior. For example, it's entirely possible that every input starting with a '{' (or a '0' if the encoded blueprint strings are being used) results in the 14th bit of the CRC being '0' and an 80% chance that the 19th bit is '1'. This is far less likely to happen with hashes like City hash and mathematically proven not to happen with hashes like SHA-1.

[dethface]

Instead of using colors, use basic shapes maybe? Triangle, circle, diamond, etc. I would suggest the visualization be a toggle and also appear in map view kinda like electric grid and pollution. This would really only be used when building and once train signals become understood maybe not all So i dont think it needs to be there all the time. Quick toggle to see what's what even if just in map i think would be perfect.

[menschmaschine]

Greetings kovarex, why would it be a concern at all, if it looks ugly as long as it it depicts data properly and easy to read?

It is not supposed to be toggled on at all times and users should be (and in this game probably are) aware of that,
so they would not blame the developers for a bad GUI-Design nor eve nwrite bad reviews based on such thoughts.

Also, iffitz ugly, that's one more reason to not have it toggled on all the time °winks°

The image with the squares is kinda confusing i would say, the lines with T's at their end looks much better.

[Venatos]

you could put the railsignalblock-details into "Alt"-mode, like the inserter and assambler-details. if its a temporary visual, its not that bad if its a little cluttered.

[brunzenstein]

i find the colored squares as in the debug tool much more less distracting than the straight lines.
Why not keep it that way?

[Sigma1]

I like the current debug option very much when designing intersections, and I am happy to hear it will be more easily accessible. I also think that it wouldn't really matter if the colours stayed the way they are right now, as they are not supposed to be on all the time.

[IronCartographer]

Here's an idea: "Less is more" AKA "What do current signals/rail see, and why?"

There are two main things people have trouble understanding with trains:

• Signals divide rail into blocks, turning red only when the next block is occupied
• Chain signals reflect the next signal along a train's route, turning red only when every possible next signal is red

Global rail block coloring aims to help with the former, but coloring every block is messy (random colors everywhere!), expensive to avoid conflicts/inconsistencies (unless you add even more random colors! ), and does little to help with chain signals.

How about this: Highlight the entire signal block while mousing over an existing rail segment, and do the same for all relevant blocks when mousing over their existing entry signals (multiple blocks for chains). Use red and green appropriately, with blue for blocks with at least one open exit, or red if mousing over a chain signal for which the block has no open exit (e.g. a crossing without merged/shared exits).

chain signal selected rail block visualization.png (2.39 MiB) Viewed 8200 times

That redundant second chain signal becomes pretty obvious here...

Cons:

• Doesn't (on its own) give a complete view of signal blocks--requires individual examination of each block with mouse hovering

Pros:

• Simpler to implement, without worry of color collisions or consistency
• Cleaner; displays in mostly unused overlay space, and only for real (built) entities
• Interactively contextual, further reducing UI clutter
• Clearly shows the connections between (chain) signals and all of their associated rail blocks, training players to read signal layouts

[mergele]

Wait you already got that? Make that stuff available for us! (Rail segment colors) I don't need it anymore, but that would probably help so much for new players... I guess whenever someone now asks about a problem with rails I can just recommend him to turn on this debug view (gotta check the name) instead of writing some long text or doing it by hand via paint.

[htgb]

It's possible to generate a sequence of visually appealing colors with a golden ratio color wheel. Using HSV color space, use fixed saturation and value according to taste, but vary the hue: start at an arbitrary point, then for each new color, add the golden ratio and modulo with one. This gives a good spread around the color wheel without requiring knowledge of how many colors will be needed, and a trivial way of tuning the flashyness of colors.

Of course, using fewer colors is still good to ensure two blocks are not too similar, but variations of this technique would probably be useful.

[Escadin]

Dat level of optimization

I really wonder if it would make any difference. Please keep us updated!

[SafetySkull]

I think I'd prefer it if the blocks looked like actual blocks. Like solid snakes surrounding the tracks with a slight gap between each one. Then you don't need different colours. It can just be a translucent teal or something

[Simon Donkers]

Few things I have in mind:Anyway, how did you compute the 9% probability. Using formula from URL: (1-exp((-20*19)/(2*2^32))) multiplied by number of players I can get approx. 4.2%. Am I doing something wrong (yeah, probabilities are tricky)?

You beat me to it as well, athough the number is 4.4237%, that is also the answer from the formula you posted. I got there by searching for birthday problem though, instead of hash collision.

As far as tracks, can you not highlight the current block where my mouse is hovering during the placement of signals, that should give me a good idea how big blocks are.
Rough example imgur.com/a/uiINF
I think showing all blocks in screen will simply add a lot of extra colors and displays, the more subtle you can make the option, the fewer people who will ask for a toggle to switch it off.

[anarcobra]

Devs, draknor is absolutely right about CRC32 not being a good choice, and it has little to do with hash output size. All of the math posted above and in the FFF is based on an incorrect assumption: that every hash value has an equal probability of being selected. This is not the case for CRC32. The numbers presented are lower bounds on the collision probability; the actual probability is much higher (probably).

Using CRC here is like... using .jpg for storing sprites instead of a bitmap format. "What's the matter, they're both images, right? An image is an image. .jpg instead of .png is no big deal." Same way, "What's the matter, a hash is a hash, right? CRC32 instead of SHA is no big deal." CRC is explicitly not intended to be used the way you're using it. It's meant as an error detection code, which is entirely different than a probabilistically-unique hash.

It probably doesn't matter if you choose the perfect hash function; MD5 might be fine here or even Murmur hash or City hash. The important thing is that you choose at least what Wikipedia calls a "non-cryptographic hash function" (i.e., one designed for hash tables, which excludes all varieties of CRC and checksum), but there's also no reason not to choose a cheap "cryptographic hash function" like SHA. (However, you might have to consider security implications. I'm not sure how blueprints and multiplayer works, but what happens if someone finds a collision with a very common blueprint — say a standard 4x4 belt balancer — and saves it to a server? Would the collided blueprint no longer be able to be used on that server?)

(Edit to add:) By the way, the reason this doesn't contradict Voltara's empirical study above is that Voltara was using randomly generated strings instead of an actual set of 20 million unique but meaningful (i.e., nonrandom) blueprints. This wouldn't matter if we were testing the collision probability of, say, SHA-1, because we already know that SHA1 produces uniformly-random output. This is not valid reasoning for CRC and thus Voltara's experiment, while interesting, was therefore not a valid predictor of real-world behavior. Because CRC is not a cryptographic hash function, nor is it meant to be, the randomness of the input can "leak through" to the output, or rather, the non-randomness of real-world blueprints can "leak through" to produce biased CRC output behavior. For example, it's entirely possible that every input starting with a '{' (or a '0' if the encoded blueprint strings are being used) results in the 14th bit of the CRC being '0' and an 80% chance that the 19th bit is '1'. This is far less likely to happen with hashes like City hash and mathematically proven not to happen with hashes like SHA-1.

I think you are understating the problem.
We are talking about user inputs where the user has almost complete control over what string gets hashed.
Using something like CRC makes it almost trivial to find collisions and as soon as someone writes up a script to find collisions with a specific string you will have a problem with denial of service attacks.
Yes, for random data you have a small chance of collisions. But this is not random data, it is user generated data.
The chance of collision when someone is looking for it is close to 100%.

[bobucles]

I'm not really seeing the issue with identical blueprints here? It's not like a blueprint library is going to be filled to the brim with gigabytes of information. Blueprints are on the order of a handful of kb, and the typical library will stretch into the MB at best. If a player wants to build a massive database of every single factory ever that's their own business, but the ordinary user doesn't need to clean house any more often than once in a blue moon.

Any way I think you can solve this problem pretty concretely by using more than one reference point of data. A hash collision is one thing, but how many hash collisions are 50x12, have 12 steam boilers and were saved on 6:30 tuesday? I'm pretty sure the odds of that are close enough to 0 for anyone.

[meganothing]

We are talking about user inputs where the user has almost complete control over what string gets hashed.
Using something like CRC makes it almost trivial to find collisions and as soon as someone writes up a script to find collisions with a specific string you will have a problem with denial of service attacks..

So someone would craft recipes that collide with recipes of other users so that the recipes of these users would be deleted? Or he could prevent many basic recipes to be created later by just making a junk recipe that has the same CRC? Probably only the second method is possible since I assume if a new recipe is imported into a multiplayer game and it is already there, the new recipe is the one that gets deleted.

So yes, if one of above is possible, Factorio needs a real cryptographic hash like SHA*. Especially since that change is probably just a simple replacement of one library function with another, hash libraries are not really hard to find.