۱. "به نام خدا"

۲. مقدمه

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

یک جمعیت ¹ را به تعداد زیادی موجودیت که به شکل فیزیکی با هم یک گروه را تشکیل داده اند، نسبت می دهند. این گروه رفتارهای خاصی دارد که با رفتارهای معمولی اعضا به صورت فردی متفاوت می باشد چرا که آن ها عضو یک جمعیت هستند و این جمعیت رفتارهای خاصی را به اعضا تحمیل می کند. شبیه سازی این رفتار مبتنی بر جمعیت را ، Crowd Simulation و یا شبیه سازی رفتار جمعیت ، به اختصار CS می نامند.

به عنوان مثال گروهی از غازها هنگام مهاجرت را درنظر بگیرید، هرکدام از غاز ها وظیفه دارد در عین حفظ فاصله با دیگران و عدم برخورد با آن ها، ویژگی گروه را حفظ کند و با دیگران پرواز کند. می بینید که گروه غازها رفتار های خاصی را به هر غاز تحمیل میکند در صورتی که گروهی وجود نداشت ، این محدودیت ها برای غاز ها نیز وجود نداشت.

۳. کاربردها

شبیه سازی جمعیت کاربردهای بسیار وسیعی دارد که در زیر به چند نمونه اشاره میکنیم :

• شبیه سازی زندگی مردم یک شهر وسیع به طوری که بتوانند نیاز های خود را تامین کنند.فرض کنید صبح، همه مردم از خواب بیدار شوند، به سر کار روند ، بچه ها به همراه مادرشان به مدرسه روند و درشب بعد از رفتن به رستوران و خوردن شام ،به خانه رفته و استراحت کنند. بله، تردید نکینید این چیزی است که در بازی ها استفاده میشود به عنوان مثال بازی GTA ، Hitman و یا Assassins Creed که دارای یک نقشه بزرگ می باشند، برای مدیرت جمعیت از این سیستم ها استفاده می کنند. دانستن این نکته الزامی است که نمی توان با انیمیشن های از پیش ساخته شده و ثابت، این جمعیت بزرگ را مدیرت کرد !! علاوه بر بحث کارایی، بحث واقع گرایی نیر مطرح می باشد که گروه، رفتار های تکراری و قابل پیشبینی از خود نشان ندهد.در بازی Assassins Creed وقتی شما در داخل شهر برای فرار از دست مامورین حکومتی پا به فرار میگذارید، عکس العمل مردم شهر در قبال رفتار شما بی نظیر می باشد. تلاش آن ها برای جلوگیری از برخورد با شما و رفتار آن ها بعد از برخود قابل تحسین است.

• شبیه سازی در پروژه های ساختمانی فرض کنید قرار است یک ورزشگاه صد هزار نفری ساخته شود!، یکی از عامل هایی که در طراحی این ورزشکاه مهم است، مدیرت ازدحام جمعیت، هنگام ورود و خروج به ورزشگاه می باشدکه می توان با شبیه سازی ورزشگاه و جمعیت،طراحی را مورد ارزیابی قرار داد تا هزینه ها به شکل قابل قبولی کاهش یابند.

۴. کارهای مرتبط

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

• 1- "اجتناب از برخورد دور بورد ترکیبی" ²
  چکیده:
  الگوریتم های جلوگیری از برخورد محلی که فقط به همسایه های نزدیک توجه می کند اغلب همسایه هایی که کمی فاصله دارند ولی به زودی تاثیر می گذارند رو مورد توجه قرار نمی دهد .
  علاوه بر این برای پیاده سازی این الگوریتم ها نیاز به دانش در مورد تعداد و چگالی جمعیت می باشد زیرا برای جمعیت های کم و با چگالی پایین حتما باید به شکل گسسته مدل شوند و برای جمعیت های زیاد و چگال باید از مدل پیوسته استفاده شود. با استفاده از روش ترکیبی به شکل کارا میتوانیم هر جمعیتی را با هر چگالی مدل کرده و مدل به شکل غیر متناهی بین گسسته و پیوسته تغییر حالت می دهد
  مقدمه :
  بر اساس مفهوم look ahead حالت های آینده ی عامل به وسیله اطلاعات گذشته و حال تخمین زده می شود . و از این نکته برای مدل کردن برخورد با عامل هایی که در الگوریتم محلی در نظر گرفته نمی شود ، یعنی عامل هایی که در دایره دید محلی ما نیستند. استفاده می شود.الگوریتم های جلوگیری از برخورد را به طور کلی می توان بر بر اساس نحوه مدل سازی جمعیت به دو دسته گسسته و پیوسته تقسیم کرد.
  هدف :
  ارائه راه حلی برای تخمین جلوگیری از برخورد دور بورد که بتوان هم در مدل پیوسته و هم در مدل گسسته با حد اقل هزینه های محاسباتی استفاده شود.
  نحوه کار:
  در این مقاله بعد از بررسی کلی مشکل و بیان کلی راه حل، الگوریتم کلی حل این گونه مسائل را آورده است:
  1) برای هر عامل global planning را اجرا میکنیم تا یک مسیر به هدف به طوری که به موانع ثابت برخورد نکند پیدا کنیم در این جا سرعت دلخواه vp بدست میاید.
  2) برای هر عامل local collision avoidness را اجرا کن تا v_{p} را از برخورد با عامل های دیگر دور کند . کاری که انجام شده است در این قسمت است و این الگوریتم را به شکلی که عامل های دور تر نیز در نطر بگیرد توسعه میدهد:

