نقشه نفوذ (Influence Map) یک نوع نمایش دانش ایجنت‌ها از جهان خود برای بدست آوردن استراتژی بهینه است. در بازی‌های رایانه ای نقشه نفوذ مشخص می‌کند، نیروهای بازیکن درچه مکان‌هایی مستقر شده‌اند، نیروهای دشمن کجا هستند و یا در چه مکان‌هایی ممکن است وجود داشته باشند، مرز میان نیروهای بازیکن و دشمن چه مکانهایی است، بزرگترین نبردها در چه مکان‌هایی اتفاق افتاده است، چه مکان‌هایی هنوز تجسس نشده است، دشمن در آینده به احتمال زیاد از چه مکان‌هایی نفوذ می‌کند، مناطقی که دارای موقعیت استراتژیک هستند را معرفی میکند، نقاط ضعف دفاعی دشمن و مناطق آسیب‌پذیر را مشخص میکند، مناطق مسدود1 بر روی زمین را پیدا کند و ویژگی‌های بامعنی دیگری را - که انسان به کمک بصیرت و تمرین آنها را کشف می‌کند - عرضه می‌کند. در این روش یک ایجنت از تمامی این اطلاعات استفاده می‌کند و به صورت بهنگام 2 اطلاعات را از محیط بازی دریافت می‌کند و بر اساس آنها بهترین استراتژی را انتخاب می‌کند[1].

شکل الف - تکنیک نقشه نفوذ اولین بار در سری بازی‌های KillZone استفاده شده‌اند.

۱. مقدمه


سبک بازی‌‌های استراتژیک بهنگام 3 ژانری است که در آن بازیکن به منظور فائق آمدن بر دشمن نیاز به ساختن یک زیربنای اقتصادی (بدست آوردن منابع و ساختن پایگاه) و یک پایگاه نظامی (برای آموزش واحدهای نظامی) و به طور کلی انتخاب استراتژی بهینه می‌باشد. بازی‌های RTS محیطی نامعین دارند، تقریبا قابل مشاهده هستند و دارای فضای حالتی بسیار عظیم هستند. بنابراین در مقایسه با بازی‌های تخته‌ای، چالش‌های بیشتری برای هوش مصنوعی ایجاد می‌کنند. یکی از این چالش‌ها کنترل گروه می‌باشد. چگونه می‌توان به صورت بهینه یک جوخه را کنترل کرد و یا رفتارهای استراتژیک و تاکتیکال پیچیده را در محیطی بهنگام شبیه‌سازی کرد. اینها هنوز هم مسائلی باز در تحقیقات هوش مصنوعی هستند[4].
تجربه نشان داده است کلید اساسی انجام یک تصمیم‌گیری کارا تنها داشتن بهترین داده‌ها نیست، بلکه نحوه ارائه داده‌ها به روش درست نیز اهمیت دارد. داده‌های خام تا زمانی که به اطلاعات طبقه‌بندی شده تقسیم نشوند، غیرقابل استفاده خواهند بود. یک نقشه نفوذ یک نمایش فضائی از دانش یک عامل درباره جهان خود می‌باشد. کامپیوتر با استفاده از این امکان می‌تواند یک دید استراتژیک از وضعیت فعلی جهان خود داشته باشد. نقشه نفوذ یک تکنیک پرارزش و اثبات شده برای انجام ارزیابی استراتژی می‌باشد. نقشه نفوذ اکثرا در بازی‌های استراتژیک مورد استفاده قرار می‌گیرد، اما برای ژانرهای دیگری نیز که نیازمند آنالیز تکنیکال می‌باشد می تواند سودمند واقع شود[1].
در عمل نقشه نفوذ سه نوع اطلاعات سودمند برای تصمیم‌گیری را میتواند فراهم کند:

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

  • اطلاعات آماری گذشته: علاوه بر ذخیره اطلاعات مربوط به موقعیت فعلی نقشه نفوذ رویدادهایی را نیز که در یک دوره معین اتفاق افتاده را به خاطر می‌سپارد. به طور مثال می‌توان فهمید که آیا این مکان قبلا مورد حمله قرار گرفته است؟ نتایج حمله قبلی چگونه بوده است؟

  • پیش‌بینی آینده: جنبه‌ای که کمتر به آن پرداخته شده‌ است پیش بینی آینده با استفاده از نقشه نفوذ و نقشه زمین 4 می‌باشد. میتوان فهمید که دشمن در آینده احتمالا به چه مناطقی خواهد رفت و تأثیر آن چگونه خواهد بود.
    بدیهی است که هر یک از خصوصیت‌های نقشه نفوذ می‌تواند به ایجنت کمک کند تا تحلیل و محاسباتی به مراتب هوشمندانه‌تر انجام دهد.

