Trình tạo mê cung Recursive Backtracker

Thuật toán recursive backtracker thực sự là một tìm kiếm theo chiều sâu mục đích chung. Khi được sử dụng để tạo mê cung, nó được sửa đổi một chút để chọn đường dẫn ngẫu nhiên, trong khi nếu được sử dụng cho mục đích tìm kiếm thực tế, người ta thường chỉ tìm kiếm từng cấp độ theo thứ tự tuyến tính. Nó có xu hướng tạo ra các mê cung với hành lang dài, quanh co và một giải pháp rất dài, xoắn.

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 đó.

Thuật toán recursive backtracker là phương pháp tìm kiếm theo chiều sâu để tạo ra mê cung hoàn hảo (mê cung không có vòng lặp và chỉ có một đường đi giữa hai điểm bất kỳ). Thuật toán này đơn giản, hiệu quả và tạo ra mê cung hấp dẫn về mặt thị giác với hành lang dài, quanh co.

Mặc dù có tên như vậy, nhưng nó không nhất thiết phải được triển khai bằng đệ quy. Nó thường được triển khai theo phương pháp lặp lại bằng cách sử dụng hàng đợi LIFO (tức là một ngăn xếp). Đối với các mê cung rất lớn, việc sử dụng đệ quy có nhiều khả năng dẫn đến tràn ngăn xếp cuộc gọi, tùy thuộc vào ngôn ngữ lập trình và bộ nhớ khả dụng. Hàng đợi LIFO có thể dễ dàng được điều chỉnh để xử lý lượng dữ liệu lớn, thậm chí giữ hàng đợi trên đĩa hoặc trong cơ sở dữ liệu nếu bộ nhớ khả dụng không đủ.

Nó hoạt động như thế nào

Thuật toán hoạt động bằng cách sử dụng phương pháp tìm kiếm theo chiều sâu dựa trên ngăn xếp. Sau đây là phân tích từng bước:

1. Chọn ô bắt đầu và đánh dấu là đã ghé thăm.
2. Trong khi có những ô chưa được thăm:
   • Nhìn vào các ô lân cận chưa được ghé thăm.
   • Nếu có ít nhất một hàng xóm chưa được ghé thăm:
     • Chọn ngẫu nhiên một trong những người hàng xóm chưa đến thăm.
     • Xóa bức tường giữa ô hiện tại và ô lân cận đã chọn.
     • Di chuyển đến người hàng xóm đã chọn và đánh dấu là đã ghé thăm.
     • Đẩy ô hiện tại vào ngăn xếp.
   • Nếu không có hàng xóm nào chưa được ghé thăm:
     • Quay lại bằng cách lấy ô cuối cùng ra khỏi ngăn xếp.
3. Tiếp tục quá trình này cho đến khi ngăn xếp trống.

Một sự thật thú vị về thuật toán này là nó hoạt động như một trình tạo mê cung và một trình giải mê cung. Nếu bạn chạy nó trên một mê cung đã tạo sẵn và chỉ dừng lại khi bạn chạm đến điểm cuối đã quyết định, ngăn xếp sẽ chứa giải pháp cho mê cung.

Tôi thực sự có hai phiên bản của thuật toán này đang được sử dụng trên trang web này: một phiên bản dựa trên hàng đợi LIFO để tạo mê cung trên trang này và một phiên bản dựa trên đệ quy để giải mê cung, cũng là mê cung được tạo ra bởi các thuật toán khác (đó là cách tạo ra các bản đồ có giải pháp). Có hai phiên bản khác nhau chỉ dành cho thể thao vì tôi là một người mọt sách thấy nó thú vị, phiên bản nào cũng có thể hiệu quả với cả hai ;-)