Làm thế nào để tạo ra một mê cung pacman ngẫu nhiên

Question

Xin chào Tôi đã làm việc trên một thuật toán để tạo ra một mê cung pacman ngẫu nhiên. Tôi đã thấy một vài bài viết nhưng không thể phá vỡ logic. Tôi đang sử dụng thuật toán mê cung tìm kiếm đầu tiên chiều sâu và sau đó tôi phản chiếu mê cung để làm cho mỗi mê cung biểu lộ. Tôi đang chạy vào các vấn đề như làm sạch các đầu chết. Nếu điều này là không thể, tôi cũng sẽ thử một thuật toán khác nếu có ai đó có logic riêng của họ để tạo ra mê cung ngẫu nhiên. Bất kỳ trợ giúp được đánh giá cao. Cảm ơn

Answer 1

Tôi muốn thực hiện một bước đi ngẫu nhiên bằng dfs trong khu vực sạch (không có bất kỳ bức tường nào, trong ma trận n * n 0), sau đó điền vào các khu vực không được bao phủ bởi lối đi ngẫu nhiên (làm cho chúng như bức tường), điều này cũng có thể gây ra không gian không sử dụng, nhưng điều này đảm bảo để có một chuyến đi dài. bạn có thể đặt kích thước đi bộ tùy ý (ví dụ: khi kích thước đi bộ của bạn đến (n ​​^ 2)/2, bạn có thể dừng đi bộ).

Answer 2

Tôi đã giải quyết được sự cố của mình và muốn chia sẻ. Đối với người mới bắt đầu, tôi đặt hàng trên cùng và cột đầu tiên và cột cuối cùng như là một trở ngại tường sau đó tôi đặt một đường dẫn trên cột thứ hai, thứ hai đến hàng cuối cùng và hàng thứ hai để nó bao quanh bức tường bên ngoài. Cũng nên nhớ rằng tôi chỉ tạo ra 50% mê cung để khi tôi hoàn thành, tôi sao chép mê cung để cả hai bên đều bình đẳng. Sau đó, tôi tạo ra một phần giữa bao quanh bởi một bức tường cho khu vực nơi những con ma đẻ trứng. Sau đó, bất kỳ phần nào của mê cung đã không được xem xét tôi tạo ra đường dẫn bằng cách sử dụng các thuật toán tìm kiếm đầu tiên chiều sâu. Sau khi điều này được thực hiện tôi biết rằng trong một mê cung pacman không có kết thúc chết. Những gì tôi đã làm là kiểm tra tất cả các tế bào là một phần của con đường mà pacman có thể đi du lịch. Nếu bất kỳ ô nào chỉ có 1 ô tiếp giáp thì đó là một kết thúc chết. Nếu nó là một kết thúc chết xem nó có thể được kết nối với một con đường khác không. Nếu không thiết lập kết thúc chết như một bức tường và kiểm tra mê cung một lần nữa cho bất kỳ kết thúc chết. Sau khi bạn làm theo các bước này, bạn sẽ có một mê cung ngẫu nhiên mà không có kết thúc chết giống như mê cung pacman điển hình.

Answer 3

Tôi đã tạo một trình tạo mê cung PacMan ngẫu nhiên một thời gian dài trước đây trên C = 64 bằng cách sử dụng độ sâu đầu tiên và loại bỏ các ngõ cụt, nhưng gần đây đã bị người bạn của tôi thử thách lại. Tìm thấy một cách tốt hơn. Kiểm tra xem nó ra tại my site

Về cơ bản, tôi tạo ra một mạng lưới phòng với mỗi hướng có một cánh cửa mở (đóng trên biên giới ngoại trừ nơi đường hầm đi), sau đó bắt đầu đóng cửa một cách ngẫu nhiên theo quy tắc mà không bao giờ nên có nhiều hơn 1 cánh cửa đóng trong một phòng liền kề nếu 2 cửa đóng lại, cửa thứ ba sẽ tạo ra một ngõ cụt. Chỉ cần tiếp tục làm điều này một cách ngẫu nhiên cho đến khi tất cả các cánh cửa tiềm năng được đóng hoặc mở theo quy tắc.

Phản chiếu là công việc nhiều hơn một chút, nhưng tôi đã bắt đầu với các khái niệm cơ bản và chỉ xây dựng các quy tắc cho phép phản chiếu, vị trí ngôi nhà ma, chiều dài tường tối thiểu (không có lỗ tròn) và chiều dài tối đa ...