Author Topic: Research code bugs summary  (Read 2125 times)

Online Meridian

  • Global Moderator
  • Commander
  • *****
  • Posts: 4978
  • Aaand we're back!
    • View Profile
    • My Wiki
Research code bugs summary
« on: June 22, 2017, 09:27:35 pm »
Continuation of hellrazor's post: https://openxcom.org/forum/index.php/topic,5494.0.html

Quote
-- 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.

Quote
-- 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.

Quote
-- 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#msg81018

6. 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.

Quote
-- 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.

Quote
-- 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.

Quote
-- 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)

Quote
-- "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...
« Last Edit: June 26, 2017, 11:56:04 am by Meridian »

Offline drages

  • Colonel
  • ****
  • Posts: 150
    • View Profile
Re: Research code bugs summary
« Reply #1 on: June 22, 2017, 09:39:38 pm »
This is realy great when i plan to make a huge research tree!

I will wait and probably be a tester when i work on my mod.


« Last Edit: June 22, 2017, 11:47:03 pm by drages »

Offline Stoddard

  • Colonel
  • ****
  • Posts: 457
  • in a fey mood
    • View Profile
    • Linux builds & stuff
Re: Research code bugs summary
« Reply #2 on: June 22, 2017, 11:32:01 pm »
Great work. Beautiful cleanup. You also beat me to it :)

I think I have a hunch on how to make zero-cost hidden topics optional without new data in saves or much extra calculations, but that's later.

Now - congratulations.



Offline hellrazor

  • Commander
  • *****
  • Posts: 2188
  • Deep Ruleset Digger & Bughunter
    • View Profile
    • Github Account
Re: Research code bugs summary
« Reply #3 on: June 22, 2017, 11:33:48 pm »
Hi Merdian,

just had a brief read through the long post here.
I am grateful that I somehow managed to help in at least locating/fixing some of the bugs.
Can I see the changes you made towards the other functions regarding the research handling codebase? (I presume you have it on github? So if you do not mind I will ask some questions there.)

I looked at addFinishedResearch, getDependeablResearch and getDependeablResearchBasic, trying to make a sense of all the recursions this code was calling each time. I think a lot of those were not really needed, and could have been handled totally differently. - Unofrtunately i didn't had the time in the last few days to twelve into the deepness of how they are connected to each other. My head still hurts from the initial logic reconstruction.

And YES i understand why someone called his iterator "ohBoy" now :D

Looking forward to asking questions and provide more help if I can.
« Last Edit: June 22, 2017, 11:37:30 pm by hellrazor »

Online Meridian

  • Global Moderator
  • Commander
  • *****
  • Posts: 4978
  • Aaand we're back!
    • View Profile
    • My Wiki
Re: Research code bugs summary
« Reply #4 on: June 23, 2017, 09:46:53 am »
Great work. Beautiful cleanup. You also beat me to it :)

I didn't know you were working on it... why didn't you say so?

I think I have a hunch on how to make zero-cost hidden topics optional without new data in saves or much extra calculations, but that's later.

I have a few ideas too, but the commit is already big enough. I would leave it this way for now... with the same (vanilla) ruleset as before, just working correctly.

We can add more modding features into OXCE+ later, no need to make Sup's life harder than it already is.

I am grateful that I somehow managed to help in at least locating/fixing some of the bugs.
Can I see the changes you made towards the other functions regarding the research handling codebase? (I presume you have it on github? So if you do not mind I will ask some questions there.)

Latest code is here:
https://github.com/MeridianOXC/OpenXcom/commits/hellrazor

It's still not final, I need to at least retest all the bugs again.
Comments/questions are welcome tho...

Offline SupSuper

  • Lazy Developer
  • Administrator
  • Commander
  • *****
  • Posts: 2116
    • View Profile
Re: Research code bugs summary
« Reply #5 on: June 23, 2017, 01:17:06 pm »
Please note that almost none of these bugs affect vanilla... this is about general correctness, completeness and consistency of the openxcom modding features.
Well that's a load off my mind. ;)

My solution for research would be to tear out the whole thing to make something new that makes sense, which would pretty much break all backwards-compatibility, so I applaud this approach to inject some sanity into the madness. As someone who's seen the hair's nest from the start, all I can say is... good luck, and thanks for all the fish. :)

Offline Stoddard

  • Colonel
  • ****
  • Posts: 457
  • in a fey mood
    • View Profile
    • Linux builds & stuff
Re: Research code bugs summary
« Reply #6 on: June 23, 2017, 02:39:23 pm »
I didn't know you were working on it... why didn't you say so?

I generally don't, unless I have results.

I have a few ideas too, but the commit is already big enough. I would leave it this way for now... with the same (vanilla) ruleset as before, just working correctly.

Yup, better have it paced.

no need to make Sup's life harder than it already is.

So true.

Online Meridian

  • Global Moderator
  • Commander
  • *****
  • Posts: 4978
  • Aaand we're back!
    • View Profile
    • My Wiki
Re: Research code bugs summary
« Reply #7 on: June 26, 2017, 02:12:40 pm »
PR: https://github.com/SupSuper/OpenXcom/pull/1155

As far as I can say, everything works as described above.

--

There is one additional thing I want to implement... poppedManufacture (similar to poppedResearch), but it's not relevant for vanilla (only for mods) and I want to make a new commit for that.
For explanation, that would be used when topics researchable multiple times also unlock some manufacture... e.g. if Sectoid Engineer would unlock let's say "Enslave Sectoid Engineer" manufacture project, we don't want the popup about possible new manufacture to pop up more than once.

Offline hellrazor

  • Commander
  • *****
  • Posts: 2188
  • Deep Ruleset Digger & Bughunter
    • View Profile
    • Github Account
Re: Research code bugs summary
« Reply #8 on: June 26, 2017, 11:17:47 pm »
PR: https://github.com/SupSuper/OpenXcom/pull/1155

As far as I can say, everything works as described above.

--

There is one additional thing I want to implement... poppedManufacture (similar to poppedResearch), but it's not relevant for vanilla (only for mods) and I want to make a new commit for that.
For explanation, that would be used when topics researchable multiple times also unlock some manufacture... e.g. if Sectoid Engineer would unlock let's say "Enslave Sectoid Engineer" manufacture project, we don't want the popup about possible new manufacture to pop up more than once.

That would be really nice =)