Miklix

شکار و کشتن ژنراتور پیچ و خم

منتشر شده: ۱۶ فوریهٔ ۲۰۲۵ ساعت ۲۰:۵۷:۴۷ (UTC)

ژنراتور Maze با استفاده از الگوریتم Hunt and Kill برای ایجاد یک پیچ و خم کامل. این الگوریتم شبیه به Recursive Backtracker است، اما تمایل به ایجاد پیچ و خم هایی با راهروهای طولانی تر و پر پیچ و خم دارد.

این صفحه ماشینی از انگلیسی ترجمه شد تا در دسترس هر چه بیشتر مردم باشد. متأسفانه، ترجمه ماشینی هنوز یک فناوری کامل نشده است، بنابراین ممکن است خطاهایی رخ دهد. در صورت تمایل می توانید نسخه اصلی انگلیسی را در اینجا مشاهده کنید:

Hunt and Kill Maze Generator

الگوریتم Hunt and Kill در واقع یک نسخه اصلاح شده از Recursive Backtracker است. این اصلاح شامل اسکن سیستماتیک (یا "شکار") برای یک سلول جدید است تا از زمانی که نمی تواند جلوتر برود ادامه یابد، برخلاف یک جستجوی بازگشتی واقعی، که همیشه به سلول قبلی در پشته باز می گردد.

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

پیچ و خم کامل، پیچ و خم هایی است که در آن دقیقاً یک مسیر از هر نقطه در پیچ و خم به هر نقطه دیگر وجود دارد. این بدان معناست که شما نمی توانید در نهایت به دور زدن در دایره بپردازید، اما اغلب با بن بست هایی روبرو می شوید که شما را وادار می کند که بچرخید و به عقب برگردید.

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


ایجاد پیچ ​​و خم جدید








درباره الگوریتم شکار و کشتن

الگوریتم Hunt and Kill یک روش ساده و در عین حال موثر برای تولید پیچ و خم است. این تا حدودی شبیه به جستجوی عمق اول (یعنی الگوریتم Recursive Backtracker) است، به جز زمانی که نمی تواند از موقعیت فعلی دورتر شود، به طور سیستماتیک روی پیچ و خم اسکن می کند (یا "شکار") می کند تا سلول جدیدی برای ادامه کار پیدا کند. این الگوریتم از دو مرحله اصلی تشکیل شده است: پیاده روی و شکار.

الگوریتم شکار و کشتن برای تولید پیچ و خم چگونه کار می کند؟

مرحله 1: از یک سلول تصادفی شروع کنید

  • یک سلول تصادفی را در شبکه پیدا کنید و آن را به عنوان بازدید شده علامت گذاری کنید.

مرحله 2: مرحله راه رفتن (پیاده روی تصادفی)

  • یک همسایه تصادفی بازدید نشده را انتخاب کنید.
  • به آن همسایه بروید، آن را به عنوان بازدید شده علامت گذاری کنید و مسیری بین سلول قبلی و جدید ایجاد کنید.
  • این کار را تکرار کنید تا هیچ همسایه ای ملاقات نشده باقی نماند.

مرحله 3: مرحله شکار (عقب نشینی از طریق اسکن)

  • شبکه را ردیف به ردیف (یا ستون به ستون) اسکن کنید.
  • اولین سلول بازدید نشده را پیدا کنید که حداقل یک همسایه بازدید شده داشته باشد.
  • آن سلول را به همسایه بازدید شده متصل کنید تا مرحله پیاده روی را از سر بگیرید.
  • این کار را تا زمانی که همه سلول ها ویزیت شوند، تکرار کنید.

در Bluesky به اشتراک بگذاریددر فیسبوک به اشتراک بگذاریددر لینکدین به اشتراک بگذاریددر Tumblr به اشتراک بگذاریددر X به اشتراک بگذاریددر لینکدین به اشتراک بگذاریدپین در پینترست

میکل بنگ کریستنسن

درباره نویسنده

میکل بنگ کریستنسن
مایکل خالق و صاحب miklix.com است. او بیش از 20 سال تجربه به عنوان یک برنامه نویس حرفه ای کامپیوتر / توسعه دهنده نرم افزار دارد و در حال حاضر به طور تمام وقت برای یک شرکت بزرگ فناوری اطلاعات اروپایی مشغول به کار است. هنگامی که وبلاگ نویسی نمی کند، اوقات فراغت خود را صرف مجموعه وسیعی از علایق، سرگرمی ها و فعالیت ها می کند، که ممکن است تا حدی در موضوعات مختلف پوشش داده شده در این وب سایت منعکس شود.