Thuật toán tạo mê cung trong trò chơi Netwalk là gì?

Question

Thuật toán tạo mê cung trong trò chơi Netwalk là gì?

Answer 1

Các source code is available tại Google Code, vì vậy bạn có thể đọc nó cho chính mình và tìm hiểu! Mê cung được tạo bởi hàm generate_maze trong game.c, dòng 78ff.

---

Update: try the demo!

Netwalk tạo ra một mê cung bằng cách chạy một phiên bản ngẫu nhiên của Prim's algorithm để tìm một minimum spanning tree. Thuật toán của Prim lặp đi lặp lại phát triển một nhánh cây một lần tại một thời điểm, bắt đầu từ một nút nguồn (hoặc các nút: trong trường hợp này, "máy chủ", hộp chiều cao gấp đôi màu xanh đậm). Tại bất kỳ điểm nào trong các hoạt động của các thuật toán, cấu trúc dữ liệu trông giống như sau:

Các tế bào màu trong xanh là những tế bào ở những lời khuyên của các ngành đang phát triển: họ vẫn có ít nhất một sản phẩm nào hàng xóm mà họ có thể phát triển. Tại mỗi bước, thuật toán chọn một trong các ô màu xanh lá cây này và sau đó chọn một trong các hàng xóm trống của nó ⁽¹⁾ và thêm chi nhánh vào hàng xóm đó. Nhánh mới này chặn các chi nhánh lân cận phát triển theo hướng của nó. Khi chi nhánh không có hàng xóm trống rỗng hơn ⁽²⁾, thì nó sẽ bị xóa khỏi danh sách các ô màu xanh lục.

Cuối cùng, danh sách màu lục bị trống: không có nhánh nào trong mạng có bất kỳ hàng xóm trống nào. Điều này có nghĩa rằng bảng đã đầy, và mỗi ô được kết nối với máy chủ bằng một đường dẫn duy nhất.

[Tôi đã lý tưởng hóa các chi tiết trong một vài địa điểm: (1) trong thực tế, thuật toán Netwalk là một chút ngây thơ, và chỉ cần chọn một hướng ngẫu nhiên, và nếu những người hàng xóm theo hướng đó là không trống, nó không làm gì và tiếp tục lặp lại tiếp theo. (2) Các chi nhánh không có hàng xóm trống không được phát hiện kịp thời: chúng chỉ bị loại khỏi danh sách xanh nếu chúng được chọn. Bản trình diễn sửa các lỗi nhỏ này.]