Author Topic: Reworked Research Code  (Read 4201 times)

Offline hellrazor

  • Commander
  • *****
  • Posts: 2207
  • Deep Ruleset Digger & Bughunter
    • View Profile
    • Github Account
Reworked Research Code
« on: June 03, 2017, 09:21:10 pm »
My Dear SupSuper and all others,

it took me a while, but i managed to rewrite the essential parts of the research code
Respective functions are:
 - getAvailableResearchProjects
 - isResearchAvailable

They are located in "SavedGame.cpp"

Changes:
 - Checking for a alive Alien and "getOneFree" have been unified
 - Checking also if their "unlocks" are in the discovered list
 - As long as not all "getOneFree" and "unlocks" are in the discovered list, the research topic stays available
 - When both are in discovered the research gets removed from list
 - Code has been made more readable and understandable, also commented

Differences:
 - All alive Aliens will stay around for research, as long as their "getOneFree" and "unlocks" are not discovered

Testing:
 - using the attached testscenario i was able to confirm that all code behaves like it should
   meaning i could research all research topics and achieve to fly to mars

If someone would, please test the code, to verify it is working 100%, i already did but more people can not hurt - THANKS.

Changed getAvailableResearchProjects:
Code: [Select]
/**
 * Get the list of RuleResearch which can be researched in a Base.
 * @param projects the list of ResearchProject which are available.
 * @param mod the game Mod
 * @param base a pointer to a Base
 */
void SavedGame::getAvailableResearchProjects (std::vector<RuleResearch *> & projects, const Mod * mod, Base * base) const
{
        const std::vector<const RuleResearch *> & discovered(getDiscoveredResearch());
        std::vector<std::string> researchProjects = mod->getResearchList();
        const std::vector<ResearchProject *> & baseResearchProjects = base->getResearch();
        std::vector<const RuleResearch *> unlocked;
        for (std::vector<const RuleResearch *>::const_iterator it = discovered.begin(); it != discovered.end(); ++it)
        {
                for (std::vector<std::string>::const_iterator itUnlocked = (*it)->getUnlocked().begin(); itUnlocked != (*it)->getUnlocked().end(); ++itUnlocked)
                {
                        unlocked.push_back(mod->getResearch(*itUnlocked, true));
                }
        }
        for (std::vector<std::string>::const_iterator iter = researchProjects.begin(); iter != researchProjects.end(); ++iter)
        {
                RuleResearch *research = mod->getResearch(*iter);

                // Check if a research is available,
                // when this is not the case remove from list
                if (!isResearchAvailable(research, unlocked, mod))
                {
                        continue;
                }

                // Check if the research has "requires" which need to be satisfied,
                // if so count them and check if all of them are in "discovered",
                // if not remove from list.
                // Check is performed here in case a modder thinks giving a "requires" to alive aliens or item with getOneFree is somehow approriate.
                // We also do not call all the rest of the function, hopefully saving some performance.
                if (!research->getRequirements().empty())
                {
                        size_t countRequirements(0);
                        for (size_t itReqs = 0; itReqs != research->getRequirements().size(); ++itReqs)
                        {
                                std::vector<const RuleResearch *>::const_iterator itDiscovered = std::find(discovered.begin(), discovered.end(), mod->getResearch(research->getRequirements().at(itReqs)));
                                if (itDiscovered != discovered.end())
                                {
                                        countRequirements++;
                                }
                        }
                        if (countRequirements != research->getRequirements().size())
                        {
                                continue;
                        }
                }

                // Lets check the list of already discovered researches and take care of cleaning up
                // the research menu list when needed, but keep alive aliens and items with getOneFree around
                // as long as they have something to discover by the player.
                std::vector<const RuleResearch *>::const_iterator itDiscovered = std::find(discovered.begin(), discovered.end(), research);
                bool liveAlien = mod->getUnit(research->getName()) != 0;
                if (itDiscovered != discovered.end())
                {
                        bool remove = true;

                        // Check if research is a item with getOneFree,
                        // which is still available,
                        // if so do not remove from list
                        if (!liveAlien && !research->getGetOneFree().empty())
                        {
                                if (isResearchAvailable(research, unlocked, mod))
                                {
                                        remove = false;
                                }
                        }
                        if (!liveAlien && remove)
                        {
                                continue;
                        }

                        // Check if alive alien still is available for research,
                        // if so do not remove from list
                        else if (liveAlien)
                        {
                                if (isResearchAvailable(research, unlocked, mod))
                                {
                                        remove = false;
                                }
                                if (remove)
                                {
                                        continue;
                                }
                        }
                }
                if (std::find_if (baseResearchProjects.begin(), baseResearchProjects.end(), findRuleResearch(research)) != baseResearchProjects.end())
                {
                        continue;
                }
                if (research->needItem() && base->getStorageItems()->getItem(research->getName()) == 0)
                {
                        continue;
                }
                projects.push_back (research);
        }
}

