Máy phát mê cung săn và giết

Thuật toán Hunt and Kill thực chất là một phiên bản được sửa đổi của thuật toán Recursive Backtracker. Sự sửa đổi nằm ở việc quét (hay "săn lùng") một cách có hệ thống để tìm một ô mới để tiếp tục khi không thể đi xa hơn, trái ngược với tìm kiếm đệ quy thực sự, vốn luôn quay lại ô trước đó trong ngăn xếp.

Do đó, thuật toán này có thể dễ dàng được điều chỉnh để tạo ra các mê cung với hình thức và cảm giác khác nhau, chỉ bằng cách chọn vào chế độ "săn tìm" thường xuyên hơn hoặc theo các quy tắc cụ thể. Phiên bản được triển khai ở đây chỉ vào chế độ "săn tìm" khi nó không thể đi xa hơn ô hiện tại.

Một mê cung hoàn hảo là một mê cung mà chỉ có đúng một đường đi từ bất kỳ điểm nào trong mê cung đến bất kỳ điểm nào khác. Điều đó có nghĩa là bạn không thể đi vòng tròn, nhưng bạn sẽ thường gặp ngõ cụt, buộc bạn phải quay lại và quay trở lại.

Bản đồ mê cung được tạo ở đây bao gồm một phiên bản mặc định không có bất kỳ vị trí bắt đầu và kết thúc nào, vì vậy bạn có thể tự quyết định: sẽ có một giải pháp từ bất kỳ điểm nào trong mê cung đến bất kỳ điểm nào khác. Nếu bạn muốn có cảm hứng, bạn có thể bật vị trí bắt đầu và kết thúc được đề xuất - và thậm chí xem giải pháp giữa hai điểm đó.

Giới thiệu về thuật toán săn bắt và tiêu diệt

Thuật toán Săn lùng và Tiêu diệt là một phương pháp đơn giản nhưng hiệu quả để tạo ra mê cung. Nó tương tự như thuật toán tìm kiếm theo chiều sâu (tức là thuật toán Quay lui đệ quy), ngoại trừ việc khi không thể đi xa hơn từ vị trí hiện tại, nó sẽ quét (hoặc "săn lùng") một cách có hệ thống trong mê cung để tìm một ô mới để tiếp tục. Thuật toán bao gồm hai giai đoạn chính: di chuyển và săn lùng.

Cách thuật toán săn đuổi và tiêu diệt hoạt động trong việc tạo mê cung

Bước 1: Bắt đầu từ một ô bất kỳ

• Chọn ngẫu nhiên một ô trong lưới và đánh dấu ô đó là đã được thăm.

Bước 2: Giai đoạn đi bộ (Đi bộ ngẫu nhiên)

• Chọn ngẫu nhiên một ô lân cận chưa được ghé thăm.
• Di chuyển đến ô lân cận đó, đánh dấu nó là đã ghé thăm, và tạo một đường dẫn giữa ô trước và ô mới.
• Lặp lại cho đến khi không còn người hàng xóm nào chưa được ghé thăm.

Bước 3: Giai đoạn săn tìm (Quay ngược lại bằng cách quét)

• Quét lưới từng hàng (hoặc từng cột).
• Tìm ô chưa được thăm đầu tiên có ít nhất một ô lân cận đã được thăm.
• Kết nối ô đó với ô lân cận đã được ghé thăm để tiếp tục giai đoạn di chuyển.
• Lặp lại cho đến khi tất cả các ô đều được thăm dò.

Đọc thêm

Nếu bạn thích bài viết này, bạn cũng có thể thích những gợi ý sau:

• Trình tạo mê cung thuật toán của Eller
• Máy phát mê cung thuật toán cây phát triển
• Máy phát mê cung thuật toán Kruskal