در این بازی ما یکسری خط لوله داریم می خواهیم از ابتدای یک لوله به انتهای آن برسیم کد ما باید خط لوله هایی که به ان میدهیم را ارزیابی کرده از طریق مسیر های مجاز از ابتدا به انتها برسد که با استفاده از الگوریتم های جستجو این کار صورت میگیرد.
۱. مقدمه
این پروژه در واقع یک بازی است و مسیر در آن از یک سری خط لوله تشکیل شده است که آن را به صورت یک فایل در اختیار داریم و نقشه ی لوله ها در آن قرار دارد.
هدف ما در این بازی رسیدن از ابتدا به انتهای مسیر از طریق مسیر های مجاز است. کد ما باید این مسیر های مجاز را ارزیابی کرده و با الگوریتم های search
و heuristic با حالت بهینه از ابتدا به انتها برسد.
ایده ی این بازی و الگوریتم هایی که از آن ها برای مسیریابی در آن استفاده میکنیم چه کاربرد هایی دارد و در کجا ممکن است استفاده شود؟
یکی از بزرگترین چالش ها در طراحی هوش مصنوعی بازی های کامپیوتری حرکت agent است و استراتژی های مسیریابی به عنوان مهمترین بخش هر
AI moving system میباشند.
این پروژه و ایده ی آن کاربرد الگوریتم های search و heuristic را به خوبی به نمایش میگذارد و بیان میدارد که میتوان از این الگوریتم ها که به خوبی حرکت agent را توصیف میکنند در طراحی مناسب حرکت agent برای بازی های کامپیوتری و feild های دیگر مثل حرکت robot ها استفاده کرد از نمونه های آن میتوان به موارد زیر اشاره کرد:
ربات هایی که به سیاره ها فرستاده میشوند تا آن سیاره را بررسی کنند که این ربات ها از توانایی های دیگری در زمینه ی هوش مصنوعی نیز برخوردارند و
میتوانند آن سیاره را به خوبی بررسی کنند مثل mars pathfinder که یک ربات آمریکایی است که در سال 1997 به مریخ فرستاده شد و در سطح مریخ
به جست و جو و بررسی پرداخت.ربات های بازیکن فوتبال که در زمین های مخصوص فوتبال بازی میکنند و باید مسیر یابی و تشخیص مکان توپ در هر لحظه را انجام دهد مثل
NAO soccer player که یک ربات اسکاتلندی است.
۲. کارهای مرتبط
برای حل این مساله از 6 الگوریتم search و heuristic استفاده میکنیم :
Breadth-first search
Depth-first search
Uniform cost search
Iterative deeping search
A* search
Manhatan heuristic search
تعریف navigation mesh:
مجموعه ای از چند ضلعی های محدب که مسیر قابل عبور یک محیط 3D را به تصویر میکشد. الگوریتم هایی برای تولید navigation mesh برای هر map
داده شده پیاده سازی شده اند. navigation mesh های تولید شده با این الگوریتم ها از چند ضلعی های محدبی تشکیل شده اند که وقتی به هم متصل شوند
شکل map را مشابه یک طرح طبقه ای در می آورند. چند ضلعی ها در یک mesh باید محدب باشند که این باعث میشود agent بتواند در یک مسیر مستقیم
از یک point روی یک چند ضلعی به point دیگر در مرکز چندضلعی مجاور جابجا شود. هر کدام از این چند ضلعی های محدب میتوانند به عنوان یک node برای الگوریتم های مسیریابی مورد استفاده قرار گیرند.
navigation mesh ها برای محیط های static مناسب میباشند.
تعریف waypoint:
مجموعه ای از node ها با لینک هایی بینشان . وقتی یک agent میخواد از A به B بره ابتدا به نزدیک ترین waypoint از A سپس از یک مسیر پیش محاسبه شده استفاده میکند و به نزدیکترین waypoint از مکان B میرود. معمولا طراح این waypoint ها را به صورت دستی در map قرار میدهد که این کار باعث میشود
تعداد node ها به کمترین حالت برسد و برای map های static مناسب میباشند.
سیستم های مسیریابی یک starting point و یک destination دارند برای رسیدن به destination یک سری از point ها را پیدا میکنند و در کنار هم قرار میدهند تا یک مسیر به destination حاصل شود.
سیستم های مسیریاب از ساختمان های داده از قبیل صف و استک برای راهیابی و یافتن مسیر استفاده میکنند.
فضا و هندسه ی بازی در یک ساختاری به نام map ذخیره میشود. map ها معمولا تمام چندضلعی هایی که فضای بازی را تشکیل میدهند را در برمیگیرد.
در خیلی از موارد برای محدود کردن فضای جست و جو map را به قسمت هایی شکسته و ساده سازی میکنند , پس از آن مسیریاب از مسیر ساده سازی
شده استفاده میکند تا از starting point به destination برسد.
مسیریاب یک مسیر در virtual world برای خود تعیین میکند تا بتواند محدودیت هایی که برایش قرار داده شده را حل کند یک مثال خوب از این محدودیت ها میتواند یافتن کوتاه ترین مسیر برای انتقال یک agent از current position به target position باشد.
مسیریابی میتواند به دو بخش عمده تقسیم شود:
مسیریابی Directed:
این نوع مسیریاب ها کورکورانه وارد محیط نمیشوند به عبارت دیگر همه ی آن ها متود هایی برای ارزیابی پیشرویشان نسبت به همه ی node های مجاور قبل از
انتخاب یکی از آن ها دارند. استراتژی ها برای الگوریتم های مسریابی dircted عبارتند از:
1- Uniform cost search- g:
جست و جو را جوری تنظیم میکند که کوتاه ترین مسیر را نسبت به node بعدی انتخاب کند.
2- Heuristic search- h:
هزینه را از node بعدی تا goal را تخمین میزند.مسیریابی Undirected:
این نوع مسیریاب ها کورکورانه وارد محیط میشوند و برای یافتن مسیر تلاش میکنند. استراتژی ها برای الگوریتم های مسیریابی Undirected عبارتند از:
1- Breadth-first search:
محیط را به چشم یک گراف بزرگ از node های به هم پیوسته میبیند و همه ی node های متصل به node فعلی را گسترش میدهد و این فرایند را همینطور ادامه میدهد بنابراین اگر مسیری وجود داشته باشد آن را می یابد.
2- Depth-first search:
به بچه های هر node نگاه میکند قبل از این که به ادامه ی node ها نگاه کن و یک مسیر خطی به goal می یابد.
۳. آزمایش ها
۴. کارهای آینده
۵. مراجع
برخی از مراجع و پیوند های مفید استفاده شده:
Ross Graham, Hugh McCabe, Stephen Sheridan , "Pathfinding in Computer Games" , School of Informatics & Engineering , Institute of Technology Blanchardstown , 2003