بازي با هوش‌ بررسي هوش‌مصنوعي در بازي‌هاي كامپيوتري‌

واضح آرشیو وب فارسی:سایت ریسک: R£ɀД14-07-2007, 07:12 AMhttp://www.shabakeh-mag.com/Data/1003007_b.jpgاشاره : در دنياي امروز يكي از مهم‌ترين قسمت‌هاي علم پزشكي، طراحي و بازسازي اجزاي مختلف بدن است. حال اين سؤال مطرح است كه در دنيايي كه ديگر، مواردي مانند نقص عضو و از بين رفتن حالت هدايتي- الكتريكي قلب، فشار بالاي جمجمه و حتي انواع مختلف فلج‌هاي دست و پا، براي بيمار، كمتر محدودكننده است و تا حدودي ديگر يك نقيصه محسوب نمي‌شود، بازسازيِ احساسات، عواطف و تفكرات چه جايي دارد؟ بشر تا چه ميزان توانسته است مسائل روحي خود را در نمونه‌اي آزمايشگاهي توليدكند؟ آيا مي‌توان اميدوار بود كه در آينده گوشه‌اي از عواطف آدمي در يك ماشين، جمع‌آوري شود؟ شايد جواب اين سؤالات با پيشرفت‌هايي كه در بازسازيِ هوش در كامپيوتر شده‌است، در آينده تا حدودي دور از دسترس نباشد. هوش‌مصنوعي، به‌ويژه آن‌چه كه در بازي‌هاي كامپيوتري شاهد آن هستيم، روز به روز در حال نزديك شدن به مدل واقعي خود است. يك بازي‌ كامپيوتري خوب، بازي‌اي ‌است كه هر نكته‌اي را در اين دنياي مجازي بهتر و واقعي‌تر به دنياي حقيقي ربط دهد. به همين منظور داشتن حريفي قدرتمند و انسان‌نما لازمه بازسازي هوش و تفكرات انساني است. اين سؤال كه <حريف كامپيوتري شما چه قدر مي‌فهمد؟> امروزه قبل از انجام هر بازي به فكر بازي‌كننده‌ها ميآيد؛ زيرا قرار است قسمتي از وقت و زندگي او معطوف اين بازي شود و اگر حريفش قدرتمند نباشد، عملاً اين وقت هدر رفته ‌است. درست ‌مانند اين است كه يك قهرمان شطرنج با كسي كه اولين بار است اين بازي را انجام مي‌دهد روبه‌رو شود. پس در كنار داشتن گرافيك، صدا و محيط بازي خوب، داشتن هوش‌مصنوعي مناسب نيز براي يك بازي كامپيوتري از محاسن آن بازي به‌حساب مي‌آيد. در اين مقاله سعي شده ‌است مفاهيم و كاربرد‌هاي ابتدايي هوش‌مصنوعي در بازي‌هاي كامپيوتري شرح داده‌ شود. گفتني‌ است براي تهيه اين مقاله از مطالب سايت‌هاي codeproject و gameai نيز استفاده‌شده است. عناصر هوش‌مصنوعي به كاررفته در بازي‌هاي كامپيوتري براي رسيدن به جايگاهي كه در حال حاضر در آن قرار دارند، راه زيادي را طي كرده‌اند. در ابتدا، سيستم‌هاي پيشرفته برپايه مجموعه‌اي از قوانين عمل مي‌كردند كه مستقيماً در كدهاي بازي نوشته‌شده بودند يا به‌ صورت متن‌هايي رفتاري كه توسط كدهايي خاص ترجمه مي‌شدند. تمام اين اعمال به‌صورت مشترك برمبناي انتخاب متناسبي از فاكتور‌هاي تصادفي، صورت مي‌گرفت. اين زمان درست همزمان با تولد بازي‌هايي به‌يادماندني و بي‌نظير مانند River Raid ،Donkey Kong ،Boulder-Dash و بسياري از بازي‌هاي جذاب براي كاربران ماشين‌هاي هشت‌بيتي در دهه 1970 بود. قدم ديگر در پروسه توسعه هوش‌مصنوعي، معرفي روش‌هاي ساده علوم كامپيوتري بود كه از ميان اين روش‌ها مي‌توان به روش Finite State Machine اشاره كرد كه هنوز محبوب است و به ‌صورت محدود كماكان مورد استفاده قرار مي‌گيرد. اساس اين روش، برپايه توصيفِ رفتاريِ دشمناني بود كه در بازي‌ها توسط كامپيوتر و عليه بازي‌كننده كنترل مي‌شدند. با توجه به نياز روزافزون بازي‌كننده‌ها، روند رشد بازي‌ها نيز پيچيده‌تر مي‌شد، و اين به لطف استفاده بيشتر از الگوريتم‌هاي پيشرفته كامپيوتري است. ظهور قلمرو بازي‌هاي ‌RTS (استراتژي‌هاي بي‌درنگ) موجب استفاده گسترده از الگوريتم‌هايي شد كه بهترين مسير را بين دو نقطه از نقشه اين نوع بازي‌ها تعيين مي‌كردند. از سوي ديگر، پيشرفت‌هاي فني سريع و افزايش استفاده از پردازشگر‌هاي قوي‌تر در كامپيوتر‌هاي خانگي نيز امكان استفاده گسترده‌تر از نرم‌افزارها براي استفاده از هوش‌مصنوعي در بازي‌ها را فراهم مي‌كرد. اولين مجموعه بازي‌هاي كامپيوتري و هوش‌مصنوعي به كاررفته در آن‌ها بايد طوري طراحي مي‌شدند كه روي ماشين‌هاي ساده آن زمان قابل اجرا باشند: ماشين‌هايي كه اكثراً فركانسِ پردازشگرهايشان بيشتر از دومگاهرتز نبود. با آمدن كامپيوتر‌هاي شخصي اوليه امكان استفاده از برنامه‌ها و امكانات بهتر، ميسر شد. بعد از اين‌كه پي‌سي‌هاي مجهز به پردازشگر‌هاي 386 و 486 به عنوان كامپيوتر‌هاي استاندارد خانگي مورد استفاده قرار گرفتند، براي نويسندگان برنامه‌ها هم امكانات گسترده‌تري فراهم شد و اين آغاز مسابقه‌اي بود براي سازندگان بازي‌هاي كامپيوتري. براي مدتي طولاني بهترين مقياس براي خوب بودن كيفيت يك بازيِ كامپيوتري، خوب بودن كيفيت گرافيكيِ‌ آن بازي محسوب مي‌شد؛ گرچه بعد‌ها اين مقياس تغيير كرد و تنها خوب بودن گرافيك، طراحي انيميشني كاراكتر‌ها و صداي بازي، نمايانگر بالابودن‌ كيفيت بازي نبود. امروزه يكي از مهم‌ترين عناصر بازي‌هاي كامپيوتري، بدون ترديد، <هوش‌مصنوعي> آن بازي شناخته مي‌شود. جريان و پروسه ساخت يك بازي‌ كامپيوتري نيز در طول اين سال‌ها دستخوش تغييرات فراواني شده ‌است. به‌طور مثال، در گذشته طراحي هوش‌مصنوعي يك بازي تقريباً يك امر بي‌اهميت انگاشته مي‌شد و طراحان بازي‌ها ترجيح مي‌دادند مرحله وارد كردن هوش‌مصنوعيِ ناقص بازي را در مراحل پاياني تهيه بازي انجام دهند، ولي امروزه طراحي مدل‌هاي هوش‌مصنوعي و ارتباطي كه اين قسمت با ديگر اجزاي بازي خواهد داشت، يكي از مهم‌ترين مراحل طراحي بازي به شمار مي‌رود. به طوري كه از ابتداي توليد بازي به آن فكر مي‌شود. در واقع اهميت اين قسمت به قدري زياد است كه حداقل يكي از اعضاي برنامه‌نويسي از ابتداي توليد يك بازي به صورت تمام وقت استخدام مي‌شود تا بر مراحل توسعه و ساخت هوش‌مصنوعي بازي و ارتباط آن با ديگر قسمت‌ها نظارت كامل داشته باشد. در حال حاضر، با توجه به اين‌كه در هر خانه‌اي مي‌توان يك كامپيوتر پنتيوم چهار با پردازشگري حدود سه تا چهارگيگاهرتز پيدا كرد، انتظار مي‌رود بازي‌هاي كامپيوتري از پيشرفته‌ترين و عظيم‌ترين سيستم‌هاي هوش‌مصنوعي بهره بگيرند. سيستم‌هايي مانند شبكه‌هاي عصبي، الگوريتم‌هاي ژنتيك‌ و منطق فازي. در عصرِ بازي‌هاي اينترنتي و شبكه‌اي، هوش‌مصنوعي در بازي‌هاي كامپيوتري هم وظايف جديد پيدا كرده است. يكي از اين وظايف اين است كه يك حريف كامپيوتري،‌ با سبك و استراتژيِ بازي منحصر به خود، بايد از يك بازي‌كننده انساني كه در آن سوي ارتباط اينترنتي در حال بازي كردن است، قابل تمايز نباشد. بازي‌هاي تأثيرگذار در هوش‌مصنوعي هنگامي كه در مورد انقلاب هوش‌مصنوعي صحبت مي‌شود، بايد به بازي‌هاي مهمي كه در تاريخچه اين انقلاب سهم بسزايي داشته‌اند نيز اشاره شود. يكي از مهم‌ترين اين بازي‌ها كه هوش‌مصنوعي را در دهه 1990 ميلادي دگرگون ساخت، بي‌شك سري بازي‌هايWarCraft بود كه توسط شركت Blizzard ساخته شد. اين بازي اولين بازي‌اي بود كه الگوريتم‌هاي مسيريابي ‌را در هوش‌مصنوعي به كار مي‌برد. يكي از اين الگوها مقياس‌هاي عالي‌اي بود كه براي صدها واحد مشغول در صحنه‌هاي عظيم جنگي اين بازي طراحي شده‌بود. بازيِ SimCity كه توسط Maxis ساخته شد، اولين بازي‌اي بود كه ثابت كرد كه مي‌شود در يك بازيِ كامپيوتري از فناوري‌هاي حيات مصنوعي استفاده كرد. يكي ديگر از پيشرفت‌هاي هوش‌مصنوعي در بازي‌هاي كامپيوتري با بازي Black and White به وجود آمد كه توسطLionhead Studios در سال 2001 ساخته شد و در آن براي اولين بار، فناوريِ يادگيريِ شخصيت‌‌هاي هدايت شونده توسط كامپيوتر مورد استفاده قرار مي‌گرفت. هوش‌مصنوعي در بازي‌هاي تيراندازيِ اول شخص http://www.shabakeh-mag.com/Data/Gallery/s71_Main_6_s.jpg شكل 1 بازي‌هاي تيراندازيِ اول شخص يا First Person Shooters معمولاً از سيستم هوش‌مصنوعي با ساختار لايه‌لايه استفاده مي‌كنند. لايه‌هايي كه در قسمت زيرين قرار دارند، وظايف ابتدايي را به ‌عهده دارند. از اين وظايف ابتدايي مي‌توان به تعيين بهترين مسير تا هدف (كه خود توسط لايه‌هاي بالايي‌تر تعيين مي‌شود) و اجراي متناسب سكانس‌هاي انيميشنِ كاراكتر، اشاره كرد. لايه‌هاي بالايي‌تر مسئولِ اجرايِ برهان‌هاي تاكتيكي و انتخاب رفتاري است كه عنصر استفاده‌كننده از هوش‌مصنوعي (به طور مثال شخصيت‌هاي دشمن در بازي‌ها) برطبق اين تاكتيك و استراتژي عمل مي‌كند. سيستم مسيريابي معمولاً برپايه نمايش‌هاي هندسي‌اي است كه دنياي بازي را شرح مي‌دهد. هر راس اين نمودار‌ها نمايانگر محلي منطقي از بازي (مانند اتاقي از يك ساختمان يا قطعه‌اي از ميدان جنگ) محسوب مي‌شود. وقتي به شخصيتي دستور داده مي‌شود كه به نقطه‌اي از نقشه بازي برود، عوامل هوش‌مصنوعي با استفاده از نمودار‌ها، نقاط ثانويه هدايتي ‌‌(Subsequent Navigation Points) را به‌ دست مي‌آورند و با هدايت پي‌درپي اين شخصيت به طرف اين نقاط، نهايتاً آن را به نقطه هدف مشخص مي‌رسانند. در حين عبور از اين نقاط هدايتي، هوش‌مصنوعي همچنان وظيفه دارد از مسير‌هاي منطقي براي رسيدن به نقطه بعدي استفاده كند و كاراكتر را از موانع متحرك يا ثابتي كه در مسير بين دو نقطه در سر راهش ظاهر مي شوند نيز عبور دهد. در شكل 1، نمايش مسيريابي را در بازي‌هاي RTS در تصويري ساده مي‌بينيد. سپس سيستم گرافيكي وظيفه دارد اجراي مناسبي از سكانس‌هاي اجرا شده در سرعت معيني از انيميشن را با توجه به دستورات ارائه‌شده توسط هوش‌مصنوعي نمايش ‌دهد. اين سيستم همچنين بايد بتواند سكانس‌هاي متحركِ مختلفي را براي اجزاي مختلف بدن شخصيت‌ها اجرا كند. نمونه‌اي از اين سيستم را مي‌توانيد در صحنه‌اي از يك بازي جنگي فرض كنيد كه در آن سربازي همزمان مي‌دود و به طرف دشمن نشانه مي‌گيرد، تيراندازي مي‌كند و اسلحه خود را در حين دويدن پر مي‌كند. بازي‌هايي از اين دست اغلب از سيستم كينماتيك معكوس ‌(Inverted Kinematics System) استفاده مي‌كنند. يك سيستم انيميشنيِ IK مي‌تواند به طور مناسب پارامتر‌هاي موقعيت‌يابي محوري يك انيميشن را محاسبه كند. درنتيجه با وجود اين سيستم، دست يك شخصيت مي‌تواند جسمي را كه در درون آن است نگه‌دارد يا ميز، قفسه، شيئي‌ را در بر مي‌گيرد كه روي آن‌ها قرار دارد. وظايف لايه‌هاي بالايي به كاررفته در هوش‌مصنوعي، استفاده مناسب از نوع رفتاري ا‌ست كه براي هر موقعيت توسط كامپيوتر استفاده مي‌شود. به‌طور مثال، در همان بازيِ جنگي اين لايه‌ها، انتخاب مي‌كنند كه سرباز‌ي از سرباز‌هاي دشمن در يك جا نگهباني كند، وارد نبرد شود، فرار كند يا به نقطه‌اي ديگر از نقشه برود تا دشمنش را پيدا كند. هنگامي كه هوش‌مصنوعي تصميم گرفت كدام رفتار براي موقعيت ايجاد‌شده بهتر است، يك لايه‌ زيرين انتخاب مي‌شود كه بهترين تاكتيك را براي انجام اين تصميم انتخاب كند. به‌طور نمونه، در مثال قبلي اگر هوش‌مصنوعي تصميم بگيرد كه سرباز وارد نبرد شود، اين لايه زيرين بهترين شيوه مبارزه را براي او تعيين مي‌كند. مثلاً تصميم مي‌گيرد كه او آرام آرام به شخصيت بازي‌كننده نزديك شود و به او تيراندازي كند، يا در گوشه‌اي پنهان شود و منتظر شود كه شخصيت بازي‌كننده به حوزه ديدش برسد و سپس به‌طرفش تيراندازي كند يا اين‌كه به طرف او بدود و تيراندازي كند. هوش‌مصنوعي در بازي‌هاي استراتژيِ بي‌درنگ در بازي‌هاي استراتژيِ بي‌درنگ ‌(Real Time Strategy) امكان تشخيص مدل‌ها و لايه‌هاي متعددِ هوش‌مصنوعي وجود دارد. يكي از اساسي‌ترين اين مدل‌ها يك سيستم مؤثرِ راهيابي براي كاراكتر‌ است كه بعضي وقت‌ها، در كسري از زمان، اين سيستم ‌بايد جوابگوي مشكل حركت صدها كاراكتر روي نقشه اين‌گونه بازي‌ها باشد. بايد توجه داشت كه مسير‌يابي اين سيستم چيزي فراتر از مسيريابي ساده‌اي است كه تنها كاراكتري را از نقطه A به Bمي‌رساند؛ زيرا در ازدحامِ نقشه، مهم‌ترين نكته در حركت، تشخيص مواجهاتِ اين واحد‌هاي كوچك در حين عبور بين دو نقطه با هم و متعاقب آن اداره آن‌ها است به نحوي كه به هم برخورد نداشته باشند. اين الگوريتم‌ها معمولاً بر پايه نقشه بازي استوار است كه اين مسئله خود توسط عناصري گرافيكيِ رشته‌مانند و چهارگوش معرفي مي‌شوند. اين رشته‌هاي مستطيل‌شكل توسط تور‌هايي شبكه‌اي، عوامل تصحيح شده از لحاظ اندازه را در محيط تعيين و معرفي مي‌كنند. در سطوح بالاتر سلسله ‌مراتب هوش‌مصنوعي اين بازي‌ها، ماژول‌هايي طراحي شده است كه وظيفه آن‌ها تعيين مسائل اقتصاديِ بازي، توسعه و از همه مهم‌تر، مدلي براي آناليز نقشه بازي، است. اين همان ماجولي است كه نوع زمين هر ناحيه از نقشه و عناصري كه روي آن ساخته مي‌شوند را آناليز مي‌كند. به‌طور مثال، در محلي از نقشه كه دريا قرار دارد، اين ماجول اجازه مي‌دهد ناوگان دريايي ساخته شود. اين ماجول زمان انجام ساختن يك شهر يا ديوار‌هاي حفاظتي و باروها را نيز تعيين مي‌كند. هوش‌مصنوعي در بازي‌هاي ورزشي عملاً كامپيوتر مي‌داند كه در پيچ بايد سرعتش را كم كند؛ زيرا در حال پيچيدن اگر سرعتش از حدي بيشتر باشد، كنترل ماشين را از دست خواهد داد. حال بسته به اين‌كه كامپيوتر از حريف انسانيش عقب‌تر است يا جلوتر، در نوع پيچيدن در اين گونه صحنه‌ها تصميم‌گيري مي‌كند. اگر او عقب‌تر باشد، سعي مي‌كند با روش بهينه‌سازيِ پيچيدن كه شامل بريدن پيچ‌ها و حركت از داخلي‌ترين مسير است، كمي مسافت عقب‌افتاده را جبران كند. در غير‌اين صورت، به روش عادي مي‌پيچد. نوع تقسيم‌بندي مسير جاده توسط هوش‌مصنوعي و دو نوع پيچيدن اتومبيل كامپيوتر در پيچ‌ها را در شكل شماره2 مي‌بينيد.نوع ديگر تقلب كامپيوتر در اين بازي‌ها هم در استفاده از راه‌هاي ميانبر ديده مي‌شود. http://www.shabakeh-mag.com/Data/Gallery/s71_Main_5_s.jpg شكل 2 هنگامي كه كامپيوتر از حريف انساني خود عقب مي‌افتد، بيشترين استفاده را از اين گونه راه‌ها كه مسير را برايش كوتاه‌تر مي‌كند، خواهد داشت. در شكل 3 نمونه‌اي از اين شيوه را مي‌بينيد. http://www.shabakeh-mag.com/Data/Gallery/s71_Main_4_s.jpg شكل 3 با توضيحاتي كه داده شد، تجاربي كه از بازي‌هاي ماشين‌سواري تا به حال كسب كرده‌ايد، كمي ملموس‌تر مي‌شود. به طور مثال، در بازي‌اي مانند Need For Speed كمتر پيش مي‌آيد كه مسافت زيادي از بهترين حريف خود جلوتر باشيد. زمان‌هايي پيش مي‌آيد كه اين حريف شما به علت تصادف يا منحرف شدن از جاده، مسافت زيادي از شما عقب مي‌ماند، ولي با پيگيري او روي نقشه كوچك بازي مي‌بينيد كه با سرعتي غيرمنطقي به شما نزديك و نزديك‌تر مي‌شود. در واقع چيزي كه فاصله او را با شما كم مي‌كند سرعت زياد او نيست، بلكه نوع بهينه‌سازي رانندگي او است. دو خصيصه مهم ديگر هوش‌مصنوعي در اين نوع بازي‌ها عبارتند از: ●‌‌ توانايي آناليز سطوح جاده براي شناسايي موانعي كه روي آن قرار دارند. ‌● هماهنگيِ محكمي كه نوع رانندگي كامپيوتر را با مدل فيزيكي طراحي شده بازي تنظيم مي‌كند. مدل فيزيكي اين امكان را فراهم مي‌كند كه هنگامي كه اتومبيل كامپيوتر بنا به هر دليلي، از جاده منحرف شد، هوش‌مصنوعي به طرز مناسب و منطقي‌اي كنترل آن را مجدداً به ‌دست بگيرد تا او از كورس رقابت بيشتر عقب نماند. تقلب‌هاي مشابه موارد ذكرشده در ديگر بازي‌هاي ورزشي نيز ديده‌ مي‌شود. براي همين، در بازي‌‌هاي FIFAمي‌بينيد كه هنگامي كه كامپيوتر از شما عقب است، بهتر بازي‌ مي‌كند. در اكثر مواقع يك بازيكن كامپيوتري در اين نوع بازي‌ها، قبل از اين كه حركت ورزشي خود را انجام دهد، نقشه‌اي از حركت خود را به‌صورت آماده و تعيين شده در اختيار دارد. اين حركت بسته به اين‌كه از حريف انسانيش جلو است يا عقب تعيين شده ‌است. به‌طور مثال، در بازي‌هاي فيفا، هنگامي كه بازيكني قصد دارد به طرف دروازه شما شوت كند، سرنوشت اين شوت از قبل مشخص است. البته عكس‌العمل شما نيز مي‌تواند روي آن تأثير گذار باشد و همين مسئله باعث پيروزي انسان بر كامپيوتر مي‌شود. درست مانند شطرنج‌بازي كه مي‌تواند بهترين حريف كامپيوتري خود را شكست دهد، اينجا هم شما با عكس‌العمل‌هاي به‌موقع خود مي‌توانيد هوش‌مصنوعي كامپيوتر را با هوش طبيعي و كامل‌تر خود شكست دهيد. هوش‌مصنوعي در بازي‌هايي كه برد و باخت آن توسط داوري انجام مي‌شود (مانند بوكس در صورتي كه حريف ناك‌اوت نشود) نيز توسط قوانيني كه از قبل براي اعمال آن ورزش در هوش‌مصنوعي تعبيه مي‌شود، محاسبه مي‌شود و برنده را مشخص مي‌كند. بعد از انجام تمام مراحل گفته شده، سناريوي از قبل تعيين‌شدهِ يك بازيكنِ كنترل‌شده توسط كامپيوتر، به وسيله سيستم انيميشن شخصيت‌ها بازسازي مي‌شود. محبوب‌ترين الگوريتم‌هاي هوش‌مصنوعي به كار رفته در بازي‌هاي كامپيوتري در ادامه اين مقاله دو نمونه از محبوب‌ترين الگوريتم‌هاي هوش‌مصنوعي معرفي مي‌شود كه به وفور از آن‌ها در طراحي هوش‌مصنوعي بازي‌هاي كامپيوتري استفاده مي‌شود. با دانستن مطالبي در مورد اين الگوريتم‌ها، شايد شما هم ترغيب شويد با طراحي يكي از آن‌ها، يك بازيِ FPS و RTS ساده بسازيد. اولين الگوريتم‌ از اين دست، *A نام دارد كه سلسله جست‌وجوهاي سريعي را براي پيدا كردن بهترين مسير بين دو نقطه انجام مي‌دهد. الگوي ديگر ماشين با حالات محدود ‌(Finite State Machine) نام دارد كه بسيار مورد استفاده قرار مي‌گيرد و وظيفه‌اش آماده‌كردن سناريو‌هاي رفتاري براي حريفاني‌ است كه توسط كامپيوتر در بازي كنترل مي‌شوند. در مرحله بعدي اين رفتارها توسط ماژول‌هاي سطوح پايين، مانند ماجول رهيابي، پردازش مي‌شوند. الگوريتمِ*A موضوع پيداكردن راه بين دو نقطه A و B در اكثر بازي‌هاي كامپيوتري، غير از بازي‌هاي ورزشي و تعداد انگشت‌شماري از بازي‌ها، مشكل كليدي‌اي محسوب مي‌شود. الگوريتم‌هاي اين گروه، در آن واحد جزئي از سطوح پايين‌تر هوش‌مصنوعي بازي هستند. همچنين به عنوان پايه‌اي براي ساختار رفتار‌هاي پيچيده‌تر و هوشمند‌تر، مانند تصميم‌هاي استراتژيك، حركت در آرايش‌هاي جنگي و گروهي و بسياري ديگر از رفتار‌هاي سطح بالاتر، مورد استفاده قرار مي‌گيرد. اين الگوريتم امروزه به طور چشمگيري پيشرفت كرده‌است. به طوري كه در بازي‌هاي كامپيوتري كنوني، الگوريتم*A جايگاه ويژه‌اي دارد. اساس اين الگوريتم برپايه <جست‌وجوي گرافيكي بين‌گرهي> استوار است. اين سيستم از يك ارزيابي غيرمستدل(Heuristic Estimate) بهره گيري مي‌كند. اين الگوريتم اولين بار در سال 1968 همزمان توسط سه رياضيدان به نام‌هاي Peter Hart ،Nils Nilsson و Bertram Raphael شرح داده شد. دنياي واقعي، تقريباً در تمامي بازي‌هاي كامپيوتري، بسته به نوع بازي، مي‌تواند با خطوطي گرافيكي بازسازي شود. در بازي‌هاي RTS، دنياي بازي معمولاً از آرايشي دو بعدي تشكيل شده‌است و نقشه بازي شامل مربع‌هاي فراواني مي‌شود كه هر يك از آن‌ها مطابق ‌است با نقشه چهارگوش بازي. هر عنصر اين سيستم (جز عناصر مرزي) هشت عنصر همسايه دارند. با استفاده از اين‌گونه مدل نمايشي در بازي‌هاي RTS، مي‌توانيم گرافيكي ايجاد كنيم كه در آن هر يك از اين عناصر به راس گرافيك كل نقشه مربوط باشد. لبه‌هاي هر يك از عناصر گرافيكي (كه هريك با عنصر همسايه خود مجاورت دارد) امكان يا عدم امكان حركت يكي از اجراي نقشه را به عنصر همسايه نمايش مي‌دهد. در استراتژي‌هاي بي‌درنگ ما معمولاً يكي از رئوس اين عناصر گرافيكي را به عنوان محلي كه كوچك‌ترين واحد بازي در آن جاي مي‌گيرد، قلمداد مي‌كنيم. در بازي‌هاي FPS رئوس عناصر گرافيكي معمولاً محل‌ها يا اتاق‌ها هستند و توسط اين رئوس است كه اين محل‌ها/ اتاق‌ها با هم ارتباط پيدا مي‌كنند. الگوريتم‌هايي فراواني براي پيدا كردن بهترين مسير‌يابي در اين عناصر گرافيكي وجود دارد. يكي از ساده‌ترين اين الگوريتم‌ها كه آتش در چمنزار ‌(Fire on the Prairie) ناميده مي‌شود، به اين صورت كار مي‌كند كه چندين دايره متوالي را در نقطه شروع مي‌سازد و در هر مرحله دايره‌هاي ديگري مي‌سازد كه قطر آن‌ها بزرگ‌تر از دايره‌هاي قبلي است. اين دواير متوالي و عناصر مربوط به هر يك، به‌تدريج بزرگ‌تر مي‌شوند و داراي شاخص‌هاي بزرگ‌تري نيز مي‌شوند. حال، با حركت به سوي طرف مقابل و با پيروي از اين قانون كه در هر قدم ما به نقطه‌اي نزديك‌تر از نقشه حركت مي‌كنيم و شاخص اين نقطه كوچك‌تر است، ما به نقطه شروع مي‌رسيم. در نتيجه توسط عناصري كه توسط آن‌ها ما نقشه‌ را طي كرده‌ايم و بار ديگر از آن مسير بازگشته‌ايم، كوتاه‌ترين مسير بين نقطه شروع و نقطه هدف به وجود مي‌آيد. با آزمايش روشي كه اين الگوريتم كار مي‌كند، متوجه خواهيم شد كه گرچه اين روش داراي برتري سادگي است، مشكل جدي‌اي هم دارد. مسيري كه اين الگوريتم در مثال ذكر‌شده پيدا كرده‌است تنها از پنج خانه نقشه بازي تشكيل شده‌ و اين سيستم براي اين كار 81 خانه را مورد آزمايش قرار داده ‌است. حال فرض كنيد كه در نقشه‌اي كه متشكل از 256 خانه عرضي و طولي است، ‌بايد 65536 خانه مورد آزمايش قرار گيرد تا مسير مشخص گردد! در شكل 4 مي‌بينيد كه دايره شاخص شماره 4 توسط يك الگوريتم مسير‌يابي ساده به هدف مورد نظر رسيده‌است. بايد توجه داشت در اين الگوريتم بهترين راه الزاماً نزديك‌ترين راه نيست. اين الگوريتم غير از مسير‌يابي، مي‌تواند فاكتور‌هاي ديگري همانند نوع زمين بازي را نيز مشخص كند. (به طور مثال، يك تانك در بازي‌هاي استراتژي در زمين معمولي تندتر از زمين گل‌آلود حركت مي‌كند). http://www.shabakeh-mag.com/Data/Gallery/s71_Main_3_s.jpg شكل 4 از ديگر استفاده‌هاي اين الگوريتم، مي‌توان به تغيير محدوديت زاويه‌هاي دوربين و نمايش تعداد بيشتري از واحد‌ها در يك زمان، اشاره كرد. همچنين اين الگوريتم شرايطي را فراهم مي‌كند كه واحد‌ها نتوانند از نقاط غيرقابل عبور نقشه عبور كنند. البته نبايد فراموش كرد كه بهترين استفاده از اين الگوريتم همان راهيابي بين دو نقطه است. در زير شبه‌كد‌ها يا Psudocodeهاي الگوريتم *A را مشاهده مي‌كنيد: http://www.shabakeh-mag.com/Data/Gallery/s71_Main_7_s.jpg به علت مشكل محاسباتي كه در بالا براي اين الگوريتم توضيح داده شد، روش‌ها سایت ما را در گوگل محبوب کنید با کلیک روی دکمه ای که در سمت چپ این منو با عنوان +1 قرار داده شده شما به این سایت مهر تأیید میزنید و به دوستانتان در صفحه جستجوی گوگل دیدن این سایت را پیشنهاد میکنید که این امر خود باعث افزایش رتبه سایت در گوگل میشود

این صفحه را در گوگل محبوب کنید

[ارسال شده از: سایت ریسک]

[مشاهده در: www.ri3k.eu]

[تعداد بازديد از اين مطلب: 272]