الخوارزميات البناءة واستخدامها في توليد النباتات

هل لاحظت مرة شكل الأشجار والأعشاب في الأفلام وألعاب الفيديو؟ هل استرعى انتباهك الكم الهائل من النباتات التي تبدو متشابهة إلا أنها غير متطابقة؟ هل فكرت كيف يمكن توليد هكذا محتوى بعدد كبير دون الحاجة ‏الماسة للتدخل ‏اليدوي؟

سنستعرض في هذا المقال الطريقة الأسهل والأكثر فاعليه واستخدام في تشكيل الأشجار والشجيرات. يطلق على هذه التقنية L-systems وهي نوع من القواعد التي يتم ترجمتها كتعليمات للرسم. إذا كنت قد سمعت عن نوع من التقنيات يدعى Fractal فإن هذه التقنية تعتبر الشكل الأعم لهذه الإجراءات.

قواعد التوليد:

تعتبر قواعد التوليد المكون الأساسي المعرف لهذه النظم كما أنها تحدد الشكل الناتج عند معالجة القواعد. سنتحدث عن القواعد من حيث استخدامها كقواعد توليد لإعادة كتابة جملة بدائية وتحويلها الى جملة أخرى. القواعد بشكلها البسيط تأخذ الشكل التالي:

A -> AB

B -> b

حيث يسمى كل من A,B رموز لانهائية بينما يعتبر b رمز نهائي. استخدام القواعد يعتبر عملية سهلة نسبيًا حيث يتم مسح القواعد واستبدال كل رمز لا نهائي يتم المرور به بمكافئة من الطرف الأيمن من القاعدة. مثلا إذا كانت العبارة المطلوب معالجتها تتكون من الرمز A فإن أول إجراء نقوم به هو استبدال الرمز A بما يقع على الطرف الأيمن ألا وهو AB. بتكرار العملية على نتيجة المرحلة الأولى نقوم باستبدال A بـ AB و B بـ b لنحصل على ABb. الاستبدال الثالث للعبارة الناتجة ABb بنفس طريقة يعطي ABbb وهكذا.

هناك طرق أخرى للقواعد ومعالجتها سنتحدث عنها فيما يلي.

أنواع القواعد وطرق معالجتها:

القواعد التي تم طرحها في المثال السابق تحوي  قاعدة واحدة يمكن تطبيقها لكل رمز لانهائي مما لا يترك مجالاً للاختيار أو الغموض. هناك أنواع أخرى من القواعد حيث يمكن إعادة كتابة بعض الرموز اللانهائيه بأكثر من طريقه كإمكانية استبدال الرمز A مثلاً إما بـ AB أو بـ Ab مما يؤدي إلى تفسير نفس القاعدة بطرق مختلفه تبعاً لتسلسل الاختيار و يعطي نتائج مختلفه تماماً. يطلق على هذا النوع من القواعد القواعد الغامضة  أو الغير محددة.

هناك عدة طرق لمعالجة وتفسير قواعد من هذا النوع يتم في بعضها اختيار احدى الخيارات المتاحة بشكل عشوائي. يتم في البعض الآخر استخدام عدد من المتحولات الداله على عدد مرات  أو احتمال استخدام كل خيار. هناك عدة استخدامات مهمة ومفيدة لمثل هذه القواعد مثل قابلية توليد أشكال متنوعة من نفس المجموعة من القواعد كما سنوضح في موضوع قادم.

 هناك وجه آخر من اختلاف القواعد يعتمد على طريقة تفسيرها. في بعض الحالات يتم معالجة العبارات باستبدال رمز واحد (الرمز النهائي الأول عند قراءة العبارة من اليسار) في كل عملية مسح. في المرحلة التالية يتم معالجة العبارة الناتجة عن المرحلة الأولى أيضاُ باستبدال الرمز الأول من اليسار وهكذا.

