Algorytmy dla 3D Mazes

Question

Czy istnieją algorytmy do tworzenia trójwymiarowych labiryntów? Zasadniczo to samo, co labirynt 2D, ale oś głębo- wą Z można pokonywać? Pomysł jest taki sam, aby uzyskać od początku do końca. Czy nadal można użyć funkcji backtrack?

Który algorytm powinienem użyć do wygenerowania labiryntu 3D?

Zobacz here. Chodzi mi o to, że możesz też wejść do kostki, a nie tylko ją przerobić.

Answer 1

Zrobiłem labirynty 2d kilka lat temu, używając algorytmu Kruskala here. Nie powinno być powodu, aby to nie działało w przypadku opisywanego przypadku 3d. Zasadniczo można rozważyć komórkę sześcianu i mieć dużą tablicę, która ma (dla każdej komórki) 6 ścianek w kierunkach +/- x, yi z. Algorytm początkowo zaczyna się od wszystkich ścian wszędzie i losowo sprawia, że ​​ściany znikają, aż każda komórka w labiryncie jest połączona.

Answer 2

Mam kod do generowania labiryntu 2D we wszystkich rzeczach, RPGLE (coś, co zrobiłem jako ćwiczenie podczas nauki języka). Ze względu na sposób, w jaki to napisałem, jedynymi koniecznymi zmianami w ogólnym algerze byłoby dodanie wymiaru Z jako dodatkowego wymiaru ...

Cała sprawa ma 20 stron długości (chociaż obejmuje to wejście/wyjście) , więc tutaj jest jakiś kod. Powinieneś być w stanie przetłumaczyć to na jakikolwiek język, którego potrzebujesz: przetłumaczyłem go z kodu spaghetti-BASIC (goto s) były zbyt nadużywane tutaj, tak, ale było to zabawne ćwiczenie).

//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); 

Cała sprawa jest wspierany przez dwóch tablic dwuwymiarowych (dobrze, odpowiednik RPG): jedna dla ścian, które zajmują „kwadrat”, a drugi do tego, czy nie, że plac został odwiedził. Labirynt jest tworzony po odwiedzeniu każdego kwadratu. Garuanteed only-path only, labirynt ślimaków.

Aby było to trójwymiarowe, należy użyć tablic trójwymiarowych i dodać niezbędny indeks wymiarów.

Answer 3

Zaprojektowałem algorytm jakiś czas temu dla labiryntów 2D na kwadratowej siatce, nie ma powodu, dla którego to nie powinno działać również dla labiryntu 3D na sześciennej siatce.

---

Zacznij od siatki 3D początkowo w pełni wypełnionej komórkami ścian.

...

start środek na krawędzi rusztu, środek porusza się po linii prostej w kierunku X, Y, Z, X, Y lub -Z kierunku polana ściany, gdy przemieszcza .

Akcja "N" ma niewielką szansę na wystąpienie każdego kroku.

Akcja "M" występuje, gdy komórka znajdująca się bezpośrednio przed agentem jest ścianą, a komórka przed nią jest pusta.

„N” jest losowy wybór:

1. usunięcie tego środka
2. obracając w lewo lub prawo o 90 stopni
3. i tworzenie agentem na tym samym placu obrócił o 90 stopni w lewo, w prawo lub w obu (dwóch agentów).

'M' jest przypadkowy dobór:

4. usunięcie tego środka
5. usunięciu ściany naprzeciwko tego środka, a następnie usunięcia tego środka
6. i nic nie robiąc, niosąc ze sobą 90 ° w lewo lub w prawo.
7. i utworzenie agenta na tym samym polu przekreślonym o 90 stopni w lewo, w prawo lub w obu (dwa agenty).

---

labirynty są charakterystyczne, a ich charakter i jest bardzo elastyczna, regulując spust „M” (związek z ważnych węzłów) i również dostosowanie szanse od 1 do 8 miejsce. Możesz usunąć akcję lub dwie lub wprowadzić własne działania, na przykład jedną, aby wykonać małą czyszczenie lub pominąć jeden krok.

Spustem dla "N" może być również inny rodzaj przypadkowości, na przykład poniższy przykład może być użyty do stworzenia dość rozłożystych labiryntów, które wciąż mają długie, proste części.

float n = 1; 

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

return (int)n; 

---

jakieś małe korekty będą potrzebne od mojego prosty opis, na przykład wyzwalacz działania „M” będą musiały sprawdzić komórek przylegających do komórek sprawdza, jak również w zależności od jakiego rodzaju skrzyżowaniach są pożądany.

Albo 5 albo 6 są potrzebne, aby labirynt zawierał cykle, a przynajmniej jedno alternatywne działanie "M" do 5 i 6 jest wymagane, aby labirynt zawierał ślepe zaułki.

Niektóre wybory szans/akcji i wyzwalaczy typu "M" będą powodowały, że labirynty nie działają, na przykład są nierozwiązywalne lub pełne pustych lub ścianek komórek, ale wiele z nich będzie dawało niezmiennie dobre wyniki.