طراحی الگوریتم بازی
فهرست مطالب
آخرین به روزرسانی در 21/07/2023
طراحی الگوریتم بازی یکی از پچیده ترین مباحثی است که معمولا بازی سازان با آن روبه رو خواهند شد .
ما در این مقاله قصد داریم توضیحات تخصصی ای را در رابطه با طراحی الگوریتم بازی،
چالش های آن، انواع الگوریتم و مفاهیمی در رابطه با الگوریتم های را برای شما شرح دهیم پس تا پایان این مقاله با ما همراه باشید .
مفاهیم اولیه الگوریتم
در واقع ریشه و مفهوم الگوریتم از آنجایی شروع می شود که ما برای حل یک مسئله ی پیچیده که این مسئله ی پیچیده می تواند بازی ، ریاضی یا هر مسئله و در هر فیلده دیگری باشد ؛ از یک راه حل مرحله به مرحله استفاده می کنیم؛ که گام به گام مشکل را حل کند.
اصطلاحا این راه حل مرحله به مرحله را طراحی الگوریتم گوییم.
تمامی الگوریتم های محاسباتی کامپیوتر از یک جمع و تفریق ساده تا الگوریتم های فوق پیشرفته در بازی سازی توسط برنامه نویسی پیاده سازی می شوند .
نکته 1 : حل یک مسئله ی ساده به معنای نداشتن الگوریتم در آن نیست بلکه به قدری آن مسئله ساده بوده
که قبلا الگوریتم حل آن بارها و بارها تکرار شده و به یک راه ساده برای شما تبدیل شده است ؛ پس می توان نتیجه گرفت تمامی محاسبات و پردازش ها توسط الگوریتم های انجام می پذیرند .
فلوچارت در الگوریتم
فلوچارت برگرفته شده است از اشکال هندسی که برای بیان بهتر و واضح تر الگوریتم نوشته شده
بصورتی که بجای نوشته های الگوریتم از اشکال هندسی مانند : مربع و مستطیل ، دایره و … استفاده میشود.
الگوریتم های اصلی بازی سازی
صف Djikstra ، MinMax و Heap Priority از الگوریتم های اصلی در بازی سازی هستند و
سایر الگوریتم ها را می توان نسخه های تغییر یافته و یا توسعه یافته از این الگوریتم ها دانست.
این لیست به یقین همه الگوریتم هایی نیست که باید برای توسعه بازی یاد بگیرید و بدانید زیراکه
ما تعداد زیادی از الگوریتم ها را داریم که هر کدام از آن مختص سبک بازی های متنوعی می باشند.
اما با این حال ، اینها مواردی هستند که قبل از وارد شدن به دنیای ساختار داده ها و الگوریتم ها ، باید یاد بگیرید ، لیست کامل تر این الگوریتم ها به شرح :
- الگوریتم جستجوی A
- الگوریتم مسیر یابی
- مسیر یاب Djikstra
- Greedybest اولین راه یابی
- صف اولویت heap
- الگوریتم MinMax
- الگوریتم NegaMax
- الگوریتم آلفا بتا
معروف ترین و بهترین الگوریتم ها
الگوریتم جستجوی دودویی :
مقدار هدف را با وسط آرایه مقایسه می کند.
الگوریتم Breadth-First Search (BFS)-Breadth-First Search :
برای حل بسیاری از مشکلات از جمله کوتاهترین مسیر در نمودار ، حل معماها و بازی ها استفاده می شود.
الگوریتم جستجوی عمق اول (DFS) :
عمق اولین پیمایش (یا جستجو) برای نمودار شبیه به پیمایش عمق اول درخت است.
تنها چیزی که در اینجا مشاهده می شود این است که بر خلاف درختان ، نمودارها ممکن است شامل چرخه باشند ، یک گره ممکن است دو بار بازدید شود.
( برای جلوگیری از فیلتر شدن یک گره بیش از یک بار ، از یک آرایه بازدید بولی استفاده کنید.)
الگوریتم Quicksort :
بر اساس تقسیم یک آرایه به موارد کوچکتر است و همچنین برای مرتب سازی لیست عناصر استفاده می شود.
الگوریتم های Quicksort سعی می کنند لیست عناصر را به دو قسمت تقسیم کرده و سپس یکدیگر را به صورت بازگشتی مرتب کنند.
الگوریتم Kruskal :
به کشف حداقل مسیر نمودار کمک می کند .
تشریح الگوریتم ها
A شاید مهمترین الگوریتم در ب ازی سازی باشد. این الگوریتم برای یافتن مسیرهای بین دو گره در یک نمودار (یا روی نقشه) استفاده می شود.
اگر بازی شما شامل کاکتر ها یا اجسامی است که باید به نوعی در دنیای مجازی حرکت کنند ، احتمالاً در نهایت به الگوریتم نوع A* نیاز خواهید داشت.
الگوریتم های مرتب سازی نیز بسیار مهم هستند. آنها غالباً برای مواردی مانند
پی بردن به منظور ترسیم ظاهر خوب ، شفافیت ، تشخیص اینکه کدام موجود در مسیر اول مورد حمله قرار می گیرد یا حتی به عنوان الفبای موارد در یک فروشگاه NPC استفاده می شود.
تقریباً همه زبانها در حال حاضر دارای توابع مرتب سازی خوب هستند ، بنابراین ، احتمالاً نباید خود را درگیر این الگوریتم بکنید .
شما باید بر درک بسیار عمیق ایده ها تمرکز کنید.
بسیاری از برنامه نویسان روی جزئیات مکانیکی یک الگوریتم تمرکز زیادی می کنند بدون آنکه به اندازه کافی فرایند فکری پشت آن را درک کنند.
برنامه نویسان معمولاً دو چیز را در مورد یک تکنیک خاص به یاد می آورند:
- جزئیات مکانیکی. به عنوان مثال ، نحوه محاسبه انتگرال ، یا مراحل مورد نیاز برای وارد کردن یک مقدار در max-heap.
- روش استفاده از یک تکنیک در شرایط واقعی. به عنوان مثال ، نحوه استفاده از انتگرال به عنوان یک ابزار مفید برای انجام محاسبات ، یا نحوه استفاده از توده ها برای حل مشکلاتی که در آن داشتن صف اولویت مفید است.
معرفی یکی از بهترین الگوریتم ها (PSO)
“Particle Swarm Optimization”
بهینه سازی ازدحام ذرات یا همان ترجمه شده ی “Particle Swarm Optimization” یک روش بهینه سازی تصادفی مبتنی بر جمعیت است
که توسط دکتر ابرهارت و دکتر کندی در سال 1995 ایجاد شده است ، که از رفتار اجتماعی پرندگان و ماهیان الهام گرفته شده است. این الگوریتم بسیار ساده اما قدرتمند می باشد.
PSO می تواند به عنوان یک روش آموزشی برای شبکه های عصبی مصنوعی یا برای به حداقل یا به حداکثر رساندن سایر توابع با ابعاد بالا استفاده شود.
برای درک الگوریتم بهتر می باشد مثالی را شرح دهیم :
گروهی از پرندگان را تصور کنید که در یک منطقه مشخص به دنبال غذا هستند و فقط یک تکه غذا در این منطقه وجود دارد.
در ابتدا ، پرندگان نمی دانند غذا کجاست ، اما در هر زمان می دانند که غذا چقدر است ؛ پرندگان از کدام استراتژی پیروی خواهند کرد؟
خب کاملا مشخص است هر پرنده از پرنده ای که غذا نزدیک تر است پیروی می کند .
PSO این رفتار را تطبیق می دهد و بهترین بردار راه حل را در فضای جستجو، ردیابی می کند.
اجازه بدهید مقداری و تئوری شویم ، به یک محلول واحد ، ذره می گویند.
هر ذره دارای ارزش تناسب/هزینه است که با تابع به حداقل رساندن ارزیابی می شود و هر ذره دارای سرعتی است
که “پرواز” ذرات را هدایت می کند. ذرات با دنبال کردن ذرات بهینه در فضای جستجو پرواز می کنند.
این الگوریتم با ذرات در موقعیت های تصادفی راه اندازی می شود و سپس فضای جستجو را برای یافتن راه حل های بهتر کاوش می کند.
در هر تکرار ، هر ذره سرعت خود را تنظیم می کند تا از بهترین راه حل پیروی کند.
اولین قسمت شناختی است ، که در آن ذره بهترین راه حل خود را تا کنون دنبال می کند. این راه حلی است که کمترین هزینه را تولید می کند
(بالاترین تناسب را دارد). پس این مقدار بهترین ذره (Pbest) نامیده می شود.
بهترین مقدار دیگر بهترین محلول فعلی ازدحام است ، یعنی بهترین محلول توسط هر ذره ای در ازدحام که این مقدار (gBest )
بهترین جهانی نامیده می شود. سپس ، هر ذره سرعت و موقعیت خود را با معادلات زیر تنظیم می کند:
v’ = v + c1.r1.(pBest – x) + c2.r2.(gBest – x)
x’ = x + v’
در اینجا v سرعت فعلی است ، v ‘ سرعت جدید ، x موقعیت فعلی ، x’ موقعیت جدید ، pBest و gBest طبق تعاریف بالا یعنی به ترتیب بهترین ذره و بهترین جهانی ، r1 و r2 اعداد تصادفی در بازه [0 ، 1] و c1 و c2 ضرایب شتاب هستند.
جایی که c1 عاملی است که بر رفتار شناختی تأثیر می گذارد ، یعنی اینکه چقدر ذره بهترین راه حل خود را دنبال می کند و c2 عامل رفتار اجتماعی است ، یعنی چقدر ذره بهترین راه حل ازدحام را دنبال می کند.
بازی های که باعث می شود ذهنتان در طراحی الگوریتم بازی تقویت یابد
سودوکو یکی از بازی های در سبک پازل عددی بسیار ساده است . حل (یا ایجاد) یک پازل سودوکو می تواند بسیار سخت باشد و در واقع این همان دلیلی است که به شما امکان می دهد مهارت های تفکر الگوریتمی و استدلالی خود را تقویت کنید.
یکی دیگر از بازی های پازل عددی ساده دیگر که دارای تنوع بالایی در پازل های آن می باشد و همچنین وجود نوعی تصادفی بودن آن را به راهی برای بهبود تفکر الگوریتمی و مهارت حل مسئله تبدیل کرده است .
بدون شک و به طور صد در صد ، شطرنج یکی از بهترین بازی هایی است که حل مسئله ، طراحی استراتژی ، استدلال و مهارت های تفکر الگوریتمی را در ذهن شما بهبود می بخشد.
این یک بازی در سبک بازی های کارتی ایرانی می باشد ، که استدلال احتمالی و مهارت های طراحی استراتژی را بهبود می بخشد .