[A17] Organized Research Tab v1.0.3

Started by Lazevedo, March 12, 2017, 09:41:25 PM

Previous topic - Next topic

Lazevedo

Organized Research Tab

Description
When you use mods that add research projects, your Research Tab gets cluttered, sometimes with projects out of view. This mod presents a solution to that problem.

The main sorting criteria is dependency. Think of each column you see as a layer, organized in way that allows projects to appear more to the right than its prerequisites. Also, layers are internally sorted to minimize edge crossing (those lines that indicate dependency), in order to avoid a spaghetti look.

The problem of drawing that kind of structure in a aesthetically pleasing way is an old one and many computer scientists dedicated themselves to solving some aspects of it along the last few decades. I chose to follow what is known as the Sugiyama Framework, while the sorting part of it is a version of the Coffman-Graham algorithm.

Download
Steam (v1.0.3 stable) [A17]
GitHub
   |- (v1.0.2 stable) Source | Package [A16]
   |- (v1.1.2 beta) Source | Package (WIP, don't use it yet if you have too many mods) [A16]

Compatibility
Compatible with your saved games. Not compatible with other mods that replace the Research Tab.

FAQ
  • Does it work with the vertical bar mod?
When you use this mod, you won't need a vertical bar.

Change Log
Version 1.1.2 beta (2017-03-27)
- Better looks
- Calculations are now done in a thread separate from Main Thread, so no more impact on loading time
- Still causing freezes and crashes when a high number of mods is used (1.1.x issue)

Version 1.0.3 stable (2017-05-25)
- Emergency update to A17

Version 1.0.2 stable (2017-03-15)
- Vertical spacing slightly decreased
- No longer causes recalculations when switching between colonies/camps


死亡领主鸩毒

U say its incompatibel with other mods changing the Research bar. I guess that includes a mod that adds a vertical Scrollbar to the Research tab ?

Otherwise pretty nice idea the overload clutter thingy can distract and confuse so having them organized is kinda neat.

Greetings

Lazevedo

You don't need a vertical bar if you use this mod.

死亡领主鸩毒

Quote from: Lazevedo on March 12, 2017, 10:53:24 PM
You don't need a vertical bar if you use this mod.

Ill wait then for the Github release and test it out =)

AngleWyrm

Looking forward to the non-steam release
My 5-point rating system: Yay, Kay, Meh, Erm, Bleh

Lazevedo

There you go, I added a Dropbox link.

skullywag

Seeing as some people have messed with this before on the modders discord (feel free to pm me for an invite, theres some people here (fluffy) that would love to have a chat with you lol), a good test is to run the Hardcore SK pack against it, if it can handle that thing most peoples modpacks will be fine.
Skullywag modded to death.
I'd never met an iterator I liked....until Zhentar saved me.
Why Unity5, WHY do you forsake me?

SpaceDorf

I just loaded the midgame with 150+ mods running.

It worked. And it's beautiful.

Quote from: skullywag on March 13, 2017, 08:51:24 AM
Seeing as some people have messed with this before on the modders discord (feel free to pm me for an invite, theres some people here (fluffy) that would love to have a chat with you lol)

woah .. that sounds threatening  :-*
Maxim 1   : Pillage, then burn
Maxim 37 : There is no overkill. There is only open fire and reload.
Rule 34 of Rimworld :There is a mod for that.
Avatar Made by Chickenplucker

Lazevedo

Quote from: SpaceDorf on March 13, 2017, 10:07:00 AM
I just loaded the midgame with 150+ mods running.

It worked. And it's beautiful.
I'm really glad to hear that!

Would you mind opening the console and telling me the what is the reported running time? It should look something like this:

<time>ms organizing Research Tab.

I believe there is a lot of potential for improvement on the performance front.


Fluffy (l2032)

nothing threathening, I just really want to know how you did the final steps ;)

I got like 3/4ths of the way there, layer assignments, crossing minimization, horizontal alignment - it was just the final block graph creation and vertical placement and compression that really screwed me up, just couldn't get it to work.

If you're interested, I've got some code that does some other things to make research prettier, as well as allowing queuing up research. I'd be perfectly happy to work together, or donate my code. God knows I don't have enough time to keep up with patching/development of my mods as it is...

PM me here, or better yet, poke me on discord.

Lazevedo

The way I see it, it takes 7 steps:

  • Step 1 - Populate requiredByThis and enforce basic topological order
