راهکاري براي حل مسئله بسيار مهم و حساس مسيريابي در بازي ها و نرم افزارهاي مهندسي

*در اين مقاله قصد داريم، يکي از مهمترين و در واقع رايج ترين الگوريتم هاي مورد استفاده در فرآيندهاي مسيريابي هوشمند را مورد بررسي قرار دهيم. اين الگوريتم *A (به صورت A Star خوانده مي شود) نام دارد و همان طور که خودتان در ادامه مشاهده خواهيد نمود، به قدري ارزش دارد که عده اي آن را ستاره الگوريتم هاي مسيريابي و هوش مصنوعي خوانده اند. اين الگوريتم اگرچه از نظر طراحي و عملکرد نسبتاً ساده مي باشد و طرز کار آن را مي توان تقريباً به راحتي درک کرد، اما پياده سازي آن بر حسب شرايط مختلف و قابليت هاي مورد نظر، بسيار متنوع و تا حدودي پيچيده است.
لازم به ذکر است، اين الگوريتم که از قدمت نسبتاً طولاني در صنعت کامپيوتر برخوردار است، در طول ساليان گذشته، به اشکال مختلفي پياده سازي شده است. البته شما نيز مي توانيد اين الگوريتم را به شيوه مورد نظر خودتان پياده سازي کنيد. به طور کلي *A به عنوان راهکاري براي حل مسئله بسيار مهم و حساس مسيريابي در بازي ها و نرم افزارهاي مهندسي و شبيه سازي محسوب مي شود و نحوه اجرا و استفاده از آن کاملاً به شرايط بستگي دارد.
*اين الگوريتم به گونه اي کار مي کند که مي توان از آن در هر محيطي بهره گرفت. اگرچه محدوديت هاي خاص خود را نيز دارد، اما *A مي تواند شما را در ساخت بازي هاي کاملاً دو بعدي، بازي هاي اول شخص و سوم شخص سه بعدي، بازي هاي استراتژي و حتي بازي هايي در محيط هاي بيروني (زمين و تپه، رودخانه و دريا، جنگل و...) ياري کند. براي اعمال *A در يک بازي (و يا هر محيط ديگري)، شما ابتدا بايد يک ناحيه جستجو براي خود تعريف کنيد. اين ناحيه (Search Area)، همان محدوده اي است که *A قرار است با انجام يک سلسله تست هاي تکراري آن را مورد بررسي قرار داده و بهترين (و کوتاهترين مسير) را در آن بيابد. البته در اين مقاله قصد نداريم وارد جزئيات پياده سازي شويم، بلکه صرفاً مي خواهيم با توضيح مفهوم اين الگوريتم، شما را در حل مسائل مربوطه ياري کنيم.
در يک کلام *A الگوريتمي قدرتمند براي يافتن نزديکترين مسير بين دو نقطه مي باشد که مي توان با انجام برخي تغييرات، آن را براي اهداف ديگري از جمله حل مسائل گراف ها نيز به کار برد.
اين ناحيه جستجو مي تواند محيط داخلي يک خانه (کليه اتاق ها، آشپزخانه، حمام و دستشويي و راهروها و ديوارها و اشيا داخل آن، يعني به صورت يک مستطيل که کل مساحت خانه را در بر مي گيرد)، يک دشت يا يک جنگل، و يا يک کارخانه باشد. البته اين محيط قطعاً داراي نقاطي مي باشد که امکان ورود به آنها وجود ندارد. همين اشيا نيز باعث پيچيده شدن فرآيند مسيريابي مي شوند. (مثلاً کاراکتر شما نمي تواند وارد ديوار يا يخچال شود، از طرفي در هنگام حرکت در اتاق ها، بايد مبلمان را تشخيص داده و از کنار آنها - و نه از درون آنها - عبور کند، همان طوري که انسانها در دنياي واقعي حرکت مي کنند، که البته همين عبور از کنار موانع، بخش دشوار الگوريتم است)
*پس از اينکه ناحيه جستجو مشخص شد، بايد اين ناحيه را به قسمت هاي کوچکتري تبديل کنيد.
اين نواحي کوچک که به عنوان سلول (cell) يا گره (node) شناخته مي شوند، اساس کار اين الگوريتم هستند. به طور معمول هرچه تعداد اين قسمت هاي کوچک بيشتر باشد، دقت عمليات نيز افزايش خواهد يافت (که باعث کاهش سرعت پردازش نيز خواهد شد). براي درک بهتر روند کار اين الگوريتم، مراحل کار در قالب چند شکل نشان داده شده اند. اگرچه ما در اينجا ناحيه جستجوي خود را به تعدادي مربع کوچک تقسيم کرده ايم (تصوير 1) ولي در حالت کلي، اين سلول ها مي توانند هر شکلي داشته باشند (تعيين شکل و اندازه اين سلول ها به شکل محيط و نحوه حرکت بستگي دارد، اما عموماً تقسيم ناحيه جستجو به مربع هاي کوچک، بهترين نتيجه را دارد). در اين شکل مربع سبز مبدأ حرکت، خانه هاي آبي ديوار (يعني مانع حرکت)، و مربع قرمز نيز مقصد مي باشد.
*همان طور که گفته شد، اين الگوريتم يک سري تست هاي تکراري را انجام مي دهد تا در نهايت به هدف مورد نظر برسد (البته در صورت امکان، يعني در صورت وجود يک مسير). در تصوير دوم 8 خانه اطراف خانه سبز، با فلش هاي مخصوصي نشان داده شده اند. ما در اولين گام، فاصله هر يک از اين 8 خانه تا مقصد (يعني سلول قرمز) را بررسي مي کنيم.
سپس از بين اين 8 خانه، نزديکترين خانه را نسبت به مقصد انتخاب مي کنيم. سپس موقعيت اين خانه را ثبت مي کنيم، زيرا در مرحله بعدي تست، بايد از اين خانه به عنوان مبدأ جديد حرکت استفاده کنيم. مجدداً اين تست را براي خانه جديد انتخاب شده انجام مي دهيم (يعني هشت خانه اطراف آن را بررسي کرده و از بين آنها نزديکترين سلول را به مقصد مي يابيم). اين تست تا زماني ادامه مي يابد که به مقصد برسيم.
البته دو نکته را نبايد فراموش کنيم. مسئله اول اينکه در هنگام بررسي خانه هاي اطراف، نبايد خانه هاي مانع را به حساب آوريم. اين سلول ها مي توانند ديوار، اشياء داخل منزل، درخت، رودخانه و يا هر شيء ديگري باشند که شما در حين حرکت نبايد درون آن وارد شويد. اما مسئله دوم هم اينکه نبايد بيش از يک بار وارد هيچ سلولي شويد. يعني در حالت کلي نبايد هيچ خانه اي را بيش از يک بار در مسير خود طي کنيد. به اين منظور مي توانيد کليه خانه هاي مورد استفاده در مسير را در يک آرايه ثبت کنيد، سپس در هنگام انجام مراحل بعدي تست، آن خانه ها را مورد بررسي قرار ندهيد.
در حقيقت اين تئوري پشت پرده الگوريتم *A است که پياده سازي آن به اشکال گوناگوني، امکان پذير است. در تصوير 3 شما مي توانيد فرآيند تست سلول هاي اطراف خانه سبز را مشاهده کنيد.
ضمن اينکه در گوشه هر خانه، فاصله آن خانه تا سلول مقصد، مشخص شده است. شکل 4 نيز کليه تست هاي انجام گرفته براي حرکت از مبداء به مقصد را نشان مي دهد. به اين ترتيب شما مي توانيد هوشمندانه مسير خود را در بين انبوهي از اشياء و در محيط هاي ناشناخته نيز بيابيد. البته کار در همين جا تمام نمي شود! کما اينکه پياده سازي اين الگوريتم بر حسب شرايط مختلف مي تواند بسيار متفاوت باشد.
در ادامه به برخي از نکات مهم در هنگام پياده سازي اين الگوريتم اشاره شده است:
1))يافتن فاصله بين سلول ها در اين الگوريتم اهميت زيادي دارد، اما منظور از فاصله چيست؟ آيا مي توان از فرمول فيثاغورث به اين منظور استفاده کرد؟ يا بايد تعداد مجموع خانه هاي عمودي و افقي موجود در مسير را به عنوان فاصله محسوب نمود؟ اين مسئله اي است که بر حسب نوع محيط و مسير مي تواند متفاوت باشد.
2))اگرچه در بسياري از پياده سازي هاي اين الگوريتم، از ليست هاي پيوندي و انواع آرايه ها براي ثبت و ذخيره کليه نقاط مسير (و انجام تغييرات احتمالي بعدي بر روي آنها) استفاده مي شود، اما شما مي توانيد در ساده ترين حالت، صرفاً شيء مورد نظر خود را بر روي نقطه بعدي مسير قرار دهيد. به اين ترتيب احتياج به ثبت هيچ داده اي نخواهيد داشت. البته در مسيرهاي پيچيده معمولاً اولين مسير يافت شده، بهترين مسير نمي باشد، پس بايد آن را به نحوي اصلاح کنيد.
3))اين الگوريتم از نظر محاسباتي مي تواند زمان بر باشد. پس درصورت امکان از تکنيک هاي ديگري نيز به صورت ترکيبي براي کاهش هزينه محاسباتي استفاده کنيد (مثلاًَ مي توانيد برخي مسيرهاي پيچيده و طولاني را با کدنويسي به صورت توکار در برنامه قرار دهيد، به گونه اي که حرکت بر روي يک سري نقاط از پيش مشخص شده انجام گيرد و احتياجي به انجام تست هاي الگوريتم *A نباشد).
4))اگرچه اين الگوريتم، کوتاهترين مسير را به شما مي دهد، اما اين مسير داراي نقاط شکست بسياري مي باشد. يعني اگر بدون انجام بهينه سازي و برخي تغييرات محاسباتي، آن را بر روي کاراکترهاي خود اعمال کنيد، خواهيد ديد که در هنگام چرخش، حرکاتي بسيار ناگهاني خواهند داشت، علاوه بر اين، برخي اوقات مسيرهاي به دست آمده چندان بهينه نمي باشند. در نتيجه بايد آنها را مورد بهينه سازي قرار دهيد (فرآيندي که اغلب ازپياده سازي اوليه الگوريتم، دشوارتر است).
5))يکي از راه حل هاي رفع مشکل چرخش ناگهاني، ذخيره کليه نقاط حرکتي و حذف نقاطي است که زاويه تندي مي سازند. در نهايت شما مي توانيد مسير اصلاح شده را مورد استفاده قرار دهيد. به اين منظور مي توانيد از ليست هاي پيوندي يا حتي آرايه هاي ساده استفاده کنيد. بي شک پياده سازي زيباي حرکت يک کاراکتر، فرآيندي دشوار مي باشد که انواع محاسبات مثلثاتي، ماتريسي و برداري را در بر مي گيرد.
6))ما در اين تست، هيچ تمايزي بين خانه هاي مختلف قائل نشديم، يعني احتمال انتخاب هر يک از خانه ها (البته نزديکترين خانه ها به مقصد)، مساوي مي باشد.
اما بيشتر اوقات شما بايد بين خانه هاي مختلف، فرق قائل شويد. اين تمايز قائل شدن بين خانه ها که در اصطلاح برنامه نويسي، به هزينه دهي (Costing) معروف است، يکي از پيچيده ترين بخش هاي اين الگوريتم است. مثلاً مي توانيد هزينه هاي ورود به خانه هاي مورب و مستقيم را نامساوي در نظر بگيريد.
7))همچنين شما مي توانيد با تهيه يک نقشه از محيط مورد نظر خود از ديد بالا، نقاط قابل حرکت و نقاط غيرقابل حرکت را به الگوريتم ارائه کنيد. به اين منظور مي توانيد از فرمت فايل RAW (که در فوتوشاپ قابل ساخت است) استفاده کنيد. اين فرمت هيچ داده اي به عنوان سرباره (header) ندارد و شما مي توانيد با تهيه يک فايل سياه و سفيد از محيط مورد نظر خود (يعني رندر صحنه به صورت Plan با رنگ هاي سياه و سفيد.مثلاً رنگ هاي سياه مشخص کننده موانع و نقاط غيرقابل ورود، و مناطق سفيد مناطق قابل حرکت باشد. حتي مي توانيد هزينه ورود به نقاط مختلف نقشه را با رنگ هاي خاصي مشخص کنيد)، به راحتي داده هاي محدوده جستجوي مورد نظر خود را برنامه بدهيد.
8))يکي از مهمترين بخش هاي اين الگوريتم، فرآيند محاسبه نزديکترين مسير مي باشد. به اين منظور راهکارهاي گوناگوني از جمله روش منهتن، روش نيوتن، روش فيثاغورث و نيز روش جستجوي عمقي (Heuristic) وجود دارد، ضمن اينکه در بسياري از بازي ها، برنامه نويسان روش هاي اختصاصي را براي محيط هاي مورد نظر ايجاد کرده اند.
هدف از اين مقاله، صرفاً معرفي اوليه الگوريتم قدرتمند و کارآمد بود. ضمن اينکه اگر شما بتوانيد به خوبي مفهوم اين الگوريتم را دريابيد، مي توانيد از آن براي اهدافي به غير از هوشمندسازي کاراکترها (همچنين فعاليت هاي پردازش تصوير) نيز استفاده کنيد. اين الگوريتم در مسائل نظري و از جمله حل مسائل رياضي (محاسبه مساحت و حجم اشکال و اشياء سه بعدي پيچيده) نيز کاربرد دارد. به طور کلي مي توان گفت *A مفهومي مي باشد که در بسياري از شاخه هاي علوم گسترش يافته و با توجه به انعطاف بالا در پياده سازي، هنوز نيز امکان بهره گيري بيشتر از آن وجود دارد.
منبع:ماهنامه دانش و کامپيوتر، شماره 85 /س