Création de labyrinthe 4D!

La voici. Accédez au lien direct pour lafficher en taille réelle (ou effectuez un zoom avant sur limage).

Cest un plan de planches (horizontal est $ w $ et vertical est $ z $) où chaque planche est un plan 2D (horizontal est $ x $ et vertical est $ y $). Pour changer vos positions $ x $ et $ y $, il vous suffit de vous promener dans le tableau actuel.

Les flèches vous permettent de changer vos positions $ w $ et $ z $. Ils vous font sauter dune planche en haut (bleu), en bas (jaune), à gauche (rouge) ou à droite (vert), selon sa direction.

Donc, si vous êtes dans un $ (a, b) $ position dun plateau:

• En utilisant la flèche vers le haut (bleue), vous atterrirez à la position $ (a, b) $ du plateau immédiatement au-dessus de celui actuel.
• En utilisant la flèche vers le bas (jaune), vous arriverez à la position $ (a, b) $ du plateau immédiatement en dessous de celui actuel.
• En utilisant la gauche (rouge) ), vous allez atterrir à la position $ (a, b) $ du plateau immédiatement à gauche de celui actuel.
• En utilisant la flèche droite (verte), vous atterrirez dans le $ (a, b) $ position du tableau immédiatement à droite de celui actuel.

Pour générer ceci, jai créé ce programme 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()); }; } } 

^{Je suis désolé que ce site nait pas de coloration syntaxique.}

Il y a des centaines ou des milliers de points dimpasse et de branchement. Bien plus que seulement 25 et 8 requis par lOP.

Pour chaque deux emplacements, il y a exactement un chemin vers chaque autre emplacement. Il ny a pas de cycles dans le graphique et il est connecté. Le programme sassure que (growMaze méthode).

Il ny a pas de point de départ ou darrivée défini. Obtenez deux points au hasard et essayez de trouver un chemin. Comme vous le voyez, trouver manuellement un chemin ici devrait être difficile, car il y a dix mille positions dans ce labyrinthe et regarder autour des dimensions $ w $ et $ z $ pour trouver un chemin utile est plus difficile pour les yeux humains que dans le $ x $ et $ y $ dimensions.

Vous pouvez utiliser le programme pour générer aléatoirement dautres labyrinthes. Changer sa taille est également facile: ce sont ces quatre dizaines au début de la méthode main. Dans la méthode main, vous pouvez modifier le fichier dans lequel le labyrinthe généré est enregistré.Pour le montrer, voici un labyrinthe beaucoup plus petit et plus simple de 4 $ \ fois 5 \ fois 3 \ fois 2 $ généré par le programme:

Au fait, en définissant $ w $ à 1 et $ z $ à 1, vous pouvez lutiliser pour générer des labyrinthes 2D. Si vous nen définissez quun seul sur 1, ce sera un labyrinthe 3D.

Commentaires

• Bien joué, Victor. Vous ‘ mavez battu pendant la nuit. Jallais écrire une réponse ce matin – pas maintenant cependant. (@warspyking: Vous pouvez être damné pour toujours de mavoir gardé éveillé à 1h du matin. )
• @BmyGuest Cétait un bon exercice de programmation. Et il est difficile den trouver un ici. 🙂
• @BmyGuest Modifié. Est-ce mieux maintenant?
• Bien: D Jadore, bon travail Victor!
• Par où commencer? : /

Maintenant que cela a été rouvert, je veux publier le  » solution  » Javais pour ça dans la nuit avant la réponse de Victor. Victor ma battu, et Warspyking a modifié les conditions de victoire depuis , donc ce nest plus une réponse valide. Je voulais toujours publier ceci pour commenter (et vérifier / réfuter.)

La réponse fonctionne pour les labyrinthes à n dimensions et cest aussi un algorithme pas un labyrinthe spécifique. Je ne poste pas de code ici, mais le concept dalgorithme.

Ma solution est basée sur lidée que chaque élément pixel / voxel / n-dim ( appelé désormais voxel ) peut être un chemin (0) ou un mur (1). Ceci est différent de ce que Victor a fait, mais il peut ( Il suffit de convertir les ouvertures des murs & en voxels supplémentaires ou inversement. )

• Les tailles des dimensions de données sont appelées n,m,k,l…
• Lindexation commence par 0 pour le premier voxel

Initialiser les données:

• Créer les données du labyrinthe sous forme de tableau booléen de dimensionnalité nécessaire

• Initialiser tous les voxels à 0 (vide)

• Créer une liste pour les indices voxel des murs (vide )

• Définit chaque voxel avec au moins un index pair à 1 (mur)

• Stockez lindex wall-voxel dans la liste.

• Désormais, chaque fois quun mur est supprimé:

  • supprimer lindex correspondant de la liste
  • définir le booléen correspondant à 0 (vide)

Définir la position de début & fin:

Définissez essentiellement les deux  » coins  » opposés comme étant début et fin.

• Définit le voxel dindex (0,0, …) comme emplacement de départ
• Définit le voxel dindex (n, m, …) pour être la destination de lobjectif
• Si le voxel de destination est un mur, supprimez le mur. (Toutes les dimensions sont de taille égale)

Créez le labyrinthe:

Le labyrinthe actuel est une grille avec des espaces vides isolés.

• Nommez tous les espaces vides avec une étiquette unique.

Maintenant, allez-y de manière itérative ( WHILE-loop ):

• Choisissez au hasard un mur dans la liste dindex.
• Supprimez lindex de la liste ( ne testez jamais un mur deux fois )

Test : la suppression de ce mur en fusionnera deux des espaces vides détiquette différente? NON: prochaine itération. AUTREMENT:

• Supprimer le mur

• De tous les libellés concernés, choisissez celui avec la valeur la plus basse

• Définissez tous les voxels ayant des étiquettes impliquées sur cette valeur choisie (= fusionner les espaces vides)

• itération suivante

Arrêter litération lorsquaucun index nest dans la liste.

Sans le prouver, je pense que cet algorithme vous donnera:

- 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 

À lorigine, javais lintention de coder cet algorithme et de penser ensuite à une belle façon dafficher le cas 4D, mais Victor a déjà fait un excellent travail à ce sujet, donc je vais en rester là .

Commentaires

• Merci pour cette réponse verbale! Cest certainement utile pour moi.