موضوع مقاله: الگوریتم ایجاد هزارتو | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم ایجاد هزارتو | مقدمه: روش‌های مبتنی بر نظریه گراف‌ها یک هزارتو می‌تواند توسط یک چیدمان از پیش تعیین شده از خانه‌ها با دیوارهایی در بین آن‌ها تولید شود. | ## بخش 1: الگوریتم ایجاد هزارتو | این چیدمان‌های از پیش تعیین شده را می‌توان در قالب گراف همبند تصور کرد که در آن یال‌ها نشانگر مکان‌های ممکن برای دیوار و گره‌ها نشانگر خانه‌ها باشند. اگر زیرگراف همبند نباشد، آنگاه قسمت‌هایی در گراف وجود خواهد داشت که بی‌استفاده می‌مانند. به همین علت، تولید هزارتو به‌طور معمول از طریق تولید درخت پوشای تصادفی انجام می‌شود. حلقه‌ها را می‌توان با اضافه کردن یال‌های تصادفی به نتیجه در مسیر تولید گراف ایجاد کرد. این الگوریتم که غالباً توسط پشته پیاده‌سازی می‌شود یکی از ساده‌ترین راه‌ها برای تولید یک هزارتو توسط رایانه است. فضای هزارتو را یک شبکه بزرگ از خانه‌ها (مانند یک صفحه شطرنج) تصور کنید به‌طوری‌که هر خانه در آن با ۴ دیوار در اطراف آن وجود دارند. با آغاز از یک خانه تصادفی، برنامه یکی از همسایه‌های آن خانه را که تاکنون انتخاب نشده‌است به‌طور تصادفی انتخاب می‌کند. حال دیوار بین آن دو خانه برداشته می‌شود و خانه جدید به پشته اضافه می‌شود (این کار مشابه کشیدن یک خط روی زمین است). سپس برنامه با همین روند ادامه پیدا می‌کند، با رسیدن به خانه‌ای که هیچ همسایهٔ قابل عزیمتی ندارد (همه همسایه‌های آن دیده شده‌اند) برنامه به بن‌بست می‌رسد. در این مرحله مسیر طی شده در جهت عکس طی می‌شود تا اولین رأس با حداقل یک همسایه رویت نشده یافت شود. سپس مسیر با رویت این خانه جدید ادامه پیدا می‌کند (این کار معادل ساخت یک نقطه اتصال در هزارتو است). همان‌طور که پیشتر بیان شد الگوریتم بسیار ساده عمل کرده و به تبع آن هزارتوهای بسیار پیچیده‌ای را هم تولید نمی‌کند. برخی اصلاحات مانند اصلاحات زیر می‌تواند به پیچیده‌تر کردن هزارتوهای ساخته شده کمک کند. برای هر همسایه و با شروع از یک همسایه تصادفی، اگر آن همسایه هنوز رویت نشده بود، دیوار بین آن و خانه اولیه را حذف کن و سپس برای آن همسایه همین عمل را به‌طور بازگشتی انجام بده. همان‌طور که در بالا اشاره شد این الگوریتم دربردارنده یک روند بازگشتی عمیق است که در برخی معماری‌های رایانه می‌تواند موجب سرریز از پشته شود. می‌توان با ذخیره کردن اطلاعات حاصل از بازگشت از هر خانه بر روی هزارتو الگوریتم را به یک حلقه تغییر داد. این کار در عین حال یک راه سریع برای نشان‌دادن جواب را نیز ارائه می‌دهد:با شروع از هر خانه و بازگشت مسیر به سمت خانه خروج می‌توان مسیر موردنظر را تولید کرد. هزارتوهایی که با روش جستجوی عمق-اول ایجاد می‌شوند ضریب شاخه کمتری دارند (شکست‌های کمتری در هر شاخه به وجود می‌آورند) و راهروهای زیادی را دربردارند. این امر باعث می‌شود که الگوریتم جستجوی عمق-اول برای تولید هزارتو در بازی‌های ویدئویی مناسب باشد. با حذف کردن تصادفی تعدادی از دیوارها در هزارتوی تولید شده با این روش، می‌توان راهروهای طولانی و باریک را شاخه‌دارتر کرد. پس‌گردان بازگشتی الگوریتم جستجوی عمق-اول در تولید هزارتو به‌طور معمول با استفاده از روش پس‌گرد Backtrack پیاده‌سازی می‌شود. | ## بخش 2: الگوریتم ایجاد هزارتو | تا زمانی که خانه‌ای وجود دارد که دیده نشده باشد: اگر خانه جاری همسایه‌ای دارد که دیده نشده‌است: یکی از همسایه‌ها را به‌طور تصادفی انتخاب کن. در غیر این صورت: یک خانه تصادفی را انتخاب کن و آن را خانه جاری قرار بده و آن را به عنوان دیده‌شده علامت بزن. فهرستی از تمامی دیوارها تهیه کن و یک مجموعه برای هر خانه ایجاد کن که تنها عضو آن همان خانه باشد. برای هر دیوار با یک ترتیب تصادفی کارهای زیر را انجام بده: اگر خانه‌هایی که با این دیوار از یکدیگر جدا می‌شوند به مجموعه‌های متفاوتی تعلق داشتند: دیوار جاری را حذف کن. داده ساختارهای متفاوتی وجود دارند که می‌توانند مجموعه‌هایی از خانه‌ها را شبیه‌سازی کنند. یک راه پیاده‌سازی کارا که توسط داده ساختار مجموعه‌های مجزا صورت می‌گیرد، می‌تواند هر عمل اجتماع و یافتن روی دو مجموعه را به‌طور سرشکن در زمان خطی انجام دهد (به‌طور دقیق تر زمان ; به ازای هر ). بنابراین زمان اجرای این الگوریتم در اصل با تعداد دیوارهای موجود در هزارتو متناسب است. این مسئله که فهرست دیوارها ابتدا به‌طور تصادفی مقداردهی اولیه شود یا هر دیوار به‌طور تصادفی از بین فهرست غیرتصادفی از دیوارها انتخاب شود، اهمیت چندانی ندارد. از آنجا که نتیجه این الگوریتم، تولید درخت پوشای کمینه یک گراف با یال‌های هم‌وزن است، الگوریتم به سمت تولید الگوهای منظمی که به نسبت ساده‌تر حل می‌شوند، متمایل است. تا زمانی که فهرست دیوارها عضو دارد: یک دیوار را به‌طور تصادفی انتخاب کن، اگر خانه در سمت دیگر دیوار هنوز به هزارتو اضافه نشده‌است: دیوار را یک گذرگاه قرار بده و خانه‌ای که در سمت دیگر دیوار قرار داشت را بخشی از هزارتو قرار بده. اگر خانه در سمت دیگر دیوار قبلاً به هزارتو اضافه شده بود، دیوار مورد بررسی را از فهرست دیوارها حذف کن. مانند الگوریتم جستجوی عمق-اول، یافتن راه به سمت خانه اول معمولاً به نسبت ساده است اما به سمت دیگر خانه‌های هزارتو دشوار. توجه کنید که اجرای الگوریتم کلاسیک پریم بر روی یک گراف با وزن تصادفی هزارتوهایی با الگویی مشابه با هزارتوهای تولید شده در الگوریتم کروسکال ایجاد می‌کند. نسخه اصلاح شده با وجود اینکه الگوریتم کلاسیک پریم فهرستی از یال‌ها را ذخیره می‌کند، برای تولید هزارتو می‌توان لیستی از خانه‌های مجاور به هر خانه را ذخیره کرد. اگر یک خانه تصادفی توسط چندین یال به هزارتو موجود متصل شود یکی از این یال‌ها به‌طور تصادفی انتخاب می‌شود. این روش تمایل بیشتری به ایجاد شاخه نسبت به روش بالا که مبتنی بر ذخیره یال بود دارد. یک الگوریتم برای این کار در زیر شرح داده شده‌است: از یک فضای بدون دیوار شروع کن و آن را یک اتاق بنام. اتاق را با دیوارهایی که به‌طور تصادفی قرار می‌گیرند تقسیم کن (برای هر دیوار یک دهانه برای شروع یک راهرو، در نقطه‌ای تصادفی روی آن دیوار قرار دارد). حال به‌طور بازگشتی همین عملیات را روی اتاق‌های درونی انجام بده تا زمانی که همه اتاق‌ها به اندازه کمینه برسند. این روش منجر به تولید هزارتوهایی می‌شود که در آن‌ها دیوارهای راست و طولانی عبور می‌کنند. این الگو هزارتوهایی تولید می‌کند که در آن‌ها نواحی‌ای که بهتر است از ورود به آن‌ها خودداری شود، ساده‌تر دیده می‌شوند. | ## بخش 3: الگوریتم ایجاد هزارتو | برای مثال، در یک هزارتو مستطیلی، در یک نقطه تصادفی از فضا دو دیوار که به یکدیگر عمود هستند را بسازید. این دو دیوار اتاق اولیه را به چهار اتاق کوچک‌تر تقسیم می‌کنند که توسط چهار دیوار از یکدیگر جدا شده‌اند. سه دیوار از این چهار دیوار را به‌طور تصادفی انتخاب کنید و یک روی هر کدام از آن‌ها و در نقطه‌ای تصادفی بر روی آن‌ها یک دهانه ورودی به عرض یک واحد ایجاد کنید. این روند را به‌طور بازگشتی ادامه دهید تا زمانی که تمامی اتاق‌ها عرضی برابر یک واحد در یکی از بعدهای خود داشته باشند. پله‌های رو به بالا با نماد "/" و پله‌های رو به پایین با نماد "\" و پله‌های دو طرفه با نماد "x" نشان داده شده‌اند. الگوریتم‌های دیگری نیز وجود دارند که تنها به میزان کافی حافظه برای ذخیره یک ردیف از یک هزارتو دوبعدی یا یک صفحه از یک هزارتو سه‌بعدی نیازمند هستند. این الگوریتم‌ها با ذخیره کردن خانه‌هایی در ردیف کنونی که به خانه‌هایی از ردیف قبل مسیر دارند، از ایجاد حلقه جلوگیری می‌کنند. اکثر الگوریتم‌های تولید هزارتو برای اطمینان از قابل حل بودن هزارتو نهایی، نیازمند نگه‌داری ارتباط میان خانه‌های درونی هستند. هزارتو درخت دودویی، یک هزارتو استاندارد با خطوط عمود بر هم است که در آن هر خانه یک راهرو به سمت بالا یا چپ دارد اما هر دو آن‌ها را نمی‌تواند داشته باشد. برای ساخت یک هزارتو درخت دودویی، برای هر خانه با انداختن سکه تصمیم گرفته می‌شود که حرکت به سمت بالا یا چپ انجام شود. برای خانه‌های روی مرز همواره یک جهت اتخاذ می‌شود و نتیجه نهایی یک هزارتو معتبر همبند ساده خواهد بود که ظاهری مانند درخت دودوییای دارد که ریشه آن، خانه بالا سمت چپ است. جای‌گزین انداختن سکه برای هر خانه، ساخت یک عکس با استفاده از ترکیبی تصادفی از کاراکترهای ممیز و ممیز رو به عقب ("\") است. این روش یک هزارتو همبند ساده و معتبر را ایجاد نمی‌کند اما گروهی از حلقه‌های بسته را ایجاد می‌کند (راهنمای استفاده از کمودور ۶۴ یک برنامه پایه را با استفاده از این الگوریتم ارائه می‌دهد، با این تفاوت که از کاراکترهای مورب گرافیکی PETSCII برای یک نمایش گرافیکی روان‌تر استفاده می‌کند). الگوریتم‌های خودکاره مشبک انواع مشخصی از خودکاره‌های شبکه می‌توانند در تولید هزارتو مورد استفاده قرار گیرند. دو نوع مشهور از این خودکاره‌های شبکه، ماز و مازکتریک، دارای قوانین رشته‌ایB۳/S۱۲۳۴۵ و B۳/S۱۲۳۴ هستند. در حالت اول، این بدان معنی است که هر خانه به این شرط از یک مرحله به مرحله بعدی باقی می‌ماند که حداقل یک و حداکثر پنج همسایه داشته باشد. برای یک الگوی شروع تصادفی، این خودکاره‌های تولیدکننده هزارتو مشبک به تولید هزارتوهایی پیچیده منجر می‌شوند که دیوارهای راهروهای آن به‌طور غیرمبهمی ترسیم شده‌اند. مازکتریک که دارای قانون B۳/S۱۲۳۴ است، در مقایسه با ماز با قانون B۳/S۱۲۳۴۵ گرایشی به تولید راهروهای طولانی و باریک دارد. این یک عیب قابل توجه محسوب می‌شود چرا که این هزارتوها به نسبت قابل پیش‌بینی می‌شوند. | ## جمع‌بندی | مانند برخی از روش‌های مبتنی بر نظریه گراف که در بالا به تفصیل بیان شد، این خودکاره‌های مشبک عموماً هزارتوهایی از یک الگوی آغازین یکتا تولید می‌کنند؛ بنابراین معمولاً منجر به تولید هزارتوهایی می‌شوند که یافتن راه به خانه ابتدایی در آن‌ها به نسبت ساده است، حال آنکه راه‌یابی به دیگر خانه‌ها به نسبت دشوارتر است.