Changed isResearchAvailable:
Code: [Select]
/**
 * Check whether a ResearchProject can be researched.
 * @param r the RuleResearch to test.
 * @param unlocked the list of currently unlocked RuleResearch
 * @param mod the current Mod
 * @return true if the RuleResearch can be researched
 */
bool SavedGame::isResearchAvailable (RuleResearch * r, const std::vector<const RuleResearch *> & unlocked, const Mod * mod) const
{
        if (r == 0)
        {
                return false;
        }
        const std::vector<const RuleResearch *> & discovered(getDiscoveredResearch());
        bool liveAlien = mod->getUnit(r->getName()) != 0;
        if (_debug  || std::find(unlocked.begin(), unlocked.end(), r) != unlocked.end())
        {
                return true;
        }

        // Checks if research has "dependencies",
        // if so count how many of them are in discovered,
        // if all are in discovered make research available.
        // Check is performed here in case a modder thinks giving a "requires" to alive aliens or item with getOneFree is somehow approriate.
        // We also do not call all the rest of the function, hopefully saving some performance.
        if (!r->getDependencies().empty())
        {
                size_t countDependencies(0);
                for (size_t itDeps = 0; itDeps != r->getDependencies().size(); ++itDeps)
                {
                        std::vector<const RuleResearch *>::const_iterator itDiscovered = std::find(discovered.begin(), discovered.end(), mod->getResearch(r->getDependencies().at(itDeps)));
                        if (itDiscovered != discovered.end())
                        {
                                countDependencies++;
                        }
                }
                if (countDependencies != r->getDependencies().size())
                {
                        return false;
                }
        }

        // Check if research is either a alive alien or has "getOneFree",
        // if so count how many of the researches "getOneFree" and "unlocks" are in discovered,
        // if at least one of each are not in discovered keep research available.
        else if (liveAlien || !r->getGetOneFree().empty())
        {
                size_t countUnlocks(0);
                size_t countGetOneFree(0);

                if (!r->getGetOneFree().empty())
                {
                        for (size_t itGetOneFree = 0; itGetOneFree != r->getGetOneFree().size(); ++itGetOneFree)
                        {
                                std::vector<const RuleResearch *>::const_iterator itDiscovered = std::find(discovered.begin(), discovered.end(), mod->getResearch(r->getGetOneFree().at(itGetOneFree)));
                                if (itDiscovered != discovered.end())
                                {
                                        countGetOneFree++;
                                }
                        }
                }

                if (!r->getUnlocked().empty())
                {
                        for (size_t itUnlocks = 0; itUnlocks != r->getUnlocked().size(); ++itUnlocks)
                        {
                                std::vector<const RuleResearch *>::const_iterator itDiscovered = std::find(discovered.begin(), discovered.end(), mod->getResearch(r->getUnlocked().at(itUnlocks)));
                                if (itDiscovered != discovered.end())
                                {
                                        countUnlocks++;
                                }
                        }
                }

                // When counters of "getOneFree" and "unlocks" are
                // equal to the respective size of the research,
                // remove topic, since nothing more can be discovered by the player.
                if (countUnlocks == r->getUnlocked().size() && countGetOneFree == r->getGetOneFree().size())
                {
                        return false;
                }
        }
        return true;
}

