Issue with Eller's algorithm - maze generation

Question

I'm trying to create a maze using Eller's algorithm. There's not much information on the Internet about this particular algorithm. So I have some difficulties with this algorithm, because there're some things I don't fully understand. But anyway this is what I have right now:

class Cell:
    def __init__(self, row, col, number, right_wall, bottom_wall):
        self.row = row
        self.col = col
        self.number = number    # defines which set this block is in
        self.right_wall = right_wall
        self.bottom_wall= bottom_wall

# every block includes 5x5 px white space + 1px on it's left and 1px on it's bottom for walls (if the block has ones)
def create_block(row, col, right_wall, bottom_wall):
    for i in range(row-2, row+4):   # since the path is 5px wide
        for j in range(col-2, col+4):   # i go to a central pixel of block's white space and make it thick
            maze[i, j] = [255, 255, 255]    # in other words i draw 2px border around central pixel
    if right_wall:  # if the block has wall on it's right
        create_right_wall(row, col, 1)  # draw right wall with a function
    if bottom_wall: # if the block has wall on it's bottom
        create_bottom_wall(row, col ,1) # draw bottom wall with a function


def create_right_wall(row, col, color):
    if color == 0:  # if color parameter = 0
        for i in range(row-2, row+4):
            maze[i, col+3] = [0, 0, 0]  # I draw (create) black wall
    else:
        for i in range(row-2, row+4):
            maze[i, col+3] = [255, 255, 255]    # I draw white wall (if I need to delete a wall)


def create_bottom_wall(row, col, color):
    if color == 0:
        for i in range(col-2, col+4):
            maze[row+3, i] = [0, 0, 0]
        if row + 4 < maze_height and maze[row+4, col-3][0] == 0:    # sometimes there's 1px gap between bottom walls
            maze[row+3, col-3] = [0, 0, 0]  # so I fill it with black pixel
    else:
        for i in range(col-2, col+4):
            maze[row+3, i] = [255, 255, 255]    # draws white wall (deleting wall)


def creating():
    current_point = [3, 3]  # where the top-left block appears ([3,3] is for the block's center)

    set_count = 1   # to have unique set numbers, it increases every time after it has been used

    for row in range(height):   # going from top to bottom
        # I print some unnecessary information just to know what's happening
        print("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - row", row) # current row being created
        if row == 0:    # if it's the first row
            for col in range(width):
                create_block(current_point[0], current_point[1], False, False)

                blocks[row].append(Cell(current_point[0], current_point[1], set_count, False, False))
                set_count += 1  # since the set number has been used, the next block will have another one

                current_point[1] += 6   # the center of the next block is 6px away from the center of the current one

        elif row == height - 1: # if it's the last row
            for i in range(width):
                create_block(current_point[0], current_point[1], False, False)
                blocks[row].append(Cell(current_point[0], current_point[1], blocks[row-1][i].number, False, True))

                current_point[1] += 6

                # I don't know why I do this. Just trying to create the last line correctly
                if (not blocks[row-1][i].bottom_wall and not blocks[row-1][i + 1].bottom_wall) and \
                        (blocks[row-1][i].number == blocks[row-1][i + 1].number):
                    create_right_wall(blocks[row][i].row, blocks[row][i].col, 0)
            break   # since it's the last row, don't do anything else



        else:
            for col in range(width):
                create_block(current_point[0], current_point[1], False, False)

                print("block on top has set:", blocks[row-1][col].number, end=" ")

                if blocks[row-1][col].bottom_wall:  # if upper block has bottom wall
                    blocks[row].append(Cell(current_point[0], current_point[1], set_count, False, False))
                    print("upper block has a bottom wall, so set for the current block is", set_count)
                    set_count += 1
                else:   # if not, the current block's set will be the same as for the upper one
                    blocks[row].append(Cell(current_point[0], current_point[1],
                                            blocks[row-1][col].number, False, False))
                    print("current block set", blocks[row-1][col].number)

                current_point[1] += 6

            # just to show set numbers for current row
            for i in blocks[row]:
                print(i.number, end=" ")


        # putting a wall between blocks of the same set (we don't want to have loops in our maze)
        for i in range(len(blocks[row]) - 1):
            if blocks[row][i].number == blocks[row][i+1].number:
                blocks[row][i].right_wall = True
                create_right_wall(blocks[row][i].row, blocks[row][i].col, 0)
                print("put a wall between", i+1, "и", i+2, "because", blocks[row][i].number, "=",\
                      blocks[row][i+1].number)


        for i in range(len(blocks[row]) - 1):
            if random.choice([0, 1]) == 0 and blocks[row][i].number != blocks[row][i+1].number:
                blocks[row][i + 1].number = blocks[row][i].number
                print("connect block", i + 1, "and", i + 2)
            else:
                blocks[row][i].right_wall = True
                create_right_wall(blocks[row][i].row, blocks[row][i].col, 0)


        # to know what set nu,bers we have in the current row
        sets_in_row = []
        for i in blocks[row]:
            print(i.number, end=" ")
            sets_in_row.append(i.number)

        sets_in_row = sorted(set(sets_in_row), key=lambda x: sets_in_row.index(x))
        print(sets_in_row)


        current_bl = 0  # current block in a
        for mn in sets_in_row:  # for every set number in a row
            current_mn_length = sum([p.number == mn for p in blocks[row]])  # how many blocks has this set number
            if current_mn_length > 1: # if the current set has more than 1 block
                quantity = random.randrange(1, current_mn_length)   # random number of bottom walls
                # whick blocks in the current set will have a bottom wall
                bloxxxx = random.sample(list(range(current_bl, current_bl + current_mn_length)), quantity)

                # just to know how it's going
                print("\nblock:")
                for y in range(current_bl, current_bl + current_mn_length):
                    print("pos:", y + 1, end=" ")
                    print("  num:", blocks[row][y].number,)


                print("bottom walls for")
                for i in bloxxxx:
                    print(i+1, end=" ")

                print()

                for b in bloxxxx:
                    blocks[row][b].bottom_wall = True
                    create_bottom_wall(blocks[row][b].row, blocks[row][b].col, 0)

                current_bl += current_mn_length

            else:
                print("\n set length of", current_bl + 1, "=", current_mn_length, "so no bottom wall\n")
                current_bl += current_mn_length

        current_point[0] += 6   # go to the center of the next row block
        current_point[1] = 3    # go to the center of the first block of the next row


