الگوریتم های ایجاد هزارتو روش هایی خودکار برای تولید هزارتو ( ماز ) هستند.
یک هزارتو می تواند توسط یک چیدمان از پیش تعیین شده از خانه ها با دیوارهایی در بین آن ها تولید شود. خانه ها به طور معمول شبکه های مستطیلی هستند اما چیدمان های دیگر هم ممکن است. این چیدمان های از پیش تعیین شده را می توان در قالب گراف همبند تصور کرد که در آن یال ها نشانگر مکان های ممکن برای دیوار و گره ها نشانگر خانه ها باشند. در این صورت هدف این الگوریتم را می توان ساختن یک زیر گراف در نظر گرفت. زیرگرافی که در آن یافتن یک مسیر بین دو راس مشخص مورد بررسی باشد. اگر زیرگراف همبند نباشد، آنگاه قسمت هایی در گراف وجود خواهد داشت که بی استفاده می مانند. چرا که آن ها نقشی در فضای جستجو بازی نمی کنند. اگر گراف شامل حلقه باشد، آنگاه امکان وجود چندین مسیر بین دو راس مشخص وجود دارد. به همین علت، تولید هزارتو به طور معمول از طریق تولید درخت پوشای تصادفی انجام می شود. حلقه ها می توانند موجب سردرگمی بازیکنان کم تجربه شوند. حلقه ها را می توان با اضافه کردن یال های تصادفی به نتیجه در مسیر تولید گراف ایجاد کرد.
این الگوریتم یک نسخه تصادفی از الگوریتم جستجوی عمق - اول است. این الگوریتم که غالباً توسط پشته پیاده سازی می شود یکی از ساده ترین راه ها برای تولید یک هزارتو توسط رایانه است. فضای هزارتو را یک شبکه بزرگ از خانه ها ( مانند یک صفحه شطرنج ) تصور کنید به طوری که هر خانه در آن با ۴ دیوار در اطراف آن وجود دارند. با آغاز از یک خانه تصادفی، برنامه یکی از همسایه های آن خانه را که تاکنون انتخاب نشده است به طور تصادفی انتخاب می کند. حال دیوار بین آن دو خانه برداشته می شود و خانه جدید به پشته اضافه می شود ( این کار مشابه کشیدن یک خط روی زمین است ) . سپس برنامه با همین روند ادامه پیدا می کند، با رسیدن به خانه ای که هیچ همسایهٔ قابل عزیمتی ندارد ( همه همسایه های آن دیده شده اند ) برنامه به بن بست می رسد. در این مرحله مسیر طی شده در جهت عکس طی می شود تا اولین رأس با حداقل یک همسایه رویت نشده یافت شود. سپس مسیر با رویت این خانه جدید ادامه پیدا می کند ( این کار معادل ساخت یک نقطه اتصال در هزارتو است ) . کار تا جایی ادامه پیدا می کند که تمامی خانه ها یک بار رویت شوند. در این حالت برنامه تمام مسیر را به سمت خانه اولیه بازمی گردد. این رویکرد، مشاهده تمام خانه های فضای هزارتو را تضمین می کند. همان طور که پیشتر بیان شد الگوریتم بسیار ساده عمل کرده و به تبع آن هزارتوهای بسیار پیچیده ای را هم تولید نمی کند. برخی اصلاحات مانند اصلاحات زیر می تواند به پیچیده تر کردن هزارتوهای ساخته شده کمک کند.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفیک هزارتو می تواند توسط یک چیدمان از پیش تعیین شده از خانه ها با دیوارهایی در بین آن ها تولید شود. خانه ها به طور معمول شبکه های مستطیلی هستند اما چیدمان های دیگر هم ممکن است. این چیدمان های از پیش تعیین شده را می توان در قالب گراف همبند تصور کرد که در آن یال ها نشانگر مکان های ممکن برای دیوار و گره ها نشانگر خانه ها باشند. در این صورت هدف این الگوریتم را می توان ساختن یک زیر گراف در نظر گرفت. زیرگرافی که در آن یافتن یک مسیر بین دو راس مشخص مورد بررسی باشد. اگر زیرگراف همبند نباشد، آنگاه قسمت هایی در گراف وجود خواهد داشت که بی استفاده می مانند. چرا که آن ها نقشی در فضای جستجو بازی نمی کنند. اگر گراف شامل حلقه باشد، آنگاه امکان وجود چندین مسیر بین دو راس مشخص وجود دارد. به همین علت، تولید هزارتو به طور معمول از طریق تولید درخت پوشای تصادفی انجام می شود. حلقه ها می توانند موجب سردرگمی بازیکنان کم تجربه شوند. حلقه ها را می توان با اضافه کردن یال های تصادفی به نتیجه در مسیر تولید گراف ایجاد کرد.
این الگوریتم یک نسخه تصادفی از الگوریتم جستجوی عمق - اول است. این الگوریتم که غالباً توسط پشته پیاده سازی می شود یکی از ساده ترین راه ها برای تولید یک هزارتو توسط رایانه است. فضای هزارتو را یک شبکه بزرگ از خانه ها ( مانند یک صفحه شطرنج ) تصور کنید به طوری که هر خانه در آن با ۴ دیوار در اطراف آن وجود دارند. با آغاز از یک خانه تصادفی، برنامه یکی از همسایه های آن خانه را که تاکنون انتخاب نشده است به طور تصادفی انتخاب می کند. حال دیوار بین آن دو خانه برداشته می شود و خانه جدید به پشته اضافه می شود ( این کار مشابه کشیدن یک خط روی زمین است ) . سپس برنامه با همین روند ادامه پیدا می کند، با رسیدن به خانه ای که هیچ همسایهٔ قابل عزیمتی ندارد ( همه همسایه های آن دیده شده اند ) برنامه به بن بست می رسد. در این مرحله مسیر طی شده در جهت عکس طی می شود تا اولین رأس با حداقل یک همسایه رویت نشده یافت شود. سپس مسیر با رویت این خانه جدید ادامه پیدا می کند ( این کار معادل ساخت یک نقطه اتصال در هزارتو است ) . کار تا جایی ادامه پیدا می کند که تمامی خانه ها یک بار رویت شوند. در این حالت برنامه تمام مسیر را به سمت خانه اولیه بازمی گردد. این رویکرد، مشاهده تمام خانه های فضای هزارتو را تضمین می کند. همان طور که پیشتر بیان شد الگوریتم بسیار ساده عمل کرده و به تبع آن هزارتوهای بسیار پیچیده ای را هم تولید نمی کند. برخی اصلاحات مانند اصلاحات زیر می تواند به پیچیده تر کردن هزارتوهای ساخته شده کمک کند.
wiki: الگوریتم ایجاد هزارتو