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

Thuật toán Growing Tree 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. Việc triển khai trên trang này sử dụng phương pháp tiếp cận 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 đó.

Về thuật toán Growing Tree

Thuật toán Growing Tree là một phương pháp linh hoạt và mạnh mẽ để tạo ra 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, quay lui đệ quy và chia đệ quy, tùy thuộc vào cách bạn chọn ô tiếp theo để xử lý.

Thuật toán Growing Tree hoạt động như thế nào

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

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

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

• Trong khi danh sách ô không trống:
  • Chọn một ô từ danh sách dựa trên chiến lược cụ thể (giải thích bên dưới).
  • Khắc một lối đ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 người hàng xóm vào danh sách vì bây giờ họ đã là một phần của mê cung.
  • Nếu ô được chọn không có ô lân cận nào chưa được ghé thăm, hãy xóa ô đó khỏi danh sách.

Bước 3: Chấm dứt

• 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 tạo ra.

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

Tính năng xác định của thuật toán Growing Tree là cách bạn chọn ô nào để xử lý tiếp theo. Lựa chọn này ảnh hưởng đáng kể đến diện mạo của mê cung:

Cell mới nhất (Hành vi giống như ngăn xếp) – Recursive Backtracker:

• Luôn chọn ô được thêm gần đây nhất.
• Tạo ra những hành lang dài, quanh co 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ó lối đi dài và dễ giải.

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

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

Tế bào cũ nhất (Hành vi giống hàng đợi):

• Luôn chọn ô cũ nhất trong danh sách.
• Tạo ra các mê cung có độ phân bố đồng đều hơn, giống như mô hình tìm kiếm theo chiều rộng.
• Những lối đi ngắn, rậm rạp với những kết nối dày đặc.
• (Đây là phiên bản được triển khai tại đâ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 giống như mê cung theo dõi ngược đệ quy, nhưng thỉnh thoảng có các nhánh rẽ ra khỏi hành lang dài.
• 50% mới nhất, 50% cũ nhất: Cân bằng giữa các hành lang dài với sự phát triển rậm rạp.