2
$\begingroup$

Hello I came across a really good algorithm perfect for a minigame I'm making.

When I was trying to implement the algorithm I stumbled with some doubts and I can't the algorithm right.

I'm talking about this old post: 4D Maze Creation!

And the algorithm is written by BmyGuest (at the end of the post). So if someone could help me understand a couple of things, I'd really appreciate:

The step I don't understand is this one: Will removing this wall merge two empty spaces of different label? NO: next iteration. ELSE:

What are the conditions when you select a wall that is in the middle. You can do the check with a white space in the top and in the bottom, and also left and right.

I don't understand what exactly are the checks that you have to do. The same happens if you want to test a voxel that is on the left or the random wall selected and on the right you don't have any because it's out of boundaries.

So my question is. What are the conditions to test that step? Thanks. I appreciate any help.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ "You can do the check with a white space in the top and in the bottom, and also left and right." Initially every cell has walls on every side (8 sides in a tesseract, 4 sides in 2-d). Every wall (apart from the boundary) separates exactly two cells from each other by blocking the path between them. You want to choose any wall at random. So at the start, just build a list of all the walls, or equivalently, a list of all pairs of neighbouring cells. Choose randomly from that list. Remove it from the list even if you keep the wall in the maze because you don't want to test the same wall twice. $\endgroup$
    – Jaap Scherphuis
    Aug 15, 2017 at 11:14
  • 1
    $\begingroup$ See also the disjoint-set data structure for keeping track of the connected spaces in the partial maze as you build it. $\endgroup$
    – Jaap Scherphuis
    Aug 15, 2017 at 11:17
  • $\begingroup$ I was thinking exactly that. At the beginning. A random wall in the middle of the grid, I can test top-bottom cells or left-right cells. The check will be random between those 2 options and if the test passes, remove the wall and next iteration. I'm still don't know what to do with boundaries. For example in a grid of 3 rows x 4 columns. If the wall in (0,4) is selected, I can't do any of the test, since the top neighbor is one of the boundaries and the right neighbor is the other boundary. And that's the same case for walls on the edges only a check is allow in some case. Is this correct? $\endgroup$
    – user3607098
    Aug 15, 2017 at 11:37
  • $\begingroup$ You are selecting a cell when you should select a wall. As I said, at the start you make a list of all pairs of neighbouring cells. This list will not contain (0,4). Instead it contains pairs like {(0,4),(1,4)} and {(0,4},(0,5)}. It does not contain boundary walls because it can't. Also, you seem to want to test all the walls of a cell. The algorithm selects just a single wall at a time, so after testing a wall between two cells, the next wall to be tested can be somewhere completely different, between two different cells. $\endgroup$
    – Jaap Scherphuis
    Aug 15, 2017 at 11:47

1 Answer 1

Reset to default
3
$\begingroup$

The step I don't understand is this one: Will removing this wall merge two empty spaces of different label? NO: next iteration. ELSE:

This portion of the algorithm is to ensure that no loops are created. When a wall is removed, the label of the paths on either side are changed to the minimum of the labels of those paths. In this way, if the two paths on either side of the wall already connect, they will have the same label. If the paths do not already connect, removing the wall will not create a loop in the maze.

What are the conditions when you select a wall that is in the middle. You can do the check with a white space in the top and in the bottom, and also left and right.

Each wall connects exactly 2 voxels. Walls in the third and fourth dimensions also only connect exactly 2 voxels. A voxel $(x,y,z,w)$, it will have 8 walls connecting it to $(x±1,y,z,w)$, $(x,y±1,z,w)$, $(x,y,z±1,w)$, and $(x,y,z,w±1)$. The voxel's label will be checked each time one of its walls is tested, but voxels themselves are never tested.

I don't understand what exactly are the checks that you have to do. The same happens if you want to test a voxel that is on the left or the random wall selected and on the right you don't have any because it's out of boundaries.

Only interior walls are added to the initial list of walls. Exterior walls do not need to be tested. The start and end points are pre-selected at opposite ends of the maze in this case.

So my question is. What are the conditions to test that step? Thanks. I appreciate any help.

The simplest way to understand is probably to go through a simple example.
Consider a 2x2 maze:

┌───┬───┐      ┌───┬───┐      ┌───┬───┐      ┌───┬───┐      ┌───┬───┐
│ A ┃ B │  1   │ A ┃ B │  2   │ A ┃ B │  3   │ A   A │  4   │ A   A │
├─━─┼─━─┤ -->  ├─━─┼─ ─┤ -->  ├─━─┼─ ─┤ -->  ├─━─┼─ ─┤ -->  ├───┼─ ─┤
│ C ┃ D │      │ C ┃ B │      │ B   B │      │ A   A │      │ A   A │
└───┴───┘      └───┴───┘      └───┴───┘      └───┴───┘      └───┴───┘

There are 4 interior walls that need to be checked. Bolded walls are unchecked. The walls would be checked in a random order, but an order has been selected for this example.

  1. Check the right wall. Since the voxels (top-right and bottom-right) are labelled differently, the wall is removed and all D voxels are relabelled B.
  2. Check the bottom wall. Since the voxels (bottom-left and bottom-right) are labelled differently, the wall is removed and all C voxels are relabelled B.
  3. Check the top wall. Since the voxels (top-left and top-right) are labelled differently, the wall is removed and all B voxels are relabelled A.
  4. Check the left wall. Since the voxels (top-left and bottom-left) are labelled the same, the wall stays to prevent the creation of a loop.

Now that all walls have been checked, the algorithm is finished.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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