L-Systems
=========

This file describes the L-System project. You can export this file in HTML with
[Markdown](http://daringfireball.net/projects/markdown/) by executing the file "exportREADME2html.sh"
in a Linux based system, with Markdown installed.


I. Introduction
===============

This project is realized by Thomas NOGUER and Rémi DUCCESCHI, students in 5th year at Polytech'Tours.
It is supervised by Dr Sébastien AUPETIT.

The goal of this project is to interpret L-Systems grammar, generating words; and use JMonkey
to create an animation based on the generated words (turtle interpretation or other).

*THIS PROJECT IS ACTUALLY IN DEVELOPPEMENT*


II. Presentation
================

This project uses L-System grammars: it generates words from a given grammar and interprets these words
to create a 2D / 3D scene (turtle interpretation or other).

1. L-Systems
------------

A L-System is a specific grammar that differs from Chomsky's ones on how the rules are applied. In fact,
in a L-System, all rules that can be apply on a word are applied in one go, whereas a Chomsky grammar
will take X steps for X rules on the same word. See
[Wikipedia](https://en.wikipedia.org/wiki/L-system) for more
details.

A L-System is defined by:

- a list of symbols (aka V)
- an axiome (composed of one symbol)
- a list of rules
- eventually an angle to set-up the turtle interpretation.

*NOTE*: In a rule, the left-part, what will be changed, must be a single symbol.

There are 2 principle types of L-Systems that can be mixed-up whether they are context-free or not,
determinist or not.

### Determinism ###
A L-System is determinist if a symbol, appear only once in the left-side of
the rules. Otherwise, the system is stochastic. Here is a little example:

Consider the following rules (V = {a, b})

- a -> b
- b -> a

This grammar is determinist.

Contrary, this grammar is stochastic (same V):

- a -> b
- a -> ab

When we find "a" symbol, we don't know which rule to apply. So, we take one randomly (default is to
have the same chance to take the first or the second one).

### Context ###
A context-free L-System (noted OL) is a grammar where the choice of a rule depends only on the current
character. There are much easier than the context-dependent L-Systems. The writting of their rules is also
simpler:

- a -> bbb

In a dependent context L-System (noted IL), we have to specify a context that can be before or after the
current symbol:

- b < a -> bbb : to apply this rule, we must have met "a" symbol previously, and actually be on "b".
- a > b -> aaa : to apply this rule, we must be on a "a" symbol, and a "b" must follow somewhere in the word.

we can give a context before AND after (this syntax is not very userfriendly, but it was to have a grammar LL(1)
easily parsable in the file):

- b < bb > aa -> "baba"

Here, we transform the sequence "b" in "baba" only if we previously met the sequence "bb" and the sequence
"aa" follows somewhere after.

*NOTE*: A context-dependent system may mix context-dependent rules with context-free rules. In this case, the
context-dependent rules are tested first (priority for the context-dependent):

- a -> b (1)
- a > a -> b (2)

(1) will be tested only if (2) is not applicable.

### Notations ###

We have seen that we can mix-up the 2 types of grammar. Here is how is identified a L-System:

- DOL is a determinist context-free L-System
- SOL is a stochastic context-free L-System
- DIL is a determinist context-dependent L-System
- SIL is a stochastic context-dependent L-System

2. Interpretations
------------------

### Tube Turtle ###

This is the basic turtle interpretatation. It is able to draw all the basic interpretations. It uses basic cylinders with parametrable width, length and color. Ths only interpretation that actually draw something is FORWARD. If you do not have any FORWARD symbol in your list of symbol to draw you will not be able to see any result on the screen.

### Tree Turtle ###

This is a turtle for drawing tree type grammar. It uses cylinders like the tube turtle but has more parameters such as width reduction and length reduction. These allow to have a trunk bigger than its branches. This interpretation can also draw the leaves with its specific symbol interpretation 21. The leaves' size and color can also be parametrable. 


III. HOWTO (how to make the program work???)
==========

Here is described how to interact with the program and how does it work
(there will be in the future a real manual if we have the time (so there won't)).

1. Load a L-System in the program
---------------------------------

The first thing to do is to give to the program a grammar and a word to work on
in order to generate a sequence applying the rules of the given grammar on the word.

This sequence will be interpreted by the system to generate a beautiful animation.

### 1. With files ###

You have to write a config file where you describe the grammar you want to use. We have seen
that a L-System is described by a type (DOL, SOL, DIL or SIL), a list of symbols, a list of rules,
an axiom and a optional angle. In the program, we also give a name to the grammars.

Each of these will have to be written in the file. Let's see how it works.

*NOTE*: the file MUST be written in UTF-8.

*NOTE*: an example file can be studied in the doc/ folder: grammars-example.txt. A example is also
available at the end of this section.

*NOTE*: You can add comments in a conf file by putting the comment between 2 characters "#". Comments
MUST begin a new line.

*NOTE*: The following sections are in the order where they should appear in a conf file. For instance,
the optional ANGLE definition must be after the AXIOME definition and before the RULES.

#### 1. The name and the type ####
To declare a grammar, you have to write the name and the type of the grammar. The grammar will be
written between "{}":

	NAME
	TYPE
	{
		# ...
	}

#### 2. Symbols ####
You have to write all the symbols the grammar will use, even if they don't appear in the rules.
To do so, you need to declare a bloc "{}" called "SYMBOLS".

A symbol is a simple character. Each symbol must be declared on a new line.

You can add a interpretation to a symbol by adding ": INTERPRETATION" after the character.
INTERPRETATION must be one of the followings (basic order to the turtle interpretation):

- FORWARD (make the turtle go forward)
- TURNLEFT (turn the orientation of the turtle on the left)
- TURNRIGHT (turn the orientation of the turtle on the left)
- TURNUP (turn the orientation of the turtle up)
- TURNDOWN (turn the orientation of the turtle down)
- ROLLLEFT (make the turtle roll on the left)
- ROLLRIGHT (make the turtle roll on the right)
- ABOUTTURN (turn the orientation of the turtle by 180°)
- SAVEPOSITION (save the current position and orientation of the turtle)
- RESTOREPOSITION (restore the last saved position and orientation of the turtle)
- Any numbers strictly greater than 20 (for personalized interpretations depending on the turtle)

Here how to write it:

	SYMBOLS
	{
		a[: INTERPRETATION]
		# ...
	}

#### 3. The axiom ####
In the program, the axiom can be a simple symbol, or a word made with the symbols previously
described. If it is a simple symbol, the declaration must be preceded by "AXIOM:", otherwise
you should use "PHRASE:".

	AXIOM: a | PHRASE: abab

#### 4. The Angle ####
An angle can be given that will be used in the turtle interpretation for the symbols TURNXXX.
You just have to put:

	ANGLE: X

Where X ∈ ⟦0;360⟧ (thx UTF-8!!!)

If no angle is precised, the default value is 90°.

#### 5. The rules ####
The rules are seperated in 2: the left side (what may be replaced) and the right side (substitute),
seperated by "->".

	a -> bb

For the stochastic systems, you may add a probability that indicates the chance a rule have to be selected
when several can be. If nothing is written, the rules have all the same probability to be selected.

	a -> bb[: X]

Where X ∈ [0;1]

The deletion is symbolized by a rule where the substitute (the right side) only contains the symbol "ε"
(you can copy / paste it from here to put it in your file if needed):

	a -> ε[: X] # the probability can be given, like for the other rules

Finally:

	RULES
	{
		X [< S] [> T] -> Y[: Z]
		# ...
	}

#### 6. Forbidden characters and words ####
For your symbols or the name of the grammar, you can use any symbols you want except the followings:

- Any numbers (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
- "{"
- "}"
- "ε"
- "#"
- "<"
- ">"
- ":"
- "\n", "\r", "\r\n" (end of line character)
- "\t" (tabulation)
- " " (space)

For the name of the grammar, you can not use the following reserved words:

- ANGLE
- AXIOM
- PHRASE
- RULES
- SYMBOLS
- DOL
- SOL
- DIL
- SIL
- FORWARD
- TURNLEFT
- TURNRIGHT
- TURNUP
- TURNDOWN
- ROLLLEFT
- ROLLRIGHT
- ABOUTTURN
- SAVEPOSITION 
- RESTOREPOSITION

#### 7. Complete file ####
Finally, this is what we get at the end:

	NAME
	TYPE
	{
		SYMBOLS
		{
			a[: INTERPRETATION]
			# ...
		}
		
		AXIOM: a | PHRASE: abab
		
		[ANGLE: X]
		
		RULES
		{
			X [< S] [> T] -> Y[: Z]
			# ...
		}
	}

You can successively write several grammars in the same file. The behavior of the program is not yet
determined.


### 2. In the program ###

NOT IMPLEMENTED YET


2. Choose an interpretation
---------------------------
The tube turtle is the interpretable that you can choose to draw any grammar that uses only basic symbol interpretation. If you have any non-default symbol interpretation you can not use the tube turtle interpretation.

For tree-type grammar the tree turtle is the best fitted. It implements width and length reduction. It can also draw leaves with the symbol interpretation 21.


3. Launch a grammar
-------------------

Here we describe all the steps you have to do to display a grammar in the program.

### Import grammar ###

First, you have to import a grammar in the program. You can do it openning a file (File -> Open).
You will be able to choose the grammar you want in the first combo box (top-left of the window), only
if your program contains more than one gramar.

### Choose an interpretation ###

Then, you can chose the interpretation you want in the second combo box. This one contains all the
interpretations that can draw your grammar. If an interpretation you want does not appear here, it
is because you use in your symbols definition a symbol that this interpretation cannot display. You
should refer to the documentation of this interpretation.

You can edit your current grammar (the interpretation of each symbols) in "Tools -> Edit current grammar".
Thus, you'll be able to remove the interpretations specific to an interpretation and the new interpretations
may appear in the second combo box.

### Choose a number of iterations ###

This is the number of steps the generator must do with the grammar. 0 display only the axiom. If you put to much
here, the program may crash or take very long time to display the result.

### Launch! ###

Clic the button "Launch!" to display the demanded iteration. If you clic on "Play", all the iterations from 0 to
what you put in the spin box will be displayed sequentially. With this button, you can see the trees grow!

You'll see the result of the generation in the text area at the bottom of the window. It contains the word generated
while the main part display the interpretation of this word. It is possible to edit this word and apply your changes
to see what it does in the interpretation.

A bug exists in Windows for the change of the text. It is because of JMonkey with Swing...

### Edit the turtle ###

Finally, you can edit the turtle (interpretation)'s configuration in "Tools -> Edit current Turtle". There, you can
change the colors, the width... Refer to the documentation of the turtle for more.


IV. About turtles
===============

It is possible to create your own turtle interpretation. For doing so it is advised to take example on the existing turtles.


V. License
===========

This project is under GNU GPL v. 3.

L-Systems is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
 
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see
[http://www.gnu.org/licenses/](http://www.gnu.org/licenses/).