Issue with Eller's algorithm - maze generation

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.

enter image description here

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

enter image description here 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.

728x90

0 Answers Issue with Eller's algorithm - maze generation