ارسم بالنمل: صور إجرائية باستخدام خوارزميات تحسين مستعمرة النمل

لماذا أردت أن أرسم مع النمل

أردت إنشاء عمل فني لاستكشاف مدى تعقيد تصميم البرمجيات. عندما أقدم قاعدة رموز ضخمة ، أفكر في تعقيدها الناشئ بشكل مستقل وأجزائه المتشابكة والمترابطة. ينشأ شكله العام ، إذا جاز التعبير ، من تصرفات العديد من الشخصيات الفردية.

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

مخطط الفورميكاريا. المصدر: ويكيميديا ​​كومنز .

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

وبسبب هذا ، بدأت البحث مرة أخرى ، وقادوني إلى فئة مختلفة تمامًا من محاكاة النملة:خوارزميات تحسين مستعمرة النمل (خوارزميات مستعمرة النمل) .

تحسين مستعمرة النمل هو خوارزمية وكيل تستخدم لحل مشكلة العثور على أقصر مسار بين نقطتين من الرسم البياني. يعني "الوكيل" أن الخوارزمية تتكون من إجراءات منفصلة (في هذه الحالة ، "النمل") ، والسلوك الناشئ الذي يحل المشكلة.

يعمل ببساطة شديدة. كل نملة تترك أثرًا لـ "الفيرومونات" في طريقها. يترك النمل نوعًا واحدًا من الفيرومون بعد مغادرة النمل والآخر عندما يجدون الطعام. يسعى النمل الباحثين عن الطعام إلى العثور على أثر فرمون "الطعام" ، بينما يسعى أولئك الذين يسعون إلى صيد النمل إلى تتبع فرمون "المنزل".

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

محاكاة

لقد كتبت محاكي النمل الخاص بي في المعالجة 3. لقد بدأت التنفيذ الخاص بي من خلال محاكاة الرمز من هذا المنشور المذهل بواسطة غريغوري براون .

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

هنا يمكنك لعب منفذ المحاكاة على p5.js مباشرة في متصفحك!

يمكنك أيضًا إلقاء نظرة على شفرة المصدر المنقولة على Github.

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

تحويل النمل إلى فن

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

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

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

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

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

الربط بين النقاط

كنت أعلم أنني أرغب في رسم نمل يسافر بين عدة نقاط ، لذلك كان رمز ربط العديد من المحاكاة في صورة واحدة هو الأول. ولكن ما الذي يجب أن أرسمه؟

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

كنت بالفعل على دراية بـ Graphviz ، لذلك قررت استخدام مجموعة الأدوات هذه ولغة وصف الرسم البياني لـ DOTلتحديد عقد وحواف المحاكاة. يحتوي Graphviz على وضع يقوم بإخراج ملف DOT مع تعليقات توضيحية لإحداثيات البكسل. لقد كتبت محلل ملف DOT قبيح جدًا واستخدمته مع ملف DOT المشروح لمحاكاة مواقع عش النمل والطعام.

بدت التجارب مع الأشجار الثنائية واعدة وأعطت مظهرًا طبيعيًا وعضويًا للغاية.

شجرة ثنائية بسيطة. قيل لي أنه مثل تصوير الأوعية الدموية.

شجرة أكثر تعقيدًا قليلاً ، بالفعل عميقة جدًا.

ثم بدأت في إنشاء المزيد من الرسوم البيانية باستخدام قواعد التعليمات البرمجية المختلفة كمدخلات. كتبت بعض البرامج النصية البسيطة في Python: قام أحدهم بتحويل شجرة git إلى ملف DOT ، والآخر حول تبعيات استيراد C إلى ملف DOT.

رسم بياني للكائنات في شجرة كائن git المرسومة بواسطة النمل.

التبعيات بين الملفات في نواة لينكس. تم إنشاء العقد والحواف باستخدام النمط المربّع للرسوم البيانية Graphviz. في الواقع ، ليس أكثر إثارة للاهتمام من الرسوم البيانية العشوائية.

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

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

