source: cpp/frams/genetics/f4/oper_f4.cpp @ 718

// This file is a part of Framsticks SDK.  http://www.framsticks.com/
// Copyright (C) 1999-2017  Maciej Komosinski and Szymon Ulatowski.
// See LICENSE.txt for details.

// Copyright (C) 1999,2000  Adam Rotaru-Varga (adam_rotaru@yahoo.com), GNU LGPL
// Copyright (C) since 2001 Maciej Komosinski

#include "oper_f4.h"
#include <frams/util/sstring.h>
#include <common/log.h>

#include <stdio.h>
#include <stdlib.h>
#include "common/nonstd_math.h"
#include <string.h>


//see also modifiers in f1
#define F4_MODIFIERS_VISUAL "" //not supported in f4
#define F4_MODIFIERS_RARE "EeWwAaSs" //expdef would need to handle these properly/specifically to ensure reasonable behavior, and hardly any expdef does. Modifying initial energy of a creature as a result of its genes (Ee) is in general not a good idea. Weight (Ww) works only in water, and in water sinking/going up should usually be caused by real "intentional" activity of a creature, not by its inherited weight. For assimilation (Aa), there is a dedicated parameter in CreaturesGroup. Stamina (Ss) is no longer needed as destructive collisions are not supported, and even if they were, some expdef would need to impose reasonable restrictions on the value of this parameter (e.g. similar to normalizeBiol4()) so there is some cost associated with it, and the specific consequences of destructions should be defined as needed.
#define F4_MODIFIERS "LlRrCcQqFfMmIi" F4_MODIFIERS_RARE F4_MODIFIERS_VISUAL
const char *Geno_f4::all_modifiers = F4_MODIFIERS;

#define FIELDSTRUCT Geno_f4

static ParamEntry GENO4param_tab[] =
{
        { "Genetics: f4", 1, F4_COUNT + F4_ADD_COUNT + 1, },
        { "f4_mut_add", 0, 0, "Add node", "f 0 100 50", FIELD(prob[F4_ADD]), "mutation: probability of adding a node", },
        { "f4_mut_add_div", 0, 0, "- add division", "f 0 100 20", FIELD(probadd[F4_ADD_DIV]), "add node mutation: probability of adding a division", },
        { "f4_mut_add_conn", 0, 0, "- add connection", "f 0 100 15", FIELD(probadd[F4_ADD_CONN]), "add node mutation: probability of adding a neural connection", },
        { "f4_mut_add_neupar", 0, 0, "- add neuron property", "f 0 100 5", FIELD(probadd[F4_ADD_NEUPAR]), "add node mutation: probability of adding a neuron property/modifier", },
        { "f4_mut_add_rep", 0, 0, "- add repetition", "f 0 100 10", FIELD(probadd[F4_ADD_REP]), "add node mutation: probability of adding a repetition", },
        { "f4_mut_add_simp", 0, 0, "- add simple node", "f 0 100 50", FIELD(probadd[F4_ADD_SIMP]), "add node mutation: probability of adding a random, simple gene", },
        { "f4_mut_del", 0, 0, "Delete node", "f 0 100 20", FIELD(prob[F4_DEL]), "mutation: probability of deleting a node", },
        { "f4_mut_mod", 0, 0, "Modify node", "f 0 100 30", FIELD(prob[F4_MOD]), "mutation: probability of changing a node", },
        { "f4_mut_exmod", 1, 0, "Excluded modifiers", "s 0 30", FIELD(excluded_modifiers), "Modifiers that will not be added nor deleted during mutation\n(all: " F4_MODIFIERS ")", },
        { 0, },
};

#undef FIELDSTRUCT


Geno_f4::Geno_f4()
{
        supported_format = '4';
        par.setParamTab(GENO4param_tab);
        par.select(this);
        par.setDefault();

        mutation_method_names = new const char*[F4_COUNT + F4_ADD_COUNT - 1];
        int index = 0;
        mutation_method_names[index++] = "added division";
        mutation_method_names[index++] = "added neural connection";
        mutation_method_names[index++] = "added neuron property";
        mutation_method_names[index++] = "added repetition gene";
        mutation_method_names[index++] = "added a simple node";
        mutation_method_names[index++] = "deleted a node";
        mutation_method_names[index++] = "modified a node";
        if (index != F4_COUNT + F4_ADD_COUNT - 1) logMessage("Geno_f4", "Constructor", 3, "Mutation names init error");
}

void Geno_f4::setDefaults()
{
        excluded_modifiers = F4_MODIFIERS_RARE F4_MODIFIERS_VISUAL;
}