Foreach leaf node p

Foreach level i in range i_{max} to 0 DO

1) Determine future state of crowd x_{i}=x_{i}+v_{c}+∆t_{i}
2) v=A(v_{p},v_{c},x_{i},ρ_{i}) Solve local collision avoidance problem
3) Update Preferred Velocity v_{p}=v

که v_{p} همان سرعت دلخواه است که از تابع global planning بدست می آید و به این معنی است که اگر هیچ عاملی وجود نداشت، عامل همواره با این سرعت به سمت مقصد حرکت می کرد. در ضمن برای بدست آوردن ∆t از فرمول زیر استفاده میکنیم :

∆t_{i}=2^{(i-1)} ∆t ,i>0,∆t_{0}=0

در تصویر زیر این مطلب کمی واضح تر بیان شده است:

• 2- "شخصی سازی رفتاری جمعیت"[مرجع 1]

اجازه دهید این مقاله را به شکل خلاصه تری بررسی نماییم در این مقاله سعی شده است تا بر اساس مدل های شخصی سازی موجود، رفتار جمعیت را بهتر نماید.
یکی از این مدل ها ، مدل PEN ( مرجع شماره 5) می باشد. این مدل محدوده تنوع شخصیت ها را ارزیابی میکند . همچنین این مدل بر پایه علوم زیستی و روانشناسی بنا شده است. بنابر این ؛این مقاله با ترکیب علوم فنی، زیستی و انسانی اقدامات جالبی را انجام داده است. در حقیقت این مقاله سعی دارد یک نگاشت بین پارامتر های سطح پایین و مصنوعی شبیه سازی جمعیت و پارامتر های سطح بالا و طبیعی و کاملا پیچیده رفتاری ایجاد کند. این پارامتر ها شخصیت عامل را به گونه های زیر به طوری ترکیبی ایجاد میکند.

1) پرخاشگر³
2) خجالتی⁴
3) متشنج⁵
4) جسور⁶
5) فعال⁷
6) با انگیزه⁸
سپس با تخصیص پارامتر های شبیه سازی جمعیت بر اساس نوع شخصیت عامل ، کار را ادامه میدهد. پارامتر هایی که در این مقاله نگاشت شده اند از قرار زیرند

• سرعت ترجیحی هر فرد ( v_{p})

• دایره فعالیت هر فرد ( این که هر عامل چه قدر از عامل های دیگر دور میشود)

• حداکثر تعداد همسایگانی که رفتار محلی یک عامل را تحت تاثیر قرار میدهند.

• حداکثر فاصله تا همسایگانی که روی عامل تاثیر گذارند و

• میزانی بلندای طرح ریزی یک عامل

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

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

۵. دید کلی برای پیاده سازی

همان طور که میدانید دامنه CS بسیار گسترده می باشد به طوری که به هیچ وجه در یک پروژه چند ماهه نمی توان تمامی جنبه های آن را بررسی کرد.
جلوگیری از برخورد⁹ یا به اختصار CA یکی از پایه ای ترین بخش های شبیه سازی جمعیت می باشد چرا که تمام دیدگاه ها و کاربردهای CS چه در بازی های رایانه ای و چه در زمینه های دیگر نیازمند هوشمندی عامل ها در برخورد و حرکت به سمت یکدیگر می باشد.
برای این منظور ما در صدد رسیدن به یک سیستم برای شبیه سازی خروج انبوه یک جمعیت از یک فروشگاه یا ورزشگاه می باشیم. وسعت فروشگاه ، تعداد درب خروجی، میزان هجوم مردم برای خروج در موقعیت های معمولی و یا اضطراری ( مانند آتش سوزی) و ... پارامتر هایی است که می تواند مورد تحقیق و آزمایش قرار گیرد.

روش های پیاده سازی CS را میتوان در مدت زمان شبیه سازی و میزان جمعیت مورد ارزیابی، تقسیم بندی کرد.
در این پروژه ابتدا ساده ترین روش ها پیاده سازی می شود و نتایج آن به ثبت می رسد و به مرور با پیچیده تر کردن شرایط، و بهبود الگوریتم های مربوط به CA تا حدی نتایج شبیه سازی را بهبود می بخشیم.