۲. اساس و اجزای نقشه نفوذ


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

۲.۱. بازنمایش سطوح بازی

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

  • تقسیم‌بندی محیط5 : نقشه نفوذ باید یک روش ساده و کارا برای تقسیم‌بندی و ذخیره اطلاعات (اثرات) برای هر قسمت ارائه دهد. این تقسیم‌بندی به ایجنت این امکان را خواهد داد که بتواند اطلاعات گذشته را ذخیره کند و در هر لحظه به صورت کارا آمار و اطلاعات جدید را بدست آورد.

  • اتصال6 : نحوه اتصال قسمت‌های مختلف باید به سادگی در نقشه نفوذ مشخص باشد. بر اساس این ارتباطات الگوریتم حاکم بر نقشه نفوذ می‌تواند پیش‌بینی کند که هر رویداد تا چه اندازه می‌تواند در سطوح بازی نفوذ پیدا کند و در آینده ممکن است چه اتفاقاتی بیافتد.

انواع مختلفی از روش‌های بازنمایش نقشه نفوذ وجود دارد که در ادامه به چند مورد اشاره می‌شود.

  1. شبکه دو بعدی7 : این روش بهترین روش برای بازی‌هایی است که بتوان آنها را به یک جهان تقریبا دوبعدی تشبیه کرد. پردازش این نوع نمایش بسیار سریع است و پیاده‌سازی آن ساده است. عیب این روش مصرف زیاد حافظه می‌باشد. اگر محیط بازی یک محیط پراکنده می‌باشد بهتر است از این روش استفاده نشود. این روش بر اساس یک شبکه ماتریسی می‌باشد که هر سلول آن یک قسمت از فضا را نشان می‌دهد و اطلاعات مربوط به آن قسمت در آن ذخیره شده است. ذکر این نکته قابل اهمیت است که اگرچه امروزه اکثر بازی‌های استراتژیک در فضایی سه‌بعدی هستند اما در بیشتر موارد ما می‌توانیم یک شبکه دو‌بعدی بر محیط بازی تحمیل کنیم و از آن برای تحلیل تاکنیکال استفاده کنیم. در ادامه این پروژه نیز از این روش برای بازنمایش اطلاعات استفاده می‌شود.

  2. گراف‌های محیط8 : اگر در بازی یک شبکه ناوبری9 برای رفت و آمد عامل‌های NPC 10 وجود داشته باشد، اساس نقشه نفوذ می‌تواند بر روی همین شبکه پیاده‌سازی شود. مزیت این روش این است که تغییرات گسترده‌ای نیاز ندارد. عیب آن نیز این است که در برخی موارد که به جزئیات زیاد برای تصمیم گیری نیاز است این روش دقت کافی را در اختیار ما قرار نمی‌دهد.

  3. شبکه هوایی11 : استفاده از یک شبکه فضایی کامل در سطح سه‌بعد می‌تواند برخی از مشکلاتی که در محیط‌های سه‌بعدی وجود دارد را مرتفع سازد. شما به راحتی می‌توانید گره‌های گراف شبکه هوایی خود را در یک ساختمان با چند طبقه قرار دهید و تمام فضا‌ها را پوشش دهید. عیب اینگونه باز‌نمایش محیط هزینه سنگین محاسبات و پزدازش است که از دو روش قبلی بیشتر است.

    شکل ۲-۱: شبکه دو بعدی

    شکل ۲-۲: گراف‌های محیط

    شکل ۲-۳: شبکه هوایی

۲.۲. نفوذ و نحوه انتشار آن