int Geno_f4::ValidateRec(f4_node * geno, int retrycount) const
{
        // ! the genotype is geno->child (not geno) !
        // build from it with repair on

        f4_Cells cells(geno->child, 1);
        cells.simulate();  //we should simulate?!

        // errors not fixed:
        if (GENOPER_OPFAIL == cells.geterror())
        {
                if (cells.geterrorpos() >= 0) return 1 + cells.geterrorpos();
                return GENOPER_OPFAIL;
        }
        // errors can be fixed
        if (GENOPER_REPAIR == cells.geterror())
        {
                cells.repairGeno(geno, 1);
                // note: geno might have been fixed
                // check again
                int res2 = GENOPER_OK;
                if (retrycount > 0)
                        res2 = ValidateRec(geno, retrycount - 1);

                if (res2 == GENOPER_OK) return GENOPER_REPAIR;
                return res2;
        }
        // no errors:
        return GENOPER_OK;
}


int Geno_f4::validate(char *& geno, const char *genoname)
{
        // convert geno to tree, then try to validate 20 times
        f4_node root;
        if (f4_processrec(geno, 0, &root) || root.childCount() != 1) return GENOPER_OK; // cannot repair
        if (ValidateRec(&root, 20) == GENOPER_REPAIR) // if repaired, make it back to string
        {
                geno[0] = 0;
                root.child->sprintAdj(geno);
        }
        return GENOPER_OK;
}


int Geno_f4::checkValidity(const char * geno, const char *genoname)
{
        f4_node root;
        int res = f4_processrec(geno, 0, &root);
        if (res) return res;  // errorpos, >0
        if (root.childCount() != 1) return 1; //earlier: GENOPER_OPFAIL
        f4_Cells cells(root.child, 0);
        cells.simulate();
        if (cells.geterror() == GENOPER_OPFAIL || cells.geterror() == GENOPER_REPAIR)
        {
                if (cells.geterrorpos() >= 0) return 1 + cells.geterrorpos();
                else return 1; //earlier: GENOPER_OPFAIL;
        }
        else return GENOPER_OK;
}


