الگوریتم درختان در حال رشد مولد ماز

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

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

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

درباره الگوریتم درخت در حال رشد

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

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

مرحله ۱: مقداردهی اولیه

• با یک شبکه از سلول‌های بازدید نشده شروع کنید.
• یک سلول شروع تصادفی انتخاب کنید و آن را به یک لیست اضافه کنید.

مرحله ۲: حلقه تولید هزارتو

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

مرحله ۳: فسخ

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

استراتژی‌های انتخاب سلول (انعطاف‌پذیری الگوریتم)

ویژگی بارز الگوریتم درخت در حال رشد، نحوه انتخاب سلول بعدی برای پردازش است. این انتخاب به طور چشمگیری بر ظاهر هزارتو تأثیر می‌گذارد:

جدیدترین سلول (رفتار پشته مانند) - Backtracker بازگشتی:

• همیشه آخرین سلول اضافه شده را انتخاب کنید.
• راهروهای طولانی و پر پیچ و خم با بن‌بست‌های فراوان (مانند یک هزارتوی جستجوی عمقی) ایجاد می‌کند.
• مازها معمولاً مسیرهای طولانی دارند و حل کردن آنها آسان است.

سلول تصادفی (الگوریتم پریم تصادفی):

• هر بار یک سلول تصادفی از لیست انتخاب کنید.
• یک هزارتو با توزیع یکنواخت‌تر با مسیرهای پیچیده و درهم‌تنیده ایجاد می‌کند.
• راهروهای طولانی کمتر و انشعابات بیشتر.

قدیمی‌ترین سلول (رفتار شبیه صف):

• همیشه قدیمی‌ترین سلول موجود در لیست را انتخاب کنید.
• مارپیچ‌هایی با پراکندگی یکنواخت‌تر، مانند الگوی جستجوی سطح-اول، تولید می‌کند.
• گذرگاه‌های کوتاه و پرپشت با اتصالات متراکم.
• (این نسخه‌ای است که اینجا پیاده‌سازی شده است)

رویکردهای ترکیبی:

برای ویژگی‌های متنوع هزارتو، استراتژی‌ها را ترکیب کنید. برای مثال:

• ۹۰٪ جدیدترین، ۱۰٪ تصادفی: بیشتر شبیه یک هزارتوی بازگشتی به عقب به نظر می‌رسد، اما گاهی شاخه‌هایی دارد که راهروهای طولانی را از هم جدا می‌کنند.
• ۵۰٪ جدیدترین، ۵۰٪ قدیمی‌ترین: راهروهای طولانی را با رشد بوته‌ای متعادل می‌کند.

مطالعه بیشتر

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

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