I know from experience that the tech tree in this game can be overwhelming to new players, so any sort of improvement in usability might make a big difference to player retention, not to mention overall quality of life. Here are a few thoughts and questions related to that.
I eventually discovered that single-clicking on a tech when the Pedia is open takes you to the Pedia page for that tech, which is quite useful for reading through descriptions of different techs. However, as far as I can tell, single-clicking when the Pedia isn't open doesn't do anything at all. Is that right? This has got to be unfriendly to new players, as single-clicking is the most common action with a mouse. I would recommend that single-clicking a tech do one or both of the following: (1) Open the Pedia to that tech, even if the Pedia isn't open already, and/or (2) highlight the various lineages leading up to that tech and leading on away from it. Here I'm imagining maybe having dots move along the lines sort of like the way dots move along ships' flight paths on the galaxy map. This would be tremendously useful for tracing long-distance connections to the other end.
Human vision is really good at doing "color pop out" being able to quickly see a particular color among a jumble of colors. The color-coding of techs by families takes advantage of this nicely. However, this could also be really useful for helping to make better sense of the jumbles of grey spaghetti that appear connecting the columns together. As a first approximation, I would suggest making each connection be the color that results from averaging the family colors at each end of the connection together with the current grey color. That would provide enough color differentiation for many of the long lines to be much more easily traceable through the tangles of spaghetti, without affecting the overall aesthetic very much.
Speaking of spaghetti, I've noticed that the techs are often drawn distributed in a way that involves much more criss-crossing of connections than would be necessary. Does anyone know what algorithm is used to distribute the techs on the display? Is there potential for fiddling with or replacing that algorithm? (If it's in Python, I might be able to knock together something that would work better. If it's in C, that's less fun for me, so I probably wouldn't mess with it. Or maybe it's from some off-the-shelf package like Graphviz?)
The filter buttons at the bottom of the tech tree are quite useful. However, I think it would be useful to somehow have an option that forces the prerequisites of displayed techs also to be displayed, as that is very often relevant for the decisions you want to make. E.g., if I display just engineering to be able to see ship hulls, it's a disappointing surprise to later learn that some of those that looked easy to research actually had a long line of prerequisites that weren't displayed!
Speaking of those filter options, there are two of them with different icons that are each labeled "Partially Unlocked" and I haven't been able to make sense of what they're supposed to do. What am I missing?
Tech Tree UI Ideas and Questions
Moderator: Oberlus
- Geoff the Medio
- Programming, Design, Admin
- Posts: 13603
- Joined: Wed Oct 08, 2003 1:33 am
- Location: Munich
Re: Tech Tree UI Ideas and Questions
See: https://github.com/freeorion/freeorion/ ... t.cpp#L224Telos wrote:Does anyone know what algorithm is used to distribute the techs on the display?
Sure, patches welcome.Is there potential for fiddling with or replacing that algorithm?
Graphviz used to be used, but there were license issues with it. OGDF was then used, but was itself replaced fairly soon with the current custom code.Or maybe it's from some off-the-shelf package like Graphviz?)
People seem to get really annoyed at having the pedia window ever be visible on the tech tree, and would likely object quite a bit if it opened itself up unrequested.Telos wrote:I would recommend that single-clicking a tech do one or both of the following: (1) Open the Pedia to that tech, even if the Pedia isn't open already
This used to happen, but was (probably?) lost during a rendering reworking. Would be good to restore highlighting of the selected tech and related connected techs.(2) highlight the various lineages leading up to that tech and leading on away from it.
Re: Tech Tree UI Ideas and Questions
Thanks for linking me to the relevant bit of code! My C is a bit rusty, but here's how I understand what it does.
One easy-to-fix oddity has to do with leaf techs that appear left of the most populated column, as these will automatically get moved near the top of the diagram, regardless of color. For example, if you hide completed techs, this is why things like Mass Drivers will suddenly jump up to the top of the diagram, away from all the other weapon techs (as soon as the tree gets shifted around enough that Mass Drivers 4 is to the left of the most populous column). One fairly easy way to improve this would be to add a condition around line 696 in the case where the count of already-placed parents and children is zero, and instead of just jumping to the top of the diagram, instead have it look in nearby columns for other techs of the same color, and use their average height instead. This will work as long as the most populous column retains enough techs to keep the standard color ordering in place.
Some other oddities could probably be helped by a careful examination of the default ordering (wherever it comes from?), ensuring that overall it is sorted in such a way that you'd always be happy having items that are higher in the list appear higher in the diagram than items further down in the list, should they all appear together in the most populous column. For example, this fix could probably help make hulls of the same type appear together, rather than being randomly sprinkled around the engineering section as they currently are. (E.g., when I look at the full tech tree, organic hulls are not grouped together in the populous fourth column, and I think this must just be due to a suboptimal default ordering sticking Force Energy Compression between them.)
This won't fix everything though, as anything outside the most populous column will still get yanked heavily towards any non-engineering connections it has (then nudged back into the engineering section if it's still close), which will make for a jumble of spaghetti within the engineering section. To help with that, I would suggest not placing techs at the unweighted average height of their parents/children, but instead using a weighted average which weighs parents/children of the same color more heavily than ones of other colors (around lines 680 and 687 in the code). By still taking the off-color ones into account, this can help to nudge techs in the direction of their-off-color prerequisites, but hopefully not yank them so far away from the same-color techs to which they are intuitively more closely related. (Call this the "red-headed stepchild" rule!)
Another fairly easy change that could help a lot would be just to add additional colors/subfamilies to the color scheme. E.g., if energy hulls are marked as being a different subfamily from organic hulls for the purposes of sorting, this would help a lot to keep hulls of the same type shuffled together. I would suggest similar subfamilies for different weapon-types, and for planetary defense types.
These changes are quick and easy, but they're still no substitute for something that more explicitly tries to avoid unnecessary crossed connections. You would probably get some mileage (around line 501 in the code) out of nudging or "wobbling" things not just in ways that cluster colors together better, but also in ways that reduce the number of crossed connections. Some crossed connection are quite easy to detect (e.g., if I connect to A, and my northern neighbor connects to B, but A is due north of B, then our connections must cross!) If wobbling could also be triggered in cases where it helps to reduce the number of crossings like this, this would probably work a few wrinkles out of many of the diagrams.
Of course, these wobbles are just small local optimizations, so won't be able to find more global maxima. Doing perfectly at that is an NP-hard problem so probably not feasible with this many techs. We could still do *better* at that though, but probably the best way to do that would be to start incrementally building a diagram from the right, rather than the middle, inserting new branches in a much more thoughtful manner. But that'd require much bigger changes to existing code, and might end up noticably slower to execute. So that's probably not in the cards any time soon.
Still, the quick local optimizations I suggested would provide quality-of-life improvements over the way it is. I'm not currently well-set-up to compile and test C-code, so I probably shouldn't make these changes myself. But if someone wanted, I could pretty easily provide an approximation of correct code for the changes I suggested, modulo the fact that my rusty C-syntax will likely require some tweaking.
- Break the nodes into columns, based on maximal distance from pre-specified "start nodes".
- Start with the column that will have the most techs, and place the techs into that column in their default order and maybe nudge them around a bit to help like-colored nodes sit together.
- Then work outward through the adjoining columns in each direction, attempting to put each node at the average altitude of whatever of its parents or children have already been placed (or as high as possible for leaf nodes without any children to determine their location), diverting latecomers into the nearest unoccupied seat; and then again nudging them around a bit to help like-colored nodes sit together.
- Then create connections between them, and you're done.
One easy-to-fix oddity has to do with leaf techs that appear left of the most populated column, as these will automatically get moved near the top of the diagram, regardless of color. For example, if you hide completed techs, this is why things like Mass Drivers will suddenly jump up to the top of the diagram, away from all the other weapon techs (as soon as the tree gets shifted around enough that Mass Drivers 4 is to the left of the most populous column). One fairly easy way to improve this would be to add a condition around line 696 in the case where the count of already-placed parents and children is zero, and instead of just jumping to the top of the diagram, instead have it look in nearby columns for other techs of the same color, and use their average height instead. This will work as long as the most populous column retains enough techs to keep the standard color ordering in place.
Some other oddities could probably be helped by a careful examination of the default ordering (wherever it comes from?), ensuring that overall it is sorted in such a way that you'd always be happy having items that are higher in the list appear higher in the diagram than items further down in the list, should they all appear together in the most populous column. For example, this fix could probably help make hulls of the same type appear together, rather than being randomly sprinkled around the engineering section as they currently are. (E.g., when I look at the full tech tree, organic hulls are not grouped together in the populous fourth column, and I think this must just be due to a suboptimal default ordering sticking Force Energy Compression between them.)
This won't fix everything though, as anything outside the most populous column will still get yanked heavily towards any non-engineering connections it has (then nudged back into the engineering section if it's still close), which will make for a jumble of spaghetti within the engineering section. To help with that, I would suggest not placing techs at the unweighted average height of their parents/children, but instead using a weighted average which weighs parents/children of the same color more heavily than ones of other colors (around lines 680 and 687 in the code). By still taking the off-color ones into account, this can help to nudge techs in the direction of their-off-color prerequisites, but hopefully not yank them so far away from the same-color techs to which they are intuitively more closely related. (Call this the "red-headed stepchild" rule!)
Another fairly easy change that could help a lot would be just to add additional colors/subfamilies to the color scheme. E.g., if energy hulls are marked as being a different subfamily from organic hulls for the purposes of sorting, this would help a lot to keep hulls of the same type shuffled together. I would suggest similar subfamilies for different weapon-types, and for planetary defense types.
These changes are quick and easy, but they're still no substitute for something that more explicitly tries to avoid unnecessary crossed connections. You would probably get some mileage (around line 501 in the code) out of nudging or "wobbling" things not just in ways that cluster colors together better, but also in ways that reduce the number of crossed connections. Some crossed connection are quite easy to detect (e.g., if I connect to A, and my northern neighbor connects to B, but A is due north of B, then our connections must cross!) If wobbling could also be triggered in cases where it helps to reduce the number of crossings like this, this would probably work a few wrinkles out of many of the diagrams.
Of course, these wobbles are just small local optimizations, so won't be able to find more global maxima. Doing perfectly at that is an NP-hard problem so probably not feasible with this many techs. We could still do *better* at that though, but probably the best way to do that would be to start incrementally building a diagram from the right, rather than the middle, inserting new branches in a much more thoughtful manner. But that'd require much bigger changes to existing code, and might end up noticably slower to execute. So that's probably not in the cards any time soon.
Still, the quick local optimizations I suggested would provide quality-of-life improvements over the way it is. I'm not currently well-set-up to compile and test C-code, so I probably shouldn't make these changes myself. But if someone wanted, I could pretty easily provide an approximation of correct code for the changes I suggested, modulo the fact that my rusty C-syntax will likely require some tweaking.
Re: Tech Tree UI Ideas and Questions
Oops, I see now that I misunderstood how the nudging works. In trying to minimize "family" distance, it's not trying to nudge things closer to their *color* family, but instead closer to their parents and children in neighboring columns. So basically this is just going to kick in in cases where two nodes were vying for the same ideal seat, the later-comer got diverted off to the nearest available seat, and then nudging discovers that a swapping a latecomer with something else would make nodes be closer to their immediate relatives on average, which then could open up space for a cascade of further swaps. But it looks like this isn't taking color into account at all, so (unless we make it start taking color into account) adding more subcolors may not actually help much at all.
Re: Tech Tree UI Ideas and Questions
I noticed another way in which the current algorithm is pretty clearly suboptimal. In calculating the "ideal" height to put a node, it computes the arithmetic mean of the heights of the connected nodes (lines 678-697). The more total length of connections there are, the more opportunities there will be for connections to cross each other, so it's best to minimize this total length. To do this, it would be much better to use the *median* rather than the *mean*. Any move away from the median shortens the few connections you're moving towards, while lengthening the many connections you're moving away from. (When there's an even number of nodes, any place between the two tied-for-median nodes will yield the same total distance.) When the current program uses the mean, it yanks nodes off in the direction of outlier prerequisites, which reduces the distance to a single outlier, but at cost of increasing the distance to multiple other nodes, which overall is a move for the worse. This is probably a big part of the reason why closely related nodes, like hulls in the same family, end up getting yanked toward their off-color prerequisites, rather than staying tightly clustered together with the nodes with which they enjoy more connections.
The nudging/"wobbling" part of the algorithm actually does this more sensibly, attempting to reduce total connection distance, rather than trying to approach arithmetic means. In some cases, this will manage to correct for the suboptimal calculation of "ideal" positions earlier on. But the success of nudging relies upon there being free spaces and/or other nodes that are conveniently happy to swap, which won't always be the case, so nudging won't always stumble into good fixes. It'd be much better to just put nodes in better "ideal" positions to start with.
The nudging/"wobbling" part of the algorithm actually does this more sensibly, attempting to reduce total connection distance, rather than trying to approach arithmetic means. In some cases, this will manage to correct for the suboptimal calculation of "ideal" positions earlier on. But the success of nudging relies upon there being free spaces and/or other nodes that are conveniently happy to swap, which won't always be the case, so nudging won't always stumble into good fixes. It'd be much better to just put nodes in better "ideal" positions to start with.