مولد پیچ ​​و خم الگوریتم ویلسون

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

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

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

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

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

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

چگونه الگوریتم ویلسون برای Maze Generation کار می کند

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

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

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

مرحله 2: یک سلول شروع تصادفی را انتخاب کنید

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

مرحله 3: پیاده روی تصادفی با حلقه پاک کردن

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

مرحله 4: تا زمانی که همه سلول ها بازدید شوند، تکرار کنید :

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