EDIT: This is the final Version of the code. I did spent the last 8 hours to test it with the attached savefile for vanilla.
I also tested it against my Hardmode Expansion Mod.

EDIT2: Updated the post with the code which is on github. Main change was the comments, for a better explanation.
« Last Edit: June 08, 2017, 09:18:55 pm by hellrazor »

Offline hellrazor

  • Commander
  • *****
  • Posts: 2207
  • Deep Ruleset Digger & Bughunter
    • View Profile
    • Github Account
Re: Reworked Research Code
« Reply #1 on: June 05, 2017, 02:42:42 pm »
Final Version see post above.

Please test this so we can in some time have in the vanilla OpenXcom.
Thanks all.

Offline Stoddard

  • Colonel
  • ****
  • Posts: 459
  • in a fey mood
    • View Profile
    • Linux builds & stuff
Re: Reworked Research Code
« Reply #2 on: June 05, 2017, 03:43:09 pm »
Do you have it somewhere on github by any chance?

Offline hellrazor

  • Commander
  • *****
  • Posts: 2207
  • Deep Ruleset Digger & Bughunter
    • View Profile
    • Github Account
Re: Reworked Research Code
« Reply #3 on: June 05, 2017, 04:07:37 pm »
Do you have it somewhere on github by any chance?

Jeah just added it in a forked repo, located here: https://github.com/hellrazor4223/OpenXcom

Feel free to test.

Also created a pull request into SupSupers main branch https://github.com/SupSuper/OpenXcom/pull/1152
« Last Edit: June 07, 2017, 10:40:24 pm by hellrazor »

Offline Meridian

  • Global Moderator
  • Commander
  • *****
  • Posts: 5573
  • Aaand we're back!
    • View Profile
    • My Wiki
Re: Reworked Research Code
« Reply #4 on: June 08, 2017, 01:34:32 pm »
Hi hellrazor,

short review as asked for:

1/ I can't say if the code is correct or not... I would have to first completely understand the whole research code and then make the changes myself and then compare... which I tried to do twice several months ago and failed miserably. I won't be trying again anytime soon...

If you want just an opinion: I think it is either wrong or at least incomplete... getAvailableResearchProjects() is not called only when the "New research" GUI is opened, it's called, directly or indirectly, on many other places and messes up things into absurdity. Changing just the 2 functions you did won't solve all the issues, and will (99.9% sure of that) introduce new ones.

2/ As for the code you wrote:

a/ Why do you treat live aliens in a special way? How are they different from any other research topics? And other way around, why only getOneFree matters for other topics, are they second-class citizens?

b/ Why do you do the same check for getonefree and unlocks in both isResearchAvailable and getAvailableResearchProjects? That's textbook code duplication. If it's absolutely necessary, extract it into a separate method, if not get rid of it completely.

c/ I thought you reviewed, understood and rewrote the algorithm... why are there open questions in the comments?

Code: [Select]
/*
* Checks if there is "getOneFree" in unlocked,
* if so make research available.
* Purpose??
*/

d/ The code is inefficient... you're doing way much more computation than necessary... remember this is executed on ALL research topics in the game/mod... e.g. in PirateZ, there are actual measurable lags when the getAvailableResearchProjects function is called, and your code can make it significantly slower compared to the current code (depending on ruleset size and complexity)

