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

الگوریتم الر یک الگوریتم تولید پیچ ​​و خم است که با استفاده از رویکرد ردیف به ردیف، پیچ و خم های کامل (پیچ وخم های بدون حلقه و یک مسیر واحد بین هر دو نقطه) را به طور موثر تولید می کند. پیچ و خم هایی شبیه به الگوریتم کروسکال تولید می کند، اما این کار را با تولید فقط یک ردیف در یک زمان، بدون نیاز به ذخیره کل پیچ و خم در حافظه انجام می دهد. این آن را برای تولید پیچ ​​و خم های بسیار بزرگ در سیستم های بسیار محدود و برای تولید محتوای رویه ای مفید می کند.

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

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

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

الگوریتم الر توسط دیوید الر معرفی شد.

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

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

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

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

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

• به هر سلول در ردیف یک شناسه مجموعه منحصربفرد اختصاص دهید.

مرحله 2: به چند سلول مجاور به صورت افقی بپیوندید

• سلول‌های مجاور را با تنظیم آن‌ها روی همان شناسه مجموعه، به‌طور تصادفی ادغام کنید. این تضمین می کند که معابر افقی وجود دارد.

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

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

مرحله 4: به ردیف بعدی بروید

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

مرحله 5: مراحل 2-4 را تکرار کنید تا به آخرین ردیف برسید

• به پردازش ردیف به ردیف ادامه دهید.

مرحله 6: ردیف نهایی را پردازش کنید

• با ادغام مجموعه‌های مجزای باقی‌مانده، مطمئن شوید که تمام سلول‌های ردیف آخر به یک مجموعه تعلق دارند.