source: cpp/frams/genetics/fS/fS_general.h @ 958

Last change on this file since 958 was 958, checked in by Maciej Komosinski, 4 years ago

Added the fS genetic encoding (for solids)

File size: 14.1 KB
Line 
1// This file is a part of Framsticks SDK.  http://www.framsticks.com/
2// Copyright (C) 2019-2020  Maciej Komosinski and Szymon Ulatowski.
3// See LICENSE.txt for details.
4
5#ifndef _FS_GENERAL_H_
6#define _FS_GENERAL_H_
7
8#include <iostream>
9#include <vector>
10#include <map>
11#include <unordered_map>
12#include <exception>
13#include "frams/model/model.h"
14#include "frams/util/multirange.h"
15
16/** @name Names of genotype modes */
17//@{
18#define MODIFIER_MODE 'M'
19#define PARAM_MODE 'S'
20#define CYCLE_MODE 'J'
21//@}
22
23/** @name Values of constants used in encoding */
24//@{
25#define BRANCH_START '('
26#define BRANCH_END ')'
27#define BRANCH_SEPARATOR ','
28#define PARAM_START '{'
29#define PARAM_END '}'
30const char PARAM_SEPARATOR = ';';
31const char PARAM_KEY_VALUE_SEPARATOR = '=';
32#define NEURON_START '['
33const char NEURON_END = ']';
34const char NEURON_SEPARATOR = ';';
35const SString NEURON_INTERNAL_SEPARATOR("_");
36#define NEURON_I_W_SEPARATOR ':'
37//@}
38
39enum class SHIFT
40{
41        LEFT = -1,
42        RIGHT = 1
43};
44
45/** @name Every modifier changes the underlying value by this multiplier */
46const double MODIFIER_MULTIPLIER = 1.1;
47/** @name In mutation parameters will be multiplied by at most this value */
48const double PARAM_MAX_MULTIPLIER = 1.5;
49
50/**
51 * Used in finding the proper distance between the parts
52 * distance between spheres / sphere radius
53 * That default value can be changed in certain cases
54 * */
55const float SPHERE_RELATIVE_DISTANCE = 0.25;
56/**
57 * Used in finding the proper distance between the parts
58 * The maximal allowed value for
59 * maximal radius of the node / sphere radius
60 */
61const int MAX_DIAMETER_QUOTIENT = 30;
62/**
63 * The tolerance of the value of distance between parts
64 */
65const double SPHERE_DISTANCE_TOLERANCE = 0.99;
66
67
68/** @name Names of node parameters and modifiers*/
69//@{
70#define INGESTION "i"
71#define FRICTION "f"
72#define SIZE "s"
73#define SIZE_X "x"
74#define SIZE_Y "y"
75#define SIZE_Z "z"
76#define ROT_X "tx"
77#define ROT_Y "ty"
78#define ROT_Z "tz"
79#define RX "rx"
80#define RY "ry"
81#define RZ "rz"
82#define JOINT_DISTANCE "j"
83//@}
84/** @name Macros and values used in collision detection */
85//@{
86#define DISJOINT 0
87#define COLLISION 1
88#define ADJACENT 2
89//@}
90
91#define HINGE_X 'b'
92#define HINGE_XY 'c'
93
94const double DEFAULT_NEURO_CONNECTION_WEIGHT = 1.0;
95
96const char ELLIPSOID = 'E';
97const char CUBOID = 'C';
98const char CYLINDER = 'R';
99const std::unordered_map<Part::Shape, char> SHAPETYPE_TO_GENE = {
100                {Part::Shape::SHAPE_ELLIPSOID, ELLIPSOID},
101                {Part::Shape::SHAPE_CUBOID,    CUBOID},
102                {Part::Shape::SHAPE_CYLINDER,  CYLINDER},
103};
104
105// This map is inverse to SHAPE_TO_SYMBOL. Those two should be compatible
106const std::unordered_map<char, Part::Shape> GENE_TO_SHAPETYPE = {
107                {ELLIPSOID, Part::Shape::SHAPE_ELLIPSOID},
108                {CUBOID,    Part::Shape::SHAPE_CUBOID},
109                {CYLINDER,  Part::Shape::SHAPE_CYLINDER},
110};
111const int SHAPE_COUNT = 3;    // This should be the count of SHAPETYPE_TO_GENE and GENE_TO_SHAPETYPE
112
113const char DEFAULT_JOINT = 'a';
114const string JOINTS = "bc";
115const int JOINT_COUNT = JOINTS.length();
116const string MODIFIERS = "IFS";
117const char SIZE_MODIFIER = 's';
118const vector<string> PARAMS {INGESTION, FRICTION, ROT_X, ROT_Y, ROT_Z, RX, RY, RZ, SIZE, SIZE_X, SIZE_Y, SIZE_Z,
119                                                          JOINT_DISTANCE};
120
121/** @name Default values of node parameters*/
122static const Part defPart = Model::getDefPart();
123const std::map<string, double> defaultParamValues = {
124                {INGESTION,      defPart.ingest},
125                {FRICTION,       defPart.friction},
126                {ROT_X,          0.0},
127                {ROT_Y,          0.0},
128                {ROT_Z,          0.0},
129                {RX,             0.0},
130                {RY,             0.0},
131                {RZ,             0.0},
132                {SIZE,           1.0},
133                {SIZE_X,         1.0},
134                {SIZE_Y,         1.0},
135                {SIZE_Z,         1.0},
136                {JOINT_DISTANCE, 1.0}
137};
138
139/** @name Number of tries of performing a mutation before GENOPER_FAIL is returned */
140#define mutationTries  20
141
142class fS_Exception : public std::exception
143{
144        string msg;
145public:
146
147        int errorPosition;
148        virtual const char *what() const throw()
149        {
150                return msg.c_str();
151        }
152
153        fS_Exception(string _msg, int _errorPosition)
154        {
155                msg = _msg;
156                errorPosition = _errorPosition;
157        }
158};
159
160/**
161 * Draws an integer value from given range
162 * @param to maximal value
163 * @param from minimal value
164 * @return Drawn value
165 */
166int randomFromRange(int to, int from);
167
168/**
169 * Represents a substring of a larger string.
170 * The reference to the original string is stored along with indexes of beginning end length of the substring.
171 */
172class Substring
173{
174public:
175        char *str;        // Pointer to the beginning of the substring
176        int start;        // The beginning index of substring
177        int len;        // The length of substring
178
179        Substring(const char *_str, int _start, int _len)
180        {
181                str = (char *) _str + _start;
182                start = _start;
183                len = _len;
184        }
185
186        Substring(const Substring &other)
187        {
188                str = other.str;
189                start = other.start;
190                len = other.len;
191        }
192
193        const char *c_str()
194        {
195                return str;
196        }
197
198        SString substr(int relativeStart, int len)
199        {
200                const char *substrStart = str + relativeStart;
201                return SString(substrStart, len);
202        }
203
204        int indexOf(char ch)
205        {
206                for (int i = 0; i < len; i++)
207                        if (str[i] == ch)
208                                return i;
209                return -1;
210        }
211
212        void startFrom(int index)
213        {
214                str += index;
215                start += index;
216                len -= index;
217        }
218
219        void shortenBy(int charCount)
220        {
221                len = std::max(len - charCount, 0);
222        }
223
224        char at(int index)
225        {
226                return str[index];
227        }
228
229        /**
230         * Create a new instance of multirange, corresponding to the substring
231         * @return a created multirange
232         */
233        MultiRange toMultiRange()
234        {
235                MultiRange range;
236                range.add(start, start + len - 1);
237                return range;
238        }
239};
240
241/**
242 * Stores the state of the node.
243 * The state consists od current location, the direction in which the branch develops
244 * and the current default values of the parameters (default values can be changed by modifiers).
245 */
246class State
247{
248public:
249        Pt3D location;  /// Location of the node
250        Pt3D v;         /// The normalised vector in which current branch develops
251        double fr = 1.0;      /// Friction multiplier
252        double ing = 1.0;      /// Ingestion multiplier
253        double s = 1.0;      /// Size multipliers
254
255        State(State *_state); /// Derive the state from parent
256
257        State(Pt3D _location, Pt3D _v); /// Create the state from parameters
258
259        /**
260         * Add the vector of specified length to location
261         * @param length the length of the vector
262         */
263        void addVector(const double length);
264
265        /**
266         * Rotate the vector by specified values
267         * @param rx rotation by x axis
268         * @param ry rotation by y axis
269         * @param rz rotation by z axis
270         */
271        void rotate(const Pt3D &rotation);
272};
273
274/**
275 * Represent a neuron and its inputs
276 */
277class fS_Neuron: public Neuro
278{
279public:
280        std::map<int, double> inputs;
281
282        fS_Neuron(const char *str, int start, int length);
283
284        bool acceptsInputs()
285        {
286                return getClass()->prefinputs < int(inputs.size());
287        }
288};
289
290/**
291 * Represents a node in the graph that represents a genotype.
292 * A node corresponds to a single part.
293 * However, it also stores attributes that are specific to fS encoding, such as modifiers and joint types.
294 */
295class Node
296{
297        friend class fS_Genotype;
298
299        friend class GenoOper_fS;
300
301private:
302        Substring *partDescription = nullptr;
303        bool cycleMode, modifierMode, paramMode; /// Possible modes
304        Node *parent;
305        Part *part;     /// A part object built from node. Used in building the Model
306        int partCodeLen; /// The length of substring that directly describes the corresponding part
307
308        std::map<string, double> params; /// The map of all the node params
309        vector<Node *> children;    /// Vector of all direct children
310        std::map<char, int> modifiers;     /// Vector of all modifiers
311        char joint = DEFAULT_JOINT;           /// Set of all joints
312        vector<fS_Neuron *> neurons;    /// Vector of all the neurons
313
314        static double calculateRadiusFromVolume(Part::Shape partType, double volume)
315        {
316                double result;
317                switch (partType)
318                {
319                        case Part::Shape::SHAPE_CUBOID:
320                                result = std::cbrt(volume / 8.0);
321                                break;
322                        case Part::Shape::SHAPE_CYLINDER:
323                                result = std::cbrt(volume / (2.0 * M_PI));
324                                break;
325                        case Part::Shape::SHAPE_ELLIPSOID:
326                                result = std::cbrt(volume / ((4.0 / 3.0) * M_PI));
327                                break;
328                        default:
329                                logMessage("fS", "calculateVolume", LOG_ERROR, "Invalid part type");
330                }
331                return result;
332        }
333
334        void cleanUp();
335
336        Pt3D getRotation();
337
338        Pt3D getVectorRotation();
339
340        bool isPartSizeValid();
341
342        bool hasPartSizeParam();
343
344        /**
345         * Get the position of part type in genotype
346         *
347         * @return the position of part type
348         */
349        int getPartPosition(Substring &restOfGenotype);
350
351        /**
352         * Extract modifiers from the rest of genotype
353         * @return the remainder of the genotype
354         */
355        void extractModifiers(Substring &restOfGenotype);
356
357        /**
358         * Extract part type from the rest of genotype
359         * @return the remainder of the genotype
360         */
361        void extractPartType(Substring &restOfGenotype);
362
363        /**
364         * Extract neurons from the rest of genotype
365         * @return the remainder of the genotype
366         */
367        void extractNeurons(Substring &restOfGenotype);
368
369        /**
370         * Extract params from the rest of genotype
371         * @return the length og the remainder of the genotype
372         */
373        void extractParams(Substring &restOfGenotype);
374
375        /**
376         * Extract child branches from the rest of genotype
377         * @return vector of child branches
378         */
379        vector<Substring> getBranches(Substring &restOfGenotype);
380
381        /**
382         * Get phenotypic state that derives from ancestors.
383         * Used when building model
384         * @param _state state of the parent
385         */
386        void getState(State *_state, const Pt3D &parentSize);
387
388        /**
389         * Build children internal representations from fS genotype
390         * @param restOfGenotype part of genotype that describes the subtree
391         */
392        void getChildren(Substring &restOfGenotype);
393
394        /**
395         * Create part object from internal representation
396         */
397        void createPart();
398
399        /**
400         * Add joints between current node and the specified child
401         * Used in building model
402         * @param mode pointer to build model
403         * @param child pointer to the child
404         */
405        void addJointsToModel(Model &model, Node *parent);
406
407        /**
408         * Get all the nodes from the subtree that starts in this node
409         * @param reference to vector which contains nodes
410         */
411        void getAllNodes(vector<Node *> &allNodes);
412
413
414        /**
415         * Build model from the subtree that starts in this node
416         * @param pointer to model
417         */
418        void buildModel(Model &model, Node *parent);
419
420public:
421        Part::Shape partType;  /// The type of the part
422        State *state = nullptr; /// The phenotypic state that inherits from ancestors
423
424        Node(Substring &genotype, bool _modifierMode, bool _paramMode, bool _cycleMode, Node *parent);
425
426        ~Node();
427
428        /**
429         * Get fS representation of the subtree that starts from this node
430         * @param result the reference to an object which is used to contain fS genotype
431         */
432        void getGeno(SString &result);
433
434        /**
435         * Calculate the effective size of the part (after applying all multipliers and params)
436         * @return The effective size
437         */
438        Pt3D calculateSize();
439
440        /**
441         * Calculate the effective volume of the part
442         * @return The effective volume
443         */
444        double calculateVolume();
445
446        /**
447         * Change the value of the size parameter by given multiplier
448         * Do not change the value if any of the size restrictions is not satisfied
449         * @param paramKey
450         * @param multiplier
451         * @param ensureCircleSection
452         * @return True if the parameter value was change, false otherwise
453         */
454        bool changeSizeParam(string paramKey, double multiplier, bool ensureCircleSection);
455
456        /**
457         * Counts all the nodes in subtree
458         * @return node count
459         */
460        int getNodeCount();
461
462        /**
463         * Extract the value of parameter or return default if parameter not exists
464         * @return the param value
465         */
466        double getParam(string key);
467};
468
469/**
470 * Represents an fS genotype.
471 */
472class fS_Genotype
473{
474        friend class Node;
475
476        friend class GenoOper_fS;
477
478private:
479        /**
480         * Draws a node that has an index greater that specified
481         * @param fromIndex minimal index of the node
482         * @return pointer to drawn node
483         */
484        Node *chooseNode(int fromIndex=0);
485
486        /**
487         * Draws a value from defined distribution
488         * @return Drawn value
489         */
490        void randomFromDistribution();
491
492        /**
493         * Find a node that is nearest (euclidean distance to specified node) and is not a child of specified node
494         * @return Nearest node
495         */
496        Node *getNearestNode(vector<Node *> allNodes, Node *node);
497
498public:
499        Node *startNode = nullptr;    /// The start (root) node. All other nodes are its descendants
500
501
502        static int precision;
503
504        /**
505         * Build internal representation from fS format
506         * @param genotype in fS format
507         */
508        fS_Genotype(const string &genotype);
509
510        ~fS_Genotype();
511
512        void getState();
513
514        /**
515         * Get a random multiplier for parameter mutation
516         * @return Random parameter multiplier
517         */
518        static double randomParamMultiplier();
519
520        /**
521         * Get all existing nodes
522         * @return vector of all nodes
523         */
524        vector<Node *> getAllNodes();
525
526        /**
527         * Get all the neurons from the subtree that starts in given node
528         * @param node The beginning of subtree
529         * @return The vector of neurons
530         */
531        static vector<fS_Neuron *> extractNeurons(Node *node);
532
533        /**
534         * Get the index of the neuron in vector of neurons
535         * @param neurons
536         * @param changedNeuron
537         * @return
538         */
539        static int getNeuronIndex(vector<fS_Neuron *> neurons, fS_Neuron *changedNeuron);
540
541        /**
542         * Left- or right- shift the indexes of neuro connections by the given range
543         * @param neurons
544         * @param start The beginning of the range
545         * @param end The end of the range
546         * @param shift
547         */
548        static void shiftNeuroConnections(vector<fS_Neuron *> &neurons, int start, int end, SHIFT shift);
549
550        /**
551         * Get all existing neurons
552         * @return vector of all neurons
553         */
554        vector<fS_Neuron *> getAllNeurons();
555
556        /**
557         * Counts all the nodes in genotype
558         * @return node count
559         */
560        int getNodeCount();
561
562        /**
563         * Check if sizes of all parts in genotype are valid
564        \retval error_position 1-based
565        \retval 0 when all part sizes are valid
566         */
567        int checkValidityOfPartSizes();
568
569        void validateNeuroInputs();
570
571        /**
572         * Builds Model object from internal representation
573         * @param a reference to a model that will contain a built model
574         */
575        void buildModel(Model &model);
576
577        /**
578         * Adds neuro connections to model
579         * @param a reference to a model where the connections will be added
580         */
581        void buildNeuroConnections(Model &model);
582
583        /**
584         * @return genotype in fS format
585         */
586        SString getGeno();
587
588        /**
589         * After creating or deleting a new neuron, rearrange other neurons so that the inputs match
590         */
591        void rearrangeNeuronConnections(fS_Neuron *newNeuron, SHIFT shift);
592
593};
594
595
596#endif
Note: See TracBrowser for help on using the repository browser.