اگر چهار سرباز خط آتش در مکانی بیرون از میدان نبرد اردو زده باشند، آن مکان تحت نفوذ آنها است اما احتمالا نه به صورت خیلی قوی. حتی یک جوخه کوچک هم می‌تواند به راحتی آن اردوگاه را تصاحب کند. اگر به جای آن یک هلیکوپتر مسلح بر بالای این اردوگاه در حال پرواز باشد، آن منطقه به مراتب بیشتر تحت کنترل آنهاست. اگر یک ضدهوایی در این منطقه قرار گرفته باشد آنگاه نفوذ آنها چیزی مابین دو حالت قبلی است (ضدهوایی ها در مقابل پیاده‌نظام‌ها آنچنان سودمند نیستند).
میزان نفوذ و اثر با فاصله گرفتن افت می‌کند. اگر ما به قدرت نفوذ به عنوان یک کمیت نگاه کنیم، آنگاه قدرت نفوذ با فاصله گرفتن کمتر و کمتر می‌شود. هرچه از واحد (در اینجا واحد به معنای یک واحد نظامی است، مانند سرباز، مسلسل، تانک و ...) دورتر باشیم میزان اثر آن کمتر است. در نهایت تأثیر آنها آنچنان کوچک خواهد شد که دیگر در نقشه انتشار نمی‌یابد.
برای مدل کردن این موضوع ما می‌توانیم افت نفوذ را خطی در نظر بگیریم. با دو برابر شدن فاصله تأثیر نصف می‌شود. میزان تأثیر با فرمول زیر بدست می‌آید که در آن { I }_{ d } میزان اثر در فاصله d و { I }_{ 0 } میزان اثر در فاصله صفر (اثر اولیه) است.

{ I }_{ d } = \frac { { I }_{ 0 } }{ 1+d }

ما همچنین می‌توانیم میزان برد نفوذ را افزایش دهیم. با این منظور می‌توانیم از فرمول زیر استفاده کنیم.
{ I }_{ d }=\frac { { I }_{ 0 } }{ \sqrt { 1+d } }

یا می‌توانیم برای کاهش برد و افت شدید اثر، میزان اثر را با عکس مجذور فاصله تناسب دهیم.
{ I }_{ d }=\frac { { I }_{ 0 } }{ { (1+d) }^{ 2 } }

افت خطی علاوه بر پردازش سریع تأثیر کاملا منطقی است و تجربه نشان داده که نتایج خوبی حاصل می‌شود.
برای انجام تحلیل باید برای هر واحد مقدار تأثیر نظامی اولیه در نظر گرفت. این مقدار چیزی متفاوت با قدرت حمله یا دفاع واحد می‌باشد. به عنوان مثال یک واحد شناسایی که می‌تواند به توپ‌خانه دستور آتش بدهد دارای تأثیر وسیعی است در حالی که توان جنگیدن این واحد به این اندازه نمی‌باشد. این مقادیر در عملکرد هوش مصنوعی تأثیر به‌سزایی دارند و معمولا همیشه قدری میزان‌سازی 12 برای رسیدن به یک حالت تعادل نیاز است. به این ترتیب با استفاده از فرمول افت و میزان قدرت ذاتی هر واحد، می‌توان نفوذ هر جناح را در هر منطقه از بازی بدست آورد: چه کسی آن منطقه را کنترل می‌کند و این کنترل چقدر است؟ میزان نفوذ هر جناح در منطقه‌ای خاص به سادگی با جمع نفوذ هر واحدی در آن منطقه که به آن جناح نعلق دارد بدست می‌آید. درجه کنترل به راحتی با استفاده از تفاضل میزان نفوذ طرفین بدست می‌آید. اگر این مقدار منفی باشد یعنی این منطقه تحت کنترل دشمن است و میزان این کنترل با قدرمطلق این مقدار بدست می‌آید. اگر تفاضل نفوذ طرفین (نفوذ ایجنت - نفوذ دشمن) مثبت باشد و میزان این تفاوت بسیار زیاد باشد، این نتیجه گرفته می‌شود که آن منطقه امن می‌باشد. نتیجه نهایی یک نقشه نفوذ می‌باشد: مجموعه‌ای از مقادیر که کنترل و میزان نفوذ طرفین (و معمولا میزان امنیت) را در هر مکان از بازی مشخص می‌کند[2].

