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

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

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

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

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

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

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

نحوه‌ی عملکرد الگوریتم شکار و کشتن برای تولید هزارتو

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

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

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

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

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

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

مطالعه بیشتر

اگر از این پست لذت بردید، ممکن است این پیشنهادات را نیز بپسندید:

• الگوریتم Kruskal مولد پیچ و خم
• مولد پیچ ​​و خم عقبگرد بازگشتی
• مولد پیچ ​​و خم الگوریتم الر