Algorithm for generating a maze with the depth of the first search with blocks instead of walls

Question

I am trying to implement the first depth search algorithm in my game. I study this web page: http://www.mazeworks.com/mazegen/mazetut/index.htm , only to find that I cannot use it with blocks instead of Walls. What I mean by blocks is a square that covers the whole cell, not just the edges. I thought it would be easier, but now I'm not sure. Has anyone done this? If so, how? (psuedocode is great). Or, if I just go with the wall way, if it's easier?

Answer 1

depending on what you really want to achieve, I have two solutions for you. both of them are basically the algorithm presented on the website you linked to.

1.) there are blocks in the predefined positions of your maze

• you run the algorithm in a 2*k+1 grid
• Suppose the numbering of your cells starts at the top left with (0,0). mark all cells with 2 odd coordinates ( (2*p+1, 2*q+1); p,q < k ) as blocks.
• you run a modified algorithm from your source to the remaining cells ("even cells"). modifications:
  • start with an even cell selected at random.
  • "neighboring cell" - the second, but the next cell in any direction of the grid; those. you are "jumping" on the brick.
  • instead of knocking down a wall between cells, you turn the block into an accessible cell. however this cell will not be considered selection and rollback

2.) instead of walls separating the cells you want to block.

Before starting the algorithm, mark any number of cells in the form of blocks. proceed as directed in your source, but never consider any of the blocks. You will need to take special precautions if you want you to guarantee full availability in your maze. a simple scheme would be to never mark a cell as a block that has more than 1 block as neighbors.

hope these ideas meet your needs,

Best regards, carsten