شبیه سازی حرکت گروهی پرندگان در پایتون (قسمت ۱)

(حوصله ندارم فقط کد ها رو نشونم بده!)

حتما برای شما هم پیش آمده است که محو تماشای حرکت پرندگان به خصوص در غروب آفتاب شوید. حرکت هایی به ظاهر نامنظم اما بسیار هماهنگ و زیبا! صدها و حتی هزاران پرنده همزمان مانند یک کل واحد در پهنه آسمان غلط می خورند و با اشکال گوناگونی که می سازند شگفتی می آفرینند!

اصلا شاید بهترین موقع برای بیرون آوردن دفترچه و نوشتن یک دل نوشته یا شعر شود! اما برای من قضیه فرق می کند من این بار لپ تابم را در می آورم تا سر از کار این الگو در بیاورم و اگر بشود آن را شبیه سازی کنم. به قول ریچارد فاینمن فیزیکدان نامی قرن بیستم:

What I can't create I don't understand

پس ما هم سعی میکنیم ابتدا کلیات آن را بفهمیم و بعد واقعا آن را درک کنیم.

هوش جمعی (Swarm Intelligence)

ورود به بحث هوش جمعی بسیار دشوار است و حتما در این مورد مطالب بیشتری قرار می دهم اما به صورت بسیار خلاصه می توان گفت قوانین معمولی که بر سیستم های کلاسیک با تعداد کمی از بازیگر (مثلا اجرام یا اشکال) در مورد سیستم های پیچیده با تعداد بسیار زیاد بازیگر صادق نیست. سیستم های کلاسیک قابل فهم عرفی هستند به این معنا که رفتار آن ها آن چیزی که است که انتظار می رود. اما سیستم های پیچیده با تعداد بسیار زیاد بازیگر و ارتباطات آن ها از فهم عرفی (common sense) تبعیت نمی کنند. تصور کلاسیک از سیستم پیچیده بر چندین فهم عرفی استوار است دو تای مهم آن ها عبارتند از:

۱- سیستم پیچیده باید قوانین پیچیده ای داشته باشد.

۲- سیستم پیچیده نیازمند ناظم (یا خالق) است که باید آن را هدایت و کنترل کند.

این دو فرض در بیشتر سیستم های پیچیده واقعی صادق نیست و اینجاست که همه چیز جالب تر می شود. اول اینکه سیستم های پیچیده گاه از قوانین بسیار ساده ای تبعیت می کنند. اما چگونه چنین سیستم هایی رفتارهای پیچیده از خود نشان می دهند؟ از طریق مکانیزم emergent!

از طرفی سیستم های پیچیده لزوما نیازی به ناظم ندارند این سیستم ها خود سازمانده (self-organization) هستند. دسته پرندگان یک مثال از آن است. برای مدت های مدید تصور می شد چیزی بسیار پیچیده در مورد حرکت این پرندگان وجود دارد شاید حتی خالقی در کار شکل دادن به آن است اما مطالعه رفتار چنین سیستمی نشان داد که می توان آن را به قوانین ساده ای شبیه سازی کرد و توضیح داد.
کریگ رینولدز ( Craig Reynolds ) سیستمی به اسم boids معرفی کرد که "زندگی مصنوعی" پرندگان را شبیه سازی می کرد. سه قاعده بر این "زندگی" حاکم است:

• جدایی (separation): طوری حرکت کن که از بخش شلوغ پرندگان اطرافت دور شوی!
• هم ترازی (alignment): طوری حرکت کن که به سمت جهت متوسط پرندگان اطرافت باشد!
• انسجام (cohesion): طوری حرکت کن که به سمت مکان متوسط (مرکز ثقل) پرندگان اطرافت باشد!

این قوانین ساده که همگی بر اساس یک تنظیم جهت محلی (پرندگان اطراف) هست منجر به الگوهای عجیبی می شود. مکانیزم complexity emergence باعث می شود چنین چیزی را شاهد باشیم. رینولدز شبیه سازی این مدل را انجام داد و هنوز بعد از سالها شبیه سازی بسیار زیبایی است.

پیاده سازی در پایتون

چون می خواهیم خروجی را مشاهده کنیم نیاز داریم که یک خروجی گرافیکی داشته باشیم. کتابخانه ای که من اینجا استفاده می کنم p5 هست که برای بسیار ساده و فوق العاده ست. کتابخانه اصلی در جاوا اسکریپت نوشته شده و می توانید از آن هم استفاده کنید(بدون نیاز به نصب چیزی و به صورت آنلاین).