while True:
    width = int(input("Width: "))
    height = int(input("height: "))

    maze_width = width * 6 + 1
    maze_height = height * 6 + 1

    maze = np.full((maze_height, maze_width, 3), 0, dtype=np.uint8)
    paths = []
    all_positions = width * height
    break

blocks = [[] for h in range(height)]

creating()

for h in range(maze_height):
    maze[h][maze_width-1] = [0, 0, 0]

for w in range(maze_width):
    maze[maze_height-1][w] = [0, 0, 0]

img = Image.fromarray(maze, 'RGB')
img.save('maze.png')
img.show()

I've tried to explain every line, so you can understand what is going on in my code. I know I have many unnecessary pieces of code. That's because I tried so many ways to generate a correct maze.

The problem is mazes are not always generated correctly. For example this one has loops. But it should not.

And look at this one This one has loops and ISOLATED block. That because of set numbers. In this maze the second row has these sets:

After I randomly connected blocks, a row of 2s has been separated with 22. So the second block is not the only one in set number 2.

Please help me fix my code. If you have any questions about my code, I'll try to give you more information about it.

Answer 1

I just came across this same issue!

After long pondering I came to the conclusion that none of the tutorials available online explain correctly the "join sets" aspect! This is what creates loops in the same way you show.

Let me try to simplify the algorithm steps here:

1. Split a row in different sets putting right walls.
2. Make at least one bottom opening for each set.
3. Separate cells with the same set to prevent loops.
4. Start from step 1

Now there's a key aspect to take in account: a set is the sum of all cells in a row marked with the same "number" (which represents a set). So if you have:

    | 1   1   1 | 2 | 1 |

The set 1 is all the cells with 1, included the last one. So if you want to make a single opening down, you can also choose to open the last cell bottom like this:

    | 1   1   1 | 2 | 1 |
    |-----------| ↓ | ↓ |

This works fine because set 1 has at least one opening.

Now the problem with loops is when you join sets:

    | 1   1   1 | 2 | 1 |
    | ↓ |-------| ↓ | ↓ | ← let's make 2 down openings for set 1
    | 1   4   5 |(2   1)| ← let's say you want to merge set 1 and 2
    | 2   4   5 | 2   2 | ← also change the set of the first cell!

You need to change the set of all cells in the row with the same set of the replaced one!

This is never shown in tutorials, but it's stated in the algorithm explanation!

This way the information that "the first cell is connected upwards with the last two" is preserved as you go down the maze and, if set 2 spreads downwards up to the third cell, you'll be prompt to put a wall to preserve loops like this:

    | 1   1   1   1   1 |
    | ↓ | ↓ | ↓ |---| ↓ |
    | 1 | 1 | 1 | 2 | 1 |
    | ↓ |-------| ↓ | ↓ |
    | 1   4   4 |(2   1)|
    | 2 | 4   4 | 2   2 |
    | ↓ |---| ↓ | ↓ |---|
    |(2   5)  4 | 2   6 |
    | 2   2 | 4 | 2 | 6 |
    |---| ↓ | ↓ | ↓ | ↓ |
    | 7  (2   4)|(2   6)|
    | 7 | 2   2 | 2   2 |
    | ↓ |---| ↓ | ↓ |---|
    |(7   8)  2  (2   9)| ← here you HAVE to put a wall between the two 2!
    | 7   7 | 2 | 2   2 |
    |---| ↓ | ↓ |-------|
    | a   7   2   b   c | ← last row connect all sets
    | a   a   a   a   a |

The resulting maze would be like:

    _____________________
    |                   |
    |   |   |   |---|   |
    |   |   |   |   |   |
    |   |-------|   |   |
    |   |       |       |
    |   |---|   |   |---|
    |       |   |   |   |
    |---|   |   |   |   |
    |   |       |       |
    |   |---|   |   |---|
    |       | Y |     X |
    |---|   |   |-------|
    |                   |
    |-------------------|

See how there's no loops and the X is still connected with the rest of the maze because in the last step we made a down opening to the Y cell which was in set 2 as well!

If we didn't merge the sets correctly it would have turned out like this:

    _____________________
    |                   |
    |   |   |   |---|   |
    |   |   |   |   |   |
    |   |-------|   |   |
    |   |       |       |
    |   |---|   |   |---|
    |       |   |   |   |
    |---|   |   |   |   |
    |   |       |       |
    |   |---|   |   |---|
    |       | 1   2   2 | ← 1 and 2 are actually in the same set!
    |---|   |   |-------|
    |                   |
    |-------------------|

Hope this helps though quite late!