int Geno_f4::MutateOne(f4_node *& g, int &method) const
{
        // ! the genotype is g->child (not g) !

        // codes that can be changed (apart being added/deleted)
#define MUT_CHAN_CODES "<[#"
#define ADD_SIMPLE_CODES ",XlLcCrRaAiIsSmMfFwWeEN@|"
#define REP_MAXCOUNT 19

        f4_node * n1, *n2, *n3, *n4, *n5;

        // do the mutation
        // pick a random node
        n1 = g->child->randomNode();
        //DB( printf("%c\n", n1->name); )

        switch (roulette(prob, F4_COUNT))
        {
        case F4_ADD:
        {
                // add a node
                switch (method = roulette(probadd, F4_ADD_COUNT))
                {
                case F4_ADD_DIV:
                {
                        // add division ('<')
                        n3 = n1->parent;
                        n3->removeChild(n1);
                        n2 = new f4_node('<', n3, n3->pos);
                        n2->addChild(n1);
                        // new cell is stick or neuron
                        // "X>" or "N>"
                        double pr = rnd01;
                        pr -= 0.5;
                        if (pr < 0) n3 = new f4_node('X', n2, n2->pos);
                        else
                        {
                                pr -= 0.5;
                                if (pr < 0)
                                {
                                        // if neuron, make muscle and add a link
                                        n3 = new f4_node('N', n2, n2->pos);
                                        if (randomN(2) == 0)
                                                n4 = new f4_node('|', n3, n2->pos);
                                        else
                                                n4 = new f4_node('@', n3, n2->pos);
                                        n5 = new f4_node('[', n4, n2->pos);
                                        linkNodeMakeRandom(n5);
                                }
                        }
                        new f4_node('>', n3, n3->pos);
                        n1->parent = n2;
                        // now with 50% chance swap children
                        if (randomN(2) == 0)
                        {
                                n3 = n2->child;
                                n2->child = n2->child2;
                                n2->child2 = n3;
                        }
                }
                        break;
                case F4_ADD_CONN:
                {
                        // add link
                        n1->parent->removeChild(n1);
                        n2 = new f4_node('[', n1->parent, n1->parent->pos);
                        linkNodeMakeRandom(n2);
                        n2->addChild(n1);
                        n1->parent = n2;
                }
                        break;
                case F4_ADD_NEUPAR:
                {
                        // add neuron modifier
                        n1->parent->removeChild(n1);
                        n2 = new f4_node(':', n1->parent, n1->parent->pos);
                        nparNodeMakeRandom(n2);
                        n2->addChild(n1);
                        n1->parent = n2;
                }
                        break;
                case F4_ADD_REP:
                {
                        // add repetition ('#')
                        // repeated code (left child) is the original, right child is empty, count is 2
                        n3 = n1->parent;
                        n3->removeChild(n1);
                        n2 = new f4_node('#', n3, n3->pos);
                        n2->i1 = 2;
                        n2->addChild(n1);
                        new f4_node('>', n2, n2->pos);
                        n1->parent = n2;
                }
                        break;
                case F4_ADD_SIMP:
                {
                        // add simple node
                        // choose a simple node from ADD_SIMPLE_CODES
                        n1->parent->removeChild(n1);
                        n2 = new f4_node(ADD_SIMPLE_CODES[randomN(strlen(ADD_SIMPLE_CODES))], n1->parent, n1->parent->pos);
                        n2->addChild(n1);
                        n1->parent = n2;
                }
                        break;
                }
        }
                break;

        case F4_DEL:
        {
                method = F4_ADD_COUNT - 1 + F4_DEL;
                // delete a node
                // must pick a node with parent, and at least one child
                // already picked a node, but repeat may be needed
                for (int i = 0; i < 10; i++)
                {
                        if ((NULL != n1->parent) && (g != n1->parent))
                                if (NULL != n1->child)
                                        break;
                        // try a new one
                        n1 = g->child->randomNode();
                }
                if ((NULL != n1->parent) && (g != n1->parent))
                {
                        switch (n1->childCount())
                        {
                        case 0: break;
                        case 1:  // one child
                        {
                                n2 = n1->parent;
                                n2->removeChild(n1);
                                if (NULL != n1->child)
                                {
                                        n1->child->parent = n2;
                                        n2->addChild(n1->child);
                                        n1->child = NULL;
                                }
                                if (NULL != n1->child2)
                                {
                                        n1->child2->parent = n2;
                                        n2->addChild(n1->child2);
                                        n1->child2 = NULL;
                                }
                                // destroy n1
                                n1->parent = NULL;
                                delete n1;
                        }
                                break;

                        case 2:  // two children
                        {
                                // two children
                                n2 = n1->parent;
                                n2->removeChild(n1);
                                // n1 has two children. pick one randomly 50-50, destroy other
                                if (randomN(2) == 0)
                                {
                                        n1->child->parent = n2;
                                        n2->addChild(n1->child);
                                        n1->child = NULL;
                                        n1->child2->parent = NULL;
                                }
                                else
                                {
                                        n1->child2->parent = n2;
                                        n2->addChild(n1->child2);
                                        n1->child2 = NULL;
                                        n1->child->parent = NULL;
                                }
                                // destroy n1
                                n1->parent = NULL;
                                delete n1;
                        }
                                break;
                        }
                }
                else return GENOPER_OPFAIL;
        }
                break;
        case F4_MOD:
        {
                method = F4_ADD_COUNT - 1 + F4_MOD;
                // change a node
                // the only nodes that are modifiable are MUT_CHAN_CODES
                // try to get a modifiable node
                // already picked a node, but repeat may be needed
                int i = 0;
                while (1)
                {
                        if (strchr(MUT_CHAN_CODES, n1->name)) break;
                        // try a new one
                        n1 = g->child->randomNode();
                        i++;
                        if (i >= 20) return GENOPER_OPFAIL;
                }
                switch (n1->name)
                {
                case '<':
                        // swap children
                        n2 = n1->child; n1->child = n1->child2; n1->child2 = n2;
                        break;
                case '[':
                        linkNodeChangeRandom(n1);
                        break;
                case '#':
                        repeatNodeChangeRandom(n1);
                        break;
                }
        }
                break;

        default: //no mutations allowed?
                return GENOPER_OPFAIL;
        }

        return GENOPER_OK;
}

// make a random [ node
void Geno_f4::linkNodeMakeRandom(f4_node * nn) const
{
        int i;
        float prob1;

        i = 0;
        // 35% chance one of *GTS
        prob1 = rnd01;
        prob1 -= 0.35f;
        if (prob1 < 0)
        {
                // '*', 'G', 'T', or 'S', 1/4 chance each
                i = 1 + (int)(3.999f * rnd01);
        }
        nn->i1 = i;
        nn->l1 = 0;
        if (0 == i)
        {
                // relative input link
                nn->l1 = (int)(4.0f * (rnd01 - 0.5f));
        }
        // weight
        nn->f1 = 10.0f * (rnd01 - 0.5f);
}