روش "اجتناب از برخورد دور بورد ترکیبی" روشی است که علاوه بر کارایی خوب، بسیار واقع گرایانه عمل می کند.
در این روش علاوه بر درنظر گرفتن همسایه های محلی، به همسایه های دور بورد نیز توجه خاصی می شود که همین عامل باعث می شود، عامل ها رفتار یکدیگر را پیشبینی کنند و قبل از نردیک شدن بیش از حد و به وجود آمدن برخورد های شدید که باعث کاهش سرعت حرکت و نرخ فریم بازی می شود، رفتاری مناسب برای عبور از کنار یکدیگر نشان دهند.

در پایان رفتار جمعیت را با استفاده از تئوری Personality Trait شخصی سازی می کنیم
به طوریکه ابتدا تمامی آدم ها دقیقا مانند یکدییگر هستند ( روحی ، جسمی و ... ) و به مرور زمان این جمعیت شخصی سازی شده و جنبه های مختلف روحی از جمله میزان پرخاشگری، جسارت، میزان فعال بودن و ... را در پارامتر های شبیه سازی دخالت می دهیم و یک نگاشت ما بین آن ها ایجاد می کنیم
و نشان میدهیم که این اختلاف رفتار باعث همگونی بهتر رفتار جمعیت می شود و در حالت میانگین، عملکرد بسیار بهتری را از خود به جای می گذارد.
به امید خدا تمامی پروسه پیاده سازی این تحقیق در موتور یونیتی اجرا میشود که در آخر می تواند یک افزونه خوب برای این موتور به حساب آید و در بازی های رایانه ای مورد استفاده قرار گیرد.

۶. پیاده سازی

تا مطاعات و تحقیقات فراوانی که بر روی شبیه سازی جمعیت انجام شد. از این مرحله همانطور که قرار مان بود به سراغ موتور بازی سازی یونیتی رفتیم تا بررسی کنیم که این موتور چه چیزهایی را در اختیار ما قرار می دهد تا بتوانیم هرچه بهتر رفتار یک جمعیت را شبیه سازی کنیم. همانطور که قبلا گفتیم برای شبیه سازی یک جمعیت به دو قسمت عمده نیاز داریم.
1) Global plannig برای بدست آوردن v_{p}
2) حل کردن یک مسئله ی اجتناب از برخورد محلی با عامل های دیگر

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

۶.۱. تحقیقات و آزمایشات

۶.۱.۱. مسئله ی Global plannig

برای شروع کار و ایجاد عامل ها ابتدا باید محیط جدول بندی بشود. چرا که تمامی الگوریتم های حرکتی و مسیر یابی آگاهانه از جمله A^* نیازمند جدولی از راه های قابل تردد و غیر قابل تردد می باشد.
در موتور یونیتی برای این کار قابلیتی در نظر نگرفته شده است، اما به جای آن از یک قابلیت بهتر که در بازی های رایانه ای کار برد بسیار بیشتری دارد استفاده شده است. این ویژگی امکان ساخت شبکه ناوبری ¹⁰ می باشد. این شبکه این امکان را به عامل میدهد که مکان هایی از نقشه که قابلیت تردد دارد را از آن هایی که این ویژگی را ندارد تشخیص دهد و بنابراین بتواند بهترین مسیر را انتخاب کند.

همان طور که در تصویر بالا می بینید شبکه ناوبری ساخته شده درون یک ساختمان ، مسیر های قابل حرکت و اصطلاحاً " قابل قدم" ¹¹ با رنگ آبی نشان داده شده است. اجازه دهید در مورد چگونگی ساخت این شبکه صحبتی نکنیم و از آن عبور کنیم. استودیو بازی سازی Valve در سایت خود مقاله ای را در این مورد قرار داده است که اگر علاقه داشتید میتوانید به این صفحه رجوع کنید.

