Trình tạo mê cung Recursive Backtracker

Thuật toán quay lui đệ quy thực chất là một thuật toán tìm kiếm theo chiều sâu đa năng. Khi được sử dụng để tạo mê cung, nó được sửa đổi một chút để chọn đường đi 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 các hành lang dài, quanh co và một lời giải rất dài, ngoằn ngoèo.

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 quay lui đệ quy là một phương pháp tìm kiếm theo chiều sâu để tạo ra các mê cung hoàn hảo (mê cung không có vòng lặp và chỉ có một đường đi duy nhất giữa bất kỳ hai điểm nào). Nó đơn giản, hiệu quả và tạo ra các mê cung trực quan hấp dẫn với các hành lang dài, quanh co.

Mặc dù tên gọi là vậy, 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 sử dụng hàng đợi LIFO (tức là 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í lưu trữ hàng đợi trên đĩa hoặc trong cơ sở dữ liệu nếu bộ nhớ khả dụng không đủ.

Cách thức hoạt động

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. Dưới đây là mô tả từng bước:

1. Chọn một ô bắt đầu và đánh dấu nó là ô đã được thăm.
2. Trong khi vẫn còn các ô chưa được thăm: Hãy nhìn vào các ô lân cận chưa được thăm. Nếu có ít nhất một ô lân cận chưa được thăm: Chọn ngẫu nhiên một trong các ô lân cận đó. Loại bỏ bức tường giữa ô hiện tại và ô lân cận đã chọn. Di chuyển đến ô lân cận đã chọn và đánh dấu nó là đã được thăm. Đẩy ô hiện tại vào ngăn xếp. Nếu không còn ô lân cận nào chưa được 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 điều thú vị về thuật toán này là nó hoạt động vừa như một công cụ tạo mê cung, vừa như một công cụ giải mê cung. Nếu bạn chạy nó trên một mê cung đã được tạo sẵn và chỉ dừng lại khi đến điểm kết thúc đã định trước, ngăn xếp sẽ chứa lời giải cho mê cung.

Thực ra tôi đang sử dụng hai phiên bản của thuật toán này 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 như các 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ó lời giải). Việc có hai phiên bản khác nhau chỉ là để cho vui vì tôi là một người đam mê khoa học và thấy điều đó thú vị, cả hai phiên bản đều có thể hoạt động cho cả hai mục đích ;-)

Đọ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:

• Máy phát mê cung thuật toán Kruskal
• Trình tạo mê cung thuật toán của Eller
• Máy phát mê cung thuật toán cây phát triển