#"به نام خدا"
#مقدمه
امروزه بازی های رایانه ای علاوه بر رفتارهای فردی شامل رفتارهای جمعی نیز می باشد برای دستیابی به این منظور مدتهاست که الگوریتم هایی برای شناسایی، ارزایابی و پیاده سازی الگو های رفتاری مورد مطالعه قرار گرفته است.
یک جمعیت [^1] را به تعداد زیادی موجودیت که به شکل فیزیکی با هم یک گروه را تشکیل داده اند، نسبت می دهند. این گروه رفتارهای خاصی دارد که با رفتارهای معمولی اعضا به صورت فردی متفاوت می باشد چرا که آن ها عضو یک جمعیت هستند و این جمعیت رفتارهای خاصی را به اعضا تحمیل می کند. شبیه سازی این رفتار مبتنی بر جمعیت را ، Crowd Simulation و یا ** شبیه سازی رفتار جمعیت** ، به اختصار *CS* می نامند.
به عنوان مثال گروهی از غازها هنگام مهاجرت را درنظر بگیرید، هرکدام از غاز ها وظیفه دارد در عین حفظ فاصله با دیگران و عدم برخورد با آن ها، ویژگی گروه را حفظ کند و با دیگران پرواز کند. می بینید که گروه غازها رفتار های خاصی را به هر غاز تحمیل میکند در صورتی که گروهی وجود نداشت ، این محدودیت ها برای غاز ها نیز وجود نداشت.
#کاربردها
شبیه سازی جمعیت کاربردهای بسیار وسیعی دارد که در زیر به چند نمونه اشاره میکنیم :
+ ** شبیه سازی زندگی مردم یک شهر وسیع** به طوری که بتوانند نیاز های خود را تامین کنند.فرض کنید صبح، همه مردم از خواب بیدار شوند، به سر کار روند ، بچه ها به همراه مادرشان به مدرسه روند و درشب بعد از رفتن به رستوران و خوردن شام ،به خانه رفته و استراحت کنند. بله، تردید نکینید این چیزی است که در بازی ها استفاده میشود به عنوان مثال بازی GTA ، Hitman و یا Assassins Creed که دارای یک نقشه بزرگ می باشند، برای مدیرت جمعیت از این سیستم ها استفاده می کنند. دانستن این نکته الزامی است که نمی توان با انیمیشن های از پیش ساخته شده و ثابت، این جمعیت بزرگ را مدیرت کرد !! علاوه بر بحث کارایی، بحث واقع گرایی نیر مطرح می باشد که گروه، رفتار های تکراری و قابل پیشبینی از خود نشان ندهد.در بازی Assassins Creed وقتی شما در داخل شهر برای فرار از دست مامورین حکومتی پا به فرار میگذارید، عکس العمل مردم شهر در قبال رفتار شما بی نظیر می باشد. تلاش آن ها برای جلوگیری از برخورد با شما و رفتار آن ها بعد از برخود قابل تحسین است.
+ ** شبیه سازی در پروژه های ساختمانی** فرض کنید قرار است یک ورزشگاه صد هزار نفری ساخته شود!، یکی از عامل هایی که در طراحی این ورزشکاه مهم است، مدیرت ازدحام جمعیت، هنگام ورود و خروج به ورزشگاه می باشدکه می توان با شبیه سازی ورزشگاه و جمعیت،طراحی را مورد ارزیابی قرار داد تا هزینه ها به شکل قابل قبولی کاهش یابند.
# کارهای مرتبط
در این قسمت قصد دارم دو نمونه از تحقیقاتی را که برای این پروژه از آن ها الهام گرفتم بررسی و سپس آن ها را بر اساس شرایط موجود و محدودیت های فعلی امکان سنجی کنم.
+ **1- "اجتناب از برخورد دور بورد ترکیبی" [^3]**
چکیده:
الگوریتم های جلوگیری از برخورد محلی که فقط به همسایه های نزدیک توجه می کند اغلب همسایه هایی که کمی فاصله دارند ولی به زودی تاثیر می گذارند رو مورد توجه قرار نمی دهد .
علاوه بر این برای پیاده سازی این الگوریتم ها نیاز به دانش در مورد تعداد و چگالی جمعیت می باشد زیرا برای جمعیت های کم و با چگالی پایین حتما باید به شکل گسسته مدل شوند و برای جمعیت های زیاد و چگال باید از مدل پیوسته استفاده شود. با استفاده از روش ترکیبی به شکل کارا میتوانیم هر جمعیتی را با هر چگالی مدل کرده و مدل به شکل غیر متناهی بین گسسته و پیوسته تغییر حالت می دهد
مقدمه :
بر اساس مفهوم 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) پرخاشگر[^9]**
**2) خجالتی[^10]**
**3) متشنج[^11]**
**4) جسور[^12]**
**5) فعال[^13]**
**6) با انگیزه[^14]**
سپس با تخصیص پارامتر های شبیه سازی جمعیت بر اساس نوع شخصیت عامل ، کار را ادامه میدهد. پارامتر هایی که در این مقاله نگاشت شده اند از قرار زیرند
+ سرعت ترجیحی هر فرد ( $v_{p}$)
+ دایره فعالیت هر فرد ( این که هر عامل چه قدر از عامل های دیگر دور میشود)
+ حداکثر تعداد همسایگانی که رفتار محلی یک عامل را تحت تاثیر قرار میدهند.
+ حداکثر فاصله تا همسایگانی که روی عامل تاثیر گذارند و
+ میزانی بلندای طرح ریزی یک عامل
نتایج بدست آمده از این آزمایشات بسیار جالب می باشد. در تصاویر زیر میبینید که شخصیت ساخته شده برای عامل ها چگونه در نوع رفتار آن ها تاثیر گذاشته است.
در پایان این مقاله با اجرای آزمایشاتی بیان میکند که اگر تمامی عامل ها از یک نوع شخصیت باشند . بازدهی کلی به مراتب پایین تر از هنگامی است که به شکل تصادفی عامل ها دارای شخصیتی متفاوت می باشند.
#دید کلی برای پیاده سازی
همان طور که میدانید دامنه CS بسیار گسترده می باشد به طوری که به هیچ وجه در یک پروژه چند ماهه نمی توان تمامی جنبه های آن را بررسی کرد.
جلوگیری از برخورد[^2] یا به اختصار CA یکی از پایه ای ترین بخش های شبیه سازی جمعیت می باشد چرا که تمام دیدگاه ها و کاربردهای CS چه در بازی های رایانه ای و چه در زمینه های دیگر نیازمند هوشمندی عامل ها در برخورد و حرکت به سمت یکدیگر می باشد.
برای این منظور ما در صدد رسیدن به یک سیستم برای شبیه سازی خروج انبوه یک جمعیت از یک فروشگاه یا ورزشگاه می باشیم. وسعت فروشگاه ، تعداد درب خروجی، میزان هجوم مردم برای خروج در موقعیت های معمولی و یا اضطراری ( مانند آتش سوزی) و ... پارامتر هایی است که می تواند مورد تحقیق و آزمایش قرار گیرد.
روش های پیاده سازی CS را میتوان در مدت زمان شبیه سازی و میزان جمعیت مورد ارزیابی، تقسیم بندی کرد.
در این پروژه ابتدا ساده ترین روش ها پیاده سازی می شود و نتایج آن به ثبت می رسد و به مرور با پیچیده تر کردن شرایط، و بهبود الگوریتم های مربوط به CA تا حدی نتایج شبیه سازی را بهبود می بخشیم.
روش "اجتناب از برخورد دور بورد ترکیبی" روشی است که علاوه بر کارایی خوب، بسیار واقع گرایانه عمل می کند.
در این روش علاوه بر درنظر گرفتن همسایه های محلی، به همسایه های دور بورد نیز توجه خاصی می شود که همین عامل باعث می شود، عامل ها رفتار یکدیگر را پیشبینی کنند و قبل از نردیک شدن بیش از حد و به وجود آمدن برخورد های شدید که باعث کاهش سرعت حرکت و نرخ فریم بازی می شود، رفتاری مناسب برای عبور از کنار یکدیگر نشان دهند.
در پایان رفتار جمعیت را با استفاده از تئوری Personality Trait شخصی سازی می کنیم
به طوریکه ابتدا تمامی آدم ها دقیقا مانند یکدییگر هستند ( روحی ، جسمی و ... ) و به مرور زمان این جمعیت شخصی سازی شده و جنبه های مختلف روحی از جمله میزان پرخاشگری، جسارت، میزان فعال بودن و ... را در پارامتر های شبیه سازی دخالت می دهیم و یک نگاشت ما بین آن ها ایجاد می کنیم
و نشان میدهیم که این اختلاف رفتار باعث همگونی بهتر رفتار جمعیت می شود و در حالت میانگین، عملکرد بسیار بهتری را از خود به جای می گذارد.
به امید خدا تمامی پروسه پیاده سازی این تحقیق در [موتور یونیتی] اجرا میشود که در آخر می تواند یک افزونه خوب برای این موتور به حساب آید و در بازی های رایانه ای مورد استفاده قرار گیرد.
#پیاده سازی
تا مطاعات و تحقیقات فراوانی که بر روی شبیه سازی جمعیت انجام شد. از این مرحله همانطور که قرار مان بود به سراغ موتور بازی سازی یونیتی رفتیم تا بررسی کنیم که این موتور چه چیزهایی را در اختیار ما قرار می دهد تا بتوانیم هرچه بهتر رفتار یک جمعیت را شبیه سازی کنیم. همانطور که قبلا گفتیم برای شبیه سازی یک جمعیت به دو قسمت عمده نیاز داریم.
1) Global plannig برای بدست آوردن $v_{p}$
2) حل کردن یک مسئله ی اجتناب از برخورد محلی با عامل های دیگر
در زیر اقداماتی که برای پیاده سازی این قسمت ها در موتور بازی سازی انجام شده است . آورده ایم.
##تحقیقات و آزمایشات
### مسئله ی Global plannig
برای شروع کار و ایجاد عامل ها ابتدا باید محیط جدول بندی بشود. چرا که تمامی الگوریتم های حرکتی و مسیر یابی آگاهانه از جمله $A^*$ نیازمند جدولی از راه های قابل تردد و غیر قابل تردد می باشد.
در موتور یونیتی برای این کار قابلیتی در نظر نگرفته شده است، اما به جای آن از یک قابلیت بهتر که در بازی های رایانه ای کار برد بسیار بیشتری دارد استفاده شده است. این ویژگی امکان ساخت شبکه ناوبری [^4] می باشد. این شبکه این امکان را به عامل میدهد که مکان هایی از نقشه که قابلیت تردد دارد را از آن هایی که این ویژگی را ندارد تشخیص دهد و بنابراین بتواند بهترین مسیر را انتخاب کند.
همان طور که در تصویر بالا می بینید شبکه ناوبری ساخته شده درون یک ساختمان ، مسیر های قابل حرکت و اصطلاحاً " قابل قدم" [^5] با رنگ آبی نشان داده شده است. اجازه دهید در مورد چگونگی ساخت این شبکه صحبتی نکنیم و از آن عبور کنیم. استودیو بازی سازی Valve در سایت خود مقاله ای را در این مورد قرار داده است که اگر علاقه داشتید میتوانید به [این صفحه] رجوع کنید.
از میان الگوریتم های مسیریابی موتور یونتی از الگوریتم $A^*$ استفاده میکند و بعد از مشخص شدن هدف، این الگوریتم به کمک مش ناوبری بهترین مسیر را پیدا میکند.
تا این جای کار ما توانستیم یک عامل ایجاد و با مشخص کردن هدف برای آن، شاهد حرکت هوشمند وی به طرف هدف با شیم. این اقدامات به وسیله کلاسی به عنوان[NavMeshAgent] قابل پیاده سازی می باشد.
حال به ساخت موانع در موتور میرسیم. سوال این جاست که چگونه باید عامل را متوجه این موانع ( ثابت و متحرک ) کرد؟ [^6] . بعد از تحقیقاتی که انجام دادیم دریافتیم که ورژن های قدیمی موتور یونیتی ( تا شماره 4 ) امکان داشتن موانع متحرک در هنگام اجرای بازی را نداشته است. در حقیقت باید تمامی اشیائی که میخواهیم عامل متوجه آن ها باشد که به آن ها برخورد نکند و در مسیریابی آن ها را در نظر بگیرد؛ را قبل از اجرای بازی و هنگام ساخت شبکه ناوبری به عنوان جسم ثابت [^7] به موتور معرفی کنیم. در این صورت تغییر مکان و تخریب این موانع، در حال اجرای بازی ، هیچ تاثیری بر رفتار عامل ندارد.
اما خوشبختانه از ورژن 4 به بعد، یونتی این امکان را برای ما فراهم میکند که علاوه بر ویژگی های قبلی ، قادر خواهیم بود که اشیاء را در حال اجرای بازی [^8] به روز رسانی کنیم ( تخریب و یا تغییر مکانی و یا زاویه ای ) . این امکان به کمک کلاسی به نام [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
حال، کار بعدی ما بررسی و آزمایش این پارامتر ها خواهد بود برای این که بتوانیم عملکرد جمعیت خود را بهبود بخشیم.
برای بررسی پارامترهای ذکر شده، آزمایشات زیادی انجام شد که نتایج آن در زیر آمده است. این آزمایشات همگی در موتور یونیتی، پیاده سازی و رفتار جمعیت به دقت بررسی شد تا بتوانیم به بهترین عملکرد برسیم.
###آزمایش اول: تنها دایره فعالیت هر فرد
این آزمایش روی پارامتر Radius از کلاس NavMeshAgent انجام شد. این پارامتر در واقع شعاع دید عامل را نشان می دهد. عامل ها برای مسیر یابی خود به این شعاع توجه می کنند و در حقیقت هر شیئی که در این شعاع قرار گرفته باشد، عامل آن را تحت نظر می گیرد و سعی می کند که به هیچ وجه ، نه به عامل دیگری برخورد کند و نه اجازه می دهد که عاملی وارد این محیط شود. برای درک بهتر از این موضوع به تصویر زیر دقت فرمایید. تصویر سمت راست نمایی از یک عامل با شعاع $0.5$ و در تصویر سمت چپ عاملی با شعاع $1$ نمایان شده است.
اما نتایج آزمایش ها بسیار جالب بود. خود من بسیار تعجب کردم. در ابتدا من این گونه فکر می کردم که هر چه این شعاع بیشتر باشد، فرد با در نظر گرفتن عامل های بیشتر رفتار بهتری را از خود نشان می دهد. اما با بار ها آزمایش در دو بخش ، قضیه طور دیگه ای رقم خورد.
####بخش اول : شعاع ثابت
در این بخش همه ی عامل ها را مانند گذشته با شعاع های مختلف به میدان فرستادیم. شعاع های $0.5$ ، $0.75$، $1$، $1.25$ و $1.5$ کافی بود تا به نتیجه دلخواه برسیم. ارزیابی این روش نشان داد که هرچه شعاع عامل ها بیشتر باشد، عامل ها کند تر به سمت هدف حرکت می کنند. در واقع اتلاف زمانی آن ها بسیار زیاد است. آن ها در این صورت خیلی ترسو به نظیر رسیده و هیچ کدام، حرکت رو به جلو به شکل جسورانه نخواهند داشت. به بیان دیگر آن ها با یکدیگر تعارف بیش از حد دارند و هیچ کدام تلاشی برای حرکت به جلو ندارد. من از این آزمایش یک فیلم تهیه کرده ام که می توانید آن را از [از این لینک] در یافت کنید. نتایج این آزمایش نشان داد که این روش مناسب نیست و نتیجه معکوس دارد. البته اگر هدف صرفاً عبور سریع نباشد، ممکن است این روش هم بسیار مناسب باشد. در ضمن لازم به تذکر می دانم این روش{شعاع های بزرگ} باعث می شود که عامل ها رفتاری صبورانه و معقولانه تر داشته باشند و از تکان خوردن های اضافی بپرهیزند.
####بخش دوم: شعاع تصادفی
با الهام از نظریه شخصی سازی سعی کردیم تا با تصادفی سازی این شعاع، عبور عامل ها را سریع تر کنیم. جزئیات این آزمایش ها نیز به این گونه بود که یک تابع Random بین یک حداقل و حداکثر که میتوانیم به عنوان ورودی به تابع دهیم شعاعی تصادفی برای عامل ها ایجاد می کند. نتایج این آزمایش ها، کمی بهتر از بخش اول بود زیرا عامل هایی که شعاع کم دارند، نیز در بین جمعیت وجود دارد. در [فیلم شعاع تصادفی] که میتوانید دریافت کنید، رفتار جمعیت را می توانید بررسی کنید. برای مشخص شدن رفتار عامل ها، عامل هایی که رنگ آن ها به قرمز نزدیک تر هستند به این معنی هستند که شعاع کمتری دارد و آن هایی که به آبی نزدیک تر هستند شعاع بزرگتری دارند.
اما ایده ی دیگر این بود که با ادغام شعاع و سرعت ، آزمایشات را تکرار کنیم.
###آزمایش دوم: دایره و سرعت هر عامل
این بار نظریه شخصی سازی را سعی کردیم بیشتر دخالت دهیم و فرض کردیم که شعاع هر عامل روی سرعت آن نیز تأثیر گذار است. این آزمایش میز دو بخش دارد، بخش اول رابطه ی مستقیم سرعت و شعاع است و بخش دوم رابطه معکوس، در رابطه مسقیم فرض کردیم که هرچه شعاع یک عامل بیشتر باشد، آن عامل سریع تر حرکت می کند و در رابطه معکوس فرض کردیم که هرچه شعاع بیشتر باشد، آن عامل آهسته تر حرکت می کند.
####بخش اول
نتایج این آزمایش به این گونه بود که عامل هایی که شعاع بیشتر داشتند بخاطر سرعت بیشتر ، به یکدیگر رسیده و با توجه به شعاع زیاد، حجم زیادی از فضا را اشغال کرده و مانع عبور عامل ها با شعاع و سرعت کمتر می باشند. در این روش یک سد از عامل های با شعاع بالا ایجاد می شود.
####بخش دوم
نتایج این بخش به این گونه بود که عامل هایی که شعاع کمتر داشتند بخاطر سرعت بیشتر، زود تر به یکدیگر می رسند و لی چون در شرایط آزمایش، فرصت کافی برای عبور از یکدیگر را نداشتند، عامل ها با شعاع بزرگتر به جمعیت اضافه میوشند. حال اتفاقی که رخ می دهید تکان ها و جابه جایی های غیر طبیعی است که عاامل ها در این شرایط از خود نشان می دهند که اصلا قابل قبول نبود. البته این تکان ها در بخش اول نیز وجود داشت اما به این شدت نبود.
در کل این روش تغییر خاصی ایجاد نکرد، شاید به خاطر سرعت بیشتر کمی اوایل شبیه سازی تعدا عبور ها افزایش می یافت و لی به دلیل گره خوردگی، زمان کلی بالا تر، یعنی بدتر بود.
###آزمایش سوم، چهارم و پنجم: شتاب حرکت، سرعت زاویه ای، اولویت دراجتناب از برخورد و میزان دقت در اجتناب از برخورد
در این آزمایش به طور کلی پارامتر های دیگر را دست کاری کردیم.
####شتاب حرکت
در مورد شتاب حرکت باید بگویم که تأثیر آن تنها در ابتدای حرکت می باشد و بعد از گذشت کمتر از 1 ثانیه دیگر کارآمدی خود را از دست می دهند. البته در شبیه سازی های حقیقی این پارامتر را نمی شود زیاد تغییر داد چرا که واقعی بودن رفتار عامل ها را نسبت به انسان ها تحت تحأثیر قرار می دهد.
####سرعت زاویه ای
در شرایط آزمایش، با تغییر این مقدار تغییر محسوسی دیده نشد. دلیل آن هم این است که اولاً سرعت پیش فرض یونیتی، در حدی است که تقریبا شما متوجه حکرت چرخشی نمی شوید ثانیاً در این آزمایش و حتی خیلی از مورد های دیگز شبیه سازی جمعیت این عامل زیاد کارآمد نیست.
####اولویت دراجتناب از برخورد
این پارامتر که مقداری بین 0 تا 99 دارد به این معنی است که ، عامل ها ، اولویت پایین تر از خود را نادیده می گیرند و از آنها عبور می کنند . با تغییر این متغیر، شاهد رفتار های عجیبی از عامل ها بودیم، آن ها ناگهان مسیر حرکت خود را تغییر می دادند ، روی زمین سر میخوردند و از یکدیگر عبور می کردند. بنابراین این پارامتر هم برای هدف ما کارآمد نیست.
### #میزان دقت در اجتناب از برخورد
این پارامتر تقریبا شبیه پارامتر "اولویت دراجتناب از برخورد" می باشد. با این تفاوت که عاملی که میزان دقت پایینتر دارد، با انجام محاسبات کمتر، خیلی سریع تر تصمیم گیری میکند و از آن جایی که خیلی از موارد را از تصمیم گیری خود حذف میکند، شاهد رفتار های غیر طبیعی از وی خواهیم بود. گذشتن از یکدیگر برای رسیدن به هدف و یا انتخاب تنها مسیر مستقیم برای رسیدن به هدف،از این گونه رفتار هاست.
با نتیجه گیری از نتایج بدست آمده و برداشت مفهومی از آن ها متوجه شدیم که بهترین روش برای کابرد ما، یعنی از کنار هم گذشتن هرچه سریع تر عامل ها، پایین بودن و ثابت بودن شعاع عامل ها ( و یا تغییر خیلی کوچک) بهترین روش است. اما ایده آخر تنها دست کاری سرعت عامل ها بود که آزمایش ششم به آن میپردازد.
###آزمایش ششم: تنها سرعت حرکت عامل ها
در این آزمایش، شعاع ها را ثابت نگه داشتیم (0.5) و با ثابت نگه داشتن رأس سرعت مانند آزمایش های قبل(سرعت برابر با مقدار 5) ، تنها با تصادفی سازی آن به بهترین نتایج رسیدیم. این نتایج به این گونه بود که عامل هایی که سرعت بیشتر داشتند ابتدا به یکدیگر می رسند و شروع به گذر از کنار یکدیگر کردند. رفته رفته با اضافه شدن عامل های کندتر وضعیت کمی متفاوت بود. این بار از آن جایی که **نرخ عبور جمعیت** در اوایل شبیه سازی بسیار بالا بود، فضای کافی برای عامل های کند تر نیز وجود داشت. به عبارت دیگر بر خلاف آزمایشات دیگر ، سرعا انتقال عامل ها در ابتدای کار بسیار بالا و در انتهای کار به دلیل کم بودن سرعت عامل ها بسیار مشخص است. فکر میکنم این یکی از بهترین نتایجی بود که می توانستیم در این وقت محدود بدست آوریم. در این این قسمت می توانید [فیلم سرعت تصادفی] را مشاهده بفرمایید. در فیلم تمام عامل ها مشابه و تنها سرعت آن ها با هم متفاوت است. آن هایی که به رنگ آبی نزدیک تر هستند سرعت بیشتری دارند. شرایط هر عامل را در این آزمایش می توانید در نمای زیر ببینید. در این نما کلاس NavMeshAgent و Core و پارامتر های آن قابل مشاهده می باشد.
. بار دیگر تآکید می کنم که این روش تنها نرخ عبور بهتری دارد و در حقیقت میانگین عبوری، بهتر است و همچنین ویژگی بهبود یافته اصلی همان طور که در فیلم مشا هده نمودید ، رفتار طبیعی تر عامل ها حتی در جمعیت های بالا است. در این آزمایش دریافتیم که دیگر عامل ها مانند قبل به یکدیگر نمیچسبند و یک نفقه کور که پر از برخورد است ایجاد نمی کند. عامل ها با زمان بندی بهتر از کنار یکدیگر خیلی معقولانه تر عبور می کنند.
قصد داشتم که در یک نمودار تفوت دو روش را نشان دهم که متأسفانه به دلیل کمبود وقت، از ایجاد آن معذور ماندم . چرا که این بار به جای زمان کل، باید از نرخ عبور استفاده میکردم.
#نتیجه گیری
بیش از 50 آزمایش روی قسمت های مختلف انجام شد و شبیه سازی جمعیت در موتور یونیتی در حد توان زیر ذره بین قرار گرفت. نظریه شخصی سازی و اجتناب از برخورد دور بورد ترکیبی، قسمت هایی بود که سعی کردیم از آن ها در آزمایشات خود استفاده کنیم. پارامتر های مهم را از آن ها استخراج کردیم و سعی کردیم آن ها در موتور یونیتی شبیه سازی کنیم. در نهایت به این نتیجه رسیدیم که با دستکاری پارامتر های عامل ها **با توجه به هدف شبیه سازی جمعیت** می توانیم این شبیه سازی را بهبود ببخشیم نتیجه ای که ما با توجه به هدف خود داشتیم این بود که با ثابت نگه داشتن شعاع عامل ها ( مقدار کم ) با تصادفی سازی سرعت، نه تنها به ** نرخ عبور** بهتری دست یافتیم بلکه توانستیم جمعیت بالایی را از کنار یکدیگر بدون گره خوردگی عبور دهیم.
**کل پروژه** رو براتون اینجا گذاشتم. [پروژه] البته برای اجرای پروژه به موتور یونتی نیاز دارید. اما می توانید کد ها و فایل ها را مشاهده کنید.
#سخن آخر و کارهای آینده
خدا رو شکر می کنیم که یک نیم سال تحصیلی توفیق داد تا با تحقیق و ارزیابی یکی از مهمترین چالش های بازی سازی ، گامی هرچند کوچک در مسیر پیشرفت بازی سازی برداشته باشیم. شبیه سازی جمعیت بسیار گسترده می باشد، و هنوز بسیاری از مسائل وجود دارد که میتوان روی آن تحققیق و آزمایش انجام داد. آن قدر این موضوعات زیاد است که عناوین آن ها را هم اگر بخواهیم ذکر کنیم، چند صفحه ای می شود. اما موضوعی که فکر میکنم در گام بعد جالب باشد، تاثیر محیط بر روی جمعیت و شبیه سازی این قسمت می باشد. خشکی،ساحل، جنگل ، کوهستان و ... رفتار های خاصی را به عامل ها تحمیل کند که ارزیابی آن ها خالی از لطف نیست و شما خود میتوانید تأثیر آن ها را در بازی سازی درک کنید.
در پایان تشکر میکنم که این مقاله را مطالعه فرمودید.
زمستان و بهار 1393.
#مراجع
+ 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.
+ دکتر بهروز مینایی، مهرداد آشتیانی، مسعود جلیلی ثابت، مهیار طاهری: مدل شبیه سازی جمعیت با خودمختاری رفتاری در
محیط های مجازی و بازیهای رایانه ای
[link4]: http://www.amazon.com/Crowd-Simulation-Daniel-Thalmann/dp/144714449X//
[link3]: http://comp.utm.my/pars/files/2013/04/COLLISION-AVOIDANCE-SERIES-OF-TECHNIQUE-FOR-CROWD-SIMULATION.pdf
[link2]: http://gamma.cs.unc.edu/lookahead//
[link]: http://gamma.cs.unc.edu/personality/
[موتور یونیتی]: http://unity3d.com/
[این صفحه]: https://developer.valvesoftware.com/wiki/Navigation_Meshes
[NavMeshAgent]: https://docs.unity3d.com/Documentation/ScriptReference/NavMeshAgent.html
[NavMeshObstacle]: https://docs.unity3d.com/Documentation/ScriptReference/NavMeshObstacle.html
[اینجا]: https://dl.dropboxusercontent.com/s/j95wmsj3lmos8ex/Unity%202014-05-25%2011-04-54-99.mp4?dl=1&token_hash=AAGepHh5isFSv5vB76JMMOeYw0rf5ME5QJdgH6sVF6WtuA&expiry=1401005245
[از این قسمت]: https://dl.dropboxusercontent.com/s/k54pn708uybt2mr/Unity%202014-05-25%2012-43-13-39.mp4?dl=1&token_hash=AAHn1PzrO45MjKg_d_dBM0VbNIqqMZGXVv-egffuDeX5fA&expiry=1401011569
[از این لینک]: https://www.dropbox.com/s/xew56tmoeu3zl9p/fIXED%20rADUI.mp4?dl=1
[فیلم شعاع تصادفی]: https://www.dropbox.com/s/xb8scnyg2xpv1kp/Randome%20RAdios.mp4?dl=1
[فیلم سرعت تصادفی]: https://www.dropbox.com/s/bsfitnvs0t8hynz/speed.mp4?dl=1
[پروژه]: https://github.com/erfan71/Ai-Crowd-Simulation
[^1]:Crowd
[^2]:Collision Avoidance
[^3]:Hybrid Long-Range Collision Avoidance
[^4]:Navigation Mesh
[^5]:Walkable
[^6]:منظور موانع مانند دیوار و وسایل و... میباشد ، نه عامل های دیگر.
[^7]:Static
[^8]:Runtime
[^9]:aggressive
[^10]:shy
[^11]:tense
[^12]:assertive
[^13]:active
[^14]:impulse