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 sửa đổi của Recursive Backtracker. Bản sửa đổi bao gồm việc quét (hoặc "săn") một cách có hệ thống một ô mới để tiếp tục khi nó không thể đi xa hơn, trái ngược với tìm kiếm đệ quy thực sự, sẽ luôn quay trở lại ô trước đó trên ngăn xếp.

Vì lý do này, thuật toán này có thể dễ dàng được điều chỉnh để tạo ra các mê cung có giao diện và cảm giác khác nhau, chỉ bằng cách chọn vào chế độ "săn" 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" khi không thể đi xa hơn khỏi ô 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 đó.

Về thuật toán săn và giết

Thuật toán Hunt and Kill là một phương pháp đơn giản nhưng hiệu quả để tạo ra mê cung. Nó có phần giống với tìm kiếm theo chiều sâu (tức là thuật toán Recursive Backtracker), ngoại trừ khi nó không thể đi xa hơn vị trí hiện tại, nó sẽ quét (hoặc "săn") một cách có hệ thống trên 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: đi bộ và săn.

Thuật toán săn và giết hoạt động như thế nào để tạo ra mê cung

Bước 1: Bắt đầu từ một ô ngẫu nhiên

• Tìm một ô ngẫu nhiên trong lưới và đánh dấu ô đó là đã ghé thăm.

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

• Chọn ngẫu nhiên một người hàng xóm chưa từng đến thăm.
• Di chuyển đến ô lân cận đó, đánh dấu là đã truy cập và tạo một đường đi 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 ghé thăm.

Bước 3: Giai đoạn săn tìm (Quay lại thông qua quét)

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