Generate a maze of with no checkboard - Eller's Method / Recursive BackTracking with pair colum-CodePudding

I'm trying to create maze with a recursive backtracking algorithm / eller's method with pair columns and pair lines. There's a problem, if the columns / lines are pair. For instance if I have a map of 4*4 :

X***
****
****
***X

The up left corner is the beginning, the other the end. Basically, I can't create a sort of "checkboard" as with a 5*5 maze (or any odd number I think).

X|X|X
-----
X|X|X
-----
X|X|X

Because it would do for a 4*4:

X|X|
----
X|X|
----

(Knowing that I have to reach the bottom right corner from the top left one). Does algorithms exist with this paterne or do I have to find a way to include these paterne with recursive backtracking / eller's method.

Also, the width of the path can be more than 1 unit.

Example for a 12 * 4 : * = empty cells X = walls

1*XXXX****XX
X****X*X**XX
X*XX***XX***
X*XXXX***XX2

Entry is 1, exit 2

Another example for a 4*4 :

1*XX
X**X
***X
XX*2

Entry point and exit are always the same and the width of the path can be one or more, it does not matter.

Thanks !

CodePudding user response：

If your data structure requires that grid cells are used for walls, then indeed you must make sure that the width and height of your grid are odd. If you have a recursive process, then you have to make sure that the subgrids also have this property (odd number of rows and columns). Two adjacent subgrids need to share one column or one row. So make sure you correctly divide the grid for the recursive process.

If for example you want to apply the iterative Eller's algorithm to potentially generate the following example:

1*XXXX****XX
X****X*X**XX
X*XX***XX***
X*XXXX***XX2

Then you need to see each character as a cell (also the X cells), not as a wall. The walls are between the cells. So you can picture the above grid in the following "syntax":

┌───────┬───────────────┬───────────────┬───────┐
│ 1     │ x   x   x   x │               │ x   x │
├───┐   └───────────┐   │   ┌───┐       │       │
│ x │               │ x │   │ x │       │ x   x │
│   │   ┌───────┐   └───┘   │   └───┐   └───────┤
│ x │   │ x   x │           │ x   x │           │
│   │   │       └───────┐   └───────┼───────┐   │
│ x │   │ x   x   x   x │           │ x   x │ 2 │
└───┴───┴───────────────┴───────────┴───────┴───┘

So here the areas with "x" are not really walls -- they are enclosures that are unreachable. This would not happen with the above referenced algorithm, because of the steps that say:

add at least one vertical connection

...and:

... the last row. This time, we must connect ALL adjacent (but disjoint) cells

If you omit these requirements, such enclosures could be created. The walls in this syntax (used by the referenced algorithm) are separations (lines) which are either horizontal or vertical. They don't translate themselves to "X" in your notation.

CodePudding user response：

If anyone wants the answer, I find a way. I set the walls every even number. For instance if I have a 6*6 maze, it will be like :

*XXXXX
XXXXXX
XXXXXX
XXXXXX
XXXXX*
XXXXX*

*XXXXX
XXXXXX
XXXXXX
XXXXXX
XXXXXX
XXXX**

I just select the bottom right corner and set an empty cell (*) above this corner or next to it. Using the recursive backtracking algorithm, I just have to check if I can move in every direction on 2 cells (the first one is a wall, second one an empty cell already visited or a wall that can be destroyed to form the path). Hope it helped some of you!