Máy tạo mê cung thuật toán Wilson

Thuật toán Wilson là một phương pháp đi bộ ngẫu nhiên xóa vòng lặp tạo ra các cây bao trùm đồng nhất để tạo mê cung. Điều này có nghĩa là tất cả các mê cung có thể có cùng kích thước đều có khả năng được tạo ra như nhau, khiến nó trở thành một kỹ thuật tạo mê cung không thiên vị. Thuật toán Wilson có thể được coi là phiên bản cải tiến của thuật toán Aldous-Broder, vì nó tạo ra các mê cung có đặc điểm giống hệt nhau, nhưng chạy nhanh hơn nhiều, vì vậy tôi không bận tâm đến việc triển khai thuật toán Aldous-Broder ở đây.

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 Wilson

Thuật toán Wilson để tạo ra các cây khung đồng nhất sử dụng tường ngẫu nhiên bị xóa vòng lặp được tạo ra bởi David Bruce Wilson.

Wilson ban đầu giới thiệu thuật toán này vào năm 1996 khi nghiên cứu cây bao trùm ngẫu nhiên và chuỗi Markov trong lý thuyết xác suất. Mặc dù công trình của ông chủ yếu là về toán học và vật lý thống kê, thuật toán này đã được áp dụng rộng rãi để tạo mê cung do khả năng tạo ra mê cung hoàn toàn đồng nhất.

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

Thuật toán của Wilson đảm bảo rằng mê cung cuối cùng được kết nối hoàn toàn mà không có bất kỳ vòng lặp nào bằng cách lặp đi lặp lại việc tạo ra các đường dẫn từ các ô chưa được đi qua bằng cách sử dụng các bước đi ngẫu nhiên.

Bước 1: Khởi tạo

• Bắt đầu bằng một lưới có nhiều bức tường.
• Xác định danh sách tất cả các ô có thể đi qua.

Bước 2: Chọn một ô bắt đầu ngẫu nhiên

• Chọn bất kỳ ô ngẫu nhiên nào và đánh dấu là đã ghé thăm. Đây là điểm bắt đầu của mê cung trong quá trình tạo.

Bước 3: Đi bộ ngẫu nhiên với xóa vòng lặp

• Chọn một ô chưa được ghé thăm và bắt đầu di chuyển ngẫu nhiên (di chuyển theo các hướng ngẫu nhiên).
• Nếu đường đi đến một ô đã từng đi qua, hãy xóa mọi vòng lặp trên đường đi.
• Khi đường đi kết nối đến khu vực đã ghé thăm, hãy đánh dấu tất cả các ô trên đường đi là đã ghé thăm.

Bước 4: Lặp lại cho đến khi tất cả các ô được truy cập :

• Tiếp tục chọn các ô chưa được ghé thăm và thực hiện di chuyển ngẫu nhiên cho đến khi mọi ô đều là một phần của mê cung.