// change a [ node
void Geno_f4::linkNodeChangeRandom(f4_node * nn) const      //rewritten by M.K. - should work as before (not tested)
{
        int i;
        float prob2;

        double probs[3] = { 0.1, 0.3, 0.6 };
        // 10% change type
        // 30% change link
        // 60% change weight

        switch (roulette(probs, 3))
        {
        case 0: // change type
                i = 0;
                // * G, 10% chance each
                prob2 = rnd01 - 0.10f;
                if (prob2 < 0) i = 1; else { prob2 -= 0.10f; if (prob2 < 0) i = 2; }
                nn->i1 = i;
                break;
        case 1: // change link
                if (0 == nn->i1) // relative input link
                        nn->l1 += (int)(2.0f * (rnd01 - 0.5f));
                break;
        case 2: // change weight
                nn->f1 += 1.0f * (rnd01 - 0.5f);
                break;
        }
}

// make a random : node
void Geno_f4::nparNodeMakeRandom(f4_node * nn) const
{
        int sign = (int)(2.0f * rnd01);
        int param = (int)(3.0f * rnd01);
        if (param > 2) param = 2;
        nn->l1 = sign;
        nn->i1 = "!=/"[param];
}

// change a repeat # node
void Geno_f4::repeatNodeChangeRandom(f4_node * nn) const
{
        int count;
        float prob1;

        // change count
        count = nn->i1;
        prob1 = rnd01;
        if (prob1 < 0.5f) count++;
        else count--;
        if (count < 1) count = 1;
        if (count > REP_MAXCOUNT) count = REP_MAXCOUNT;
        nn->i1 = count;
}


int Geno_f4::MutateOneValid(f4_node *& g, int &method) const
// mutate one, until a valid genotype is obtained
{
        // ! the genotype is g->child (not g) !
        int i, res;
        f4_node * gcopy = NULL;
        // try this max 20 times:
        //   copy, mutate, then validate

        for (i = 0; i < 20; i++)
        {
                gcopy = g->duplicate();

                res = MutateOne(gcopy, method);

                if (GENOPER_OK != res)
                {
                        // mutation failed, try again
                        delete gcopy;
                        continue;  // for
                }
                // try to validate it
                res = ValidateRec(gcopy, 10);
                // accept if it is OK, or was repaired
                if (GENOPER_OK == res)
                        //(GENOPER_REPAIR == res)
                {
                        // destroy the original one
                        g->destroy();
                        // make it the new one
                        *g = *gcopy;
                        gcopy->child = NULL;
                        gcopy->child2 = NULL;
                        delete gcopy;
                        res = GENOPER_OK;
                        goto retm1v;
                }
                delete gcopy;
        }
        // attempts failed
        res = GENOPER_OPFAIL;
retm1v:
        return res;
}


int Geno_f4::mutate(char *& g, float & chg, int &method)
{
        f4_node *root = new f4_node;
        if (f4_processrec(g, 0, root) || root->childCount() != 1)
        {
                delete root;
                return GENOPER_OPFAIL;
        } // could not convert or bad: fail
        // mutate one node, set chg as this percent
        chg = 1.0 / float(root->child->count());
        if (MutateOneValid(root, method) != GENOPER_OK)
        {
                delete root;
                return GENOPER_OPFAIL;
        }
        // OK, convert back to string
        g[0] = 0;
        root->child->sprintAdj(g);
        delete root;
        return GENOPER_OK;
}


/*
int Geno_f4::MutateMany(char *& g, float & chg)
// check if original is valid, then
// make a number of mutations
{
int res, n, i;
int totNodes = 0;
int maxToMut = 0;

// convert to tree
f4_node * root;
root = new f4_node();
res = f4_processrec(g, 0, root);
if (res) {
// could not convert, fail
goto retm;
}
if (1 != root->childCount()) {
res = GENOPER_OPFAIL;
goto retm;
}

// check if original is valid
res = ValidateRec( root, 20 );
// might have been repaired!
if (GENOPER_REPAIR==res) {
res = GENOPER_OK;
}
if (GENOPER_OK != res) {
goto retm;
}

// decide number of nodes to mutate
// decide maximum number of nodes to mutate: 0.25*nodes, min 2
totNodes = root->child->count();
maxToMut = (int)( 0.25f * totNodes);
if (maxToMut<2) maxToMut=2;
if (maxToMut>totNodes) maxToMut=totNodes;

// decide number of nodes to mutate
n = (int)( 0.5f + rnd01 * maxToMut );
if (n<1) n=1;
if (n>totNodes) n=totNodes;
// set chg as this percent
chg = ((float)n) / ((float)totNodes);
for (i=0; i<n; i++)
{
res = MutateOneValid(root);
if (GENOPER_OK != res)
{
res = GENOPER_OPFAIL;
goto retm;
}
}
// OK, convert back to string
g[0]=0;
root->child->sprintAdj(g);
retm:
delete root;
return res;
}
*/


