Practical Procedural Modeling Of Plants And Apply Permutation
Introduction
This paper will discuss the utilisation of L-Systems regarding procedural generation relative to the creation of flora, and how it can be altered to create unique plants every time. Before this paper begins to elaborate on a procedural method, a definition of procedural generation will be given. Togelius, Yannakakis, Stanley and Browne, 2010, state that Procedural Content Generation refers to creating game content automatically, through algorithmic means, as opposed to hand-authored methods. This involves a defined set of rules and parameters for the algorithm to follow. With this definition, the procedural method this paper will be evaluating will be L-Systems due its popularity in vegetation generation. The aim of this paper is to analyse the algorithmic method used in creating plants within a game, and to evaluate how it can be altered to create unique plants on each execution. This will involve applying random values to the algorithm to allow for variation in the foliage. Within this paper, L-Systems will be evaluated and its application in plant generation will be discussed.
Methods to create variation in the product will also be analysed and compared, to discuss which method is best to use each scenario. Plants are relatively difficult to model realistically due to their random nature in growth, yet like all living beings, follow a certain set of rules. These rules allow people to be able to distinguish between a plant from any other being, by giving it unique identifiable features. In nature, tree’s have specific growth patterns, dependant on the species, yet each tree looks unique due to the subtle varieties. With each subtle difference, each plant is exclusive, which procedural generation must consider. The Lindenmayer System is the most successful in doing so. GrammarsBefore continuing to the explanation of L-Systems it is important to understand grammars, as the L-System is a type of formal grammar. Togelius, Shaker and Dormans, 2016, define formal grammar as a set of production rules for rewriting strings, i. e. converting one string into another. Each rule is set out in the following form: A -> B, where A is the symbol(s) to find in a string, and B is the symbol(s) to replace it. Then the system goes through the string following this set of rules. If we had a rule of D->DE and the starting string was D, the first iteration will replace the D with DE. The new string is now DE.
Following a second iteration, the current string DE, will become DEE due the replacement of D with DE. This can be repeated an infinite amount of times. Chomsky, 1956, originally introduced formal grammars to model the natural language. It has since been adopted by computer science due to the nature of its problems being expressible in strings. This, in such, has led to the creation of procedural generation and L-Systems. When grammars are used in the computer industry, how the strings are rewritten is a key aspect to consider, relative to the desired outcome. There are two types of rewriting: sequential rewriting and parallel rewriting. Sequential rewriting is the process in which the string is viewed from left to right and is rewritten as its read. Therefore, when a rule is applied to a symbol, the replacement symbols will be entered into the same string being read, before it moves onto the following symbol. Parallel rewriting, however, handles all the rewriting at the same time. This is executed by writing the replacement symbols into a new string, in a separate memory location, ensuring the original string is not tampered with.
L-Systems
What are they? An L-System, or Lindenmayer System, consists of two main features; parallelism in the rewriting process and the notion of grammar conceived as a description of a dynamic process (Rozenbery and Salomaa, 1980). This definition can be simplified to describing an L-System as a set of rules set by string of letters, that rewrites the string at the same time. Lindenmayer invented L-Systems to study the growth of plants and their self-similarity (where part of an object is exactly or similarly replicated throughout). The recursive and iterative nature of L-Systems allows for fractal-like forms to be easily replicated.
Fractal Systems
A fractal system is based on repetition of a certain equation, leading to self-similarity. When looking at a tree, it can be assumed that the branches at the top of the tree are similar in structure to the whole tree. This can be represented using a fractal system. Iterated system of a function to create a fractal tree. Figure 1 represents a simple equation used with the L-System to create a tree. With each iteration, the plant becomes more and more defined, due the increase in repetition. However, just looking at the product after five iterations, it is clear is it a plant. In this, the tree has been recursively built based upon a predefined rule, by creating self-similar patterns within a structure. This is the outcome of a fractal system.
