From a72b74f5a63e10fc78061500e51ccb15c20eabfe Mon Sep 17 00:00:00 2001
From: Nick Gasson <nick@nickg.me.uk>
Date: Sat, 16 Jan 2010 12:30:57 +0000
Subject: [PATCH] Basic L-system generation

---
 src/LTree.cpp     | 96 +++++++++++++++++++++++++++++++++++++++++++++++
 src/LTreeDemo.cpp | 10 ++++-
 2 files changed, 104 insertions(+), 2 deletions(-)

diff --git a/src/LTree.cpp b/src/LTree.cpp
index d54ad02..a9baa2c 100644
--- a/src/LTree.cpp
+++ b/src/LTree.cpp
@@ -16,6 +16,90 @@
 //
 
 #include "IScenery.hpp"
+#include "ILogger.hpp"
+
+#include <list>
+#include <vector>
+#include <ostream>
+#include <iterator>
+
+namespace lsystem {
+
+   enum Token {
+      X = 'X',   // Only used for replacement
+      F = 'F',   // Draw forward
+      L = 'L',   // Turn left N degrees
+      R = 'R',   // Turn right N degrees
+   };
+
+   typedef list<Token> TokenList;
+
+   struct Rule {
+      Rule(Token lhs, const TokenList& rhs)
+         : lhs(lhs), rhs(rhs)
+      {}
+
+      Rule(Token lhs, const char* tokenStr);
+
+      Token lhs;
+      TokenList rhs;
+   };
+
+   struct LSystem {
+      LSystem(const Rule* rules, int nRules, Token start);
+
+      const Rule* rules;
+      int nRules;
+      Token start;
+      TokenList state;
+   };
+
+   void evolve(LSystem& l);      
+
+   ostream& operator<<(ostream& os, const LSystem& l)
+   {
+      copy(l.state.begin(), l.state.end(),
+         ostream_iterator<char>(os));
+      return os;
+   }
+   
+}
+
+lsystem::Rule::Rule(Token lhs, const char* tokenStr)
+   : lhs(lhs)
+{
+   while (*tokenStr)
+      rhs.push_back((Token)*tokenStr++);
+}
+
+
+lsystem::LSystem::LSystem(const Rule* rules, int nRules, Token start)
+   : rules(rules), nRules(nRules), start(start)
+{
+   state.push_back(start);
+}
+
+void lsystem::evolve(LSystem& l)
+{
+   TokenList::iterator it = l.state.begin();
+   do {
+      bool replaced = false;
+      for (int r = 0; r < l.nRules; r++) {
+         if (l.rules[r].lhs == *it) {
+            l.state.insert(it, l.rules[r].rhs.begin(),
+               l.rules[r].rhs.end());
+            replaced = true;
+            break;
+         }
+      }
+
+      if (replaced)
+         it = l.state.erase(it);
+      else
+         ++it;
+            
+   } while (it != l.state.end());
+}
 
 // Trees generated by L-systems
 class LTree : public IScenery {
@@ -30,7 +114,19 @@ private:
 
 LTree::LTree()
 {
+   using namespace lsystem;
+   
+   Rule rules[] = {
+      Rule(X, "F-[[X]+X]+F[+FX]-X"),
+      Rule(F, "FF"),
+   };
+   LSystem l(rules, 2, X);
 
+   debug() << "Initial: " << l;
+   for (int n = 0; n < 5; n++) {
+      evolve(l);
+      debug() << "n=" << n << ": " << l;
+   }
 }
 
 void LTree::render() const
diff --git a/src/LTreeDemo.cpp b/src/LTreeDemo.cpp
index 363a09e..da40114 100644
--- a/src/LTreeDemo.cpp
+++ b/src/LTreeDemo.cpp
@@ -17,13 +17,14 @@
 
 #include "IScreen.hpp"
 #include "ILogger.hpp"
+#include "IScenery.hpp"
 
 class LTreeDemo : public IScreen {
 public:
    LTreeDemo();
 
    // IScreen interface
-   void display(IGraphicsPtr aContext) const {}
+   void display(IGraphicsPtr context) const;
    void overlay() const;
    void update(IPickBufferPtr aPickBuffer, int aDelta) {}
    void onKeyDown(SDLKey aKey) {}
@@ -40,7 +41,12 @@ private:
 
 LTreeDemo::LTreeDemo()
 {
-   
+   makeLTree();
+}
+
+void LTreeDemo::display(IGraphicsPtr context) const
+{
+
 }
 
 void LTreeDemo::overlay() const
-- 
2.39.2