int Geno_f4::CrossOverOne(f4_node * g1, f4_node * g2, float chg) const
{
        // ! the genotypes are g1->child and g2->child (not g1 g2) !
        // single offspring in g1
        int smin, smax;
        float size;
        f4_node * n1, *n2, *n1p, *n2p;

        // determine desired size
        size = (1 - chg) * (float)g1->count();
        smin = (int)(size*0.9f - 1);
        smax = (int)(size*1.1f + 1);
        // get a random node with desired size
        n1 = g1->child->randomNodeWithSize(smin, smax);

        // determine desired size
        size = (1 - chg) * (float)g2->count();
        smin = (int)(size*0.9f - 1);
        smax = (int)(size*1.1f + 1);
        // get a random node with desired size
        n2 = g2->child->randomNodeWithSize(smin, smax);

        // exchange the two nodes:
        n1p = n1->parent;
        n2p = n2->parent;
        n1p->removeChild(n1);
        n1p->addChild(n2);
        n2p->removeChild(n2);
        n2p->addChild(n1);
        n1->parent = n2p;
        n2->parent = n1p;

        return GENOPER_OK;
}

int Geno_f4::crossOver(char *&g1, char *&g2, float &chg1, float &chg2)
{
        f4_node root1, root2, *copy1, *copy2;

        // convert genotype strings into tree structures
        if (f4_processrec(g1, 0, &root1) || (root1.childCount() != 1)) return GENOPER_OPFAIL;
        if (f4_processrec(g2, 0, &root2) || (root2.childCount() != 1)) return GENOPER_OPFAIL;

        // decide amounts of crossover, 0.25-0.75
        // adam: seems 0.1-0.9 -- MacKo
        chg1 = 0.1f + 0.8f*rnd01;
        chg2 = 0.1f + 0.8f*rnd01;

        copy1 = root1.duplicate();
        if (CrossOverOne(copy1, &root2, chg1) != GENOPER_OK) { delete copy1; copy1 = NULL; }
        copy2 = root2.duplicate();
        if (CrossOverOne(copy2, &root1, chg2) != GENOPER_OK) { delete copy2; copy2 = NULL; }

        g1[0] = 0;
        g2[0] = 0;
        if (copy1) { copy1->child->sprintAdj(g1); delete copy1; }
        if (copy2) { copy2->child->sprintAdj(g2); delete copy2; }
        if (g1[0] || g2[0]) return GENOPER_OK; else return GENOPER_OPFAIL;
}



uint32_t Geno_f4::style(const char *g, int pos)
{
        char ch = g[pos];
        // style categories
#define STYL4CAT_MODIFIC F4_MODIFIERS ","
#define STYL4CAT_NEUMOD "[]|@*GTS:+-/!="
#define STYL4CAT_DIGIT "0123456789."
#define STYL4CAT_REST "XN<># "
        if (!strchr(STYL4CAT_MODIFIC STYL4CAT_NEUMOD STYL4CAT_DIGIT STYL4CAT_REST, ch))
                return GENSTYLE_CS(0, GENSTYLE_INVALID);
        uint32_t style = GENSTYLE_CS(0, GENSTYLE_STRIKEOUT); //default, should be changed below
        if (strchr("X ", ch))              style = GENSTYLE_CS(0, GENSTYLE_NONE);
        if (strchr("N", ch))               style = GENSTYLE_RGBS(0, 200, 0, GENSTYLE_NONE);
        if (strchr("<", ch))               style = GENSTYLE_RGBS(0, 0, 200, GENSTYLE_BOLD);
        if (strchr(">", ch))               style = GENSTYLE_RGBS(0, 0, 100, GENSTYLE_NONE);
        if (strchr(STYL4CAT_DIGIT, ch))     style = GENSTYLE_RGBS(100, 100, 100, GENSTYLE_NONE);
        if (strchr(STYL4CAT_MODIFIC, ch))   style = GENSTYLE_RGBS(100, 100, 100, GENSTYLE_NONE);
        if (strchr(STYL4CAT_NEUMOD, ch))    style = GENSTYLE_RGBS(0, 150, 0, GENSTYLE_NONE);
        return style;
}