python - How do you create a perfect maze with walls that are as thick as the other tiles?

http://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/

I read this article about dungeon and maze generation. The author uses a kind of specialized algorithm for generating 'perfect' mazes that have walls of non-zero thickness.

(Edit: I misunderstood the term 'perfect' here. It actually means there are no loops in the maze)

As I understand, typical maze algorithms work for walls of zero thickness but this is not what I want.

He posted his code in the article, but after a cursory glance, I think I need someone to explain the procedure (or a similar one) in plain english.

My first two attempts looked like:

Which produces an effect with the diagonals that are unsightly.

and then:

Which is better but its not 'perfect' in the sense that it seems to waste some space.

If someone can give me simple english instructions I might post the python code after I get it working.

Answer

If I understand you correctly, you want to create a densely packed maze like this, where each wall is the same thickness as each corridor:

But you say the maze algorithms you've found only deal with infinitely thin partitions between cells corridor cells, rather than thick walls like these.

Let's look closer. Here I've overlaid a grid on the maze above, colouring all the even columns blue, and all the even rows orange:

You can see, the walls only show up on the coloured rows & columns. This gets a bit more obvious if we play with the grid spacing, making the coloured rows & columns thinner:

Gosh, that looks a lot like the output of one of those algorithms with infinitely-thin maze walls, doesn't it? Just at half the resolution.

So, we can take any maze algorithm that works on a rectangular grid with infinitely thin partitions between cells, and convert it to a thick maze like so:

• Open cell at (x, y) --> Open cell at (2x + 1, 2y + 1)


• Wall between (x, y) and (x, y + 1) --> Wall cell at (2x + 1, 2(y + 1))


• Wall between (x, y) and (x + 1, y) --> Wall cell at (2(x + 1), 2y + 1)


• --> All corner cells (2x, 2y) are walls