اولین پست این سری عبور کرد کد استراتژی فعلی من این یکی تعدادی از آموخته های نوشتن الگوریتم های کاربردی در پروژه (به عنوان مثال) را که در آن از ماژول های استاندارد کتابخانه کریستال استفاده کردم، به اشتراک می گذارد.
تجزیه JSON در کریستال
این یک وظیفه رایج است که باید در هر زبانی با آن برخورد شود. کریستال فراهم می کند JSON::Serializable ماژول را برای شما در کلاس خود قرار دهید. به این ترتیب شما دریافت می کنید to_json و from_json روش های مبتنی بر ویژگی ها و حاشیه نویسی دستورالعمل های استفاده از ماژول (اسناد) عالی هستند.
ممکن است هنگام تنظیم یک سلسله مراتب شی تودرتو کار کردن سخت باشد، اما تجزیه و تحلیل زمینه Battlesnake و سپس کار با همه اشیا (به عنوان مثال @context.board.snakes.head، @context.board.width، و غیره). به لطف کامپایلر پس از آن نیز هنگام کار با این موارد، بازخورد فوری در برابر اشتباهات املایی داشته باشید.
کلاس ها در /src/battle_snake دایرکتوری نمایشی از بازی است که در هر نوبت به عنوان بار JSON وارد می شود.
الف* الگوریتم جستجو
a_star.cr روش کاربردی (مرجع اسناد) است که کوتاه ترین مسیر را از یک نقطه A تا یک نقطه B پیدا می کند. در این زمینه، یک نقطه یک BattleSnake::Point که نشان دهنده یک مختصات است (x, y) در هیئت مدیره.
تاریخچه و نحوه کار آن در ویکی پدیا توضیح داده شده است. پیاده سازی من در GitHub است (اینجا).
مطمئنم بهینه‌سازی‌های بالقوه‌ای وجود دارد، اما تمام تلاشم را کردم تا با مواردی مانند استفاده از ساختار داده‌های صف اولویت توصیه شده با spider-gazelle/priority-queue. بالاخره سرور باید سریع پاسخ دهد (<500ms) برای اینکه بازی را انجام دهد و ما باید اعتماد کنیم، می‌توانیم چندین بار در یک نوبت با روش‌های کاربردی تماس بگیریم تا تصمیم بگیریم.
مقایسه نقاط (فاصله)
به منظور مقایسه و مرتب‌سازی کلاس‌های سفارشی بر روی ساختارهای داده، کریستال به شما کمک می‌کند Comparable ماژول/میکسین فرمول دانستن فاصله بین دو BattleSnake::Point به نظر می رسد (کد کلاس در اینجا):
def <=>(other : Point)
(x - other.x).abs + (y - other.y).abs
end
این که به نام فاصله منهتن و با چند نام دیگر شناخته می شود، اساس این است که چگونه می توانیم تشخیص دهیم که دو نقطه از یکدیگر چقدر فاصله دارند. این نکته کلیدی است که بتوان A* را روی یک برد پیاده سازی کرد، که می تواند به عنوان نموداری با فاصله مساوی (1) از هر گره در نظر گرفته شود.
اکنون کلاس ما به طور خودکار عملگرهای مقایسه معمولی را دریافت می کند (<، <=، ==، >=، و >) بر اساس آن پر می شود و ساختارهای داده مانند آرایه ها نیز می توانند آنها را مرتب کنند.
پر شدن سیل
این الگوریتمی است که تمام مناطق ممکن را که می توان به آن دسترسی پیدا کرد، بر خلاف نقاط خالی روی برد تعیین می کند، زیرا ممکن است یک بخش مسدود و غیر قابل دسترس باشد (مرجع اسناد).
راه (خلاصه) من برای توضیح آن خواهد بود “پردازش تکراری تمام فضاهای معتبر نزدیک”.
اطلاعات بیشتر درباره سیل پر در ویکی پدیا. پیاده سازی من در GitHub است (اینجا).
این هنگام تصمیم گیری بین حرکات معتبر مختلف در یک استراتژی مفید است. در نظر بگیرید که آیا مجبور بودید bewteen را انتخاب کنید (آ) به سمت راست حرکت کنید و در نهایت با یک منطقه سیل پر از 3 یا (ب) به سمت چپ حرکت کنید و در پایان با یک منطقه پر از سیل 12 برسید. گزینه (آ) به نظر می رسد بهترین است
که چگونه CautiousCarol تصمیم می گیرد به جای دویدن در یک منطقه بسته (بن بست) به سمت چپ حرکت کند: با محاسبه نتایج پر شدن سیل و انتخاب بزرگترین آنها.
نتیجه گیری
ماژول‌ها/میکس‌های دیگری نیز وجود دارند که می‌توانند برای گسترش کلاس‌ها گنجانده شوند یا مورد استفاده قرار گیرند (یعنی Enumerable)، بنابراین اینها فقط دو حالت هستند که برای این پروژه خاص اعمال می‌شوند.
وقتی روی اینها کار می کردم به خاطرات دانشگاه فلاش بک داشتم. نوستالژیک و سرگرم کننده. نکته جالب این است که اکنون هر استراتژی جدیدی که بتوانم روی آن کار کنم، می‌توانم در صورت نیاز از هر یک از اینها استفاده کنم.
با تشکر از تیم BattleSnake برای منابعی که آپلود می کنند، مانند Deep Learning: Useful Battlesnake Algorithms
ویدیوی یوتیوب، جایی که من چیزهای زیادی در مورد نحوه اعمال این الگوریتم ها و سایر الگوریتم ها در BattleSnake یاد گرفتم.
زندگی ناب.