در مورد استفاده از p5 در پایتون در یک مطلب جدا توضیح خواهم داد. اما اینجا فقط تاکید بر روی خود الگوریتم است. ابتدا p5 را نصب می کنیم:

pip install p5

ابتدا نیاز داریم که تعدادی نقطه به عنوان پرنده بسازیم. ما از اسم پرنده استفاده نمیکنیم بلکه از boid استفاده می کنیم که در مقاله اصلی استفاده شده. دلیل اصلی برای این کار این است که این رفتار فقط به پرنده ها محدود نمی شود شما برای ماهی ها و خیلی از موجودات دیگر هم چنین چیزی را مشاهده می کنید. برای این منظور یک کلاس می سازیم.

from p5 import *

class Boid():

    def __init__(self, x, y, width, height):
        self.position = Vector(x, y)

به صورت بسیار ساده اولین چیزی که انتظار داریم این است که هر بوید یک مکان داشته باشد. یک فایل دیگر به اسم main میسازیم که باید همه چیز را رسم کند. در p5 دو تابع اصلی داریم. تابع setup که در واقع آماده سازی بوم است و فقط یک بار اجرا می شود و تابع draw که در یک حلقه هر بار اجرا می شود و انیمیشن را می سازد.

from p5 import *
import numpy as np
from boid import Boid

width = 1000
height = 1000


def setup():
    #this happens just once
    size(width, height) #instead of create_canvas



def draw():
    #this happens every time
    background(30, 30, 47)

run()

اگر کد بالا را اجرا کنید باید یک بوم خالی ببینید. در setup تابع size فراخوانی می شود که یک بوم با اندازه داده شده ایجاد می شود و در draw هر بار رنگ پس زمینه به مقدار RGB داده شده تغییر می کند(که چون ثابت است شما یک بوم ثابت با رنگ آبی بسیار پر رنگ می بینید). run هم کل برنامه را اجرا می کند.

حالا می خواهیم یک مجموعه بوید (بدون حرکت) را بر روی بوم نقاشی کنیم. باید یک تابع نمایش به کلاس Boid اضافه کنیم.

def show(self):
    stroke(255)
    circle((self.position.x, self.position.y), radius=10)

تابع stroke رنگ قلم را تعیین می کند که اینجا سفید است و تابع circle یک دایره می کشد.(دایره برای هر بوید) با مکان و شعاع تعیین شده.

حالا به main بر می گردیم و از این کلاس ۳۰ بوید نمونه می گیریم و سپس در تابع draw آن را فراخوانی می کنیم.

from p5 import *
import numpy as np
from boid import Boid

width = 1000
height = 1000

flock = [Boid(*np.random.rand(2)*1000, width, height) for _ in range(30)]

def setup():
    #this happens just once
    size(width, height) #instead of create_canvas



def draw():
    #this happens every time
    background(30, 30, 47)

    for boid in flock:
        boid.show()


run()

دقت کنید که تابع random.rand نقاط را به صورت تصادفی ایجاد می کند. باید خروجی ای شبیه به زیر ببینید:

برای اینکه این بوید ها حرکت کنند باید سرعت برای آن ها تعریف کنیم. اگر فیزیک خوب یادتان باشد سرعت چیزی نیست جز یک بردار. خوشبختانه نیازی به پیاده سازی کلاس بردار نداریم. خود p5‌ دارای کلاس Vector هست. می توان این کار را برای شتاب هم انجام داد. اگر بخواهیم هر بوید سرعت و شتابی تصادفی داشته باشند آنگاه داریم:

class Boid():

    def __init__(self, x, y, width, height):
        self.position = Vector(x, y)
        vec = (np.random.rand(2) - 0.5)*10
        self.velocity = Vector(*vec)

        vec = (np.random.rand(2) - 0.5)/2
        self.acceleration = Vector(*vec) 

و یک تابع دیگر باید اضافه کنیم که مقادیر را بروزرسانی کند:

def update(self):
    self.position += self.velocity
    self.velocity += self.acceleration

پس در main برنامه باید این تابع را هم بعد از تابع show اضافه کنیم:

def draw():
    #this happens every time
    background(30, 30, 47)

    for boid in flock:
        boid.show()
        boid.update()

خروجی این مرحله بوید هایی هستند که به صورت تصادفی حرکت می کنند.