النقاط في المقطع ، على الجانب الأيمن من المقطع ، النقاط أقرب لبعضها البعض.

ترددات موجات جيبية مختلفة. أفترض أن الذبذبات الجيدة ستخرج من النمل.

بدا لي أن أبسط المساحات المثلثة هي الأكثر إثارة للاهتمام. لقد ولدت العديد من النقاط الموزعة بالتساوي - إما بشكل عشوائي أو عن طريق رسم الأشكال - ثم استخدمت مكتبة المعالجة لتحويل هذه النقاط إلى تثليث Delaunay أو مخطط Voronoi. ثم تم استخدام الأضلاع الناتجة لمحاكاة النمل ، حيث يشير كل ضلع إلى "تلة نملة" أو "طعام".

رسمها النمل Voronoi الرسم التخطيطي.

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

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

ممرات النمل تحاول حل متاهة بسيطة. يمكنك أن ترى شكل المتاهة من خلال ملاحظة أين لا يمكن للنمل أن يذهب.

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

عمل فني منتهي

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

تشغيل المحاكاة المكتملة. يحتوي على العديد من المسارات المتراكبة التي يتم الحصول منها على البقع المشوشة.

كانت القضية الأخيرة هي كيفية تحويل انحناءات SVG إلى عمل منتهي. من خلال التجارب ، كنت أعرف أنني أردت فرز المسارات بطريقة ما لإبراز المسارات بشكل جميل. لكن تشغيل المحاكاة النهائية استغرق من ساعة إلى ساعتين ، ولهذا السبب كان من غير المناسب تغيير المتغيرات في كل تشغيل من التجربة.

قررت كتابة رسم تخطيطي ثانٍ للمعالجة يقوم بتحميل مخرجات المحاكاة في SVG ثم تطبيق المؤثرات البصرية التي أحتاجها. علاوة على ذلك ، أردت أن أجعل النص البرمجي لما بعد المعالجة تفاعليًا حتى أتمكن من تجربة الأوزان والألوان المختلفة للخطوط ، بالإضافة إلى عتبات الفرز.

لقد جربت عدة طرق مختلفة لتقييم المسارات التي يجب أن تكون في المقدمة وفي الخلفية. تم حساب عدة عوامل مختلفة: عدد التقاطعات الذاتية للخط ، وعدد التقاطعات حسب خط المنحدر ، واحتمال أن يتبع الخط المنحدر الذي توقعته النقطتان السابقتان.

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

إعداد العتبة للخطوط الأمامية والخلفية.

عند هذه النقطة ، ساعد حفظ الصورة عند تغيير كل متغير كثيرًا. عندما اقتربت من الصورة التي أحتاجها ، كان من الأسهل بكثير مقارنة عدد من الاختلافات الطفيفة مقارنة بتغيير عدة عوامل في كل مرة.

بعد إعداد طويل وإجراء تغييرات بسيطة ، قمت بإنشاء الصورة التالية من محاكاة الخاص بي:

قمت بتكبير المنطقة التي بدت أكثر إثارة للاهتمام بالنسبة لي ، وقمت بقصها لخلق توازن جيد بين المساحة الفارغة والمملوءة.

كانت الخطوة الأخيرة هي اختيار كيفية تحويل هذه الصورة إلى كائن مادي. اعتدت على طباعتها رقميًا على شكل ملصق مقاس 40 × 50 سم وحاولت (دون جدوى) طباعة الشاشة على ورق ملون. يبدو الملصق المطبوع رقميًا رائعًا ، ولكن في المستقبل أريد نسخ الصورة كجزء من الصورة. أجد رسومات معقدة تأملية وأعتقد أنه يمكنني تحقيق تأثيرات مثيرة للاهتمام عن طريق رسمها يدويًا.

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

Source: https://habr.com/ru/post/undefined/