For example:
- in isResearchAvailable, if you find the first not-yet-discovered getonefree topic... you don't need to continue looking for more... just return true
- in isResearchAvailable, if you find the first not-yet-unlocked topic... you don't need to continue looking for more... just return true
- in isResearchAvailable, if you find the first not-yet-discovered dependency... you don't need to continue looking for more... just return false
- the whole thing with live aliens and getonefree topics is duplicated in getAvailableResearchProjects after isResearchAvailable is called ... there must be a better way to do it (if it's necessary at all)

M.

Offline hellrazor

  • Commander
  • *****
  • Posts: 2207
  • Deep Ruleset Digger & Bughunter
    • View Profile
    • Github Account
Re: Reworked Research Code
« Reply #5 on: June 08, 2017, 03:03:43 pm »
Hi hellrazor,

short review as asked for:

1/ I can't say if the code is correct or not... I would have to first completely understand the whole research code and then make the changes myself and then compare... which I tried to do twice several months ago and failed miserably. I won't be trying again anytime soon...

I tested the code and its correctly handling all the researches in vanilla and in my own Mod.
It also does well with the FMP.

If you want just an opinion: I think it is either wrong or at least incomplete... getAvailableResearchProjects() is not called only when the "New research" GUI is opened, it's called, directly or indirectly, on many other places and messes up things into absurdity. Changing just the 2 functions you did won't solve all the issues, and will (99.9% sure of that) introduce new ones.

It is not wrong and not incomplete, it is basically a reconstruction off the old code, which indeed is a mess, brought me up to the some serious headaches.

2/ As for the code you wrote:

a/ Why do you treat live aliens in a special way? How are they different from any other research topics? And other way around, why only getOneFree matters for other topics, are they second-class citizens?

The original code had a special check for alive aliens, which was used to especially check for Leader and Commanders, so
the final research topics could be unlocked safely.
All other aliens were only handled by getOneFree, and if those were exhausted, the would no longer be researchable.
Which is ok in vanilla. But as soon as a alien Engineer for example had more topics in "unlocks" (ruleset list), then it had
in "getOneFree" (ruleset list), those topics could never be unlocked by this alien engineer (from the same race).

Now the function "isResearchAvailable" makes a explizit check for all alive aliens and for items with getOneFree,
It check if they have "unlocks" asigned via ruleset and then checks if getOneFree and unlocks appear in the list of discovered research. It only removes them from the research menu list if all of those are satiesfied, meaning the player can not get any more information out of them.

b/ Why do you do the same check for getonefree and unlocks in both isResearchAvailable and getAvailableResearchProjects? That's textbook code duplication. If it's absolutely necessary, extract it into a separate method, if not get rid of it completely.

The check only happens in "isResearchAvailable" function which is indeed called multiple times thats correct.
"getAvailableResearchProjects" handles the removel off topics from the menu list.
Normal only Items topics are only tested for "dependencies" and "requires", which the only need to satiesfy them.

c/ I thought you reviewed, understood and rewrote the algorithm... why are there open questions in the comments?

Code: [Select]
/*
* Checks if there is "getOneFree" in unlocked,
* if so make research available.
* Purpose??
*/

Thats old undeed code, it was removed.

d/ The code is inefficient... you're doing way much more computation than necessary... remember this is executed on ALL research topics in the game/mod... e.g. in PirateZ, there are actual measurable lags when the getAvailableResearchProjects function is called, and your code can make it significantly slower compared to the current code (depending on ruleset size and complexity)

For example:
- in isResearchAvailable, if you find the first not-yet-discovered getonefree topic... you don't need to continue looking for more... just return true
- in isResearchAvailable, if you find the first not-yet-unlocked topic... you don't need to continue looking for more... just return true
- in isResearchAvailable, if you find the first not-yet-discovered dependency... you don't need to continue looking for more... just return false
- the whole thing with live aliens and getonefree topics is duplicated in getAvailableResearchProjects after isResearchAvailable is called ... there must be a better way to do it (if it's necessary at all)

M.

I will answer this later need to go to work

The current code outstanding as pull request in SupSuper Master brnach is here:
https://github.com/hellrazor4223/OpenXcom/commit/7698abe1ef5c8ec68f217ed7d6603e2e3ce56134

Offline Meridian

  • Global Moderator
  • Commander
  • *****
  • Posts: 5573
  • Aaand we're back!
    • View Profile
    • My Wiki
Re: Reworked Research Code
« Reply #6 on: June 08, 2017, 03:55:12 pm »
I tested the code and its correctly handling all the researches in vanilla and in my own Mod.
It also does well with the FMP.

It is not wrong and not incomplete, it is basically a reconstruction off the old code, which indeed is a mess, brought me up to the some serious headaches.

Chuck Norris is nobody next to you ;)

The current code outstanding as pull request in SupSuper Master brnach is here:
https://github.com/hellrazor4223/OpenXcom/commit/7698abe1ef5c8ec68f217ed7d6603e2e3ce56134

OK, so ignore the whole review above, it's obsolete.

I reviewed the code you have pasted here on June 3rd or 4th (I copied it from this post on Sunday morning, just before I went on vacation)... and said was definitely final and 100% working... thanks for wasting my time.
I'm not gonna review (yet another) new version again...

Btw. you've posted many pastebin links on IRC earlier, and amended source code pasted here on forum at least once (hard to check how many times it was actually)... and EACH time you say now it's 100% working... thanks, but no thanks.
« Last Edit: June 08, 2017, 04:10:05 pm by Meridian »

Offline hellrazor

  • Commander
  • *****
  • Posts: 2207
  • Deep Ruleset Digger & Bughunter
    • View Profile
    • Github Account
Re: Reworked Research Code
« Reply #7 on: June 08, 2017, 07:44:44 pm »
Chuck Norris is nobody next to you ;)