في طرق أخرى من المعالجة كما في المثال السابق تقوم عملية التفسير بإعادة كتابة العبارة كاملة خلال كل عملية مسح أي استبدال جميع الرموز الانهائية في العبارة الحالية. هذا ما يسمى ب المعالجة المتوازيه (parallel rewriting) وهي ما يميز نظم الـ L-systems.

نظم الـ L-systems:

تنسب نظم الـ L-systems للعالم البيولوجي Lindenmayor الذي طرحها للمرة الأولى أثناء دراسته للنمو في عالم النباتات. تتميز هذه النظم بشكل أساسي بعملية المعالجه المتوازيه للقواعد. النظام الاول الذي تم طرحه لهذه النظم يعتبر تمثيل لعملية النمو في الخمائر ويأخذ الشكل التالي:

A -> AB

B -> A

إذا حاولت إعادة كتابة هذه القواعد ابتداءً من العبارة A فإن النتيجه التي ستحصل عليها في المرة السادسه من المعالجه ستكون على الشكل ABAABABAABAAB (حاول بنفسك). لتسهيل عملية التفسير يمكنك استخدام التمثيل الشجري للقواعد كما في الشكل التالي:

l-stree
مثال عن طريقة لتفسير القواعد لعدد من المرات

إذا أمعنت النظر في هذه السلسلة ستجد عدة خصائص مميزة منها مثلاً أنها منتظمة بمعنى أن العبارة نفسها تتكرر عدد من المرات في نفس التفسير. أحد الخصائص الأخرى هي أنها تتمتع بخاصية سلاسل فيبوناتشي Fibonacci أي انه في أي مرحلة من مراحل التفسير تكون العبارة الناتجه عبارة عن دمج للعبارتين الناتجتين في المرحلتين السابقتين لها.

استخدم القواعد كتعليمات للرسم أو ما يدعى بـ Turtle Interpretation:

تعد سلاسل الـ l-system مفيدة لإنشاء رسوم ثنائية أو ثلاثية الأبعاد. يتم عادة استخدام الرموز كتعليمات لتحريك مؤشر يقوم بعملية الرسم تبعاً لنوع الرمز المقروء. الرموز المستخدمة عادة تفسر على أنها تعليمات للتحرك للأمام، الدوران 90 درجة إلي اليمين أو اليسار. في  هذه الحالات يتم استخدام الرموز التالية:

F: التحرك للأمام مسافة معينة

+: الدوران 90 درجة لليمين

 -: الدوران 90 درجة لليسار

لنأخذ المثال التالي المكون من قاعدة واحدة:

F -> F+F-F-F+F

إذا كانت العبارة البدائية التي يتم تفسيرها هي F فإن التفسير الثاني لها بنظم الـ l-system سينتج عنه:

F + F – F – F + F + F + F – F – F + F – F + F – F – F + F – F + F – F – F + F + F + F – F – F + F

 بتحويل مثل هذا التفسير و تفسيرات المراحل التالية كتعليمات للرسم كما أوضحنا سابقاً (قم باستبدال كل رمز بمكافئه من تعليمات الرسم السابقة) فإننا سنحصل على شكل هرمي يعرف بـ Koch curve وهو حالة خاصة من الأشكال ذات النمط المتكررة أو ما يعرف بـ Fractal.

لاحظ أنه في مثل هذه النظم يجب علينا أن نرسم الشكل بالكامل وفق التعليمات ”دون أن نرفع القلم على الورقة“  مما يعني أن الشكل يكون دائماً مستمر دون انقطاع باتجاه واحد.

هذه بعض الأمثلة الناتجة عن مثل هذه النظم:

kohen

رغم كون هذه النظم مفيده و فعالة في رسم عدد من الأشكال المتنوعة إلا أن خاصية الاستمرارية تجعلها غير قادرة على رسم كثير من الاشكال الأكثر تعقيدا وواقعية. لهذه الأسباب تم اختراع ما يعرف بـ  bracketed l-systems أو ما سنطلق عليه اسم النظام الممنطق.

:Bracketed L-systems النظم الممنطقة

