2

Description

"Procedural generation is useful to generate content, being meshes, levels or worlds. One might use noise functions, neural networks or, in our case, L-Systems. This kind of tool is usually employed in mesh generation like trees or vegetation.\r\n\r\nThe following article will focus on how to implement quickly a stochastic L-System as a usable resource. An usage example could be the following:\r\n\r\n```\r\nextends PrimitiveMesh\r\n\r\n@export var system : LSystem\r\n\r\nfunc _create_mesh_array() -> Array:\r\n\tsystem.axiom = \"F\"\r\n\tsystem.iterations = 3\r\n\tvar generated : String = system.get_result()\r\n\treturn _generate_my_beautiful_mesh(generated)\r\n```\r\n\r\nIn further articles, we will reuse this to create random complex meshes with few efforts.\r\n\r\n## Concept\r\n\r\nA [L-System](https:\/\/en.wikipedia.org\/wiki\/L-system) can be seen as a set of rules that transforms an input string to an output string. For instance, let's consider the following rules:\r\n> A -> AB\r\n> B -> C\r\n\r\nAnd an input string:\r\n> A\r\n\r\nLet's iterate once, and we obtain the following output string:\r\n> AB\r\n\r\nThe first rule has been applied.\r\nNow, let's iterate several times and we'll obtain:\r\n> ABC -> ABCC -> ABCCC\r\n\r\nLet's spice things up and add a set of rules to be randomly selected for each symbol. For example, let's enhance the previous system with other rules.\r\n> A -> AB\r\n> A -> BA\r\n> B -> C\r\n\r\nNow, `A` can be replaced by either `AB` or `BA`. If we run the system with `A` as an input, we'll _probably_ obtain:\r\n> A -> AB -> BAC -> CABC -> CABCC -> CBACCC\r\n\r\nAnd so on.\r\n\r\nFinally, if we add a weight to rules, some of them will be more likely to be selected.\r\n\r\nTime to implement this simple concept as a resource.\r\n\r\n## Replacement Rule\r\n\r\nA rule describes the replacement of a symbol by a series of symbol. As we are in a stochastic system, a rule is weighted, meaning that a symbol can be replaced by one of the rules given a probability.\r\n\r\n```\r\n@tool\r\nclass_name LSystemRule\r\nextends Resource\r\n\r\n@export_range(0., 1.) var weight : float = 1.\r\n@export var replacement : String = \"\"\r\n```\r\n\r\n## Symbol\r\n\r\nA symbol is a string of length 1 associated to a set of rules.\r\n\r\n```\r\n@tool\r\nclass_name LSystemSymbol\r\nextends Resource\r\n\r\n@export var symbol : String = \"\"\r\n@export var rules : Array[LSystemRule] = []\r\n```\r\n\r\n## System\r\n\r\nThe system itself is an alphabet (a set of symbols), an axiom (the input string), and a number of iteration.\r\n\r\n```\r\n@tool\r\nclass_name LSystem\r\nextends Resource\r\n\r\n@export var alphabet : Array[LSystemSymbol] = []\r\n\r\n@export var axiom : String = \"\" :\r\n\tset(value) :\r\n\t\taxiom = value\r\n\t\temit_changed()\r\n\r\n@export_range(0, 16) var iterations : int :\r\n\tset(value) :\r\n\t\titerations = value\r\n\t\temit_changed()\r\n\r\n# Produces the result of a stochastic grammar given the axiom\r\nfunc get_result() -> String:\r\n\t# For more convenience, checks the system sanity and rebuild the rule dictionary\r\n\tvar rules : Dictionary = {}\r\n\tfor a in alphabet:\r\n\t\tvar s : String = a.symbol\r\n\t\tassert(s != null and s.length() == 1 and not rules.has(s))\r\n\t\tvar local_rules : Array[LSystemRule] = a.rules\r\n\t\tvar total_weight : float = 0\r\n\t\tfor r in local_rules:\r\n\t\t\ttotal_weight += r.weight\r\n\t\tassert(total_weight > 0)\r\n\t\tvar weighted_rules : Array = []\r\n\t\tfor r in local_rules:\r\n\t\t\tweighted_rules.append({ \"w\" : r.weight \/ total_weight, \"r\" : r.replacement })\r\n\t\trules[s] = weighted_rules\r\n\t# And now, produces the result !\r\n\tvar production : String = \"\"\r\n\tvar start : String = axiom\r\n\tfor i in range(iterations):\r\n\t\tfor c in start:\r\n\t\t\tif rules.has(c):\r\n\t\t\t\tvar rule_set : Array = rules[c]\r\n\t\t\t\tvar rule_count : int = rule_set.size()\r\n\t\t\t\tvar p : float = randf()\r\n\t\t\t\tvar acc : float = 0\r\n\t\t\t\tvar selected : int = 0\r\n\t\t\t\twhile acc < p and selected < rule_count:\r\n\t\t\t\t\tacc += rule_set[selected][\"w\"]\r\n\t\t\t\t\tselected += 1\r\n\t\t\t\tselected -= 1\r\n\t\t\t\tproduction += rule_set[selected][\"r\"]\r\n\t\t\telse:\r\n\t\t\t\tproduction += c\r\n\t\tstart = production\r\n\treturn production\r\n```\r\n\r\n## Example\r\n\r\n"

Comments