OK, so ignore the whole review above, it's obsolete.

I reviewed the code you have pasted here on June 3rd or 4th (I copied it from this post on Sunday morning, just before I went on vacation)... and said was definitely final and 100% working... thanks for wasting my time.
I'm not gonna review (yet another) new version again...

Btw. you've posted many pastebin links on IRC earlier, and amended source code pasted here on forum at least once (hard to check how many times it was actually)... and EACH time you say now it's 100% working... thanks, but no thanks.
Jeah that code was more then a headache...
I found some wrong boolean checks in it, which i corrected.
And yes maybe i can improve the check in isResearchAvailable.
But regarding performance, it only enters the getAvailableResearchProjects, when you actually open the Research menu on a base.
As you can see here

It will only perform the checks then, to begin with.
Actually i also did some testing on the DOS Version and it just keeps alive aliens by default available, if the give results or not. So we could just go and check if a researchprojects is a alive alien and directly return true, to always keep them available.
My idea was to remove alive aliens from the research list (and also Items with getOneFree) once the player can not learn anything from them anymore, thats why i check for their "unlocks" and "getOneFree".
Which would help players, especially when they play big mods, like FMP, Piratez, Area51 or my own Mod.
The current still active code of for the research in the current main branch, doesn't do that.
In this regard it is actually bugged, since stuff isn't correctly handled, even if you just wanna replicate vanilla behaviour.
Feel free to test the DOS Version in this regard yourself, it just keeps alive aliens open for research forever, of course researching them removes them from the alien containment.

About my post above, i was in my lunch break and had to return to work. I did not want to be rude or so.

Now a small explanation on how the reworked research code actually works:
 - first we check if the topic is in the unlocked list, if not we skip and move directly to the next topic
 - after that we check if a topic has fulfilled dependencies, if not we skip all the other test.
 - a alive alien will be tested if he has something to discover for the player or not, if so it will be shown in the research list.
 - after this we check if all the "requires" of the research are met, if not we skip all the rest of the function and move to the next topic.

This process is then used to fill the list of the research menu and to remove already discovered topics.
Best is you read the comments in the code on github, i tried to as plain as possible.

Kind regards hellrazor.

Offline Meridian

  • Global Moderator
  • Commander
  • *****
  • Posts: 5573
  • Aaand we're back!
    • View Profile
    • My Wiki
Re: Reworked Research Code
« Reply #8 on: June 08, 2017, 08:13:39 pm »
But regarding performance, it only enters the getAvailableResearchProjects, when you actually open the Research menu on a base.
As you can see here

