7
\$\begingroup\$

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:

enter image description here

Which produces an effect with the diagonals that are unsightly.

and then:

enter image description here

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It looks like you're using the term "perfect" to mean something a bit different than the linked article. In the article, "perfect" means the maze has no loops: there is a unique path from any one point in the maze to any other. (Taken as a graph, the maze is a tree) But you seem to use the word "perfect" to mean that the maze is densely packed - that there is no contiguous block of uncarved wall thicker than a corridor. Have I read this correctly? The article also goes into some detail on making mazes imperfect - adding loops and solid wall areas - is that something you want? \$\endgroup\$
    – DMGregory ♦
    Commented Jun 16, 2017 at 2:12
  • \$\begingroup\$ Yes you were right I misunderstood that, thanks for clearing that up. I am pretty sure I understand how to make loops. \$\endgroup\$
    – Curtis Sherwood
    Commented Jun 16, 2017 at 2:21

1 Answer 1

Reset to default
11
\$\begingroup\$

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:

Maze with thick walls

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:

Maze with tinted rows & columns

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:

Maze with thinned rows & columns

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
\$\endgroup\$
2
  • \$\begingroup\$ It seems if you were to follow the example in this article, you would want to carve/create the entire dungeon (including rooms) in the reduced form before converting it to the 'full resolution'. Does that sound about right to you? \$\endgroup\$
    – Curtis Sherwood
    Commented Jun 16, 2017 at 5:30
  • \$\begingroup\$ You could do that, or you could work natively at full res and only draw rooms with corners on odd intersections. Carving out one wall is replaced with tunneling two cells. \$\endgroup\$
    – DMGregory ♦
    Commented Jun 16, 2017 at 10:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .