-4
$\begingroup$

You must design an algorithm for a 16x17 rectangle grid. Each "cell" is either a wall or an opening. This algorithm must achieve a maze without long hallways in 1 general direction, and must have dead ends.

Most online algorithms include cells with 4 walls. This has only squares with either cell or wall.

The simplest algorithm will be accepted. Accepted may change.

$\endgroup$

closed as too broad by Aza Jul 27 '15 at 10:40

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Is my algorithm on your previous maze question acceptable if you set the dimensions to $1, 16, 17, 1$? $\endgroup$ – Victor Stafusa Dec 14 '14 at 3:48
  • $\begingroup$ @Victor I'd appreciate a specifically 2D version of it, but yea I guess so if you fix it up for that. $\endgroup$ – warspyking Dec 14 '14 at 3:56
  • $\begingroup$ Dooknob can answer this, I watched his program do it, it was last year. $\endgroup$ – awesomepi Dec 14 '14 at 3:57
  • 6
    $\begingroup$ There are already well-known well-documented maze-generation algorithms for which you can find explanations and code online. Have you looked at these already? Is there something you find unsatisfying or confusing about them? $\endgroup$ – xnor Dec 14 '14 at 4:19
  • 2
    $\begingroup$ I think it should be added that you can always "map" algorithms which produce "cells with wall" and those which produces "cells are corridor or wall" into each other easily! So this is really a bad restriction for your question... $\endgroup$ – BmyGuest Dec 14 '14 at 17:39
3
$\begingroup$

This is an adapted version of the algorithm posted at this question.

Note that you ask for a 16 x 17 maze requiring each point either wall or empty. If you require the maze to be "enwalled" you need to use a 14x15 dimension in my algorithm and then draw a border of wall around it. (With or without hole close to the "exit" and "entry" points depending on your liking.)


This algorithm works for n-dimensional mazes and arbitrary maze dimensions. I do not post code here, but the algorithm concept. Hence there is no 100% verification it is correct.


My solution is based on the idea that each pixel/voxel/n-dim-element ( called voxel from now on) can either be a path (0) or a wall (1).

  • The data dimensions sizes are called n,m,k,l... [n = 16, m = 17]
  • Indexing starts with 0 for the first voxel

Initialize data:

  • Create the maze-data as Boolean array of needed dimensionality [16 x 17 = 2D]
  • Initialize all voxels as 0 (empty)
  • Create a list for voxel-indices of walls (empty)
  • Set every voxel with at least one even index to 1 (wall)
  • Store the wall-voxel index in the list.
  • From now on, whenever a wall is removed:

    • remove the according index from the list
    • set the according Boolean to 0 (empty)

Define start & end position:

Essentially set the two opposing "corners" to be start and end.

  • Set the voxel of index (0,0,...) to be the starting location
  • Set the voxel of index (n,m,...) to be the goal destination
  • If the destination voxel is a wall, remove the wall. (if at least one dimension is even-sized, this will be the case.)

So, the start for a 17x16 looks like this (Start is red, goal is green): Starting position

Create the maze:

The current maze is a grid with isolated empty spaces.

  • Label all empty spaces with a unique label.

Now go iteratively (WHILE-loop):

  • Randomly choose a wall from the index list.
  • Remove the index form the list (never test a wall twice)

Test: Will removing this wall merge two empty spaces of different label? NO: next iteration. ELSE:

  • Remove wall

  • Of all involved labels choose the one with lowest value

  • Set all voxels having involved labels to this chosen value (=merge empty spaces)

  • next iteration

Stop iteration when no indices are in the list.

Now this will produce something random like this for intermediate steps (colour indicates label):

enter image description here

with some more merging

enter image description here

...and eventually everything is merged into one maze with no loops and mazimized "area" like this: enter image description here

Without proofing it, I think this algorithm will give you:

- 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

Now, this is what I proposed for the original question on 4D puzzles.


Now comes your new restriction of the "long hallways". This is very vaguely defined restriction at the moment! In general, very large (or multidimensional) mazes you could do an auto-correlation of the maze (with itself) and measure the extension of the auto-correlation in each dimension - if it's too big, maze-creation failed and repeat (or break&repeat as suggested below.)

