هزارتو

مانند الگوریتم جستجوی عمق-اول، یافتن راه به سمت خانه اول معمولاً به نسبت ساده است اما به سمت دیگر خانه‌های هزارتو دشوار.

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

اکثر الگوریتم‌های تولید هزارتو برای اطمینان از قابل حل بودن هزارتو نهایی، نیازمند نگه‌داری ارتباط میان خانه‌های درونی هستند. هرچند هزارتوهای معتبر و همبند تنها با تمرکز بر روی هر خانه قابل تولید هستند.

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

تو خدای خویی تو صفات هویی تو یکی نباشی تو هزارتویی

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

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

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

ور هوش تو بی‌خبر شد از گوش یک توی نه ای هزارتویی

هزارتو درخت دودویی، یک هزارتو استاندارد با خطوط عمود بر هم است که در آن هر خانه یک راهرو به سمت بالا یا چپ دارد اما هر دو آن‌ها را نمی‌تواند داشته باشد.

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