Tworzenie labiryntu 4D!

Oto jest. Uzyskaj dostęp do bezpośredniego linku , aby zobaczyć go w pełnym rozmiarze (lub powiększyć obraz).

To jest płaszczyzna desek (pozioma to $ w $, a pionowa to $ z $), gdzie każda plansza to płaszczyzna 2D (pozioma to $ x $, a pionowa to $ y $). Aby zmienić pozycje $ x $ i $ y $, po prostu chodź po bieżącej tablicy.

Strzałki pozwalają zmienić pozycje $ w $ i $ z $. Sprawiają, że przeskakujesz o jedną deskę w górę (niebieski), w dół (żółty), w lewo (czerwony) lub w prawo (zielony), zgodnie z jej kierunkiem.

Więc jeśli jesteś w konkretnym $ (a, b) Pozycja $ planszy:

• Używając strzałki w górę (niebieskiej), wylądujesz na pozycji $ (a, b) $ bezpośrednio nad bieżącą.
• Używając strzałki w dół (żółtej) wylądujesz na pozycji $ (a, b) $ bezpośrednio pod bieżącą.
• Używając lewej (czerwonej ), wylądujesz na pozycji $ (a, b) $ planszy bezpośrednio na lewo od aktualnej.
• Używając prawej (zielonej) strzałki, wylądujesz w $ (a, b) $ pozycja tablicy bezpośrednio na prawo od bieżącej.

Aby to wygenerować, utworzyłem ten program Java:

import java.awt.Color; import java.awt.Graphics2D; import java.awt.image.BufferedImage; import java.io.File; import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; import javax.imageio.ImageIO; /** * @author Victor */ public class Tesseracter { public static void main(String[] args) throws IOException { TesseractMaze maze = new TesseractMaze(10, 10, 10, 10); BufferedImage im = maze.draw(); ImageIO.write(im, "png", new File("maze.png")); } public static final class Coordinate4D { private final TesseractMaze maze; private final int w, x, y, z; public Coordinate4D(TesseractMaze maze, int w, int x, int y, int z) { Objects.requireNonNull(maze); if (w < 0 || w >= maze.wSize || x < 0 || x >= maze.xSize || y < 0 || y >= maze.ySize || z < 0 || z >= maze.zSize) throw new IndexOutOfBoundsException(); this.maze = maze; this.w = w; this.x = x; this.y = y; this.z = z; } @Override public int hashCode() { return Objects.hash(maze, w, x, y, z); } @Override public boolean equals(Object another) { if (!(another instanceof Coordinate4D)) return false; Coordinate4D c4d = (Coordinate4D) another; return maze == c4d.maze && w == c4d.w && x == c4d.x && y == c4d.y && z == c4d.z; } public int squareDistance(Coordinate4D another) { Objects.requireNonNull(another); if (maze != another.maze) throw new IllegalArgumentException(); int dw = Math.abs(w - another.w); int dx = Math.abs(x - another.x); int dy = Math.abs(y - another.y); int dz = Math.abs(z - another.z); return dw + dx + dy + dz; } public Coordinate4D minusW() { return w == 0 ? null : new Coordinate4D(maze, w - 1, x, y, z); }; public Coordinate4D plusW() { return w == maze.wSize - 1 ? null : new Coordinate4D(maze, w + 1, x, y, z); }; public Coordinate4D minusX() { return x == 0 ? null : new Coordinate4D(maze, w, x - 1, y, z); }; public Coordinate4D plusX() { return x == maze.xSize - 1 ? null : new Coordinate4D(maze, w, x + 1, y, z); }; public Coordinate4D minusY() { return y == 0 ? null : new Coordinate4D(maze, w, x, y - 1, z); }; public Coordinate4D plusY() { return y == maze.ySize - 1 ? null : new Coordinate4D(maze, w, x, y + 1, z); }; public Coordinate4D minusZ() { return z == 0 ? null : new Coordinate4D(maze, w, x, y, z - 1); }; public Coordinate4D plusZ() { return z == maze.zSize - 1 ? null : new Coordinate4D(maze, w, x, y, z + 1); }; public TesseractMaze getMaze() { return maze; } } public static final class TesseractMaze { private final int wSize, xSize, ySize, zSize; private final Map<Coordinate4D, Node> nodes; private final Node start; public TesseractMaze(int w, int x, int y, int z) { this.wSize = w; this.xSize = x; this.ySize = y; this.zSize = z; nodes = new HashMap<>(w * x * y * z); fill(); this.start = chooseRandomNode(); growMaze(); } private void fill() { for (int a = 0; a < wSize; a++) { for (int b = 0; b < xSize; b++) { for (int c = 0; c < ySize; c++) { for (int d = 0; d < zSize; d++) { Coordinate4D coord = new Coordinate4D(this, a, b, c, d); nodes.put(coord, new Node(coord)); } } } } } public Node nodeAt(Coordinate4D coord) { if (coord == null) return null; return nodes.get(coord); } private Node chooseRandomNode() { int n = (int) (Math.random() * wSize * xSize * ySize * zSize); return new ArrayList<>(nodes.values()).get(n); } private void growMaze() { List<Node> frontier = new ArrayList<>(wSize * xSize * ySize * zSize); frontier.add(start); start.linked = true; while (!frontier.isEmpty()) { Collections.shuffle(frontier); Node n = frontier.get(0); Node next = n.linkRandomUnlinkedNeighbour(); if (next != null) { frontier.add(next); } else { frontier.remove(0); } } } public BufferedImage draw() { int cellWidth = 16; int cellHeight = 16; int boardWidth = cellWidth * (xSize + 1); int boardHeight = cellHeight * (ySize + 1); int arrowSize = 3; int margin = 2; Color red = Color.RED; Color blue = Color.BLUE; Color yellow = new Color(128, 128, 0); Color green = new Color(0, 128, 0); BufferedImage im = new BufferedImage(wSize * boardWidth + cellWidth - 1, zSize * boardHeight + cellHeight - 1, BufferedImage.TYPE_INT_ARGB); Graphics2D g = im.createGraphics(); for (int w = 0; w < wSize; w++) { for (int z = 0; z < zSize; z++) { for (int x = 0; x < xSize; x++) { for (int y = 0; y < ySize; y++) { Coordinate4D c = new Coordinate4D(this, w, x, y, z); Node n = nodeAt(c); int x1 = cellWidth * x + boardWidth * w + cellWidth - 1; int y1 = cellHeight * y + boardHeight * z + cellHeight - 1; int x2 = x1 + cellWidth; int y2 = y1 + cellHeight; int x3 = (x1 + x2) / 2; int y3 = (y1 + y2) / 2; g.setColor(Color.BLACK); if (!n.isLinkedTo(n.minusY())) g.drawLine(x1, y1, x2, y1); if (!n.isLinkedTo(n.plusY())) g.drawLine(x1, y2, x2, y2); if (!n.isLinkedTo(n.minusX())) g.drawLine(x1, y1, x1, y2); if (!n.isLinkedTo(n.plusX())) g.drawLine(x2, y1, x2, y2); if (n.isLinkedTo(n.minusW())) { // Board left, left arrow. g.setColor(red); for (int i = 0; i < arrowSize; i++) { g.drawLine(x1 + margin + i, y3 - i, x1 + margin + i, y3 + i); } } if (n.isLinkedTo(n.plusW())) { // Board right, right arrow. g.setColor(green); for (int i = 0; i < arrowSize; i++) { g.drawLine(x2 - margin - i, y3 - i, x2 - margin - i, y3 + i); } } if (n.isLinkedTo(n.minusZ())) { // Board up, up arrow. g.setColor(blue); for (int i = 0; i < arrowSize; i++) { g.drawLine(x3 - i, y1 + margin + i, x3 + i, y1 + margin + i); } } if (n.isLinkedTo(n.plusZ())) { // Board down, down arrow. g.setColor(yellow); for (int i = 0; i < arrowSize; i++) { g.drawLine(x3 - i, y2 - margin - i, x3 + i, y2 - margin - i); } } } } } } return im; } } public static final class Node { private final Coordinate4D coord; private final List<Node> linkedNeighbours; private List<Node> neighbours; private boolean linked; public Node(Coordinate4D coord) { Objects.requireNonNull(coord); this.coord = coord; linkedNeighbours = new ArrayList<>(8); } public Node linkRandomUnlinkedNeighbour() { List<Node> list = new ArrayList<>(getNeighbours()); list.removeIf(n -> n.linked); if (list.isEmpty()) return null; Collections.shuffle(list); Node next = list.get(0); next.getNeighbours(); linkedNeighbours.add(next); next.linkedNeighbours.add(this); next.linked = true; return next; } @SuppressWarnings("ReturnOfCollectionOrArrayField") public List<Node> getNeighbours() { if (neighbours == null) { List<Node> nodes = new ArrayList<>(Arrays.asList(minusW(), plusW(), minusX(), plusX(), minusY(), plusY(), minusZ(), plusZ())); nodes.removeIf(x -> x == null); neighbours = Collections.unmodifiableList(nodes); } return neighbours; } public boolean isDeadEnd() { return linkedNeighbours.size() == 1; } public boolean isBranch() { return linkedNeighbours.size() > 2; } public boolean isLinkedTo(Node node) { return linkedNeighbours.contains(node); } public TesseractMaze getMaze() { return coord.getMaze(); } public Coordinate4D getCoord() { return coord; } public Node minusW() { return getMaze().nodeAt(coord.minusW()); }; public Node plusW() { return getMaze().nodeAt(coord.plusW()); }; public Node minusX() { return getMaze().nodeAt(coord.minusX()); }; public Node plusX() { return getMaze().nodeAt(coord.plusX()); }; public Node minusY() { return getMaze().nodeAt(coord.minusY()); }; public Node plusY() { return getMaze().nodeAt(coord.plusY()); }; public Node minusZ() { return getMaze().nodeAt(coord.minusZ()); }; public Node plusZ() { return getMaze().nodeAt(coord.plusZ()); }; } } 

^{Przykro mi, że ta witryna nie ma kolorowania składni.}

Istnieją setki lub tysiące ślepych zaułków i rozgałęzień. O wiele więcej niż tylko 25 i 8 wymagane przez OP.

Dla każdych dwóch lokalizacji istnieje dokładnie jedna ścieżka do siebie. Na wykresie nie ma cykli i jest połączony. Program zapewnia, że (metoda growMaze).

Nie ma zdefiniowanego punktu początkowego ani końcowego. Po prostu losowo zdobądź dwa dowolne punkty i spróbuj znaleźć ścieżkę. Jak widać, ręczne znalezienie ścieżki w tym miejscu powinno być trudne, ponieważ w tym labiryncie jest dziesięć tysięcy pozycji, a rozglądanie się po wymiarach $ w $ i $ z $ w celu znalezienia użytecznej ścieżki jest trudniejsze dla ludzkich oczu niż w $ Wymiary x $ i $ y $.

Możesz użyć programu do losowego generowania innych labiryntów. Zmiana jego rozmiaru też jest łatwa: są to te cztery dziesiątki na początku metody main. W metodzie main możesz zmienić plik, do którego zapisywany jest wygenerowany labirynt.Aby to pokazać, tutaj jest znacznie mniejszy i prostszy 4 $ \ times 5 \ times 3 \ times 2 $ labirynt wygenerowany przez program:

Nawiasem mówiąc, ustawiając $ w $ na 1 i $ z $ na 1, możesz go użyć do generowania 2D labiryntów. Jeśli ustawisz tylko jeden z nich na 1, będzie to trójwymiarowy labirynt.

Komentarze

• Niezły, Victor. ' pobiłeś mnie w ciągu nocy. Miałem napisać odpowiedź dziś rano – ale nie teraz. (@warspyking: Możesz być przeklęty na zawsze za to, że nie pozwoliłeś mi zasnąć o 1 w nocy. Było blisko, aby pozostać miłym, przytulnym i ciepłym w łóżku lub wyjść ponownie, aby napisać zimne litery w zimnym pokoju na obojętnym komputerze … )
• @BmyGuest To było dobre ćwiczenie programistyczne. I tutaj ciężko znaleźć. 🙂
• @BmyGuest Edited. Czy teraz jest lepiej?
• Fajnie: D Uwielbiam to, dobra robota Victor!
• Od czego zaczynasz? : /

Teraz, gdy to zostało ponownie otwarte, chcę opublikować ” rozwiązanie ” Miałem to w nocy przed odpowiedzią Victora. Victor mnie pokonał, a Warspyking zmodyfikował warunki zwycięstwa od , więc nie jest to już prawidłowa odpowiedź. Nadal chciałem ją opublikować w celu skomentowania (i weryfikacji / obalenia).

Odpowiedź działa dla n-wymiarowych labiryntów i jest również algorytm nie jest konkretnym labiryntem. Nie zamieszczam tutaj kodu , ale koncepcję algorytmu.

Moje rozwiązanie opiera się na założeniu, że każdy piksel / woksel / n-element-dim ( nazywany od teraz wokselem ) może być ścieżką (0) lub ścianą (1). Różni się to od tego, co stworzył Victor, ale może można łatwo zamienić na siebie. ( Po prostu przekonwertuj ściany & otwory na dodatkowe woksele lub odwrotnie. )

• Rozmiary wymiarów danych nazywane są n,m,k,l…
• Indeksowanie zaczyna się od 0 dla pierwszego woksela

Zainicjuj dane:

• Utwórz dane labiryntu jako tablicę logiczną potrzebnej wymiarowości

• Zainicjuj wszystkie woksele jako 0 (puste)

• Utwórz listę indeksów wokseli ścian (puste )

• Ustaw każdy woksel z co najmniej jednym indeksem parzystym na 1 (ściana)

• Przechowuj indeks wall-voxel na liście.

• Od teraz za każdym razem, gdy ściana zostanie usunięta:

  • usuń odpowiedni indeks z listy
  • ustaw odpowiednią wartość logiczną na 0 (pusty)

Zdefiniuj początek & pozycja końcowa:

Zasadniczo ustaw dwa przeciwstawne ” rogi ” na początek i koniec.

• Ustaw woksel o indeksie (0,0, …) jako lokalizację początkową
• Ustaw woksel o indeksie (n, m, …) jako cel docelowy
• Jeśli docelowym wokselem jest ściana, usuń ją. (Wszystkie wymiary są równe)

Utwórz labirynt:

Bieżący labirynt to siatka z izolowanymi pustymi przestrzeniami.

• Oznacz wszystkie puste przestrzenie unikalną etykietą.

Teraz przejdź iteracyjnie ( WHILE-loop ):

• Losowo wybierz ścianę z listy indeksu.
• Usuń indeks z listy ( nigdy nie testuj ścianę dwukrotnie )

Test : Usunięcie tej ściany spowoduje połączenie dwóch puste przestrzenie o innej etykiecie? NIE: następna iteracja. ELSE:

• Usuń ścianę

• Spośród wszystkich zaangażowanych etykiet wybierz tę o najniższej wartości

• Ustaw wszystkie woksele zawierające etykiety na tę wybraną wartość (= połącz puste spacje)

• następna iteracja

Zatrzymaj iterację, gdy na liście nie ma żadnych indeksów.

Bez sprawdzania tego myślę, że ten algorytm da ci:

- a non-looping maze from start to end - maximize the size of the maze within the volume - The identical algorithm could be used for arbitrary amount of dimensions 

Początkowo miałem zamiar zakodować ten algorytm, a następnie wymyślić ładny sposób wyświetlania przypadku 4D, ale Victor wykonał już świetną robotę, więc zostawię to z tym .

Komentarze

• Dzięki za tę odpowiedź werbalną! Na pewno jest dla mnie przydatna.