از میان الگوریتم های مسیریابی موتور یونتی از الگوریتم A^* استفاده میکند و بعد از مشخص شدن هدف، این الگوریتم به کمک مش ناوبری بهترین مسیر را پیدا میکند.
تا این جای کار ما توانستیم یک عامل ایجاد و با مشخص کردن هدف برای آن، شاهد حرکت هوشمند وی به طرف هدف با شیم. این اقدامات به وسیله کلاسی به عنوانNavMeshAgent قابل پیاده سازی می باشد.
حال به ساخت موانع در موتور میرسیم. سوال این جاست که چگونه باید عامل را متوجه این موانع ( ثابت و متحرک ) کرد؟ ¹² . بعد از تحقیقاتی که انجام دادیم دریافتیم که ورژن های قدیمی موتور یونیتی ( تا شماره 4 ) امکان داشتن موانع متحرک در هنگام اجرای بازی را نداشته است. در حقیقت باید تمامی اشیائی که میخواهیم عامل متوجه آن ها باشد که به آن ها برخورد نکند و در مسیریابی آن ها را در نظر بگیرد؛ را قبل از اجرای بازی و هنگام ساخت شبکه ناوبری به عنوان جسم ثابت ¹³ به موتور معرفی کنیم. در این صورت تغییر مکان و تخریب این موانع، در حال اجرای بازی ، هیچ تاثیری بر رفتار عامل ندارد.
اما خوشبختانه از ورژن 4 به بعد، یونتی این امکان را برای ما فراهم میکند که علاوه بر ویژگی های قبلی ، قادر خواهیم بود که اشیاء را در حال اجرای بازی ¹⁴ به روز رسانی کنیم ( تخریب و یا تغییر مکانی و یا زاویه ای ) . این امکان به کمک کلاسی به نام NavMeshObstacle قابل پیاده سازی می باشد.

۶.۱.۲. مسئله ی اجتناب از برخورد محلی با عامل های دیگر

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

برای درک کامل این موضوع این آزمایش را بترتیب برای 50، 100، 200 و 400 عامل انجام و مدت زمانی که طول میکشد تا هرکدام از گروه ها به طور کامل از یک دیگر عبور کنند را اندازه گرفتیم. نمودار زیر این مسئله را بیان میکند. همچنین میتوانید فیلم کامل 400 عامل را از این قسمت در یافت نمایید.

۶.۲. بهینه سازی و آزمایشات

همانطور که مشاهده فرمودید . تا این جای کار بسیار خوب پیش رفتیم. اما شاید کافی نباشد. برای همین ما به دنبال راه حل هایی رفتیم تا نتایج بدست آمده در این قسمت را بهبود بخشیم. در بخش دوم کارهای مرتبط به نظریه شخصی سازی آشنا شدیم. نظریه ای که برای هر عامل شخصیتی متفاوت در نظر می گیرد. و در آن مقاله اظهار داشتند که این کار موجب بهبود عملکرد جمعی جمعیت می باشد. همان طور که مطالعه فرمودید در آن مقاله شخصیت هر فرد پارامتر های مهمی را در شبیه سازی تحت تاثیر قرار می دهد. این پارامتر ها عبارتند از :
1) سرعت ترجیحی هر فرد ( v_{p})
2)دایره فعالیت هر فرد ( این که هر عامل چه قدر از عامل های دیگر دور میشود)
3) حداکثر تعداد همسایگانی که رفتار محلی یک عامل را تحت تاثیر قرار میدهند.
4) حداکثر فاصله تا همسایگانی که روی عامل تاثیر گذارند و
5) میزانی بلندای طرح ریزی یک عامل
با توجه به این نکات به دنبال پارامتر های مشابه در موتور یونیتی گشته و پارامتر های زیر را از کلاس NavMeshAgent استخراج کردیم:

1)دایره فعالیت هر فرد ( این که هر عامل چه قدر از عامل های دیگر دور میشود) :

NavMeshAgent.radius

2) شتاب حرکت هر عامل :

NavMeshAgent.acceleration

3) حداکثر سرعت حرکت هر عامل :

NavMeshAgent.speed

4) سرعت زاویه ای :

NavMeshAgent.angularSpeed

5) اولویت دراجتناب از برخورد :

NavMeshAgent.avoidancePriority

6) میزان دقت در اجتناب از برخورد :

NavMeshAgent.obstacleAvoidanceType

حال، کار بعدی ما بررسی و آزمایش این پارامتر ها خواهد بود برای این که بتوانیم عملکرد جمعیت خود را بهبود بخشیم.

۷. مراجع

• Stephen J. Guy†, Sujeong Kim, Ming C. Lin, Dinesh Manocha: Simulating Heterogeneous Crowd BehaviorsUsing Personality Trait Theory The Eurographics Association link

• Noralizatul Azma Bte Mustapha and Abdullah Bin Bade : COLLISION AVOIDANCE SERIES OF TECHNIQUE FOR
  CROWD SIMULATION link3

• Abhinav Golas, Rahul Narain, Sean Curtis, and Ming C. Lin, Fellow, IEEE1 : Hybrid Long-Range Collision Avoidance for
  Crowd Simulation link2

• Daniel Thalmann ? Soraia Raupp Musse : Crowd Simulation
  Second Edition link4

+[EE85] EYSENCK H., EYSENCK M.: Personality and individual differences: A natural science approach. Plenum Press NewYork, 1985.

• دکتر بهروز مینایی، مهرداد آشتیانی، مسعود جلیلی ثابت، مهیار طاهری: مدل شبیه سازی جمعیت با خودمختاری رفتاری در
  محیط های مجازی و بازیهای رایانه ای