شکل ۲-۴: یک نقشه نفوذ که برای تمامی مکان‌ها محاسبه شده است. دو جناج سفید (W) و سیاه (B) با تعداد کمی نیرو وجود دارند و نفوذ نظامی هر واحد با عددی نشان داده شده است. هر مکان هرچه تیره‌تر باشد، نفوذ در آن مکان بیشتر است. مرز میان مناطقی که طرفین تحت کنترل دارند نیز مشخص شده است.

۲.۳. اطلاعات سلول‌های نقشه نفوذ

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

  • توانایی رزم: نشان‌دهنده این است که میزان قدرت و پتانسیل تخمینی واحدهای موجود در سلول به چه میزان است. این مقادیر باید با استفاده از فاکتورهایی مانند میزان قدرت هجومی یا دفاعی، میزان سلامتی نیروها13، برد حمله، سرعت آتش و از این قبیل موارد محاسبه و شمارش شوند. دسته‌بندی مناسب نیروها هم در این زمینه می‌تواند مفید واقع شود. به عنوان مثال می‌توان قدرت تیراندازان را در مقابل نیزه‌اندازان، پیاده‌نظامان در مقابل سواره‌نظامان، نیروهای هوایی در مقابل نیروهای دریایی و نیروهای زمینی را به طور نسبی سنجید و داده‌های منطقی‌تری ایجاد نمود.

  • سرمایه‌های آسیب‌پذیر: این یک مقدار تخمینی از وسایل گران‌بها و حیاتی‌ای است که بازیکن در این سلول دارد، مانند تکه‌ای از دهکده بازیکن و یا پایگاه نظامی بازیکن.

  • میدان دید منطقه: عددی ک نشان‌دهنده این است در این مکان تا چه مسافتی قابل دید یا غیر قابل مشاهده برای بازیکن است. به عنوان مثال سلولی که در آن یک دکل قرار داده شده است میدان دید به مراتب بهتری از مناطق درون یک جنگل دارد.

  • شمار اجساد: مشخص می‌کند که چه تعداد از واحد‌ها در این مکان در گذشته کشته شده‌اند و در چه زمانی.

  • منابع: میزان کلی منابعی که هنوز برای بهره‌برداری در دسترس هستند، منابعی نظیر طلا، الوار و ...

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

یک نقشه نفوذ می‌تواند تمامی این مقادیر به طور جداگانه برای هر ایجنت هوش مصنوعی ثبت و تحلیل کند. اما داشتن چند نقشه نفوذ موازی نیز ایده‌ای جالب است. تصور کنید که هر ایجنت علاوه بر اینکه نقشه نفوذ مخصوص به خود، یک نقشه نفوذ دیگری که دانش او را از بقیه بازیکنان نشان می‌دهد را بهنگام می‌کند. این کار به شما این اجازه را می‌دهد که نقاط قوت یا ضعف خاصی از دشمن را که منجر به رسیدن هدفی خاص می‌شود را به صورت گروهی دنبال کنیم. به عنوان مثال فرض کنید که می‌خواهیم بمبی را که در مکانی وسیع کار گذاشته شده است پیدا کنیم و آن را خنثی سازیم. بدون استفاده از چنین راهکاری رسیدن به این هدف برای ایجنت‌های انفرادی بسیار دشوار می‌باشد[1].

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


تاکنون کارهای و تلاش‌های زیادی بر روی بازسازی حرکات معقول برای دسته‌‌ها انجام شده است. رفتار دسته‌ای پرنگان که در سال ۱۹۸۷ توسط Reynolds معرفی شد[5]، پس از آن مسیریابی بهینه با استفاده از نقشه نفوذ[1] و در نهایت در سال ۲۰۱۱ تلفیقی از این دو تکنیک برای بازی‌های RTS ارائه شد[6].