This allows for bidirectional navigation and also helps dealing with dummy vertices, since it will screw edge drawing if I mess around with prerequisites too much. I hitched a ride in this pass to enforce basic ordering, since the game already almost provides it.
  • Step 2 - Transitive reduction
I currently skip this part, but I think it's important in case some modder screw up and add redundant prerequisites.
  • Step 3 - Find a topological order compliant with Coffman–Graham algorithm
I decided to go with Coffman-Graham Algorithm because it's the only one that naturally incorporates the layer width constraint (in our context, window height). Longest Path Layering and Network Simplex were my other options that I quickly discarded.
  • Step 4 - Distribute tasks among hierarchical layers
Step 3 makes this one a very trivial O(|V|+|E|). Here I take the time to apply some specifics, like bringing those lonely projects (Devilstrand, Stone Cutting, etc) to the far left.
  • Step 5 - Add dummy nodes to layers, to make edges more visible
This is essential for the next steps and it got me stuck for some time since I was doing it wrong. Coffman-Graham does not take dummy vertices into account, so my solution was to work with two width constraints, one that considers only orignal vertices and another considering dummies too. There is room for improvement here if I make those dynamic instead of fixed.
  • Step 6 - Minimize edge crossings with vertex ordering within layers
This was the really hard part and I kinda rushed through it to be able to release yesterday, since I was very anxious to do it. :) It's also the heaviest part in terms of computation and that's the main reason I believe there is so much room for performance improvement.
  • Step 7 - Set X and Y coordinates for each project based off layering
Also rushed this part and implemented it the dumbest possible way. Also, the paper I was reading to learn good heuristics for this mentioned that:
"These heuristics make good layouts quickly, but they are complicated to program and the results are sometimes noticeably imperfect. Further fine tuning is difficult because the heuristics begin to interfere with each other."
So I decided to improve that some other day.

About the offer, I'm very welcoming to your collaboration! Talk to you on discord.

Kindyj

It's Beautiful! I can't wait to download!

Der Failer

Quote from: Lazevedo on March 13, 2017, 10:19:56 AM
I'm really glad to hear that!

Would you mind opening the console and telling me the what is the reported running time? It should look something like this:

<time>ms organizing Research Tab.

I believe there is a lot of potential for improvement on the performance front.
Wow this is awesome dude!

Around 120 mods* here and only 1389ms. I mean seriously, considering the whole minute it takes to even start the game and almost another one and a half to get the save loaded, ~1.4s is like nothing to me. :)

None the less there still seem to be a few problems with cut off texts (see screenshot).

From the first look, it seems that with a huge amount of mods like I'm running, the way you sort things in to columns may not be the very best way to organize, but a) i don't think most people run that may mods, so it is a bit of a edge case and b) it is with out a doubt way better then anything else we got. And all thou i know little to nothing about programming and actual problem solving in CS, I'm generally aware that some problems are way harder to solve then they seem. So i don't really want to complain to much here. Should you anyway be interested about what I'm mumbling here, I'll be happy to provide some examples/ additional information.

*Added my currant list should you be interested. If you want to test your mod under a lot of stress, i could give you list of mods with quite some research, which should still be stableTM.

[attachment deleted by admin due to age]

Lazevedo

#13
Quote from: Der Failer on March 13, 2017, 01:50:40 PM
Around 120 mods* here and only 1389ms. I mean seriously, considering the whole minute it takes to even start the game and almost another one and a half to get the save loaded, ~1.4s is like nothing to me. :)

None the less there still seem to be a few problems with cut off texts (see screenshot).

I can totally fix that cropping!

About the complexity, you are right. Graph drawing has NP-hard written all over it, which is CS lingo for "if you don't do things smart, it will take forever; even if you do, it will not be optimal". To make this mod I spent 80% of the time reading papers and only 20% coding, but that's also because I didn't have much knowledge about this specific topic.

The problem with that many mods is the limited area for drawing. I do have some changes in mind that might improve both looks and performance. That mod list will prove itself useful when testing!  ;)

edit: improvements that improve...

Tyolan

Great idea. Could save a lot of time when trying some mod packs.
Despite not perfect for me, you can look what the mod does here: http://imgur.com/a/V3GSE. There is no bugs, but it's far more complicated to read than the original in my opinion. Good for research that are already mess up i think.