source: cpp/frams/genetics/fL/fL_general.h @ 934

Last change on this file since 934 was 821, checked in by Maciej Komosinski, 6 years ago

Performance and stability improvements in fB, fH, and fL; improved parsing and math evaluations in fL

File size: 18.4 KB
Line 
1// This file is a part of Framsticks SDK.  http://www.framsticks.com/
2// Copyright (C) 1999-2018  Maciej Komosinski and Szymon Ulatowski.
3// See LICENSE.txt for details.
4
5#ifndef _FL_GENERAL_
6#define _FL_GENERAL_
7
8#include <frams/util/sstring.h>
9#include <frams/param/mutableparam.h>
10#include <frams/param/paramobj.h>
11#include <vector>
12#include <list>
13#include <unordered_map>
14#include <frams/model/model.h>
15#include "fL_matheval.h"
16
17/// determines to which class fL element belongs
18enum fLElementType {
19        TERM, ///< word of L-System
20        INFO, ///< fL_Builder object
21        RULE, ///< rule of L-System
22        BRANCH ///< special type of fL word, which represents branch
23};
24
25/** @name Constants used in fL methods */
26//@{
27#define FL_PART_PROPS_COUNT   4 ///<Count of part properties
28#define FL_JOINT_PROPS_COUNT  3 ///<Count of joint properties
29#define FL_PE_NEURO_DET       "d" ///<Id of details type definition in f0_neuro_paramtab
30#define FL_PE_CONN_WEIGHT     "w" ///<Id of weight type definition in f0_neuroconn_paramtab
31#define FL_PE_CONN_ATTR       "attr" ///<Id of attractor of neural connection
32#define FL_DEFAULT_LENGTH     1.0 ///<Default length of a stick in fL encoding
33#define FL_MINIMAL_LENGTH     0.0 ///<Minimal length of a stick in fL encoding
34#define FL_MAXIMAL_LENGTH     2.0 ///<Maximal length of a stick in fL encoding
35#define FL_MAXITER           "100.0" ///<Maximal iteration available in fL
36#define FL_MAXPARAMS          "3" ///<Maximal number of user-parameters
37//@}
38
39extern const char *fL_part_names[];
40extern const char *fL_joint_names[];
41extern const char *fL_joint_fullnames[FL_JOINT_PROPS_COUNT];
42extern const char *fL_part_fullnames[FL_PART_PROPS_COUNT];
43
44#define LSYSTEM_PARAM_TYPE "s" ///< standard type of L-System elements
45
46class fL_Builder;
47
48/**
49 * Most abstract class of L-System. It requires from inheriting classes to implement
50 * methods processDefinition and toString.
51 */
52class fL_Element
53{
54public:
55        fLElementType type; ///< type of fL_Element
56
57        int begin; ///<beginning of the element definition in genotype
58        int end; ///<end of the element definition in genotype
59
60
61        fL_Element(fLElementType type) : type(type) { begin = end = 0; }
62        virtual ~fL_Element() { }
63
64        /**
65         * Performs connecting current element to fL_Builder and parsing of input
66         * with respect of builder.
67         * @param builder fL_Builder object responsible for creating this element
68         * @return 0 if processing went successfully, other values otherwise
69         */
70        virtual int processDefinition(fL_Builder *builder) = 0;
71
72        /**
73         * Creates string line for current element. This method is used by Builder
74         * to create string representation of words, rules and informations of L-System.
75         * @return stringified element
76         */
77        virtual SString toString() = 0;
78};
79
80/**
81 * Represents word objects of L-System representation. They are used in axiom,
82 * produced sequences and rules.
83 */
84class fL_Word : public fL_Element
85{
86public:
87        SString name; ///<name of word
88        int npar; ///<number of word parameters
89        MutableParam mut; ///<MutableParam for word parameters
90        ParamEntry *tab; ///<ParamTab used for loading and saving properties of word
91        void *data; ///<pointer to properties of word
92        bool builtin; ///<determines if word is built-in (true) or not (false).
93        PartBase *bodyelementpointer; ///<helper field for built-in words
94        std::vector<MathEvaluation *> parevals; ///<stores MathEvaluation objects with parameter functions
95        double creationiter; ///<this helper field is used during L-System iterations and determines when word was created
96        fL_Word(bool builtin = false, int begin = 0, int end = 0) :
97                fL_Element(fLElementType::TERM), mut("Word", "Properties"),
98                builtin(builtin)
99        {
100                name = "";
101                npar = 0;
102                tab = NULL;
103                data = NULL;
104                creationiter = 0;
105                this->begin = begin;
106                this->end = end;
107                bodyelementpointer = NULL;
108        }
109
110        /**
111         * Destroys data ParamObject and MathEvaluation objects. ParamTab for Word
112         * should be deleted separately, because all words with same name share same
113         * pointer to ParamTab.
114         */
115        ~fL_Word()
116        {
117                if (data)
118                        ParamObject::freeObject(data);
119                for (MathEvaluation *ev : parevals)
120                {
121                        if (ev) delete ev;
122                }
123                parevals.clear();
124        }
125
126        /**
127         * Checks if there is no other word stored in the builder with the same name,
128         * prepares ParamTab for defined word and adds created word definition to the
129         * builder.
130         * @param builder pointer to the builder that process this word definition
131         * @return 0 if word is added, 1 if word is redefined
132         */
133        int processDefinition(fL_Builder *builder);
134
135        /**
136         * Operator copies name string, npar value, pointer to ParamTab and pointers
137         * to MathEvaluation objects for parameters. It sets data of this word to
138         * NULL.
139         * @param src source word
140         */
141        void operator=(const fL_Word& src);
142
143        /**
144         * Returns 'w:' line defining word in genotype.
145         * @return string representation of word definition
146         */
147        virtual SString toString();
148
149        /**
150         * Returns token version of this word. It is used during converting successor's
151         * list or axiom list into strings. Flag 'keepformulas' should be set to true
152         * if word parameters should be represented as formulas, and set to false if
153         * word parameters should contain the result of evaluation.
154         * @param keepformulas true if parameters should have mathematical formula, false if it should have result of evaluation
155         */
156        virtual SString stringify(bool keepformulas = true);
157
158        /**
159         * Saves formulas or evaluations of parameters in ParamObject.
160         * @param keepformulas true if parameters should have mathematical formula, false if it should have result of evaluation
161         * @return 0 if method successfully managed to save data, 1 if an error occured
162         */
163        int saveEvals(bool keepformulas);
164
165        /**
166         * Computes distance between two L-System words in genotype. Distance has sense
167         * only when two words have the same name. Otherwise, returned value equals -1.
168         * The distance is computed as Euclidean distance between words arguments.
169         * @param right the second word
170         * @return Euclidean distance between words in genotype or -1 if words have different name
171         */
172        double distance(fL_Word *right);
173};
174
175/**
176 * Represents special branching word in L-System genotype.
177 */
178class fL_Branch : public fL_Word
179{
180public:
181        /// Determines if branching parenthesis is opened or closed
182        enum BranchType {
183                OPEN,
184                CLOSE
185        };
186        BranchType btype; ///< branch parenthesis type
187        fL_Branch(BranchType branchtype, int begin, int end) : fL_Word(true, begin, end)
188        {
189                type = fLElementType::BRANCH;
190                btype = branchtype;
191                name = stringify();
192        }
193        SString toString() { return ""; };
194        SString stringify(bool keepformulas = false) { return btype == BranchType::OPEN ? "[" : "]"; }
195};
196
197/**
198 * Represents rules in L-System genotype. Every rule has predecessor and successors.
199 * The optional argument is a condition of deploying rule. Every rule is ran
200 * synchronously for every letter of the current genotype. If condition and
201 * predecessor are satisfied, then predecessor is replaced by successors.
202 */
203class fL_Rule : public fL_Element
204{
205public:
206        SString predecessor; ///<string representation of the predecessor
207        SString condition; ///<string representation of the condition
208        SString successor; ///<string representation of the successor
209
210        fL_Word *objpred; ///<object representation of the predecessor
211        MathEvaluation *condeval; ///<object representation of the condition
212
213        std::list<fL_Word *> objsucc; ///<objec representation of successors
214
215        fL_Rule(int begin, int end)  : fL_Element(fLElementType::RULE)
216        {
217                predecessor = "";
218                condition = "";
219                successor = "";
220                objpred = NULL;
221                condeval = NULL;
222                this->begin = begin;
223                this->end = end;
224        }
225
226        ~fL_Rule()
227        {
228                if (objpred) delete objpred;
229                if (condeval) delete condeval;
230                for (fL_Word *word : objsucc)
231                {
232                        delete word;
233                }
234                objsucc.clear();
235        }
236
237        /**
238         * Loads rule definition from the genotype, checks if word defined in
239         * predecessor does exist, tokenizes successor and condition.
240         * @param builder pointer to the builder that process this word definition
241         * @return 0 if word is added, 1 if an error occured during parsing
242         */
243        int processDefinition(fL_Builder *builder);
244
245        SString toString();
246
247        /**
248         * Runs rule for a given word, if all conditions and starting rules are satisfied.
249         * Method alters given list of tokens by removing matching word pointed by
250         * pointer and iterator of list and inserting successor sequence into list.
251         * Final iterator value points to the first word after processed word.
252         * @param builder builder containing current genotype
253         * @param in word that is currently processed
254         * @param it iterator of genotype list which determines position of current analysis
255         * @param currtime value representing continuous time value for rule
256         * @return 0 if rule processed current word, 1 if rule is no applicable
257         */
258        int deploy(fL_Builder *builder, fL_Word *in, std::list<fL_Word *>::iterator &it, double currtime);
259};
260
261/**
262 * Structure for holding current Turtle state.
263 */
264struct fL_State
265{
266        Pt3D direction; ///<Direction of turtle
267        Part *currpart; ///<Latest created part
268        Neuro *currneuron; ///<Latest created neuron
269        fL_State() : direction(1,0,0), currpart(NULL), currneuron(NULL)
270        { }
271};
272
273/**
274 * Main class of L-System processing. It holds all information required to perform
275 * steps of development of a creature. It allows to create Timed D0L-Systems with
276 * following limitations:
277 *
278 *  - fractions of time affect only parameters of currently produced words,
279 *  - integer steps deploy rules in order to develop new elements of body,
280 *  - if parameter should use time fraction, then $t variable must be used,
281 *  - $t variable always contain values from 0 to 1 that represent current fraction
282 *    of step.
283 */
284class fL_Builder : public fL_Element
285{
286public:
287        SString axiom; ///<starting sequence of genotype
288        double time; ///<time of creature development
289        int numckp; ///<number of checkpoints per growth step - checkpoints are always created after rules deployment in integer steps, numckp determines how many checkpoints should be created within single step (to watch changes of parameters)
290        int maxwords; ///<maximum number of words that can
291        bool using_checkpoints; ///<true if checkpoints should be created, or false
292        bool using_mapping; ///<true if mappings should be created, or false
293
294        int builtincount; ///<number of built-in words
295
296        std::list<fL_Word *> genotype; ///<list of current words of genotype
297        std::unordered_map<std::string, fL_Word *> words; ///<map from string to words existing in L-System
298        std::vector<std::string> wordnames;
299        std::vector<fL_Rule *> rules; ///<rules available in system
300
301        fL_Builder(bool using_mapping = false, bool using_checkpoints = false) : fL_Element(fLElementType::INFO),
302                        using_checkpoints(using_checkpoints), using_mapping(using_mapping)
303        {
304                axiom = "";
305                time = 1.0;
306                numckp = 1;
307                builtincount = 0;
308                maxwords = -1;
309        }
310        ~fL_Builder();
311
312        /**
313         * Helper function for trimming leading and trailing spaces from sequence.
314         * @param data input string
315         * @return string with trimmed spaces
316         */
317        static std::string trimSpaces(const std::string& data);
318
319        /**
320         * Processes single line of input sequence and load line properties with use
321         * of proper ParamTab.
322         * @param type which type of line is this
323         * @param line line to be processed
324         * @param obj variable storing pointer to created L-System element
325         * @param linenumber for error messages
326         * @param begin index of first character of line
327         * @param end index of last character of line
328         * @return 0 if processing ended successfully, 1-based position of error otherwise
329         */
330        int processLine(fLElementType type, const SString &line, fL_Element *&obj, int linenumber, int begin, int end);
331
332        /**
333         * Parses input genotype with words, information and rules. First of all,
334         * model-specific words defined in addModelWords method are added to words map.
335         * Every genotype should start with words definitions. They cannot collide
336         * with model words and with each other. Secondly, information line, containing
337         * axiom and number of iteration must be processed. In the end, all rules
338         * have to be processed by builder. After determining line type and creating
339         * fL_Element specialized object, the builder runs object's processDefinition
340         * method to generate all important objects and register element in builder
341         * structures.
342         * @param genotype input genotype
343         * @return 0 if processing finished successfully, 1-based position of error if it occured
344         */
345        int parseGenotype(const SString &genotype);
346
347        /**
348         * Prepares structures and tokenizes axiom.
349         * @param builder this method should receive pointer to itself
350         * @return 0 if processing went successfully, 1 otherwise
351         */
352        int processDefinition(fL_Builder *builder);
353
354        /**
355         * Adds words used for Framsticks body and brain development.
356         */
357        void addModelWords();
358
359        /**
360         * Helper method that tokenizes string sequence by closing parenthesis
361         * with respect to parenthesis nesting.
362         * @param pos index of character, from which next token needs to be extracted. Method replaces this parameter with next starting position, or -1 if there was an error during parsing, like parenthesis mismatch
363         * @param src original sequence
364         * @param token reference to variable holding new token
365         * @return true if new token is found, false if there is no more tokens or when there was parenthesis mismatch (if pos == -1, then it is parenthesis mismatch)
366         */
367        bool getNextObject(int &pos, const SString &src, SString &token);
368
369        /**
370         * Creates fL_Word object for a given token.
371         * @param worddef string representing single word object in sequence
372         * @param word a reference to a pointer of created word by this method
373         * @param numparams number of parameters for a given sequence (usually number of rule predecessor's arguments)
374         * @param begin the begin of word definition in genotype
375         * @param end the end of word definition in genotype
376         * @return 0 if conversion went successfully, 1 when there is a problem with parsing
377         */
378        int createWord(const SString &worddef, fL_Word *&word, int numparams, int begin, int end);
379
380        /**
381         * Helper function that converts input sequence into list of L-System words.
382         * @param sequence input sequence of stringified word objects
383         * @param result reference to list holding generated words
384         * @param numparams number of parameters that can be used for words stored in result list
385         * @return 0 if tokenizing finished successfully, 1 otherwise
386         */
387        int tokenize(const SString &sequence, std::list<fL_Word *> &result, int numparams, int begin, int end);
388
389        /**
390         * Uses rules to process current genotype and make next iteration step for
391         * L-System development.
392         * @param currtime current time of genotype processing
393         * @return always 0
394         */
395        int iterate(double currtime);
396
397        /**
398         * Alters only parameters that depend on time. Should be used if only fraction
399         * of iteration has changed, not integer part.
400         * @param currtime current time of processing
401         * @return always 0
402         */
403        int alterTimedProperties(double currtime);
404
405        /**
406         * Developes L-System from given genotype and builds Framsticks Model from it.
407         * When using_checkpoints is enabled, method generates checkpoint for each
408         * step defined in timestamp.
409         * @param neededtime reference to a time value after stopping development (usually it will be equal to time specified in the time field, unless the number of allowed words will be exceeded earlier)
410         * @return final model from a fL genotype
411         */
412        Model* developModel(double &neededtime);
413
414        /**
415         * Creates new checkpoint for a given model based on current state of genotype.
416         * @param model reference to model
417         * @return 0 if developing went successfully, 1 otherwise
418         */
419        int buildModelFromSequence(Model *model);
420
421        /**
422         * Returns stringified product of L-System development.
423         * @return stringified words of developed L-System
424         */
425        SString getStringifiedProducts();
426
427        /**
428         * Returns genotype stored by objects in fL_Builder.
429         * @return genotype converted from L-System objects
430         */
431        SString toString();
432
433        /**
434         * Alters part properties according to informations stored in stickword.
435         * Method takes current values of part's properties computed from previous
436         * calls of the alterPartProperties and computes mean according to upcoming
437         * values of properties.
438         * @param part analysed part
439         * @param stickword the L-System word that affects current part
440         * @param alterationcount the number of times of part modifications - used to compute mean of every word properties
441         * @return always 0
442         */
443        int alterPartProperties(Part *part, fL_Word *stickword, double &alterationcount);
444
445        /**
446         * Finds input neuron that is nearest to attractor or connection definition.
447         * When attractor object is given, then the word with name matching attractor and
448         * with nearest values of parameters is chosen as the point, from which input
449         * neuron is looked for. The searching goes both sides.
450         * @param currneu object storing informations about connection word iterator and current neuron
451         * @param attractor pointer to an attractor definition presented in connection word
452         * @return pointer to the input neuron, or NULL if no neuron could be found
453         */
454        Neuro* findInputNeuron(std::pair<std::list<fL_Word *>::iterator, Neuro *> currneu, fL_Word *attractor);
455
456        /**
457         * Removes joints, parts and neurons with its connections from current model, without
458         * removing checkpoint data.
459         * @param m model to clear
460         */
461        void clearModelElements(Model *m);
462
463        /**
464         * Converts parameters defined in built-in words into desired
465         * range with use of sigmoid function, which ensures staying
466         * within min and max value.
467         * @param input the value from evaluation of parameter
468         * @param min minimal value of property
469         * @param max maximal value of property
470         * @return value of body element property
471         */
472        double sigmoidTransform(double input, double min, double max);
473
474        /**
475         * Counts words defined in the genotype.
476         * @return number of defined words
477         */
478        int countDefinedWords();
479
480        /**
481         * Counts number of sticks in a given sequence
482         * @return number of sticks in sequence
483         */
484        int countSticksInSequence(std::list<fL_Word *> *sequence);
485
486        /**
487         * Counts all definitions of words, all words in axiom and rule successors in a genotype.
488         * Used for computing change between original genotype and mutation.
489         * @return number of words in definitions, axiom and rule successors
490         */
491        int countWordsInLSystem();
492
493        /**
494         * Sorts rules and removes rules that will not be used. The "sorting" is
495         * done in such way that all rules with conditions are first, and rules
496         * without conditions go to the end. If there are more than one rule
497         * for the same word with no condition or same condition, than the
498         * second one is removed.
499         */
500        void removeRedundantRules();
501};
502
503#endif // _FL_GENERAL_
Note: See TracBrowser for help on using the repository browser.