4D Maze Creation!

Hier is het. Ga naar de directe link om deze op volledige grootte te zien (of zoom in op de afbeelding).

Dit is een vlak van planken (horizontaal is $ w $ en verticaal is $ z $) waar elk bord een 2D-vlak is (horizontaal is $ x $ en verticaal is $ y $). Om je $ x $ en $ y $ posities te veranderen, loop je gewoon rond in het huidige bord.

Met de pijlen kun je je $ w $ en $ z $ posities veranderen. Ze laten je één bord omhoog (blauw), omlaag (geel), links (rood) of rechts (groen) springen, afhankelijk van de richting.

Dus als je in een bepaalde $ (a, b) $ positie van een bord:

• Door de pijl omhoog (blauw) te gebruiken kom je terecht in de $ (a, b) $ positie van het bord direct boven het huidige.
• Door de pijl omlaag (geel) te gebruiken, kom je op de $ (a, b) $ positie van het bord direct onder de huidige.
• Door de linker (rode ), dan beland je op de $ (a, b) $ -positie van het bord, direct links van de huidige.
• Door de rechter (groene) pijl te gebruiken, kom je terecht in de $ (a, b) $ positie van het bord direct rechts van de huidige.

Om dit te genereren heb ik dit Java-programma gemaakt:

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

^{Het spijt me dat deze site geen syntaxiskleuring heeft.}

Er zijn honderden of duizenden doodlopende en vertakkingspunten. Veel meer dan alleen 25 en 8 vereist door het OP.

Voor elke twee locaties is er precies één pad naar elkaars locatie. Er zijn geen cycli in de grafiek en deze is verbonden. Het programma zorgt ervoor dat (growMaze methode).

Er is geen gedefinieerd begin- of eindpunt. Pak willekeurig twee punten en probeer een pad te vinden. Zoals je ziet, zou het moeilijk moeten zijn om hier handmatig een pad te vinden, aangezien er tienduizend posities in dit doolhof zijn en rondkijken in de $ w $ en $ z $ dimensies om een bruikbaar pad te vinden is moeilijker voor menselijke ogen dan in de $ x $ en $ y $ dimensies.

U kunt het programma gebruiken om willekeurig andere doolhoven te genereren. Het veranderen van de grootte is ook gemakkelijk: het zijn die vier tientallen aan het begin van de main -methode. In de main methode kun je wijzigen in welk bestand het gegenereerde doolhof wordt opgeslagen.Om aan te tonen dat het hier een veel kleiner en eenvoudiger $ 4 \ maal 5 \ maal 3 \ maal $ 2 $ doolhof is, gegenereerd door het programma:

Trouwens, door $ w $ in te stellen op 1 en $ z $ op 1, kun je het gebruiken om 2D-doolhoven te genereren. Als je er maar één op 1 instelt, wordt het een 3D-doolhof.

Reacties

• Leuke, Victor. Je ‘ hebt me er s nachts voor verslagen. Ik wilde vanmorgen een antwoord schrijven, maar nu niet. (@warspyking: Je bent misschien voor altijd verdoemd omdat je me om 1 uur s nachts wakker hebt gehouden. Het was dichtbij om lekker knus en warm in bed te blijven, of ga weer naar buiten om wat koude letters in een koude kamer op een onaangename pc te typen … )
• @BmyGuest Was een goede programmeeroefening. En het is moeilijk om er hier een te vinden. 🙂
• @BmyGuest bewerkt. Is het nu beter?
• Leuk: D Ik vind het geweldig, goed gedaan Victor!
• Waar begin je? : /

Nu dit heropend is, wil ik de ” oplossing ” Ik had hiervoor de avond voor Victor s antwoord. Victor heeft me verslagen en Warspyking heeft de overwinningsvoorwaarden gewijzigd sinds , dus het is niet langer een geldig antwoord. Ik wilde dit nog steeds posten voor commentaar (en verificatie / weerlegging).

Het antwoord werkt voor n-dimensionale doolhoven en het is ook een algoritme niet een specifiek doolhof. Ik plaats hier geen code , maar het algoritmeconcept.

Mijn oplossing is gebaseerd op het idee dat elk pixel / voxel / n-dim-element ( vanaf nu voxel genoemd ) kan een pad (0) of een muur (1) zijn. Dit is anders dan wat Victor heeft gemaakt, maar het kan worden vrij gemakkelijk in elkaar omgezet. ( Converteer muren & openingen in extra voxels of andersom. )

• De afmetingen van de gegevensdimensies worden n,m,k,l…
• Indexering begint met 0 voor de eerste voxel

Gegevens initialiseren:

• Maak de doolhofgegevens als een Booleaanse array van benodigde dimensionaliteit

• Initialiseer alle voxels als 0 (leeg)

• Maak een lijst voor voxel-indices van wanden (leeg )

• Zet elke voxel met minstens één even index op 1 (muur)

• Sla de wall-voxel-index op in de lijst.

• Vanaf nu, telkens wanneer een muur wordt verwijderd:

  • verwijder de overeenstemmende index uit de lijst
  • zet de overeenstemmende Boolean op 0 (leeg)

Definieer start & eindpositie:

Stel in wezen de twee tegenoverliggende ” hoeken ” in op begin en einde.

• Stel de voxel van index (0,0, …) in als startlocatie
• Stel de voxel van index (n, m, …) om de doelbestemming te zijn
• Als de doelvoxel een muur is, verwijder dan de muur. (Alle afmetingen zijn even groot)

Maak het doolhof:

Het huidige doolhof is een raster met geïsoleerde lege ruimtes.

• Label alle lege ruimtes met een uniek label.

Ga nu iteratief ( WHILE-loop ):

• Kies willekeurig een muur uit de indexlijst.
• Verwijder de index uit de lijst ( test nooit een muur tweemaal )

Test : zal het verwijderen van deze muur twee samenvoegen lege ruimtes van een ander label? NEE: volgende iteratie. ELSE:

• Muur verwijderen

• Kies van alle betrokken labels degene met de laagste waarde

• Zet alle voxels met betrokken labels op deze gekozen waarde (= voeg lege spaties samen)

• volgende iteratie

Stop de iteratie als er geen indices in de lijst staan.

Zonder het te bewijzen, denk ik dat dit algoritme je:

- 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 

Oorspronkelijk was ik van plan om dit algoritme te coderen en dan een mooie manier te bedenken om de 4D-case weer te geven, maar Victor heeft dat al geweldig gedaan, dus ik laat het hierbij .

Reacties

• Bedankt voor dit mondelinge antwoord! Het is zeker nuttig voor mij.