{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# L-systems\n",
    "Written by Jean-Luc Stevens<br>\n",
    "Last updated: August 3, 2021"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualizing Lindenmayer system\n",
    "\n",
    "<img src='assets/Fern-leaf-oliv.jpg' width='50%'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A [Lindenmayer system](https://en.wikipedia.org/wiki/L-system) or L-system is a mathematical system that can be used to describe growth process such as the growth of plants. Formally, it is a symbol expansion system whereby [rewrite rules](https://en.wikipedia.org/wiki/Rewriting) are applies iteratively to generate a longer string of symbols starting from a simple initial state. In this notebook, we will see how various types of fractal, including plant-like ones can be generated with L-systems and visualized with HoloViews."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import holoviews as hv\n",
    "from holoviews import opts\n",
    "import numpy as np\n",
    "hv.extension('bokeh')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook makes extensive use of the ``Path`` element and we will want to keep equal aspects and suppress the axes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "opts.defaults(opts.Path(xaxis=None, yaxis=None, show_title=False, color='black'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Some simple patterns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook, we will be drawing paths relative to an agent, in the spirit of [turtle graphics](https://en.wikipedia.org/wiki/Turtle_graphics). For this we define a simple agent class that has a ``path`` property to show us the path travelled from the point of initialization:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SimpleAgent(object):\n",
    "    \n",
    "    def __init__(self, x=0,y=0, heading=0):\n",
    "        self.x, self.y = x,y\n",
    "        self.heading = heading\n",
    "        self.trace = [(self.x, self.y)]\n",
    "        \n",
    "    def forward(self, distance):\n",
    "        self.x += np.cos(2*np.pi * self.heading/360.0)\n",
    "        self.y += np.sin(2*np.pi * self.heading/360.0)\n",
    "        self.trace.append((self.x,self.y))\n",
    "    \n",
    "    def rotate(self, angle):\n",
    "        self.heading += angle\n",
    "        \n",
    "    def back(self, distance):\n",
    "        self.heading += 180\n",
    "        self.forward(distance)\n",
    "        self.heading += 180\n",
    "        \n",
    "    @property\n",
    "    def path(self):\n",
    "        return hv.Path([self.trace])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now test our ``SimpleAgent`` by drawing some spirographs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pattern(angle= 5):\n",
    "    agent = SimpleAgent()\n",
    "    for i in range(360//angle):\n",
    "        for i in range(4):\n",
    "            agent.forward(1)\n",
    "            agent.rotate(90)\n",
    "        agent.rotate(angle)\n",
    "    return agent\n",
    "    \n",
    "(pattern(20).path + pattern(10).path + pattern(5).path\n",
    " + pattern(5).path * pattern(10).path * pattern(20).path).cols(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "We can also draw some pretty rose patterns, adapted from [these equations](http://www.mathcats.com/gallery/fiverosedetails.html):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def roses(l,n,k):\n",
    "    agent = SimpleAgent()\n",
    "    n * 10\n",
    "    x = (2.0 * k -n) / (2.0 * n)\n",
    "    for i in range(360*n):\n",
    "        agent.forward(l)\n",
    "        agent.rotate(i + x)\n",
    "    return agent\n",
    "\n",
    "roses(5, 7, 3).path + roses(5, 12, 5).path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Following rules"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now want to the capabilites of our agent with the ability to read instructions, telling it which path to follow. Let's define the meaning of the following symbols:\n",
    "\n",
    "**F**: Move forward by a pre-specified distance.<br>\n",
    "**B**: Move backwards by a pre-specified distance.<br>\n",
    "**+**: Rotate anti-clockwise by a pre-specified angle.<br>\n",
    "**-**: Rotate clockwise by a pre-specified angle.<br>\n",
    "\n",
    "Here is an agent class that can read strings of such symbols to draw the corresponding pattern:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Agent(SimpleAgent):\n",
    "    \"An upgraded agent that can follow some rules\"\n",
    "    \n",
    "    default_rules = {'F': lambda t,d,a: t.forward(d),\n",
    "                     'B': lambda t,d,a: t.back(d),\n",
    "                     '+': lambda t,d,a: t.rotate(-a),\n",
    "                     '-': lambda t,d,a: t.rotate(a)}\n",
    "    \n",
    "    def __init__(self, x=0,y=0, instructions=None, heading=0,  \n",
    "                 distance=5, angle=60, rules=default_rules):\n",
    "        super(Agent,self).__init__(x,y, heading)\n",
    "        self.distance = distance\n",
    "        self.angle = angle\n",
    "        self.rules = rules\n",
    "        if instructions: self.process(instructions, self.distance, self.angle)\n",
    "        \n",
    "    def process(self, instructions, distance, angle):\n",
    "        for i in instructions:          \n",
    "            self.rules[i](self, distance, angle)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defining L-Systems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L-systems are defined with a [rewrite system](https://en.wikipedia.org/wiki/Rewriting), making use of a set of [production rules](https://en.wikipedia.org/wiki/Production_(computer_science)).  What this means is that L-systems can generate instructions for our agent to follow, and therefore generate paths.\n",
    "\n",
    "Now we define the ``expand_rules`` function which can process some expansion rules to repeatedly substitute an initial set of symbols with new symbols:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def expand_rules(initial, iterations, productions):\n",
    "    \"Expand an initial symbol with the given production rules\"\n",
    "    expansion = initial\n",
    "    for i in range(iterations):\n",
    "        intermediate = \"\"\n",
    "        for ch in expansion:\n",
    "            intermediate = intermediate + productions.get(ch,ch)\n",
    "        expansion = intermediate\n",
    "    return expansion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Koch curve and snowflake"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To demonstrate ``expand_rules``, let's define two different rules:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "koch_curve = {'F':'F+F-F-F+F'}     # Replace 'F' with 'F+F-F-F+F'\n",
    "koch_snowflake = {'F':'F-F++F-F'}  # Replace 'F' with 'F-F++F-F'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are the first three steps using the first rule:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(3):\n",
    "    print('%d: %s' % (i, expand_rules('F', i, koch_curve)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that these are instructions our agent can follow!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k1 = Agent(-200, 0, expand_rules('F', 4, koch_curve), angle=90).path\n",
    "k2 = Agent(-200, 0, expand_rules('F', 4, koch_snowflake)).path\n",
    "(k1 + k2 + (k1 * k2)).opts(opts.Path(color=hv.Cycle()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This shows two variants of the [Koch snowflake](https://en.wikipedia.org/wiki/Koch_snowflake) where ``koch_curve`` is a variant that uses right angles."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sierpinski triangle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following example introduces a mutual relationship between two symbols, 'A' and 'B', instead of just the single symbol 'F' used above:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sierpinski_triangle = {'A':'B-A-B', 'B':'A+B+A'}\n",
    "for i in range(3):\n",
    "    print('%d: %s' % (i, expand_rules('A', i,sierpinski_triangle)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once again we can use these instructions to draw an interesting shape although we also need to define what these symbols mean to our agent:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sierpinski_rules = {'A': lambda t,d,a: t.forward(d),\n",
    "         'B': lambda t,d,a: t.forward(d),\n",
    "         '+': lambda t,d,a: t.rotate(-a),\n",
    "         '-': lambda t,d,a: t.rotate(a)}\n",
    "\n",
    "instructions = expand_rules('A', 9,sierpinski_triangle)\n",
    "Agent(x=-200, y=0, rules=sierpinski_rules, instructions=instructions, angle=60).path.opts(opts.Path(color='green'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that with our L-system expansion in terms of 'A' and 'B', we have defined the famous [Sierpinski_triangle](https://en.wikipedia.org/wiki/Sierpinski_triangle) fractal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Dragon curve"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now for another famous fractal:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dragon_curve = {'X':'X+YF+', 'Y':'-FX-Y'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now have two new symbols 'X' and 'Y' which we need to define in addition to 'F', '+' and '-' which we used before:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dragon_rules = dict(Agent.default_rules, X=lambda t,d,a: None, Y=lambda t,d,a: None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that 'X' and 'Y' don't actual do anything directly! These symbols are important in the expansion process but have no meaning to the agent. This time, let's use a ``HoloMap`` to view the expansion:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pad_extents(path):\n",
    "    \"Add 5% padding around the path\"\n",
    "    minx, maxx = path.range('x')\n",
    "    miny, maxy = path.range('y')\n",
    "    xpadding = ((maxx-minx) * 0.1)/2\n",
    "    ypadding = ((maxy-miny) * 0.1)/2\n",
    "    path.extents = (minx-xpadding, miny-ypadding, maxx+xpadding, maxy+ypadding)\n",
    "    return path\n",
    "    \n",
    "hmap = hv.HoloMap(kdims='Iteration')\n",
    "for i in range(7,17):\n",
    "    path = Agent(-200, 0, expand_rules('FX', i, dragon_curve), rules=dragon_rules, angle=90).path\n",
    "    hmap[i] = pad_extents(path)\n",
    "hmap.opts(framewise=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This fractal is known as the [Dragon Curve](https://en.wikipedia.org/wiki/Dragon_curve)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Plant fractals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have seen how to generate various fractals with L-systems, but we have not yet seen the plant-like fractals that L-systems are most famous for. This is because we can't draw a realistic plant with a single unbroken line: we need to be able to draw some part of the plant then jump back to an earlier state.\n",
    "\n",
    "This can be achieved by adding two new actions to our agent: ``push`` to record the current state of the agent and ``pop`` to pop back to the state of the last push:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class AgentWithState(Agent):\n",
    "    \"Stateful agent that can follow instructions\"\n",
    "    \n",
    "    def __init__(self, x,y, instructions, **kwargs):\n",
    "        super(AgentWithState, self).__init__(x=x,y=y, instructions=None, **kwargs)\n",
    "        self.traces = []\n",
    "        self.state = []\n",
    "        self.process(instructions, self.distance, self.angle)\n",
    "        \n",
    "    def push(self):\n",
    "        self.traces.append(self.trace[:])\n",
    "        self.state.append((self.heading, self.x, self.y))\n",
    "        \n",
    "    def pop(self):\n",
    "        self.traces.append(self.trace[:])\n",
    "        [self.heading, self.x, self.y] = self.state.pop()\n",
    "        self.trace = [(self.x, self.y)]\n",
    "        \n",
    "    @property\n",
    "    def path(self):\n",
    "        traces = self.traces + [self.trace]\n",
    "        return hv.Path(traces)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at the first three expansions of a new ruleset we will use to generate a plant-like fractal:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plant_fractal = {'X':'F-[[X]+X]+F[+FX]-X', 'F':'FF'}\n",
    "for i in range(3):\n",
    "    print('%d: %s' % (i, expand_rules('X', i, plant_fractal)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The new symbols '[' and ']' correspond to the new push and pop state actions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plant_rules = dict(Agent.default_rules, X=lambda t,d,a: None, \n",
    "                   **{'[': lambda t,d,a: t.push(), ']': lambda t,d,a: t.pop()})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now generate a nice plant-like fractal:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hmap = hv.HoloMap(kdims='Iteration')\n",
    "for i in range(7):\n",
    "    instructions = expand_rules('X', i, plant_fractal)\n",
    "    if i > 2:\n",
    "        hmap[i] = AgentWithState(-200, 0, instructions, heading=90, rules=plant_rules, angle=25).path\n",
    "hmap.opts(opts.Path(framewise=True, color='g', line_width=1))"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}