Creating a Parametric L-System in C#
Hello! I have been working on creating an L-system for use in a game that involves many different species of plants.
Here's some background: an L-system is a way of generating a string by using a replacement rule. For example A -> AB. This can be iterated creating an increasingly large string. Then you can interpret this string into objects or directions. For example 'F' may mean draw a line of length x and '-' may mean change angle by -x degrees, so the string "F-F" would mean draw a line of length x, change angle by -x, and then draw another line of length x.
Now from this you can create more complex L-systems, in the literature one of these more complex models is called a "parametric L-system". A normal L-system is a string built of characters, a parametric one is a list made of modules. For example a module might be F(l) l being a float representing the length. So you could have a list of modules something like F(5)-F(3) which would be interpreted as: draw a line of length 5, change angle by -x, and then draw a line of length 3.
Now that seems simple enough but the problem comes in when you want to iterate on this list. What I'm wondering is how you might write a rule that says F(l) -> F(l/2).
If anyone has ideas or can point me in the right direction it would be much appreciated Ty!
Answer by Bunny83 · Aug 12, 2017 at 10:26 PM
This is actually a quite pointless substitution rule:
F(l) -> F(l/2)
You probably mean something like
F(I) -> F(I/2) + F(I/2)
Otherwise the result will always be just one single "F" and iterating that system just makes the parameter smaller.
However the main question is what you want to use this for? For example if you want to use it to actually perform the resulting "command string" it would make more sense to already use actual objects / classes for each module. Because when using an actual string you have the following problems:
strings can't be changed. So when you modify them you have to recreate the string. The larget the string gets the more garbage you create each iteration.
strings require you to constantly parse the string, extract the module identifies, split off their parameters and when done re-assemble the string.
If each module is an actual class instance, you can keep the parameters as fields of each module instance. That simplifies the sustitution process and makes it easier to actually do something with the result.
As for how the substitution rule can be processed, it's just the same as without parameters, You first substitude the modules by their names and finally process the parameters. A rule usually specifies arbitrary placeholders for each parameter which can be used in an expression in the substitution parameters.
If you need a simple expression parser, have a look at my ExpressionParser.
I would probably allow the rules to be written as string and parse them into some structured way.
public enum EModuleType
{
ModA,
ModB,
ModC
}
public class Module
{
public EModuleType type;
public List<float> parameters;
}
public class LSystem
{
public List<Module> content;
}
public class Substitution
{
public EModuleType type;
public List<Expression> parameterExp;
}
public class Rule
{
public EModuleType type;
public Expression condition = null;
public List<Substitution> replacement;
}
So the "Module" class represents a single "symbol" in our alphabet including the parameters. The enum just specifies the type of symbol. An "LSystem" instance is an actual string which might be iterated to refine the system. "Rule" is a class that represents a single rule definition. The type specifies which module this rule will replace. An optional "condition" expression might be used to activate / deactivate that rule based on the parameters. A "Substitution" instance is a single replacement module. However it doesn't specify parameters directly but each parameter is represented by an expression which is based on the rule parameter variables. So a Substitution instance can be used to create the actual replacement Module based on the source module parameters.
This is of course one way you can accomplish such a system. Of course you can go the string parsing route as well. It highly depends on your goals. How large strings do you want to support? How should the system be defined? How should the rules be defined? Which parts do you want to be dynamic?
I actually have refined my original ExpressionParser to allow logical expression as well. It supports comparising operators like (==, >, <, !=, ...) which can compare number expressions and return a "logic result" (aka boolean). It also supports logic operators like (&&, and, ||, or, !, not, ^, xor). However the parser is still in an experimental state and not ready to be published.
edit
I finally had some time to clean up my LogicExpressionParser. I can't guarantee it works 100% but in my tests everything works as it should. Keep in mind the parser uses a quite strict syntax. If unsure just put some additional pairs of brackets ^^. Note that it does not perform an implicit multiplication. So 2x
should be 2*x
. Also "unary minus" need to be inside brackets. This does not work: a * -b
. It should be a * (-b)
.
At the same time i made a string based Lindenmayer system. It also contains a parser that can parse a simple text based definition into an LSystem.
I didn't really test this system to the bone, but i've done some complex testing systems. I also created a simple non parametric sample (HilbertCurve). It properly generates a texture that looks like this(upscaled image).
I've added some documentation in comments that should be enough to understand how it's supposed to work. The main classes (LSystem and Module) have an overridden ToString so it makes it easier to visualize the result of an iteration for testing purposes. Though note that the more complex a system is and the more iteration you run the longer the results get. So be careful. For a simple A-->A; A the growth is 2^X
A parametric example would be:
Axiom: A(0, 2)
Count: 5
Rules:
A(a, b): a<4 --> B(b); A(a+1, b^2 + 2*b); B(b)
A(a, b): a>=4 -->
B(val) --> Plot(val)
This willl produce:
Plot(2); Plot(8); Plot(80); Plot(6560); Plot(6560); Plot(80); Plot(8); Plot(2)
"a" is basically used as counter. There are two rules that involve "A" but with different conditions. Note that only one rule is applied at a time. If two rules would match, only the first one is applied.
Note that this is just a pointless example ^^. After the 5 iterations the system enters a stable state and more iterations don't do anything as all rule symbols are vanished.
Ty for the reply! That ExpressionParser is exactly the kind of thing I was looking for!
I was already thinking of creating a list of modules ins$$anonymous$$d of a string, but I couldn't think of anyway way to interact with the modules parameters (while still keeping the program flexible) and your ExpressionParser seems to be the perfect solution! Also glad to see someone else was thinking along the same lines.
Before I go about implementing it I did have a few questions though.
This L-system generator is meant for a mobile game, would you still recommend your ExpressionParser in that situation? If it's going to be super hard on the hardware I'll stick to my purely context-sensitive L-system.
Could you clarify the difference between a parameter and a constant in your system? I just want to make sure I have everything solidified in my head before I start implementing.
Is there anywhere I can get notifications about updates to your ExpressionParser? even if I don't end up using it here this is definitely something I want to keep track of!
Again ty for the time you took to answer this question! You gave a very thoughtful well formulated response and I appreciate it!
I'm currently not home for the next few days. If i find some time i might implement an L-System myself and publish it here. I don't really have a public repository which i update on a regulary basis. $$anonymous$$ost things i wrote recently was for an answer here on UA.
ps: The expression parser has some features which you don't really need. $$anonymous$$y LogicExpressionParser is a bit simpler but has support for conditions which will be more helpful in this case i guess.
That sounds really cool! $$anonymous$$aybe if you do end up creating an L-System we could compare and contrast results?
It seems like you already know a lot about them but if you haven't seen it there are some great resources here: http://algorithmicbotany.org/papers/#abop
And yeah that LogicExpressionParser sounds really exciting! I'd love to see it once you're ready to release it into the wild!
@Beks_Omega:
Update! ^^
I've finally released my new expression parser and a simple string based LSystem.
Wow your L-system is super fancy! $$anonymous$$ine looks pretty armature in comparison (probably because I am an armature lol) but I'm happy with the way it works! I really need to take the time to read over your stuff more carefully, maybe I can absorb some of your amazing fancyness.
Here's a link to the LSystem I designed. The premise of it is that it's meant to be pretty modular-izable, so it takes in the rules set, the turtle data (constants for the expression parser mostly), and the l-system interpreter. The link has the LSystem Generator, which controls the interaction of all of the parts, and the rules set, because I worked hard on it and I think it's pretty cool hehe. I'm still working on some stuff like checking to make sure the system is valid, and creating a custom inspector so it's easier to input the rules (which I'm almost done with) but for virtually all purposes is it is a working Stochastic-Parametric-ContextSensative Lsystem!
Ty for the help, the code, and the correspondence! Hopefully I'll be able to convert it over to your LogicExpressionParser soon as well!
$$anonymous$$y implementation is not a context sensitive LSystem but a stochastic behaviour can be achieved with a proper condition. An expression has support for "rand" to aquire a random number. Though it might be necessary to allow the setting of a seed for the random number generator.
I think adding context specific conditions shouldn't be too difficult. Even when the context requires a certain parameter range. So a rule could look something like this:
[A(v>0&&v<5)] B(a,b) [C] --> ...
This would only match a "B" if it is followed by a C and there's an A infront and its parameter is in the specified range. So a valid match would be:
A(2); B(2, 5); C
While thinking about this i just realised that the logic expression parser is missing constants / variables for "true" and "false" -.-. I also found another C&P error (the "!" operator has a length of 1 not 4 (line 791)). I quickly fixed the error and added true and false as "hardcoded" constants.
Your answer
Follow this Question
Related Questions
Custom editor plus/minus list 0 Answers
Detect multiple gamobjects 1 Answer
Notifying about character/item selection 1 Answer
Automatic reloading issues 1 Answer
Making an image appear 0 Answers