در ابتدا راهکارهایی بیان می‌شود که تاکنون برای محاسبه نفوذ ارائه شده‌اند، رویکردهایی که در عمل بیشتر مورد استفاده قرار می‌گیرد. پس از آن نیز ساختاری برای نقشه نفوذ ارائه می‌شود. بسته به نوع شرایط و نوع بازی این ساختار می‌تواند گونه‌ای دیگر داشته باشد، همانطور که در مقالات و پژوهش‌ها دیده شده است، اما ساختاری که در این بخش ارائه می‌شود چهارچوبی کلی برای نقشه نفوذ معین می‌کند و می‌تواند بسته به شرایط تعمیم یابد.

۳.۱. محاسبه میزان نفوذ

برای محاسبه نقشه ما نیاز به پردازش تأثیر هر واحد در هر مکان از بازی هستیم. در عمل اگر تعداد واحدها n و تعداد سلول‌های نقشه m باشد، زمان محاسبه از پیچیدگی O(nm) و میزان فضای مورد نیاز حافظه از پیچیدگی O(m) می‌باشد. مسلما این کار یک تکلیف سنگینی است. برای مثال در بازی‌های استراتژیک فعلی که در یک صحنه هزاران واحد و میلیون‌ها مکان وجود دارد، میلیارد‌ها محاسبه در هر دوره را می‌طلبد. به این منظور سه رویکرد برای بهبود این امر وجود دارد که در ادامه به طور خلاصه به آنها می‌پردازیم.

۳.۱.۱. محدود کردن شعاع تأثیر

اولین رویکرد این است که شعاع تأثیر را برای هر واحد محدود کنیم. فراتر از این شعاع واحد نمی‌تواند تأثیری داشته باشد، هر چند که می‌تواند تأثیر کوچکی داشته باشد. حداکثر شعاع می‌تواند به صورت دستی تعیین شود، یا می‌توان از یک حد آستانه استفاده کرد. اگر ما از یک فرمول افت خطی برای اعمال تأثیر استفاده می‌کنیم، میزان شعاع نفوذ می‌تواند از فرمول زیر بدست آید که در آن { I }_{ t } حد آستانه می‌باشد.

r = \frac { { I }_{ 0 } }{ { I }_{ t } -1}

این رویکرد این امکان را به ما می‌دهد که با یک پیمایش14 بر روی واحد‌ها، میزان اثر واحد را بر روی مکان‌های که در شعاع آن وجود دارند اعمال کنیم. پیچیدگی این روش O(nr) و میزان فضای مورد نیاز برای حافظه O(m) می‌باشد. عیب این رویکرد این است که تأثیر‌های کوچک نمی‌توانند تا شعاع زیادی نفوذ کنند و عملا در نطفه خفه می‌شوند. به عنوان مثال سه سربازی که در کنار یکدیگر در یک منطقه حضور دارند می‌توانند میزان معقولی از نفوذ در آن منطقه ایجاد کنند، اما هنگامی که این سه سرباز پراکنده می‌شوند، هر کدام به صورت انفرادی نفوذ کمتری خواهند داشت.

۳.۱.۲. فیلترهای کانولوشن15

در این رویکرد در ابتدا با یک نقشه نفوذ‌ی شروع خواهیم کرد که در آن تنها مکان‌هایی مقدار دارند که در آنها یک واحد وجود دارد. شما می‌توانید این را اینگونه تصور کنید که لکه‌هایی از نفوذ در دل نقشه بدون هیچ تأثیری وجود دارند. سپس الگوریتم بر تمامی سلول‌های نقشه عمل می‌کند و مقادیر آنها را بگونه‌ای تغییر می‌دهد که در آنها علاوه بر اثر واحد‌های موجود در همان سلول، نفوذ همسایگانش نیز جا داده شده است. این یک روش مرسوم در کاربردهای گرافیکی می‌باشد که در آن نتیجه مات کردن16 لکه‌های اولیه حاصل می‌شود. هرچه مقادیر اولیه بزرگتر باشند، مات کردن (اعمال نفوذ) آن در سطح وسیعتری انجام می‌شود.
این رویکرد از یک فیلتر استفاده می‌کند: یک قاعده که می‌گوید مقدار یک مکان تحت تأثیر همسایگانش چگونه است. بسته به این که ما از چه نوع فیلتری استفاده کنیم، می‌توانیم انواع مختلفی از مات کردن را اعمال کنیم. فیلتری که بیش از همه مورد استفاده قرار می‌گیرد «فیلتر Gaussian» نام دارد و بدلیل اینکه دارای خصوصیت‌های ریاضی‌ای است که به راحتی قابل محاسبه است بسیار مفید می‌باشد.
به منظور انجام فیلترینگ، هر مکان موجود در نقشه باید به وسیله این قاعده بهنگام شوند. برای اینکه مطمئن شویم نفوذ واحد‌ها به میزان قابل قبولی در نقشه گسترش داده شده‌اند، باید برای هر دوره چند مرتبه فیلترینگ انجام داد. اگر تراکم واحد‌ها در بازی کم باشد، این رویکرد پرهزینه‌تر از حتی الگوریتم خام اولیه می‌باشد. در بخش‌های بعدی به طور مفصل در این باره صحبت خواهیم کرد.

