Creația labirintului 4D!

Iată-l. Accesați link-ul direct pentru a-l vedea în dimensiunea completă (sau măriți imaginea).

Acesta este un plan de plăci (orizontală este $ w $ și verticală este $ z $) în care fiecare placă este un plan 2D (orizontală este $ x $ și verticală este $ y $). Pentru a vă schimba pozițiile $ x $ și $ y $, trebuie doar să vă plimbați în placa curentă.

Săgețile vă permit să vă schimbați pozițiile $ w $ și $ z $. Vă fac să săriți o scândură în sus (albastru), în jos (galben), stânga (roșu) sau dreapta (verde), în funcție de direcția sa.

Deci, dacă vă aflați într-un anumit $ (a, b) Poziția $ a unei plăci:

• Utilizând săgeata sus (albastră) veți ateriza în poziția $ (a, b) $ a plăcii imediat deasupra celei actuale.
• Utilizând săgeata în jos (galbenă) veți ateriza în poziția $ (a, b) $ a plăcii imediat sub cea curentă.
• Folosind stânga (roșu) ) săgeată, veți ateriza în poziția $ (a, b) $ a plăcii imediat în stânga celei actuale.
• Folosind săgeata dreaptă (verde), veți ateriza în $ (a, b) $ poziția plăcii imediat în dreapta celei actuale.

Pentru a genera acest lucru, am creat acest 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()); }; } } 

^{Îmi pare rău că acest site nu are culoare de sintaxă.}

Există sute sau mii de puncte de blocaj și ramuri. Mult mai mult decât doar 25 și 8 cerute de OP.

Pentru fiecare două locații există exact o cale către fiecare altă locație. Nu există cicluri în grafic și este conectat. Programul asigură că (metoda growMaze).

Nu există un punct de pornire sau de sfârșit definit. Obțineți la întâmplare două puncte și încercați să găsiți o cale. După cum vedeți, găsirea manuală a unei căi aici ar trebui să fie dificilă, deoarece există zece mii de poziții în acest labirint și a privi în jurul dimensiunilor $ w $ și $ z $ pentru a găsi o cale utilă este mai greu pentru ochii umani decât este în $ dimensiunile x $ și $ y $.

Puteți utiliza programul pentru a genera aleatoriu alte labirinturi. Și modificarea dimensiunii este ușoară: acestea sunt cele patru zeci de la începutul metodei main. În metoda main puteți schimba la fișierul în care este salvat labirintul generat.Pentru a arăta acest lucru, aici este un labirint mult mai mic și mai simplu de 4 $ ori 5 \ ori 3 \ ori 2 $ generat de program:

Apropo, setând $ w $ la 1 și $ z $ la 1, îl puteți folosi pentru a genera labirinturi 2D. Dacă setați doar unul dintre ele la 1, va fi un labirint 3D.

Comentarii

• Frumos, Victor. ‘ m-ai învins peste noapte. Aveam de gând să scriu un răspuns în această dimineață – însă nu acum. (@warspyking: S-ar putea să fii condamnat pentru totdeauna pentru că m-ai ținut treaz la 1 dimineața. A fost un apel strâns să rămâi frumos și confortabil și cald în pat sau să ieși din nou să introduci niște litere reci într-o cameră rece într-un computer indiferent … )
• @BmyGuest A fost un exercițiu bun de programare. Și este greu să găsești unul aici. 🙂
• Editat @BmyGuest. Este mai bine acum?
• Frumos: D Îmi place, treabă bună Victor!
• De unde începi? : /

Acum că a fost redeschis, vreau să postez ” soluție ” Am avut pentru asta în noaptea dinaintea răspunsului lui Victor. Victor m-a învins, iar Warspyking a modificat condițiile victoriei de atunci , deci nu mai este un răspuns valid. Încă am vrut să postez acest lucru pentru comentare (și verificare / respingere.)

Răspunsul funcționează pentru labirintele n-dimensionale și este, de asemenea, un algorithm nu este un labirint specific. Nu postez cod aici, ci conceptul algoritmului.

Soluția mea se bazează pe ideea că fiecare pixel / voxel / n-dim-element ( numit voxel de acum înainte ) poate fi o cale (0) sau un perete (1). Acest lucru este diferit de ceea ce a făcut Victor, dar poate să fie transformate unul în celălalt destul de ușor. ( Convertiți pereții & deschideri în voxeli adiționale sau invers. )

• Dimensiunile dimensiunilor datelor sunt numite n,m,k,l …
• Indexarea începe cu 0 pentru primul voxel

Inițializați datele:

• Creați datele labirintului ca matrice booleană dimensiunea necesară

• Inițializați toți voxelii ca 0 (gol)

• Creați o listă pentru indicii voxel ai pereților (gol )

• Setați fiecare voxel cu cel puțin un index pare la 1 (perete)

• Stocați indexul wall-voxel în listă.

• De acum înainte, ori de câte ori este eliminat un perete:

  • eliminați indexul corespunzător din listă
  • setați booleanul respectiv la 0 (gol)

Definiți începutul & poziția finală:

Setați în mod esențial cele două ” colțuri opuse ” începe și se termină.

• Setați voxelul indexului (0,0, …) pentru a fi locația de pornire
• Setați voxelul indexului (n, m, …) să fie destinația obiectivului
• Dacă voxelul de destinație este un perete, îndepărtați peretele. (Toate dimensiunile sunt egale)

Creați labirintul:

Labirintul actual este o grilă cu spații goale izolate.

• Etichetați toate spațiile goale cu o etichetă unică.

Acum mergeți iterativ ( WHILE-loop ):

• Alegeți aleatoriu un perete din lista index.
• Eliminați indexul din listă ( nu testați niciodată un perete de două ori )

Test : Se va elimina acest perete fuzionează două spații goale cu etichetă diferită? NU: următoarea iterație. ALTE:

• Eliminați peretele

• Dintre toate etichetele implicate, alegeți-o pe cea cu cea mai mică valoare

• Setați toate voxelurile care au etichete implicate la această valoare aleasă (= combinați spațiile goale)

• următoarea iterație

Opriți iterația atunci când nu există indici în listă.

Fără a-l demonstra, cred că acest algoritm vă va oferi:

- 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 

Inițial intenționam să codez acest algoritm și apoi să mă gândesc la un mod frumos de a afișa carcasa 4D, dar Victor a făcut deja o treabă excelentă, așa că o voi lăsa cu asta .

Comentarii

• Vă mulțumim pentru acest răspuns verbal de acoperire! Este sigur că este util pentru mine.