الگوریتم ایجاد هزارتو

روش‌های مبتنی بر نظریه گراف‌ها

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

نسخه اصلاح شده

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

روش تقسیم بازگشتی

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

الگوریتم‌های ساده

الگوریتم‌های دیگری نیز وجود دارند که تنها به میزان کافی حافظه برای ذخیره یک ردیف از یک هزارتو دوبعدی یا یک صفحه از یک هزارتو سه‌بعدی نیازمند هستند. این الگوریتم‌ها با ذخیره کردن خانه‌هایی در ردیف کنونی که به خانه‌هایی از ردیف قبل مسیر دارند، از ایجاد حلقه جلوگیری می‌کنند.
اکثر الگوریتم‌های تولید هزارتو برای اطمینان از قابل حل بودن هزارتو نهایی، نیازمند نگه‌داری ارتباط میان خانه‌های درونی هستند. هرچند هزارتوهای معتبر و همبند تنها با تمرکز بر روی هر خانه قابل تولید هستند.
هزارتو درخت دودویی، یک هزارتو استاندارد با خطوط عمود بر هم است که در آن هر خانه یک راهرو به سمت بالا یا چپ دارد اما هر دو آن‌ها را نمی‌تواند داشته باشد.
برای ساخت یک هزارتو درخت دودویی، برای هر خانه با انداختن سکه تصمیم گرفته می‌شود که حرکت به سمت بالا یا چپ انجام شود. برای خانه‌های روی مرز همواره یک جهت اتخاذ می‌شود و نتیجه نهایی یک هزارتو معتبر همبند ساده خواهد بود که ظاهری مانند درخت دودوییای دارد که ریشه آن، خانه بالا سمت چپ است.
جای‌گزین انداختن سکه برای هر خانه، ساخت یک عکس با استفاده از ترکیبی تصادفی از کاراکترهای ممیز و ممیز رو به عقب ("\") است. این روش یک هزارتو همبند ساده و معتبر را ایجاد نمی‌کند اما گروهی از حلقه‌های بسته را ایجاد می‌کند (راهنمای استفاده از کمودور ۶۴ یک برنامه پایه را با استفاده از این الگوریتم ارائه می‌دهد، با این تفاوت که از کاراکترهای مورب گرافیکی PETSCII برای یک نمایش گرافیکی روان‌تر استفاده می‌کند).

الگوریتم‌های خودکاره مشبک

انواع مشخصی از خودکاره‌های شبکه می‌توانند در تولید هزارتو مورد استفاده قرار گیرند. دو نوع مشهور از این خودکاره‌های شبکه، ماز و مازکتریک، دارای قوانین رشته‌ایB۳/S۱۲۳۴۵ و B۳/S۱۲۳۴ هستند.
در حالت اول، این بدان معنی است که هر خانه به این شرط از یک مرحله به مرحله بعدی باقی می‌ماند که حداقل یک و حداکثر پنج همسایه داشته باشد. در حالت دوم، هر خانه با داشتن یک تا چهار همسایه باقی می‌ماند. اگر خانه‌ای دقیقاً سه همسایه داشته باشد متولد می‌شود.
برای یک الگوی شروع تصادفی، این خودکاره‌های تولیدکننده هزارتو مشبک به تولید هزارتوهایی پیچیده منجر می‌شوند که دیوارهای راهروهای آن به‌طور غیرمبهمی ترسیم شده‌اند.
مازکتریک که دارای قانون B۳/S۱۲۳۴ است، در مقایسه با ماز با قانون B۳/S۱۲۳۴۵ گرایشی به تولید راهروهای طولانی و باریک دارد. این یک عیب قابل توجه محسوب می‌شود چرا که این هزارتوها به نسبت قابل پیش‌بینی می‌شوند.
مانند برخی از روش‌های مبتنی بر نظریه گراف که در بالا به تفصیل بیان شد، این خودکاره‌های مشبک عموماً هزارتوهایی از یک الگوی آغازین یکتا تولید می‌کنند؛ بنابراین معمولاً منجر به تولید هزارتوهایی می‌شوند که یافتن راه به خانه ابتدایی در آن‌ها به نسبت ساده است، حال آنکه راه‌یابی به دیگر خانه‌ها به نسبت دشوارتر است.

شبه کد جاوا

class MazeBuilder implements Runnable {
    public static final int CW_TOP = 1;
    public static final int CW_BOT = 2;
    public static final int CW_LEFT = 4;
    public static final int CW_RIGHT = 8;
    static final int CW_VIRGIN = 16;
    public static final int CW_ALL = CW_TOP|CW_BOT|CW_LEFT|CW_RIGHT;
    static final int CW_BOUND_SHIFT = 5;
    static final int CW_TOP_BOUND = 32;
    static final int CW_BOT_BOUND = 64;
    static final int CW_LEFT_BOUND = 128;
    static final int CW_RIGHT_BOUND = 256;
    static final int CW_ALL_BOUNDS =
CW_TOP_BOUND|CW_BOT_BOUND|CW_LEFT_BOUND|CW_RIGHT_BOUND;
    static final int CW_IN_ROOM = 512;
    
    public static int dirsx[] = { 1, 0, -1, 0 };
    public static int dirsy[] = { 0, 1, 0, -1 };
    int width, height, startx, starty;
    int cells[][], origdirs[][], dists[][];
    
    boolean can_go(int x, int y, int dx, int dy) {
int bit = get_bit(dx, dy) << CW_BOUND_SHIFT;
if ((cells[x][y] & bit) != 0)
    return false;
return (cells[x+dx][y+dy] & CW_VIRGIN) != 0;
    }
    
    int get_bit(int dx, int dy) {
int bit = 0;
switch (dx + dy * 2) {
case 1:  bit = CW_RIGHT; break;
case -1: bit = CW_LEFT;  break;
case 2:  bit = CW_BOT;   break;
case -2: bit = CW_TOP;   break;
default: dbg("get_bit problem "+dx+" "+dy); break;
}
return bit;
    }

    Random random;
    Maze maze;
    
    int randno(int lo, int hi) {
return (Math.abs(random.nextInt()) % (hi-lo+1)) + lo;
    }

    void delwall(int x, int y, int dx, int dy) {
int bit;
bit = get_bit(dx, dy);
cells[x][y] &= ~bit;
bit = get_bit(-dx, -dy);
cells[x+dx][y+dy] &= ~bit;
    }

    void delbound(int x, int y, int dx, int dy) {
int bit;
bit = get_bit(dx, dy);
cells[x][y] &= ~(bit << CW_BOUND_SHIFT);
bit = get_bit(-dx, -dy);
cells[x+dx][y+dy] &= ~(bit << CW_BOUND_SHIFT);
    }

    void addboundwall(int x, int y, int dx, int dy) {
int bit = get_bit(dx, dy);
cells[x][y] |= bit | (bit<<CW_BOUND_SHIFT);
int bit2 = get_bit(-dx, -dy);
cells[x+dx][y+dy] |= bit2 | (bit2<<CW_BOUND_SHIFT);
    }

    int partiters = 0;
    
    int grade_partition(Vector sl, Seg pe) {
int x  = pe.x;
int y  = pe.y;
int dx = pe.dx;
int dy = pe.dy;
int lcount = 0, rcount = 0, splits = 0;
int inc = 1;
if (sl.size() >= 100)
    inc = sl.size() / 50;
for (int i = 0; i < sl.size(); i += inc) {
    Seg se = (Seg) sl.elementAt(i);
    int df1x = se.x-x;
    int df1y = se.y-y;
    int sendx = se.x + se.dx;
    int sendy = se.y + se.dy;
    int df2x = sendx - x;
    int df2y = sendy - y;
    int nx = dy;
    int ny = -dx;
    int dot1 = df1x * nx + df1y * ny;
    int dot2 = df2x * nx + df2y * ny;
    if (getSign(dot1) != getSign(dot2)) {
if (dot1 == 0)
    dot1 = dot2;
else if (dot2 != 0) {
    splits++;
    continue;
}
    }
    if (dot1 > 0 ||
       (dot1 == 0 && se.GetDir() ==  pe.GetDir())) {
rcount++;
    } else if (dot1 < 0 ||
       (dot1 == 0 && se.GetDir() == -pe.GetDir())) {
lcount++;
    } else {
dbg("grade_partition problem: dot1 = "+dot1+", dot2 = "+dot2);
    }
}
return Math.abs(lcount-rcount) + splits * 3;
    }
    
    Vector seglist;
    static int getSign(int num) {
return (num < 0) ? -1 : (num > 0) ? 1 : 0;
    }
    void Initialize() {
int x, y;

for (x = 0; x != width; x++) {
    for (y = 0; y != height; y++) {
cells[x][y] = CW_VIRGIN | CW_ALL;
    }
    cells[x][0] |= CW_TOP_BOUND;
    cells[x][height-1] |= CW_BOT_BOUND;
} 
for (y = 0; y != height; y++) {
    cells[0][y] |= CW_LEFT_BOUND;
    cells[width-1][y] |= CW_RIGHT_BOUND;
}
    }
    
    void Generate() {
int x, y;

y = 0;
int firstx = x = randno(0, width-1);
int dir = 0;
int origdir = dir;
cells[x][y] &= ~CW_VIRGIN;
while (true) { 
    int dx = dirsx[dir], dy = dirsy[dir];
    if (!can_go(x, y, dx, dy)) { 
dir = (dir+1) & 3;
if (origdir == dir) {
    if (x == firstx && y == 0)
break;
    int odr = origdirs[x][y];
    dx = dirsx[odr];
    dy = dirsy[odr];
    x -= dx;
    y -= dy;
    origdir = dir = randno(0, 3);
}
    } else {
delwall(x, y, dx, dy);
x += dx;
y += dy;
cells[x][y] &= ~CW_VIRGIN;
origdirs[x][y] = dir;
origdir = dir = randno(0, 3);
    }
}