4D labyrint skabelse!

Her er det. Gå til direkte link for at se det i sin fulde størrelse (eller zoome ind på billedet).

Dette er et plan af brædder (vandret er $ w $ og lodret er $ z $) hvor hvert kort er et 2D-plan (vandret er $ x $ og lodret er $ y $). Hvis du vil ændre dine $ x $ og $ y $ positioner, skal du bare gå rundt i det aktuelle tavle.

Pilene giver dig mulighed for at ændre dine $ w $ og $ z $ positioner. De får dig til at hoppe et bræt op (blå), ned (gul), venstre (rød) eller højre (grøn) i overensstemmelse med dets retning.

Så hvis du er i en bestemt $ (a, b) $ brætposition:

• Ved at bruge pil op (blå) lander du i brættet $ (a, b) $ lige over det aktuelle.
• Ved at bruge pil ned (gul) lander du i $ (a, b) $ -positionen på tavlen umiddelbart under den aktuelle.
• Ved at bruge venstre (rød ) pil, vil du lande i $ (a, b) $ position på tavlen straks til venstre for den aktuelle.
• Ved at bruge den højre (grønne) pil lander du i $ (a, b) $ position af tavlen straks til højre for den aktuelle.

For at generere dette oprettede jeg dette Java-program:

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

^{Jeg er ked af, at dette websted ikke har nogen syntaksfarvning.}

Der er hundreder eller tusinder af blindgange og forgreningssteder. Meget mere end bare 25 og 8 krævet af OP.

For hver to placeringer er der nøjagtigt en sti til hinanden. Der er ingen cyklusser i grafen, og den er forbundet. Programmet sikrer, at (growMaze -metoden).

Der er ikke noget defineret start- eller slutpunkt. Bare få tilfældigt to point, og prøv at finde en sti. Som du ser, skal det være svært at finde en sti her manuelt, da der er ti tusind positioner i denne labyrint, og det er sværere for menneskelige øjne at se sig omkring $ w $ og $ z $ -dimensionerne for at finde en sti x $ og $ y $ dimensioner.

Du kan bruge programmet til tilfældigt at generere andre labyrinter. Det er også let at ændre størrelsen: De er de fire tiere i starten af main -metoden. I main -metoden kan du ændre til hvilken fil den genererede labyrint gemmes.For at vise det her er det en meget mindre og enklere $ 4 \ gange 5 \ gange 3 \ gange 2 $ labyrint genereret af programmet:

Forresten, ved at indstille $ w $ til 1 og $ z $ til 1, kan du bruge den til at generere 2D labyrinter. Hvis du kun indstiller en af dem til 1, er det en 3D-labyrint.

Kommentarer

• Dejlig, Victor. Du ‘ har slået mig til det i løbet af natten. Jeg skulle skrive et svar i morges – dog ikke nu. (@warspyking: Du kan blive forbandet for evigt for at holde mig vågen klokken 1. )
• @BmyGuest Var en god programmeringsøvelse. Og det er svært at finde en her. 🙂
• @BmyGuest redigeret. Er det bedre nu?
• Dejligt: D Jeg elsker det, godt job Victor!
• Hvor starter du? : /

Nu da dette er blevet åbnet igen, vil jeg sende ” løsning ” Jeg havde til dette natten før Victor svarede. Victor har slået mig til det, og Warspyking har ændret sejrforholdene siden , så det er ikke længere et gyldigt svar. Jeg ville stadig sende dette til kommentar (og bekræftelse / afvisning).

Svaret fungerer for n-dimensionelle labyrinter, og det er også et algoritme ikke en bestemt labyrint. Jeg sender ikke kode her, men algoritmekonceptet.

Min løsning er baseret på tanken om, at hver pixel / voxel / n-dim-element ( kaldes voxel fra nu af ) kan enten være en sti (0) eller en væg (1). Dette er forskelligt fra hvad Victor lavede, men det kan omdannes til hinanden ret let. ( Konverter bare vægge & åbninger til yderligere voxels eller omvendt. )

• Datadimensionsstørrelserne kaldes n,m,k,l…
• Indeksering starter med 0 for den første voxel

Initialiser data:

• Opret labyrintdata som boolsk matrix af nødvendig dimensionalitet

• Initialiser alle voxels som 0 (tom)

• Opret en liste til voxel-indekser på vægge (tom )

• Indstil hver voxel med mindst et lige indeks til 1 (væg)

• Gem wall-voxel-indekset på listen.

• Fra nu af, når en væg fjernes:

  • fjern det ifølge indekset fra listen
  • indstil det ifølge Boolean til 0 (tom)

Definer start & slutposition:

Indstil i det væsentlige de to modsatte ” hjørner ” start og slut.

• Indstil voxel for indeks (0,0, …) til at være startplacering
• Indstil voxel for index (n, m, …) for at være måldestinationen
• Hvis destinations voxel er en mur, skal du fjerne muren. (Alle dimensioner er i lige størrelse)

Opret labyrinten:

Den aktuelle labyrint er et gitter med isolerede tomme rum.

• Mærk alle tomme rum med en unik etiket.

Gå nu iterativt ( WHILE-loop ):

• Vælg tilfældigt en væg fra indekslisten.
• Fjern indekset fra listen ( test aldrig en væg to gange )

Test : Fjerner denne mur sammen to tomme rum med forskellig etiket? NEJ: næste iteration. ELSE:

• Fjern væg

• Af alle involverede etiketter skal du vælge en med laveste værdi

• Indstil alle voxels med involverede etiketter til denne valgte værdi (= flet tomme mellemrum)

• næste iteration

Stop iteration, når der ikke er nogen indeks på listen.

Uden korrektur, tror jeg, at denne algoritme giver dig:

- 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 

Oprindeligt havde jeg til hensigt at kode denne algoritme og så tænke på en god måde at vise 4D-sagen på, men Victor har allerede gjort et godt stykke arbejde med det, så jeg vil lade det være med dette .

Kommentarer

• Tak for dette rækkevidde verbale svar! Det er sikkert nyttigt for mig.