۳.۱.۳. سرریز مقادیر در نقشه17

در آخرین رویکرد ما از یک فرض بسیار ساده استفاده می‌کنیم: نفوذ در هر مکان برابر تأثیری است که قوی‌ترین (مؤثرترین) واحد در آن مکان دارد. با این فرض اگر یک تانک یک خیابان را پوشش دهد، نفوذ آن به اندازه زمانی است که ۲۰ سرباز هم در کنار تانک در حال پوشش خیابان باشند. واضحا این رویکرد منجر به ایجاد برخی خطاها می‌شود؛ ایجنت فرض می‌کند که یک واحد قدرتمند می‌تواند بر تعداد زیادی از سربازان فائق آید.
در نیمه پر لیوان، یک الگوریتم بسیار سریع است که می‌تواند مقادیر نفوذ را بر اساس الگوریتم دایجسرا18 محاسبه کند. الگوریتم به سرعت نقشه را با مقادیر پر می‌کند، به سراغ هر واحد می‌رود و نفوذ آن را در نقشه منتشر می‌کند. این رویکرد از نظر پیچیدگی زمانی حوالی O(min[nr, m]) است و از نظر حافظه از مرتبه O(m) می‌باشد. به خاطر اینکه این الگوریتم از نظر پیاده‌سازی است و در عمل بسیار سریع عمل می‌کند، این الگوریتم در موارد بسیاری می‌تواند مورد استفاده قرار گیرد.

نکته ای که در اینجا باید به آن اشاره کرد این است که ما میتوانیم برای اتخاذ تاکتیک دفاعی یا هجومی از مقادیر وزن‌دار برای نفوذها استفاده کنیم. با افزایش وزن نفوذ نیرو‌های دشمن (استفاده از ضریب بزرگتر از یک برای نفوذ اولیه هر کدام از واحدهای دشمن)، مرز میان جناحین به ما نزدیک‌تر می‌شود و ژست دفاعی در نیروها گرفته می‌شود. برعکس اگر وزن نیروهای ایجنت بیشتر باشد مرز‌ها به سمت دشمن رانده می‌شوند و نیرو‌ها آرایش هجومی به خود می‌گیرند[1].
نکته‌ دیگری که در اینجا حائز اهمیت است این است که تعادل قدرت در سطح بازی معمولا فریم به فریم تغییر نمی‌کند، پس اگر الگوریتم نقشه نفود در دوره‌ای به اندازه تعداد زیادی فریم اجرا شود اتفاق ناخوشایندی نخواهد افتاد. همه الگوریتم‌ها به راحتی می‌توانند متوقف شوند. اگرچه نقشه نفوذ فعلی ممکن است اطلاعات کاملا به‌روزی داشته باشد اما حتی اگر نرخ بهنگام‌سازی ۱۰ ثانیه هم باشد، اطلاعات به اندازه‌ای کافی هستند که ایجنت معقول عمل کند[2].

۳.۲. ساختار تحلیل تاکتیکال[2]

می‌توان انواع مختلفی از تحلیل تاکتیکال را بر اساس زمان و چگونگی به‌روز رسانی متصور شد. شکل زیر این تفاوت‌ها را نشان می‌دهد.

