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

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

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

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

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

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

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

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

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

از لحاظ تئوری می‌توان از آن برای تولید هزارتوهای بی‌نهایت استفاده کرد، با این حال برای اطمینان از اینکه هزارتوی تولید شده واقعاً قابل حل است، لازم است در مقطعی به منطق «ردیف نهایی» تغییر دهید تا هزارتو را تمام کنید.

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

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

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

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

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

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

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

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

مرحله ۵: مراحل ۲ تا ۴ را تا رسیدن به آخرین ردیف تکرار کنید

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

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

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

مطالعه بیشتر

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

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