4D labirintus létrehozása!

Itt van. Hozzáférhet a közvetlen linkhez , ha teljes méretben szeretné megtekinteni (vagy nagyítani szeretné a képet).

Ez egy táblák síkja (vízszintes $ w $ és függőleges $ z $), ahol minden tábla 2D sík (vízszintes $ x $ és függőleges $ y $). A $ x $ és $ y $ pozíció megváltoztatásához járkáljon az aktuális táblán.

A nyilak segítségével megváltoztathatja $ w $ és $ z $ pozícióit. Egy táblával felfelé (kék), lefelé (sárga), balra (piros) vagy jobbra (zöld) ugorhat, annak irányának megfelelően.

Tehát, ha egy adott $ (a, b) Egy tábla $ helyzete:

• A felfelé mutató (kék) nyíl használatával a tábla $ (a, b) $ pozíciójába kerül közvetlenül az aktuális fölött.
• A lefelé mutató (sárga) nyíl használatával a tábla $ (a, b) $ pozíciójába kerül közvetlenül az aktuális tábla alatt.
• A bal (piros) használatával ) nyíl, a tábla $ (a, b) $ pozíciójába kerül, közvetlenül az aktuális bal oldalán.
• A jobb (zöld) nyíl használatával a $ (a, b) A tábla $ helyzete közvetlenül a jelenlegi jobb oldalán.

Ennek létrehozásához létrehoztam ezt a Java programot:

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

^{Sajnálom, hogy ennek a webhelynek nincs szintaxis-színezése.}

Több száz vagy ezer zsákutca és elágazási pont található. Sokkal több, mint csak 25 és 8, amelyet az OP megkövetel.

Mindkét helyhez pontosan egy út vezet egymáshoz. A grafikonon nincsenek ciklusok, és össze van kapcsolva. A program biztosítja (growMaze módszer).

Nincs meghatározott kezdő vagy végpont. Csak véletlenszerűen szerezzen be két pontot, és próbáljon megtalálni az utat. Amint látja, az útvonal manuális megtalálásának nehéznek kell lennie, mivel ebben az útvesztőben tízezer pozíció van, és a $ w $ és $ z $ dimenziók körüli nézetekkel hasznos utat találni az emberi szem számára nehezebb, mint a $ -ban x $ és $ y $ dimenziók.

A program segítségével véletlenszerűen generálhat más útvesztőket is. Méretének megváltoztatása is egyszerű: Ők az a négy tíz a main módszer elején. A main metódusban megváltoztathatja, hogy a létrehozott labirintus melyik fájlra legyen mentve.Ennek bemutatására itt sokkal kisebb és egyszerűbb 4-szeres $ 4-szer 5-szer 3-szor 2x labirintus jön létre, amelyet a program generál:

Egyébként azáltal, hogy a $ w $ értéket 1-re és a $ z $ értéket 1-re állítja, felhasználhatja 2D labirintusok létrehozására. Ha csak az egyiket állítja 1-re, akkor ez 3D-labirintus lesz.

Megjegyzések

• Szép, Victor. ‘ egyik napról a másikra megvertél. Ma reggel választ akartam írni – bár most nem. (@warspyking: Lehet, hogy örökre elkárhoznak, amiért hajnali 1 órakor ébren tartasz. Közeli hívás volt, hogy kedves, hangulatos és meleg maradj az ágyban, vagy újra kijusson, hogy hideg helyiségben írjon néhány hideg betűt egy gondtalan PC-be … )
• @BmyGuest Jó programozási gyakorlat volt. És nehéz itt találni. 🙂
• @BmyGuest szerkesztve. Most jobb?
• Szép: D Imádom, jó munkát Victor!
• Hol kezded? : /

Most, hogy ez újra megnyílt, fel akarom küldeni a ” megoldás ” erre a Victor válasza előtti éjszakán volt. Victor megvert, és a Warspyking azóta módosította a győzelem feltételeit , így ez már nem érvényes válasz. Ezt továbbra is kommentálni (és ellenőrzésre / cáfolásra) akartam közzé tenni.

A válasz n-dimenziós labirintusok esetén működik, és ez egyben algoritmus nem egy adott labirintus. Nem a code t teszem itt közzé, hanem az algoritmus koncepcióját.

Megoldásom azon az ötleten alapul, hogy minden pixel / voxel / n-dim-elem ( mostantól voxelnek hívják ) lehet útvonal (0) vagy fal (1). Ez különbözik attól, amit Victor készített, de meglehetősen könnyen egymásba alakíthatók. ( Csak alakítsa át a falakat & nyílásokat további voksokká vagy fordítva. )

• Az adatdimenziók méreteit n,m,k,l…
• Az indexelés 0-val kezdődik az első voxelnél

Adatok inicializálása:

• A labirintusadatok létrehozása logikai tömbként a szükséges dimenzionalitás

• Inicializálja az összes voxelt 0-ként (üres)

• Készítsen listát a falak voxel-indexeihez (üres )

• Állítson minden vokselt legalább egy páros indexel 1-re (fal)

• Tárolja a wall-voxel indexet a listában.

• Mostantól kezdve, amikor egy falat eltávolítanak:

  • távolítsa el a megfelelő indexet a listából
  • állítsa a logikai értéket 0-ra (üres)

Define start & véghelyzet meghatározása:

Alapvetően állítsa be a két ellentétes ” sarkot ” eleje és vége.

• Állítsa be az index voxeljét (0,0, …) kiinduló helyül
• Állítsa be az index voxeljét (n, m, …) hogy legyen a cél cél
• Ha a cél voxel egy fal, akkor távolítsa el a falat. (Minden dimenzió páros méretű)

Készítse el az útvesztőt:

A jelenlegi labirintus egy rács, üres üres helyekkel.

• Az összes üres teret egyedi címkével látja el.

Most menjen iteratív módon ( WHILE-loop ):

• Véletlenszerűen válasszon egy falat az indexlistából.
• Távolítsa el az indexet a listából ( soha ne teszteljen egy fal kétszer )

Test : A fal eltávolítása kettőt egyesít üres címkék? NEM: következő iteráció. MÁS:

• Fal eltávolítása

• Az összes érintett címke közül válassza ki a legalacsonyabb értéket

• Az összes olyan címkét tartalmazó vokselt állítsa erre a kiválasztott értékre (= egyesítse az üres helyeket)

• következő iteráció

Állítsa le az iterációt, ha nincs index a listában.

Igazolás nélkül azt hiszem, hogy ez az algoritmus megadja:

- 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 

Eredetileg ezt az algoritmust szándékoztam kódolni, majd a 4D eset megjelenítésének jó módjára gondoltam, de Victor ebben már nagyszerű munkát végzett, ezért ezt meghagyom .

Megjegyzések

• Köszönöm ezt az eléréses szóbeli választ! Biztosan hasznos számomra.