ما يميز هذه النظم هو طرحها لرمزين جديدين هما ] و [ الذين يتم تفسيرهما كتعليمات دفع ] و سحب [ من مكدس (نوع معين من السلاسل حيث يتم إضافة وحذف عناصر من طرف واحد في مقدمة السلسلة). مع كل تعليمة سحب يتم إزالة العنصر في مقدمة المكدس. على الورق يتم إعادة القلم إلى المكان الذي بدأ رسم العصر عنده (دون مسح ما تم رسمه).  أي يتم فقط رفع القلم عن الورقة والعودة الى مكان سابق.

مثل هذه النظم أثبتت فعالية كبيرة في رسم أشكال تشبه الى حد كبير النباتات. إذا أخذنا كمثال النظام التالي مع إضافة رمزي الدفع والسحب:          [F -> F [-F] F [+F] [F

إذا قمنا بإعادة تعريف إشارات  + و ـ  لتشير إلى دوران بقيمة ٣٠ درجة وقمنا بإعادة تفسير العبارة لأربع مرات فإننا نحصل على الشكل التالي:

tree

حاول انت تجرب قيم أخرى للزوايا وقم بتعديل شكل قواعد ثم فسرها لعدة مراحل وستحصل على نتائج مبهرة أخرى تشبه في معظمها النباتات الشجيريه إلى حد كبير.

سنعرض بعض الأمثلة المأخوذة من كتاب (The Algorithmic Beauty of Plants) الذي يتحدث بالكامل عن هذه العبارات وخصائصها وكيفية استخدامها.

trees

إدخال بعض التعديلات على مثل هذه النظم يمكننا من توليد أشكال أكثر تعقيدا كالأشجار ذات النمو غير المنتظم. كما يمكننا أيضا من إضافة أزهار إلى نهايات الأفرع أو توليد أشكال ثلاثية الأبعاد.

الاستخدامات التطبيقية لنظم الـ L-systems:

يتم حاليا استخدام مثل هذه النظم بشكل كبير لتوليد المشاهد الطبيعيه في الأفلام والألعاب حيث تحوي بعض المشاهد على كم هائل من الأشجار الشجيرات والأعشاب التي لا يمكن توليدها بشكل يدوي مما يستدعي الحاجة الى أدوات للتوليد وطرق تمكن من التحكم بتعقيد وشكل واختلاف الأشكال المتولدة. تعتبر أداة Speed Tree مثال مستخدم بشكل كبير في الألعاب لتوليد مشاهد الغابات والمروج حيث توفر هذه الأداة واجهة سهلة للمصممين تمكنهم من إنشاء وتعديل عدد كبير من النباتات بوقت قصير نسبياً.

speedtree

أمثلة عملية:

إذا كنت ممن يحبون التجريب و الاكتشاف إليك بعض المواقع التي ستساعدك على توليد و تعديل نظم الـ l-systems. أدخل بعض القواعد و .استمتع برؤية الأشكال المعقدة الناتجة

المراجع:

  1. The Algorithmic  beauty of plants. P Prusinkiewicz, A Lindenmayer – 2012
  2. Grammars and L-systems with applications to vegetation and levels. Procedural Content Generation  in Games, a Textbook and an Overview of Current  Research.  Noor Shaker, Julian Togelius and Mark Nelson.

 

Advertisements

اترك رد

إملأ الحقول أدناه بالمعلومات المناسبة أو إضغط على إحدى الأيقونات لتسجيل الدخول:

WordPress.com Logo

أنت تعلق بإستخدام حساب WordPress.com. تسجيل خروج   / تغيير )

صورة تويتر

أنت تعلق بإستخدام حساب Twitter. تسجيل خروج   / تغيير )

Facebook photo

أنت تعلق بإستخدام حساب Facebook. تسجيل خروج   / تغيير )

Google+ photo

أنت تعلق بإستخدام حساب Google+. تسجيل خروج   / تغيير )

Connecting to %s