4D 미로 만들기!

여기 있습니다. 직접 링크 에 액세스하여 전체 크기로 보거나 이미지를 확대합니다.

이것은 각 보드가 2D 평면 (수평이 $ x $이고 수직이 $) 인 보드의 평면입니다 (가로는 $ w $이고 세로는 $ z $). y $). $ x $ 및 $ y $ 위치를 변경하려면 현재 보드를 둘러보세요.

화살표를 사용하여 $ w $ 및 $ z $ 위치를 변경할 수 있습니다. 방향에 따라 한 보드를 위로 (파란색), 아래 (노란색), 왼쪽 (빨간색) 또는 오른쪽 (녹색)으로 점프하게합니다.

그러므로 특정 $ (a, b) 보드의 $ 위치 :

• 위 (파란색) 화살표를 사용하면 현재 보드 바로 위에있는 보드의 $ (a, b) $ 위치에 도착합니다.
• 아래쪽 (노란색) 화살표를 사용하면 현재 보드 바로 아래에있는 보드의 $ (a, b) $ 위치로 이동합니다.
• 왼쪽 (빨간색)을 사용하여 ) 화살표를 사용하면 현재 보드의 바로 왼쪽에있는 보드의 $ (a, b) $ 위치에 착륙합니다.
• 오른쪽 (녹색) 화살표를 사용하면 $에 착륙합니다. (a, b) $ 현재 보드 바로 오른쪽에 위치합니다.

이것을 생성하기 위해 다음 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()); }; } } 

^{이 사이트에 구문 색상이 없어서 죄송합니다.}

수백 또는 수천 개의 막 다른 지점과 분기점이 있습니다. OP에는 25 개와 8 개 이상이 필요합니다.

각 두 위치에 대해 서로 정확히 하나의 경로가 있습니다. 그래프에는 사이클이 없으며 연결되어 있습니다. 프로그램은 (growMaze 메소드)를 확인합니다.

정의 된 시작 또는 종료 지점이 없습니다. 무작위로 두 점을 얻고 경로를 찾으십시오. 보시다시피,이 미로에는 10,000 개의 위치가 있고 유용한 경로를 찾기 위해 $ w $ 및 $ z $ 차원을 둘러 보는 것이 $에서보다 인간의 눈에 더 어렵 기 때문에 여기서 경로를 수동으로 찾는 것은 어려울 것입니다. x $ 및 $ y $ 차원.

프로그램을 사용하여 무작위로 다른 미로를 생성 할 수 있습니다. 크기를 변경하는 것도 쉽습니다. main 메서드의 시작 부분에있는 10입니다. main 메소드에서 생성 된 미로가 저장되는 파일을 변경할 수 있습니다.이를 보여주기 위해 다음은 프로그램에 의해 생성 된 훨씬 더 작고 단순한 $ 4 \ times 5 \ times 3 \ times 2 $ 미로입니다.

그런데 $ w $를 1로, $ z $를 1로 설정하면 2D 미로를 생성하는 데 사용할 수 있습니다. 그중 하나만 1로 설정하면 3D 미로가됩니다.

댓글

• 잘하셨습니다, Victor. ' 밤새 저를 때렸습니다. 나는 오늘 아침에 답을 쓰려고했지만 지금은 아니었다. (@warspyking : 오전 1시에 나를 깨어있게하여 영원히 저주받을 수 있습니다. 침대에서 편안하고 따뜻하게 지내거나, 차가운 방에있는 차가운 편지를 다시 나가서 무관심한 PC에 입력하러 가야합니다 … )
• @BmyGuest 좋은 프로그래밍 연습이었습니다. 그리고 여기서 하나를 찾기가 어렵습니다. 🙂
• @BmyGuest가 수정되었습니다. 지금은 더 나아 졌나요?
• 좋습니다 : D 좋아요, Victor!
• 어디부터 시작하세요? : /

이제 다시 열렸으므로

솔루션 " Victor의 답변 전날 밤에이 문제를 해결했습니다. Victor는 저를 이겼고 Warspyking은 그 이후로 승리 조건을 수정했습니다. , 그래서 더 이상 유효한 답변이 아닙니다. 저는 여전히 댓글 (및 검증 / 반증)을 위해이 글을 게시하고 싶었습니다.

답은 n 차원 미로에서 작동하며 또한 algorithm 은 특정 미로가 아닙니다. 여기에 코드 를 게시하지 않고 알고리즘 개념을 게시합니다.

제 솔루션은 각 픽셀 / 복셀 / n-dim- 요소 ( 지금부터는 복셀이라고 함 )는 경로 (0) 또는 벽 (1) 일 수 있습니다. 이는 Victor가 만든 것과는 다르지만 가능합니다. 서로 쉽게 바꿀 수 있습니다. ( 벽을 & 개구부를 추가 복셀로 또는 그 반대로 변환하세요. )

• 데이터 크기는 n, m, k, l … 입니다.
• 인덱싱은 첫 번째 복셀에 대해 0으로 시작합니다.

데이터 초기화 :

• 미로 데이터를 부울 배열로 생성 필요한 차원의 수

• 모든 복셀을 0 (비어 있음)으로 초기화

• 벽의 복셀 인덱스 목록 생성 (비어 있음) )

• 하나 이상의 짝수 색인이있는 모든 복셀을 1 (벽)로 설정

• 목록에 벽-복셀 색인을 저장합니다.

• 지금부터 벽이 제거 될 때마다 :

  • 목록에서 해당 색인 제거
  • 관련 부울을 0 (비어 있음)으로 설정

시작 위치 정의 & 끝 위치 :

본질적으로 반대되는 두 개의 " 코너 "를 시작 및 끝.

• 인덱스 (0,0, …)의 복셀을 시작 위치로 설정
• 인덱스의 복셀 (n, m, …) 목표 목적지로 설정
• 목적지 복셀이 벽인 경우 벽을 제거합니다. (모든 치수는 균등 한 크기입니다.)

미로 만들기 :

현재 미로는 분리 된 빈 공간이있는 격자입니다.

• 모든 빈 공간에 고유 한 레이블을 지정합니다.

이제 반복적으로 이동합니다 ( WHILE-loop ) :

• 인덱스 목록에서 벽을 임의로 선택합니다.
• 목록에서 인덱스를 제거합니다 ( 벽 두 번 )

테스트 :이 벽을 제거하면 두 개가 병합됩니다. 다른 라벨의 빈 공간? 아니오 : 다음 반복. ELSE :

• 벽 제거

• 관련된 모든 레이블 중에서 가장 낮은 값을 가진 레이블 선택

• 관련 레이블이있는 모든 복셀을 선택한 값으로 설정 (= 빈 공간 병합)

• 다음 반복

목록에 인덱스가 없으면 반복을 중지합니다.

증명하지 않으면이 알고리즘이 다음을 제공 할 것이라고 생각합니다.

- 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 

원래 저는이 알고리즘을 코딩하고 4D 케이스를 표시하는 좋은 방법을 생각하려고했지만 Victor는 이미 그 작업을 훌륭하게 수행 했으므로 여기에 남겨 두겠습니다. .

댓글

• 이 도달 범위 구두 답변에 감사드립니다. 정말 유용합니다.