For smaller mazes like the one in this question (16x17), you could specify "no more than X into one direction" as criterion and then test your created maze against it. If it fails, you could either - recreate from scratch (and accept longer computing times in "bad luck" scenarios. - make the algorithm "split" to long corridor with a wall (creating 2 IDed areas) and then repeat the "merger" with all walls (Usually 1 step only will be enough!).

Assume you defined "no corridors >15" then you would potentially get something like the following from the above: (red "fills" green "opens")

enter image description here

enter image description here

enter image description here

I think that should get you where you wanted.

I could write this into an algorithm to actually do it, but I don't feel for it and I wouldn't be able to do it in a "web-accessible" language like Java (because I don't know Java that well ;c) ) But then, your requirement was to devise an algorithm not a program.

$\endgroup$
  • $\begingroup$ Interesting... Accepted for now but no guarentees it'll stay accepted (open-ended) $\endgroup$ – warspyking Dec 14 '14 at 18:22
  • $\begingroup$ Yea sorry, meant to come back and accept. Must've forgot. $\endgroup$ – warspyking Dec 14 '14 at 19:12
2
$\begingroup$

This is just an adaptation of an answer that I posted on another question, just reduced and simplified to be 2D instead of 4D.

Here is the java code:

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 Maze2D {
    public static void main(String[] args) throws IOException {
        Maze maze = new Maze(16, 17);
        BufferedImage im = maze.draw();
        ImageIO.write(im, "png", new File("maze5.png"));
    }

    public static final class Coordinate2D {
        private final Maze maze;
        private final int x, y;

        public Coordinate2D(Maze maze, int x, int y) {
            Objects.requireNonNull(maze);
            if (x < 0 || x >= maze.xSize || y < 0 || y >= maze.ySize) throw new IndexOutOfBoundsException();
            this.maze = maze;
            this.x = x;
            this.y = y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(maze, x, y);
        }

        @Override
        public boolean equals(Object another) {
            if (!(another instanceof Coordinate2D)) return false;
            Coordinate2D c4d = (Coordinate2D) another;
            return maze == c4d.maze && x == c4d.x && y == c4d.y;
        }

        public int squareDistance(Coordinate2D another) {
            Objects.requireNonNull(another);
            if (maze != another.maze) throw new IllegalArgumentException();
            int dx = Math.abs(x - another.x);
            int dy = Math.abs(y - another.y);
            return dx + dy;
        }

        public Coordinate2D minusX() { return x == 0              ? null : new Coordinate2D(maze, x - 1, y); };
        public Coordinate2D plusX()  { return x == maze.xSize - 1 ? null : new Coordinate2D(maze, x + 1, y); };
        public Coordinate2D minusY() { return y == 0              ? null : new Coordinate2D(maze, x, y - 1); };
        public Coordinate2D plusY()  { return y == maze.ySize - 1 ? null : new Coordinate2D(maze, x, y + 1); };
        public Maze getMaze() { return maze; }
    }

    public static final class Maze {
        private final int xSize, ySize;
        private final Map<Coordinate2D, Node> nodes;
        private final Node start;

        public Maze(int x, int y) {
            this.xSize = x;
            this.ySize = y;
            nodes = new HashMap<>(x * y);
            fill();
            this.start = chooseRandomNode();
            growMaze();
        }

        private void fill() {
            for (int b = 0; b < xSize; b++) {
                for (int c = 0; c < ySize; c++) {
                    Coordinate2D coord = new Coordinate2D(this, b, c);
                    nodes.put(coord, new Node(coord));
                }
            }
        }

        public Node nodeAt(Coordinate2D coord) {
            if (coord == null) return null;
            return nodes.get(coord);
        }

        private Node chooseRandomNode() {
            int n = (int) (Math.random() * xSize * ySize);
            return new ArrayList<>(nodes.values()).get(n);
        }

        private void growMaze() {
            List<Node> frontier = new ArrayList<>(xSize * ySize);
            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);
            BufferedImage im = new BufferedImage(boardWidth + cellWidth - 1, boardHeight + cellHeight - 1, BufferedImage.TYPE_INT_ARGB);
            Graphics2D g = im.createGraphics();
            for (int x = 0; x < xSize; x++) {
                for (int y = 0; y < ySize; y++) {
                    Coordinate2D c = new Coordinate2D(this, x, y);
                    Node n = nodeAt(c);
                    int x1 = cellWidth * x + cellWidth - 1;
                    int y1 = cellHeight * y + cellHeight - 1;
                    int x2 = x1 + cellWidth;
                    int y2 = y1 + cellHeight;
                    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);
                }
            }
            return im;
        }
    }

    public static final class Node {
        private final Coordinate2D coord;
        private final List<Node> linkedNeighbours;
        private List<Node> neighbours;
        private boolean linked;

        public Node(Coordinate2D 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(minusX(), plusX(), minusY(), plusY()));
                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 Maze getMaze() { return coord.getMaze(); }
        public Coordinate2D getCoord() { return coord; }
        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());  };
    }
}

I am sorry that this site has no syntax-coloring.

Here is a generated maze:

maze

Most of the code is boilerplate code (java is too verbose) and there is some code used only for drawing, what really matters to the algorithm is this:

        private void growMaze() {
            List<Node> frontier = new ArrayList<>(xSize * ySize);
            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 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;
        }

Which basically starts with a random cell in a list called frontier. Then it repeatly randomly chooses a cell in that list and looks randomly for an unlinked neighbouring cell to the cell chosen. Then, the neighbouring cell is linkedand added to the list. If there is no unlinked neighbouring cell, the chosen cell is removed from the list. This is repeats until the list eventually gets empty.

There is nothing in the code to avoid long corridors. I just executed it several times until you get a maze without long corridors. If this should be enforced, a simple way would be to just regenerate the maze all again if there is some long corridor until no long corridor exists.

$\endgroup$
  • $\begingroup$ I was wrong, this won't work. Each square on the grid is either wall or cell $\endgroup$ – warspyking Dec 14 '14 at 10:01
  • $\begingroup$ @warspyking Done. Note that it's valid for N-dimensional mazes fulfilling the conditions of your other question on "maximum filling level" and "no loopholes" as well ;c) $\endgroup$ – BmyGuest Dec 14 '14 at 17:37
  • 3
    $\begingroup$ @warspyking Victors algorithm is very valid. You can always "map" those type of mazes. Simply "enlarge" the maze of Victor by 2 (each "cell" getting 8 neighbour-cells) and "fill" those which are walls... Obviously, you have to restart Victors algorithm with half-dimensions in this case... $\endgroup$ – BmyGuest Dec 14 '14 at 17:41

Not the answer you're looking for? Browse other questions tagged or ask your own question.