شکل ۳-۱: لایه‌های مختلف ساختار تحلیل تاکتیکال

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

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

  • برد وسیعی از میدان دید (برای بدست آوردن حداکثر اطلاعات)

  • منطقه‌ای امن (رادارها به راحتی قابل نابودی‌اند)

  • دور بودن از بقیه رادارها (به منظور استفاده بهینه از تجهیزات)

این سه فاکتور نهایتا در یک مقدار خلاصه می‌شوند که نشان می‌دهد یک مکان تا چه اندازه برای این منظور مناسب است. این ترکیب می‌تواند به فرم زیر باشد:

Quality=Security*Visibility*Distance

این پروسه در شکل زیر نشان داده شده است.
شکل ۳-۲: تحلیل‌های جداگانه بر اساس نقشه‌های نفوذ مختلف و نحوه ترکیب آنها در یک مقدار

پس بدین ترتیب به جای استفاده مستقیم از آمار و ارقام هر سلول به منظور تصمیم گیری،باید آنها را با هم ترکیب کرد تا بتوان مقادیری با معنا بدست آورد که ارزش‌های مطلوب19 نام دارند. ارزش‌ مطلوب مقداری است که به منظور یک تصمیم معین برای هر مکان محاسبه می‌شود. با مقایسه مقادیر مطلوب سلول‌های مختلف و رتبه‌بندی آنها می‌توان بهترین مکان برای انجام عملی خاص را انتخاب نمود.
بهترین فرمول برای محاسبه مقدار مطلوب همانطور که ارائه شد، یک جمع وزن‌دار ساده می‌باشد. مقادیر نفوذ هر سلول که به آن تصمیم خاص مرتبط هستند جمع‌آوری می‌شود و هر کدام در یک ضریبی که اهمیت آن فاکتور را در آن تصمیم نشان می‌دهد ضرب می‌شوند و در نهایت همه جمع شده و نتیجه نهایی مقدار مطلوب را مشخص می‌سازد. در ادامه به چند نمونه از این مقادیر اشاره می‌کنیم[1].

  • قابلیت حمله و دفاع: می‌توان مقداری برای میزان آسیب‌پذیری در یک مکان اختصاص داد که توانایی حمله یا دفاع برای ایجنت و دشمن را نشان می‌دهد. مناطق آسیب‌پذیر مناطقی هستند که در آنها تجهیزات و منابعی کلیدی وجود دارد در حالی که تعداد واحد‌های نظامی در نزدیکی آنها کم است. آسیب‌پذیری بالا در منطقه‌ای تحت نفوذ دشمن به این معناست که ما باید حمله به دشمن در آن مکان را در نظر داشته باشیم. آسیب پذیری بالا در منطقه تحت نفوذ ایجنت به این معناست که ما میزان قابل توجهی منابع در اختیار داریم که در معرض حمله می‌باشند و ما باید از آنها با مراقبت بیشتری دفاع کنیم.

  • قابلیت اکتشاف:در بازی‌های RTS یک ایجنت باهوش برای بروز کردن دیدش از میدان جنگ جاسوسانی را به مناطق مختلف اعزام می‌کند. راهکاری مناسب به منظور انتخاب بهترین مکان برای اکتشاف، انتخاب سلول‌هایی از نقشه نفوذ است که به مدت طولانی‌ای دیده نشده‌اند. فاکتورهای خوب دیگر می‌توانند میزان نفوذ دشمن در آن مکان‌ها و توانایی عبور باشد (تا جاسوس شما در صورت حمله دشمن بتواند فرار کند).

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

  • قرار دادن مراکز تولید منابع: باید در مکان‌هایی قرار گیرند که به واحد‌هایی دفاعی نزدیک باشند و تا حد امکان در نزدیکی مکان‌هایی باشند که پتانسیل بالایی برای اکتشاف و استخراج منابع دارند.

  • قرار دادن ادوات آسیب پذیر: این ادوات باید در مکان‌هایی قرار گیرند که نفوذ دفاعی در آن منطقه بسیار بالاست. مکان‌هایی که سخت‌تر قابل دسترسی هستند نیز برای این منظور مناسب‌اند.

۴. پیاده‌سازی

