Tôi đang tìm kiếm một thuật toán tạo mê cung có thể tạo ra mê cung không có kết thúc chết mà chỉ là khởi đầu và kết thúc. Như thế này:Thuật toán cho tạo mê cung không có kết thúc chết?
hình ảnh từ http://www.astrolog.org/labyrnth/maze/unicursl.gif
Tôi có thể tìm hoặc đi về xây dựng như một thuật toán thế hệ mê cung?
Có vẻ như bạn muốn có một đường cong không gian điền giả ngẫu nhiên (ví dụ, xem Context-based Space Filling Curves -EUROGRAPHICS ’2000 (định dạng PDF, 1.1 MB))
Hãy xem một Space-filling curve.
Tôi nghi ngờ bạn có thể áp dụng một số ngẫu nhiên để xây dựng một trong số này để đạt được những gì bạn muốn.
Đường cong làm đầy không gian thật tuyệt, nhưng những đường cong trong giấy đó có phần đuôi chết, và tôi không chắc chắn làm thế nào bạn có thể loại bỏ chúng. –
@j_random_hacker: Tôi nghĩ ý tưởng là "bức tường" trong một đường cong đầy không gian là một đường dài; vì vậy nếu bạn đảo ngược người da đen và người da trắng thì bạn nên có một mê cung giải pháp mà không có kết thúc chết. –
@Lie: Tốt. –
Tôi đã không nghĩ rằng điều này thông qua, chỉ là một ý tưởng:
Quá trình lựa chọn 'tùy ý' cho các bit tường mới có thể bắt đầu cố gắng 'phát triển' các phần thẳng vuông góc với tường ngoài, sau đó ở một giai đoạn chuyển đổi để điền vào bất cứ nơi nào có thể.
Có thể sẽ cần khả năng quay lại nếu bị kẹt.
Có lẽ nó không quá hiệu quả.
Tôi nghĩ rằng điều này cũng có thể dẫn đến kết thúc chết. – phimuemue
@phimuemue: Một kết thúc chết ngụ ý rằng có các khối có thể được biến thành tường mà không làm tường không có giải pháp (tức là thuật toán tìm đường dẫn từ đầu đến cuối không thành công). Miễn là nó có thể thêm một khối tường mà không chặn các giải pháp, sau đó thêm tường. –
Tôi sẽ sugest để bắt đầu với hình vuông hoàn toàn màu đen (đầy đủ) và cố đào đường. Trong quá trình đào, bạn dễ dàng đảm bảo không có kết thúc chết, chỉ đơn giản là tiếp tục đi. Sử dụng thuật toán tìm kiếm ngược, chiều sâu đầu tiên. Thực hiện "bước đi ngẫu nhiên" - trong mỗi bước, ngẫu nhiên quyết định có nên giữ hướng hoặc thay đổi nó hay không. Kiểm tra tình trạng kết thúc chết - nếu bạn gặp khó khăn, bạn có thể nói "tốt, tôi đã hoàn thành, tôi đang kết thúc", hoặc, nếu bạn xem xét mê cung chưa được đào đủ, chỉ cần quay lại. Luôn nhớ những gì bạn đã làm trước đây và thử ngẫu nhiên một số hành động khác. Có thể sử dụng một số heuristic để thích hướng nhất định, như, nói, luôn luôn giữ một số không gian trống trước khi dodging tường, hãy thử đầu tiên đi bộ xung quanh bức tường vv - theo cách này bạn có thể tìm thấy các giải pháp mong muốn mà điền vào tất cả các hình vuông nhanh hơn nhiều.
Trong ví dụ bạn cung cấp, chỉ có một đường dẫn thực tế từ đầu đến cuối. Nếu đó là tất cả những gì bạn muốn, tôi nghĩ bạn có thể sử dụng đi bộ ngẫu nhiên! Khái niệm rất đơn giản: được đưa ra các ranh giới bên ngoài của mê cung, một điểm bắt đầu và một điểm kết thúc, viết một hàm để tạo ra các bước đi ngẫu nhiên từ điểm bắt đầu mà cuối cùng kết thúc tại điểm kết thúc. Các điều kiện sẽ là "người đi bộ ngẫu nhiên" của chúng tôi chỉ có thể di chuyển lên, xuống, phải hoặc trái từ hình vuông trước đó, và không thể đi vào trong một hình vuông của một hình vuông trước đó (bức tường này tạo ra).
Như tôi thấy, có hai thách thức về thuật toán ở đây. Việc đầu tiên là xác định xem chúng ta đang ở trong một hình vuông của một hình vuông trước đó (va chạm). Có lẽ chúng ta có thể duy trì một danh sách các ô vuông đi ngang (tọa độ của chúng) và ranh giới mê cung, và cho mỗi ô vuông mới đánh giá khoảng cách từ mọi ô vuông trong danh sách. Điều này nghe không hiệu quả lắm.
Thử thách khác thực sự là đạt đến điểm kết thúc với bước đi ngẫu nhiên của chúng tôi.Nếu va chạm với các ô vuông trước đây không phải là một vấn đề, chúng ta sẽ bị ràng buộc để đạt đến điểm cuối cùng, nhưng với chúng, chúng ta có vấn đề mà chúng ta có thể tránh khỏi điểm cuối. Cách để tránh điều này là để kiểm tra và tránh việc nhập vòng lặp. Nếu chúng ta tránh các vòng lặp được hình thành bởi đường đi ngang và/hoặc ranh giới mê cung, thì chúng ta duy trì một con đường có thể đến điểm kết thúc. Theo như thực sự tìm ra nếu chúng ta đang ở trong một vòng lặp ... Meh đó là loại khó.
Nếu bạn đã có thuật toán giải quyết mê cung, bạn có thể chạy nó bất cứ khi nào bạn có xung đột có thể để xem liệu đường dẫn có tồn tại từ hình vuông hiện tại của bạn đến điểm cuối hay không. Khi bạn chạy nó, có nó nghĩ rằng tất cả các ô vuông trước đây là các bức tường, cũng như ranh giới của chúng.
Khi 'đi bộ' giữ các thay đổi được thực hiện trên mỗi bước trong ngăn xếp, vì vậy bạn có thể nhìn x bước trước và sau đó ở từng giai đoạn sao cho bạn không thể thực hiện thêm bước nào (đi vào góc hoặc hình xoắn ốc giống như đi bộ) cho đến khi bạn có một con đường đi bộ khả thi và tiếp tục đi bộ từ đó cho đến khi ngăn xếp trống (tức là bạn bật ngăn xếp tất cả các con đường trở lại vì tại mỗi bước trước đó không có hàng xóm khả thi). Sau đó áp dụng các phép biến đổi cho cấu trúc dữ liệu mê cung.
Tôi đang làm việc này vào lúc này ... Bắt đầu từ một cạnh, tôi ngẫu nhiên đi qua một mảng vuông, đánh dấu các ô có độ dài đường đi khi tôi đi qua chúng.
Khi bạn gặp khó khăn (và bạn sẽ), hãy tạo một đường giao nhau hình thành một vòng lặp với đường dẫn gần nhất gần bạn (nhưng xem bên dưới). Sau đó tôi quay trở lại theo con đường hiện tại đến phía bên kia của ngã ba và phá vỡ vòng lặp đó. Đuôi lủng lẳng này sau đó tạo thành 'đầu' mới của bước đi ngẫu nhiên (nhớ tính toán lại độ dài đường dẫn của bạn từ nguồn đường dẫn) và bạn có thể tiếp tục.
Thử nghiệm cho thấy rằng bằng cách thực hiện điều này không (hoặc chưa xem - xem bên dưới) đã tạo ra một vòng tạo đuôi mới, miễn là 'đuôi' mới của bạn bị mắc kẹt, bạn không chỉ không ngừng tái tạo một liên kết với ô mà bạn vừa mới tách ra nếu đó là lần gần đây nhất - chọn lần thứ hai gần đây nhất trong trường hợp đó.
Trường hợp chấm dứt là khi bạn bị 'kẹt' trên phần tử cạnh, và bạn đã điền mảng (chiều dài đường dẫn của bạn giống với vùng của mảng) - bạn đã hoàn tất. Điểm xuất phát của bạn dẫn đến điểm kết thúc.
Có vẻ như có hai sự thiếu hiệu quả và trục trặc tiềm năng với điều này (Tôi đang chơi với thuật toán tại thời điểm này) - Đôi khi bạn sẽ đi vào một góc và cách duy nhất để tiếp tục là tạo lại vòng lặp liên kết với trang bạn vừa mới hỏng. Sau đó, trình tự quay trở lại theo dõi tất cả các vòng bạn đã thực hiện trước đó tại điểm mà ban đầu bạn bị kẹt. Nếu rằng không thể đi bất cứ nơi nào khác (nó là một góc khác) sau đó bạn sẽ chỉ trả lại giữa hai người. Có nhiều cách xung quanh điều đó, nhưng nó có nghĩa là giữ một số loại danh sách các ô được lặp lại, chỉ xóa nó khi bạn thực sự nằm xuống một số đường dẫn mới.
Cách khác là dường như dễ bị bỏ trống một hình vuông lẻ, đặc biệt khi mảng của bạn là lẻ-lẻ. Tôi đã không hoàn toàn điều tra tại sao đây là trường hợp, và đó là khi điều này xảy ra rằng vấn đề góc trước đó có vẻ đặc biệt phổ biến.Công việc tiếp tục ...
Ahh - Tôi đã tìm thấy một cách dễ dàng hơn để tạo ra một mê cung kỳ dị. – Nick
Ahh - Tôi đã tìm thấy một cách dễ dàng hơn để tạo ra một mê cung kỳ dị.
Bắt đầu với một lưới trống và điền vào với các vòng 2x2 nhỏ. Nếu lưới là lẻ-by-even, bạn sẽ cần phải kết hợp trong một số vòng 2x3, và nếu nó lẻ-lẻ, bạn sẽ phải để lại một hình vuông miễn phí - Tôi thường để lại một góc không được lấp đầy.
Tiếp theo, tùy ý tham gia các vòng với nhau để tạo thành các vòng lớn hơn - vì vậy (ví dụ) 2 vòng 2x2 trở thành một vòng lặp 4x2 duy nhất. Tiếp tục làm điều này, đảm bảo bạn không tham gia vòng lặp vào chính nó.
Cuối cùng bạn sẽ kết thúc với một vòng lặp đơn sử dụng hết tất cả các ô bị chiếm đóng bởi trang trại gốc của vòng lặp. Phá vỡ vòng lặp này ở bất kỳ vị trí nào và bạn có một mê cung kỳ dị, nơi các vị trí bắt đầu và kết thúc nằm cạnh nhau. Bây giờ bạn có thể di chuyển các điểm kết thúc xung quanh lưới bằng cách hình thành và phá vỡ các vòng nhỏ - móc đầu vào một điểm khác trong mê cung, và sau đó phá vỡ ngã ba ở phía đối diện để tái tạo thành mảnh duy nhất của bạn chuỗi có vị trí kết thúc mới.
Nếu bạn đang làm việc trên một mê cung kỳ lạ, hãy sử dụng kỹ thuật cuối cùng này để giun một trong những đầu của bạn qua góc chưa hoàn thành để hoàn thành mê cung của bạn.
Tôi nghĩ rằng tôi đã tìm thấy một phương pháp khác, tuy nhiên tôi chưa thử nghiệm nó rộng rãi.
Xem https://twitter.com/tdhooper/status/340853820584230915/photo/1
Từ trái sang phải:
Tạo một mê cung phi unicursal như mô tả ở đây https://en.wikipedia.org/wiki/File:Prim_Maze.svg, tôi nghĩ rằng đây là Thuật toán Prim
Niêm phong lối ra
Vẽ đường dẫn đến mọi điểm trong mê cung (ví dụ: cố gắng giải quyết nó)
Make con đường này một bức tường
Nó hoạt động: http://www.stainlessvision.com/lab/maze-generator/unicursal.html mã tại đây: https: // github.com/tdhooper/trình tạo ngẫu nhiên-mê cung –
là có bất kỳ hạn chế, ví dụ không có hình vuông đen 2x2? –
@Lie Ryan: Không. Mặc dù sẽ rất tuyệt khi có các thuật toán như vậy trong số các câu trả lời. – Fejuto
Liên quan: http://stackoverflow.com/questions/2641964/algorithm-to-generate-a-segment-maze – nico