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

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

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

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

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

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

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

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

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

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

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

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

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

مرحله ۳: پیمایش تصادفی با حذف حلقه

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

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

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

مطالعه بیشتر

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

• مولد پیچ ​​و خم الگوریتم الر
• الگوریتم درختان در حال رشد مولد ماز
• شکار و کشتن ژنراتور پیچ و خم