۵. آزمایش‌ها

۶. کارهای آینده

۷. مراجع

[1] Mark DeLoura. "Games programming gems 2", Charles River Media; 1 edition (July 26, 2001)
[2] Ian Millington. "Artificial Intelligence for games", George Morrison
[3] Jang, Su-Hyung, and Sung-Bae Cho. "Evolving neural NPCs with layered influence map in the real-time simulation game ‘Conqueror’." Computational Intelligence and Games, 2008. CIG'08. IEEE Symposium On. IEEE, 2008.
[4] Alberto Uriarte and Santiago Ontanon. "Kiting in RTS Games Using Influence Maps", 2012 AIIDE Workshop
AAAI Technical Report WS-12-15
[5] Craig W. Reynolds. "Flocks, Herds, and Schools: A Distributed Behavioral Model", Computer Graphics, 21(4), July 1987
[6] M. Preuss, N. Beume, H. Danielsiek, T. Hein, N. B, N. Piatkowski, R. Stuer, A. Thom, and S. Wessing, “Towards Intelligent Team Composition and Maneuvering in Real-Time Strategy Games” IEEE Transactions on Computational Intelligence and AI in Games, pp. 82–98, 2010.


  1. Choke points

  2. Real-Time

  3. Real-tiem strategic (RTS)

  4. terrain map

  5. Spatial partition

  6. Connectivity

  7. 2D Grid

  8. Area Graphs

  9. Navigation mesh

  10. Non-player characters

  11. Waypoint Network

  12. Tunning

  13. Hit point

  14. Iterate

  15. Convolution Filters

  16. Blurring

  17. Map Flooding

  18. Dijkstra algorithm

  19. Desirability Values

  20. Passability

رد شده

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

رد شده

موضوع جذابی را برای پروژه انتخاب نمودید و مشخص است که زمان زیادی صرف نموده‌اید. نکاتی که به نظرم رسید را در ادامه ذکر کرده‌ام:
توضیحات کامل بود و ابعاد مختلف مسأله بخوبی برای خواننده روشن شده است.
در رابطه به الگوریتم‌‌های نفودی که ذکر کردید بهتر بود برای نمونه یک مورد را کامل توضیح می‌دادید(ترجیحا موردی که قصد دارید در پیاده‌سازی استفاده نمایید).
نگارش مقاله بسیار روان بود نتها موردی که می‌توان در این رابطه ذکر کرد این است که بهتر بود بجای کلمه ایجنت از عامل که ترجمه ‌agent می‌باشد استفاده می‌نمودید.
و نکته آخر اینکه برای فار دوم پیاده‌سازی نداشتید امیدوارم برای فار بعد بتوانید جبران کنید و زحماتی که تا اینجا کشیدید به نتیجه برسد.
موفق باشید.

تایید شده

متاسفانه بر خلاف فاز اول که بسیار خوب کار کرده بودید، در این فاز کاری انجام نداده‌اید.

رد شده

با عرض سلام و خسته نباشید
با توجه به این که پروژه ای که انتخاب کرده اید یک پروژه جدید (حداقل متفاوت به پروژه‌های روتین قبلی) است و حداقل برای جست و جو در اینترنت هم که شده مجبور بوده اید وقت زیادی بگذارید و اطلاعات جمع کنید بنابراین همین مقدار داده نیز می‌تواند بسیار جالب توجه باشد. در برخی موارد این امکان وجود داشت تا توضیح بیشتری داده می شد مثلا هنگام اشاره به رفتار دسته‌ای پرندگان می‌توانستید flocking algorithm ها رو که شامل سه بخش هستند را بیشتر توضیح دهید تا خواننده حس بهتری بگیرد یا در هر کدام از کار‌های مرتبط این امکان وجود داشت تا بتوانیم بهتر با آن کار‌ها آشنا شویم ولی بعد از خواندن کار‌های مرتبط کمی گنگی به وجود می‌آمد. و در آخر هم اگر اشتباه نکرده باشم اصلا به منبع شماره سه هیچ اشاره ای در مقاله نشده است، لطفا اصلاح بفرمایید.
با تشکر
موفق و پیروز باشید