You can clearly see there that getAvailableResearchProjects is called also in getDependableResearchBasic, which is then called in all sorts of places, e.g. addFinishedResearch, getDependableResearch, etc. ... it even calls itself recursively!

I don't know what else do I need to say to open your eyes...

Offline hellrazor

  • Commander
  • *****
  • Posts: 2207
  • Deep Ruleset Digger & Bughunter
    • View Profile
    • Github Account
Re: Reworked Research Code
« Reply #9 on: June 08, 2017, 09:15:46 pm »
You can clearly see there that getAvailableResearchProjects is called also in getDependableResearchBasic, which is then called in all sorts of places, e.g. addFinishedResearch, getDependableResearch, etc. ... it even calls itself recursively!

I don't know what else do I need to say to open your eyes...

The only thing i wanted is to improve something.
I am still learning ok and of course i make errors, but thats human.
But getting ridiculed is not really nice..., at least that is how i feel now.
Test the code which is in my repo and you will see it works.
When you do not like what i did, tell me what to change, or make a suggestion what to change.
I am open to learn more.

Disregarding something because you just do not like me in general is not nice.

Offline Meridian

  • Global Moderator
  • Commander
  • *****
  • Posts: 5573
  • Aaand we're back!
    • View Profile
    • My Wiki
Re: Reworked Research Code
« Reply #10 on: June 08, 2017, 09:31:11 pm »
And how do you think I feel?

I feel like I am talking to a wall... just look how long it took me until you finally understood that your change is incomplete.

As for suggestions... the only suggestion I can give, sadly, is "let it go".
If I knew how to safely fix this code, I would do it myself already... but I don't know how to fix it... other than rewrite it from scratch.

Offline hellrazor

  • Commander
  • *****
  • Posts: 2207
  • Deep Ruleset Digger & Bughunter
    • View Profile
    • Github Account
Re: Reworked Research Code
« Reply #11 on: June 08, 2017, 09:41:22 pm »
And how do you think I feel?

I feel like I am talking to a wall... just look how long it took me until you finally understood that your change is incomplete.

As for suggestions... the only suggestion I can give, sadly, is "let it go".
If I knew how to safely fix this code, I would do it myself already... but I don't know how to fix it... other than rewrite it from scratch.

Please specify why you think it is incomplete.

My suggestion to you is to go and read the code i wrote and understand it.
Then will see that it actually fixed the problems we had before with research in the game.

Offline Meridian

  • Global Moderator
  • Commander
  • *****
  • Posts: 5573
  • Aaand we're back!
    • View Profile
    • My Wiki
Re: Reworked Research Code
« Reply #12 on: June 08, 2017, 09:50:07 pm »
If I give you an example, where it doesn't work... will you stop working on this... or will you work even more?

Offline hellrazor

  • Commander
  • *****
  • Posts: 2207
  • Deep Ruleset Digger & Bughunter
    • View Profile
    • Github Account
Re: Reworked Research Code
« Reply #13 on: June 08, 2017, 11:01:40 pm »
If I give you an example, where it doesn't work... will you stop working on this... or will you work even more?

Feel free to find a example. The diff on github shows now the changes i made only, sorry for the broken tab/spaces thing to begin with.

Offline Meridian

  • Global Moderator
  • Commander
  • *****
  • Posts: 5573
  • Aaand we're back!
    • View Profile
    • My Wiki
Re: Reworked Research Code
« Reply #14 on: June 08, 2017, 11:56:56 pm »
Since you avoided my direct question, I assume the answer is "no, you will continue working on it if I show you more issues".

If so, I can respond only with:
I regret that I told you about the issue, which you are trying to solve here... I should have kept my mouth shut.
This whole discussion is my fault, I just wish I could un-tell you about it.
I won't tell you about the other issues, because I don't want to continue along this path.
This is my last post on this topic.

I understand you just want to help... but starting with one of the most perplexing pieces of oxc code with lots of side effects is just a bad idea.

Good luck, whatever your decision to continue may be...