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

Thuật toán Wilson là một phương pháp bước 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ó với kích thước nhất định đề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à một 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 nó chạy nhanh hơn nhiều, vì vậy tôi không cần phải 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 đó.

Giới thiệu về thuật toán Wilson

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

Wilson lần đầu giới thiệu thuật toán này vào năm 1996 khi nghiên cứu về 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 thuộc lĩnh vực toán học và vật lý thống kê, thuật toán này sau đó đã được áp dụng rộng rãi để tạo mê cung nhờ khả năng tạo ra các mê cung hoàn toàn đồng nhất.

Cách thuật toán Wilson hoạt động để tạo mê cung

Thuật toán Wilson đảm bảo 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 liên tục tạo ra các đường đi từ các ô chưa được thăm bằng cách sử dụng các bước đi ngẫu nhiên.

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

• Hãy bắt đầu với một lưới gồm các 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 ngẫu nhiên một ô và đánh dấu nó là đã được ghé thăm. Ô này sẽ đóng vai trò là điểm bắt đầu của mê cung trong quá trình tạo ra mê cung.

Bước 3: Thuật toán bước ngẫu nhiên có xóa vòng lặp

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

Bước 4: Lặp lại cho đến khi tất cả các ô đều được duyệt qua:

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

Đọ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 Recursive Backtracker
• Máy phát mê cung thuật toán Kruskal
• Trình tạo mê cung thuật toán của Eller