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.
- 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.
- 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.
- 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.
- 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.