Continuation of hellrazor's post:
https://openxcom.org/forum/index.php/topic,5494.0.html-- OVERVIEW
Since SupSuper indicated willingness to merge research code corrections, I've picked up on hellrazor's code and delved into the fixing again for the 3rd time (after 2 unsuccessful attempts about a year ago... due to frustration from the code quality and subsequent lack of motivation).
For the last two weeks, I've been taking it apart and found 17 bugs in total:
- 4 critical: 1, 2, 3, 9
- 7 major: 5, 6, 7, 10, 12, 13, 16
- 4 minor: 4, 8, 11, 14
- 2 trivial: 15, 17
Please note that almost none of these bugs affect vanilla... this is about general correctness, completeness and consistency of the openxcom modding features.Unfortunately, it is really not possible to fix all these bugs without basically rewriting the whole research-logic-related code.
So, I ended up "rewriting everything".
The new code is available already, but I'll spend at least 1 more week testing it.
After that, I kindly ask any volunteers to help me with testing before making a PR.
Below is a list of bugs, with a short description and a short explanation how it was fixed.
After that some information about how the recursion was removed from the code.
And last, but not least, the complete and user-friendly explanation for modders of how EXACTLY the research ruleset works.
-- PREVIOUS RULESET LIMITATIONS
1. The "requires" attribute worked correctly only for STR_LEADER_PLUS and STR_COMMANDER_PLUS, it was hardcoded! In all other cases, it worked incorrectly or not at all.
=> Fixed. It works according to the rules at the bottom.
2. Attributes "getOneFree" and "dependencies" couldn't work together! If getOneFree was defined, dependencies were ignored.
=> Fixed. It works according to the rules at the bottom.
3. Live alien interrogations could not be protected by dependencies (not only because of the above bug, but also for other reasons).
=> Fixed. It works according to the rules at the bottom.
-- RESEARCH LOGIC BUGS (when finishing a research)
4. Finishing a research could end up in an endless loop (in case of cyclic dependencies and/or unlocks, e.g. A -> B -> C -> A)
=> Fixed. The code detects cyclic dependencies/unlocks and doesn't enter the cycle more than once.
5. Finishing a research could end up in an endless loop (even without cyclic ruleset!)
=> Fixed. The code strictly follows the rules on the bottom... the previous code could move "backwards" via one-way relations, causing endless loops even without cyclic ruleset.
Test case:
https://openxcom.org/forum/index.php/topic,4058.msg81018.html#msg810186. Finishing a research could sometimes additionally give wrong research (zero-cost topics from the "wrong half" of the research tree)
=> Fixed. Same reason as the bug above.
7. When the same research (that can yield multiple results via getOneFree or protected unlocks) was done in 2 different bases; and it was not an alien interrogation (e.g. could be for example Alien Data Slate or Encrypted Data Disc in various mods)... the second research was deleted after the first one was completed
=> Fixed. If a research topic can still yield something, it's not deleted.
8. When the same research (that cannot yield multiple results via getOneFree or protected unlocks) was done in 2 different bases; and it was an alien interrogation (e.g. Sectoid Soldier)... the second research was not deleted after the first one was completed
=> Fixed. If a research topic cannot yield anything anymore, it is deleted.
Example: if 2 alien leaders are researched at the same time and they can only unlock one more thing... after first one is researched, the second one is removed from the labs.
Note: it works only for the SAME topics... so, theoretically, if you were researching alien leader and alien commander at the same time and both of them could tell you only one thing, and it would be the SAME one thing... after researching one, the other would NOT be removed... but the probability of that is astronomically low in vanilla... and the side effect is only that you waste a little bit of research time for nothing... for me, acceptable.
-- RESEARCH LOGIC BUGS (when showing "We can now research" GUI)
9. "We can now research" GUI was never able to show any alien interrogations
=> Fixed. I removed special handling of alien interrogations from everywhere in research-related code (not only here). Alien interrogations do not have any special status or side effects anymore (with one exception: when "retain corpses" advanced option is turned on, they generate corpses)
10. "We can now research" GUI was not always showing all new topics that can be researched
=> Fixed. Instead of "guessing" what is new, we actually compare status before and status after... and show the difference.
11. "We can now research" GUI was sometimes showing more topics than needed (i.e. topics that were shown before already)
=> Fixed. Previously popped topics could have been removed from poppedResearch prematurely.
12. "We can now research" GUI was sometimes showing completely wrong topics (zero-cost topics from the "wrong half" of the research tree)
=> Fixed. Same as bug #6.
Theoretically the game could get into an endless loop here as well (just like in #4 and #5), but such conditions would already make it freeze earlier.
-- OTHER ISSUES
13. Ruleset inconsistency for topics protected by "requires"; it was possible to have such topics with cost != 0 even though the code strictly assumes that the cost for such topics must be zero
=> Fixed/Avoided. By adding a check during loading of ruleset... game will (intentionally) crash in such a case with a clear message to the user/modder about what's wrong.
14. Research logic didn't work properly with debug mode turned on.
=> Fixed. Although this is not a normal gameplay scenario, it might be useful for development/testing. Debug mode now only affects the available research in the "New Research" GUI (and nothing else within research-related code).
15. Vanilla save converter could (only theoretically) add more finished zero-cost research than desired.
=> Fixed. This is not even strictly a bug, since this cannot happen with vanilla ruleset (both XCOM and TFTD) and save converter is irrelevant for mods; still the algorithm wouldn't be robust enough if the vanilla ruleset was more complicated.
16. Vanilla save converter (XCOM only, not TFTD) was reading complete nonsense from UP.DAT file (which includes some discovered research)
=> Fixed. The ruleset was wrong and caused to read entries of 11 bytes instead of 12 bytes.
17. Vanilla save converter gives too much research score bonus.
=> Fixed. Research from UP.DAT gave extra score, while research from RESEARCH.DAT didn't. Now both don't give any extra score. Score should be given only from UIGLOB.DAT.
-- OPTIMISATIONS
A. The code was quite sub-optimal on the performance side (e.g. potentially calling expensive methods like getAvailableResearchProjects() way too many times)
This was improved by a factor between 1 and 10 in average case (hard to say exactly, because it depends on several things).
In the extreme/worst case however, the new code can be even much more than 10x faster than the old one.
Actually, in the worst case, the game would freeze (see bug #5).
B. The code was using recursion, which was inefficient, unreadable and also plain wrong. It's a small miracle it somehow "worked" at the end (except for all the bugs above, duh).
Recursion was called on 2 occasions:
1/ when finishing research: in this case non-tail recursion was replaced by tail-recursion, depth-first approach was replaced by breadth-first approach and finally the breadth-first tail recursion was replaced by a while loop equivalent
2/ when showing "We can now research" GUI: in this case, the algorithm was completely changed and doesn't use any recursion at all (not even a for/while loop equivalent)
-- "NEW" GENERIC RULES
I guess these rules are not really new, but they should actually work now!
1. "unlocks:" will make the target topic available for research
- even if its "dependencies:" are not met!
2. "requires:" will block "unlocks:" until everything in this list is researched
- and after that you may need to perform the unlock once more (since the previous unlocks were blocked, remember?)
3. "dependencies:" will keep the topic unavailable until all dependencies are fulfilled
- unless it is unlocked directly (dependencies will not block the "unlocks:" command, remember?)
4. "getOneFree:" game picks something from the listed options randomly and gives it to you as a completed research item without considering anything else (i.e. ignores both dependencies and requirements).
There is one limitation of the previous implementation, which still applies:
- Any topic protected by "requires:" must have a zero cost (cost: 0) and can only be researched indirectly (=given gratis) via unlocks
- The player will NEVER EVER see such topics directly anywhere!
- Example of such topics are: STR_LEADER_PLUS and STR_COMMANDER_PLUS
It would be possible to remove even this limitation, but it would require saving more information into the save file (and *could* break existing saves... hard to say upfront). Using zero-cost helper topics seems like an acceptable (and already used) workaround.
Stay tuned for more...
