4D Maze Creation! (Deutsch)

Hier ist es. Greifen Sie auf den direkten Link zu, um ihn in voller Größe anzuzeigen (oder das Bild zu vergrößern).

Dies ist eine Ebene von Brettern (horizontal ist $ w $ und vertikal ist $ z $), wobei jedes Brett eine 2D-Ebene ist (horizontal ist $ x $ und vertikal ist $ y $). Um Ihre $ x $ – und $ y $ -Positionen zu ändern, gehen Sie einfach in der aktuellen Tafel herum.

Mit den Pfeilen können Sie Ihre $ w $ – und $ z $ -Positionen ändern. Sie lassen Sie ein Brett nach oben (blau), unten (gelb), links (rot) oder rechts (grün) entsprechend seiner Richtung springen.

Wenn Sie sich also in einem bestimmten $ befinden (a, b) $ Position eines Bretts:

• Mit dem Aufwärtspfeil (blau) landen Sie in der Position $ (a, b) $ des Bretts unmittelbar über dem aktuellen.
• Mit dem Abwärtspfeil (gelb) landen Sie in der Position $ (a, b) $ des Bretts unmittelbar unter dem aktuellen.
• Mit dem linken (rot) ) Pfeil, landen Sie in der Position $ (a, b) $ des Bretts unmittelbar links von der aktuellen.
• Mit dem rechten (grünen) Pfeil landen Sie in der Position $ (a, b) $ Position der Karte unmittelbar rechts von der aktuellen.

Um dies zu generieren, habe ich dieses Java-Programm erstellt:

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()); }; } } 

^{Es tut mir leid, dass diese Site keine Syntaxfarbe aufweist.}

Es gibt Hunderte oder Tausende von Sackgassen und Verzweigungspunkten. Viel mehr als nur 25 und 8, die vom OP benötigt werden.

Für jeweils zwei Standorte gibt es genau einen Pfad zu jedem anderen Standort. Das Diagramm enthält keine Zyklen und ist verbunden. Das Programm stellt sicher, dass (growMaze -Methode).

Es gibt keinen definierten Start- oder Endpunkt. Holen Sie sich zufällig zwei beliebige Punkte und versuchen Sie, einen Pfad zu finden. Wie Sie sehen, sollte es schwierig sein, hier manuell einen Pfad zu finden, da es in diesem Labyrinth zehntausend Positionen gibt und es für das menschliche Auge schwieriger ist, sich in den Dimensionen $ w $ und $ z $ umzusehen, um einen nützlichen Pfad zu finden, als im $ x $ und $ y $ Dimensionen.

Sie können das Programm verwenden, um zufällig andere Labyrinthe zu generieren. Das Ändern der Größe ist ebenfalls einfach: Dies sind die vier Zehner zu Beginn der Methode main. In der Methode main können Sie ändern, in welcher Datei das generierte Labyrinth gespeichert wird.Um dies zu zeigen, ist es hier ein viel kleineres und einfacheres $ 4 \ mal 5 \ mal 3 \ mal 2 $ Labyrinth, das vom Programm generiert wird:

Übrigens, indem Sie $ w $ auf 1 und $ z $ auf 1 setzen, können Sie damit 2D-Labyrinthe erzeugen. Wenn Sie nur einen von ihnen auf 1 setzen, handelt es sich um ein 3D-Labyrinth.

Kommentare

• Schön, Victor. Sie ‚ haben mich über Nacht geschlagen. Ich wollte heute Morgen eine Antwort schreiben – allerdings nicht jetzt. ! )
• @BmyGuest War eine gute Programmierübung. Und es ist schwer, hier einen zu finden. 🙂
• @BmyGuest bearbeitet. Ist es jetzt besser?
• Schön: D Ich liebe es, gute Arbeit, Victor!
• Wo fängst du an? : /

Nachdem dies wieder geöffnet wurde, möchte ich die “ Lösung “ Ich hatte dies in der Nacht vor Victors Antwort. Victor hat mich geschlagen, und Warspyking hat seitdem die Siegbedingungen geändert Daher wollte ich dies nicht mehr zum Kommentieren (und Überprüfen / Widerlegen) posten.

Die Antwort funktioniert für n-dimensionale Labyrinthe und ist auch eine Algorithmus ist kein bestimmtes Labyrinth. Ich poste hier keinen Code , sondern das Algorithmuskonzept.

Meine Lösung basiert auf der Idee, dass Jedes Pixel / Voxel / n-Dim-Element ( von nun an Voxel genannt ) kann entweder ein Pfad (0) oder eine Wand (1) sein. Dies unterscheidet sich von dem, was Victor gemacht hat, aber es kann ziemlich einfach ineinander verwandelt werden. ( Wandeln Sie einfach die & Öffnungen in zusätzliche Voxel um oder umgekehrt. )

• Die Größen der Datendimensionen heißen n,m,k,l…
• Die Indizierung beginnt mit 0 für das erste Voxel

Daten initialisieren:

• Erstellen Sie die Labyrinthdaten als Boolesches Array der benötigten Dimensionalität

• Initialisieren Sie alle Voxel als 0 (leer)

• Erstellen Sie eine Liste für Voxelindizes von Wänden (leer) )

• Setzen Sie jedes Voxel mit mindestens einem geraden Index auf 1 (Wand)

• Speichern Sie den Wall-Voxel-Index in der Liste.

• Von nun an, wenn eine Wand entfernt wird:

  • Entfernen Sie den entsprechenden Index aus der Liste.
  • Setzen Sie den entsprechenden Booleschen Wert auf 0 (leer)

Startposition definieren & Endposition:

Legen Sie im Wesentlichen die beiden gegenüberliegenden “ Ecken “ fest Start und Ende.

• Legen Sie das Voxel des Index (0,0, …) als Startposition fest.
• Legen Sie das Voxel des Index (n, m, …) um das Ziel zu sein
• Wenn das Zielvoxel eine Wand ist, entfernen Sie die Wand. (Alle Dimensionen sind gerade))

Erstellen Sie das Labyrinth:

Das aktuelle Labyrinth ist ein Raster mit isolierten Leerzeichen.

• Beschriften Sie alle Leerzeichen mit einer eindeutigen Beschriftung.

Gehen Sie nun iterativ vor ( WHILE-loop ):

• Wählen Sie zufällig eine Wand aus der Indexliste aus.
• Entfernen Sie den Index aus der Liste ( testen Sie niemals a Wand zweimal )

Test : Beim Entfernen dieser Wand werden zwei zusammengeführt Leerzeichen unterschiedlicher Bezeichnung? NEIN: nächste Iteration. SONST:

• Wand entfernen

• Wählen Sie von allen beteiligten Etiketten die mit dem niedrigsten Wert

• Setzen Sie alle Voxel mit beteiligten Beschriftungen auf diesen ausgewählten Wert (= Leerzeichen zusammenführen)

• nächste Iteration

Stoppen Sie die Iteration, wenn keine Indizes in der Liste enthalten sind.

Ohne es zu beweisen, wird dieser Algorithmus Ihnen Folgendes geben:

- 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 

Ursprünglich wollte ich diesen Algorithmus codieren und mir dann eine gute Möglichkeit vorstellen, den 4D-Fall anzuzeigen, aber Victor hat das bereits großartig gemacht, also werde ich es damit belassen .

Kommentare

• Vielen Dank für diese mündliche Antwort! Es ist sicher nützlich für mich.