Máy phát mê cung thuật toán cây phát triển

Thuật toán Cây Phát Triển rất thú vị vì nó có thể mô phỏng hành vi của một số thuật toán khác, tùy thuộc vào cách chọn ô tiếp theo trong quá trình tạo cây. Việc triển khai trên trang này sử dụng phương pháp tìm kiếm theo chiều rộng, giống như hàng đợ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 cây phát triển

Thuật toán Cây Phát Triển là một phương pháp linh hoạt và mạnh mẽ để tạo ra các mê cung hoàn hảo. Thuật toán này thú vị vì nó có thể mô phỏng hành vi của một số thuật toán tạo mê cung khác, chẳng hạn như thuật toán Prim, thuật toán quay lui đệ quy và thuật toán chia đệ quy, tùy thuộc vào cách bạn chọn ô tiếp theo để xử lý.

Cách thức hoạt động của thuật toán cây phát triển

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

• Bắt đầu với một lưới các ô chưa được thăm.
• Chọn ngẫu nhiên một ô bắt đầu và thêm nó vào danh sách.

Bước 2: Vòng lặp tạo mê cung

• Trong khi danh sách ô chưa trống: Chọn một ô từ danh sách dựa trên một chiến lược cụ thể (được giải thích bên dưới). Tạo một đường đi từ ô đã chọn đến một trong những ô lân cận chưa được ghé thăm (được chọn ngẫu nhiên). Thêm ô lân cận đó vào danh sách vì nó hiện là một phần của mê cung. Nếu ô đã chọn không có ô lân cận nào chưa được ghé thăm, hãy xóa nó khỏi danh sách.

Bước 3: Kết thúc

• Thuật toán kết thúc khi không còn ô nào trong danh sách, nghĩa là toàn bộ mê cung đã được khắc xong.

Chiến lược lựa chọn tế bào (Tính linh hoạt của thuật toán)

Điểm đặc trưng của thuật toán Cây Phát Triển là cách bạn chọn ô nào sẽ được xử lý tiếp theo. Lựa chọn này ảnh hưởng rất lớn đến hình dạng của mê cung:

Ô mới nhất (Hành vi giống ngăn xếp) – Thuật toán quay lui đệ quy:

• Luôn chọn ô được thêm vào gần đây nhất.
• Tạo ra những hành lang dài, ngoằn ngoèo với nhiều ngõ cụt (giống như mê cung tìm kiếm theo chiều sâu).
• Mê cung thường có những lối đi dài và dễ giải.

Ô ngẫu nhiên (Thuật toán Prim ngẫu nhiên):

• Mỗi lần chọn ngẫu nhiên một ô từ danh sách.
• Tạo ra một mê cung được phân bố đều hơn với các đường đi phức tạp và rối rắm.
• Ít hành lang dài hơn và nhiều đường rẽ hơn.

Tế bào lâu đời nhất (Hành vi giống như xếp hàng):

• Luôn chọn ô cũ nhất trong danh sách.
• Tạo ra các mê cung có sự phân bố đồng đều hơn, giống như mô hình tìm kiếm theo chiều rộng.
• Các lối đi ngắn, rậm rạp với mật độ kết nối dày đặc.
• (Đây là phiên bản đã được triển khai ở đây)

Các phương pháp kết hợp:

Kết hợp các chiến lược cho các đặc điểm mê cung khác nhau. Ví dụ:

• 90% mới nhất, 10% ngẫu nhiên: Nhìn chung giống như một mê cung quay lui đệ quy, nhưng thỉnh thoảng có các nhánh rẽ giúp phá vỡ các hành lang dài.
• 50% cây mới nhất, 50% cây cũ nhất: Cân bằng giữa các hành lang dài và sự phát triển rậm rạp của cây.

Đọ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 tạo mê cung thuật toán Wilson
• Máy phát mê cung thuật toán Kruskal