Thuật toán cho mê cung 3D

Question

Có các thuật toán để tạo ra mê cung 3 chiều không? Về cơ bản giống như một mê cung 2D nhưng trục độ sâu Z có thể đi ngang qua? Ý tưởng vẫn là như nhau, để có được từ Start to End. Có thể sử dụng backtracking được không?

Tôi nên sử dụng thuật toán nào để tạo mê cung 3D?

Xem here. Tôi có nghĩa là bạn có thể đi vào khối lập phương quá, không chỉ lặp lại các khuôn mặt của nó.

Answer 1

Tôi đã tạo 2 mê cung cách đây vài năm sử dụng Thuật toán của Kruskal here. Không có lý do gì mà điều này không thể làm việc với trường hợp 3d bạn mô tả. Về cơ bản bạn sẽ xem xét một tế bào một khối lập phương, và có một mảng lớn có (cho mỗi tế bào), 6 bức tường theo hướng +/- x, y và z. Các thuật toán ban đầu bắt đầu với tất cả các bức tường ở khắp mọi nơi và ngẫu nhiên làm cho bức tường biến mất cho đến khi mọi tế bào trong mê cung được kết nối.

Answer 2

Tôi có mã để tạo mê cung 2D trong tất cả mọi thứ, RPGLE (thứ tôi đã làm khi tự học trong khi học ngôn ngữ). Bởi vì cách tôi viết nó, về những thay đổi duy nhất cần thiết cho alogrithm chung sẽ là thêm kích thước Z làm kích thước bổ sung ...

Toàn bộ điều dài 20 trang (mặc dù điều này bao gồm đầu vào/đầu ra) , vì vậy, đây là một số mã. Bạn sẽ có thể dịch điều này sang bất kỳ ngôn ngữ nào bạn cần: Tôi đã dịch nó từ BASIC-spaghetti-mã (goto s đã bị lạm dụng ở đây, vâng. Nhưng đó là một bài tập thú vị).

//set out maximum maze size 
maximumMazeSquareCounter = mazeHorizontalSize * mazeVerticalSize + 1; 
// generate a starting horizontal positiongetRandomNumber(seed : randomNumber); 
currentHorizontalPosition = %inth(randomNumber * (mazeHorizontalSize - 1)) + 1; 
currentVerticalPosition = 1; 
mazeSquareCounter = 1; 
// generate the top row of the maze (with entrance) 
mazeTopRow = generateEntrance(currentHorizontalPosition); 
//write to the printer file 
writeMazeDataLine(mazeTopRow); 
mazeSquareCounter += 1; 
//set the first position in the maze(the entry square 
setPathPoint(currentHorizontalPosition : currentVerticalPosition); 
//do until we've reached every square in the maze 
dou mazeSquareCounter >= maximumMazeSquareCounter; 
//get the next available random direction 
mazeDirection = getNextRandomDirection(getNextAvailableDirection(currentHorizontalPosition : currentVerticalPosition)); 
//select what to do by the returned results 
select; 
//when FALSE is returned - when the maze is trapped 
when mazeDirection = FALSE; 
//if not at the horizontal end of the maze 
if currentHorizontalPosition <> mazeHorizontalSize; 
//add one to the position 
currentHorizontalPosition += 1; 
//else if not at the vertical end of the maze 
elseif currentVerticalPosition <> mazeVerticalSize; 
//reset the horizontal position 
currentHorizontalPosition = 1; 
//increment the vertical position 
currentVerticalPosition += 1; 
//otherwise 
else; 
//reset both positions 
currentHorizontalPosition = 1; 
currentVerticalPosition = 1; 
endif; 
//when 'N' is returned - going up (other directions removed) 
when mazeDirection = GOING_NORTH; 
//set the point above current as visited 
setPathPoint(currentHorizontalPosition : currentVerticalPosition - 1); 
//set the wall point to allow passage 
setWallDirection(currentHorizontalPosition : currentVerticalPosition : GOING_NORTH); 
//change the position variable to reflect change 
currentVerticalPosition -= 1; 
//increment square counter 
mazeSquareCounter += 1; 
endsl; 
enddo; 
//generate a random exit 
// get a random number 
getRandomNumber(seed : randomNumber); 
// set to the horzontal position 
currentHorizontalPosition = %inth(randomNumber * (mazeHorizontalSize - 1)) + 1; 
//set the vertical position 
currentVerticalPosition = mazeVerticalSize; 
//set wall to allow for exit 
setWallDirection(currentHorizontalPosition : currentVerticalPosition : GOING_SOUTH); 