مشکل این است که این بوید ها به صورت تصادفی بعد از چند ثانیه از صفحه محو می شوند. بنابراین نیاز داریم که آن ها را همانجا نگه داریم! برای اینکار هر وقت بویدی از محدودیت صفحه خارج شد از آن طرف بر می گردانیمش. مثل اینکه تمام دنیای بوید ها همین صفحه است و چیزی خارج از آن نیست!

کافی است که تابع زیر را به کلاس boid اضافه کنیم:

def edges(self):
    if self.position.x > self.width:
        self.position.x = 0
    elif self.position.x < 0:
        self.position.x = self.width

    if self.position.y > self.height:
        self.position.y = 0
    elif self.position.y < 0:
        self.position.y = self.height

پس از اضافه کردن edges به تابع draw اصلی. نتیجه:

می بینید که بوید ها ابتدا آرام شروع می کنند اما بعد از مدتی دیوانه وار به اطراف حرکت می کنند. برای اینکه این رفتار را نرمال کنیم باید سرعت را نرمال کنیم یعنی یک حداکثر برای سرعت قایل شویم و پس از هر بار بروزرسانی شتاب را صفر کنیم. در کد زیر self.max_speed یک مقدار ثابت و برابر با ۵ است.

def update(self):
    self.position += self.velocity
    self.velocity += self.acceleration
    #limit
    if np.linalg.norm(self.velocity) > self.max_speed:
        self.velocity = self.velocity / np.linalg.norm(self.velocity) * self.max_speed

    self.acceleration = Vector(*np.zeros(2))

نتیجه می شود:

حالا وقت آن است که قانون های گفته شده را اعمال کرد. اولین قانون ساده هم ترازی alignment است.

می دانیم شتاب تغییر دهنده سرعت است. پس قاعدتا باید شتاب را تغییر دهیم. اما گفتیم که هر بوید فقط اطراف خود را می بینید پس باید فقط بوید هایی که در معرض دید هستند را در نظر بگیریم و میانگین جهت حرکت آن ها را پیدا کنیم و سپس در آن جهت حرکت کنیم.

در شکل بالا دایره بوید های محلی را نشان می دهد. جهت فعلی(self.velocity) بوید سبز با سبز نشان داده شده است. اما جهت متوسط همه بوید ها(avg_vec) آبی رنگ است. پس باید نیرویی (برداری) در جهت قرمز (steering) آن را جابجا کند. پس:

steering = avg_vec - self.velocity

def align(self, boids):
    steering = Vector(*np.zeros(2))
    total = 0
    avg_vec = Vector(*np.zeros(2))
    for boid in boids:
        if np.linalg.norm(boid.position - self.position) < self.perception:
            avg_vec += boid.velocity
            total += 1
    if total > 0:
        avg_vec /= total
        avg_vec = Vector(*avg_vec)
        avg_vec = (avg_vec /np.linalg.norm(avg_vec)) * self.max_speed
        steering = avg_vec - self.velocity

    return steering

دقت کنید در حلقه بر روی همه بوید ها فقط آنهایی که در فاصله self.perception هستند را در نظر می گیریم(فاصله اقلیدسی با linalg.norm محاسبه شده) و در نهایت اگر کسی در اطراف باشد(total>۰) آنگاه بردار متوسط را نرمال کرده(طوری که از مقدار self.max_speed بیشتر نشود) و جهت نیروی وارده را با تفاضل میانگین سرعت بوید های همسایه از سرعت فعلی بدست می آوریم.

از آنجایی که می خواهیم رفتار های دیگر را هم اضافه کنیم تابعی به اسم apply_behaviour می سازیم و آنجا رفتار ها را (سه قانون گفته شده را اعمال می کنیم) تا اینجای کار:

def apply_behaviour(self, boids):
    alignment = self.align(boids)
    self.acceleration += alignment

این تابع را به draw هم اضافه می کنیم پس:

def draw():
    #this happens every time
    background(30, 30, 47)

    for boid in flock:
        boid.show()
        boid.apply_behaviour(flock)
        boid.update()
        boid.edges()

از اینجا به بعد تغییری در draw نمی دهیم. (ترتیب تابع ها در draw مهم نیستند!). نتیجه به صورت زیر می شود:

تا همینجا هم می توان رفتار جالب و پیچیده ای را دید. بوید ها سعی میکنند در جهت گروه حرکت کنند!

در قسمت بعدی رفتار های جدایی و انسجام رو هم پیاده سازی می کنیم.