Toàn bộ điều được hỗ trợ bởi hai mảng hai chiều (tốt, RPG tương đương): Một cho các bức tường mà chiếm 'vuông', và một cho hay không vuông đã được truy cập. Mê cung được tạo ra sau mỗi ô vuông đã được truy cập. Chỉ có một con đường duy nhất, mê cung biến sâu.

Để thực hiện điều này ba chiều, hãy sử dụng mảng ba chiều và thêm chỉ số thứ nguyên cần thiết.

Answer 3

Tôi đã thiết kế một thuật toán một thời gian trước đây cho mê cung 2D trên lưới vuông, không có lý do gì khiến việc này cũng không hoạt động đối với mê cung 3D trên lưới khối.

---

Bắt đầu với lưới 3D ban đầu được điền đầy đủ với ô tường.

...

Bắt đầu một đại lý tại một cạnh của lưới điện, các đại lý đi theo một đường thẳng trong X, Y, Z, X, -Y hoặc -Z hướng tường thanh toán bù trừ khi cô đi .

Hành động 'N' có một cơ hội nhỏ xảy ra mỗi bước.

Hành động 'M' xảy ra khi ô trực tiếp ở phía trước tác nhân là tường và ô ở phía trước ô trống.

'N' là một sự lựa chọn ngẫu nhiên:

1. loại bỏ tác nhân
2. chuyển sang trái hoặc phải 90 độ
3. và tạo ra một đại lý trên cùng một vuông quay 90 độ sang trái, phải hoặc cả hai (hai đại lý).

'M' là một lựa chọn ngẫu nhiên:

4. loại bỏ mà đại lý
5. loại bỏ các bức tường trước mặt đại lý đó và sau đó loại bỏ mà đại lý
6. và không làm gì cả, mang theo số
7. rẽ trái hoặc phải 90 độ.
8. và tạo tác nhân trên cùng một hình vuông được xoay 90 độ sang trái, sang phải hoặc cả hai (hai tác nhân).

---

Các mê cung là đặc biệt, và nhân vật của họ là rất linh hoạt bằng cách điều chỉnh kích hoạt cho 'M' (để làm với nút giao thông có hiệu lực) và cũng điều chỉnh khả năng 1-8 xảy ra. Bạn có thể muốn xóa một hoặc hai hành động, hoặc giới thiệu các hành động của riêng bạn, ví dụ một hành động để thực hiện một thanh toán bù trừ nhỏ hoặc sidestep một bước. Kích hoạt cho 'N' cũng có thể là một loại ngẫu nhiên khác, ví dụ ví dụ dưới đây có thể được sử dụng để tạo ra các mê cung khá phân nhánh mà vẫn có một số phần thẳng dài.

float n = 1; 

while (random_0_to_1 > 0.15) 
{ 
    n *= 1.2; 
} 

return (int)n; 

---

Một số điều chỉnh nhỏ sẽ là cần thiết từ mô tả đơn giản của tôi, ví dụ như kích hoạt cho hành động 'M' sẽ cần phải kiểm tra các tế bào tiếp giáp với các tế bào nó sẽ kiểm tra cũng tùy thuộc vào những gì sắp xếp của các nút là mong muốn.

Cần 5 hoặc 6 để mê cung chứa chu kỳ và ít nhất một hành động 'M' thay thế thành 5 và 6 là bắt buộc để mê cung chứa các đầu chết. Một số lựa chọn cơ hội/hành động và kích hoạt 'M' sẽ có xu hướng tạo ra mê cung không hoạt động, ví dụ là không thể giải quyết được hoặc đầy các ô trống hoặc tường, nhưng nhiều người sẽ tạo ra kết quả tốt đẹp nhất.