>> however, in rogue, and in wmaze, walls occupy a whole grid cell.
I think I know what you mean and I had the same kind of problem: pretty much evey maze-generation algorithm assumes the map is initially a grid of cells with four walls and proceeds by removing those walls one-by-one, systematically.
The problem you had, and that I had in my project, is that your grid is made up of single characters, say like this:
■ ■ ■ ■
■ ■ ■ ■
■ ■ ■ ■
■ ■ ■ ■
Where "■" is a wall. It is not clear how you can "remove a wall" from this grid. If you just replace each wall character with a floor character, say, "□", you have removed _four_ walls, not just one. Then if you use any of the standard maze-generation algos you end up with "maze snow", like this:
One way to work around this that I found online is to implicitly pad every wall with an extra character, so that for example, if you carved a two-step path starting at the top-left corner of the fully blocked maze above and going to the right, it would look like this:
■ ■ ■ ■
□ □ ■ ■
■ ■ ■ ■
■ ■ ■ ■
Instead of like this:
□ □ ■ ■
■ ■ ■ ■
■ ■ ■ ■
■ ■ ■ ■
I didn't like that because it effectively halves the dimensions of every maze. So I had a cunning plan and came up with an alternative that models an agent moving through a grid representing a maze and "discovering" the maze as it goes, as usual, but with some constraints that ensure the maze never loops back to itself. I'm working in Prolog so you might find it as hard to read my code as I found it to read your Forth :) but it's here anyway:
The idea is that, at any timestep, an agent navigating a grid is observing the following cells, with the agent centered on 1/1:
0/0 1/0 2/0
0/1 >1/1< 2/1
0/2 1/2 2/2
Where the cells in this 3 × 3 grid (I call it an "observation matrix") are populated at random, with wall or floor tiles, which may result e.g. in an observation matrix like this:
□ ■ ■
□ @ ■
■ ■ ■
With the agent as a '@'. Now it's obvious that if the agent moves one step up it will create a four-cell open-space, a "plaza", like so (there's a floor tile under the agent now):
□ @ ■
□ □ ■
■ ■ ■
So in this case you don't let the agent move up, only right, or down (it probably came from the left so you don't let it go back that way or it will enter a military oscillation: right-left-right-left-right... ). In a similar way you can avoid looping (it gets a bit complicated but you can find the logic in my comments in maze_generator.pl linked above).
Then it's a matter of moving through a fully-blocked initial grid cell-by-cell and laying down "observation matrices" at random, while respecting the anti-plaza and anti-looping constraints. You have to restart the process from a wall cell in a "hunt-and-kill" fashion every time it reaches a dead end to complete the maze but you get mazes that look like this (for a 40 × 40 maze):
Oh and you randomly place the S[tart] and E[nd] tiles of course. And you know generated mazes are always solvable because you solve them to generate them (like with DFS etc).
But note that in the maps you get this way there are blocked-out regions, "clumps" of wall tiles. There may be a better set of constraints that gets rid of those, but the result was good enough for my needs and I didn't bother.
And of course you can use the same technique to solve a maze and even do a bit of SLAM (Simultaneous Localisation and Mapping) by placing observation matrices in an expanding grid as the agent moves in an initially unseen map. OK, TMI, I'm stopping here.
I think I know what you mean and I had the same kind of problem: pretty much evey maze-generation algorithm assumes the map is initially a grid of cells with four walls and proceeds by removing those walls one-by-one, systematically.
The problem you had, and that I had in my project, is that your grid is made up of single characters, say like this:
Where "■" is a wall. It is not clear how you can "remove a wall" from this grid. If you just replace each wall character with a floor character, say, "□", you have removed _four_ walls, not just one. Then if you use any of the standard maze-generation algos you end up with "maze snow", like this: One way to work around this that I found online is to implicitly pad every wall with an extra character, so that for example, if you carved a two-step path starting at the top-left corner of the fully blocked maze above and going to the right, it would look like this: Instead of like this: I didn't like that because it effectively halves the dimensions of every maze. So I had a cunning plan and came up with an alternative that models an agent moving through a grid representing a maze and "discovering" the maze as it goes, as usual, but with some constraints that ensure the maze never loops back to itself. I'm working in Prolog so you might find it as hard to read my code as I found it to read your Forth :) but it's here anyway:https://github.com/stassa/ijclr_2024_experiments/blob/6cf3cc...
The idea is that, at any timestep, an agent navigating a grid is observing the following cells, with the agent centered on 1/1:
Where the cells in this 3 × 3 grid (I call it an "observation matrix") are populated at random, with wall or floor tiles, which may result e.g. in an observation matrix like this: With the agent as a '@'. Now it's obvious that if the agent moves one step up it will create a four-cell open-space, a "plaza", like so (there's a floor tile under the agent now): So in this case you don't let the agent move up, only right, or down (it probably came from the left so you don't let it go back that way or it will enter a military oscillation: right-left-right-left-right... ). In a similar way you can avoid looping (it gets a bit complicated but you can find the logic in my comments in maze_generator.pl linked above).Then it's a matter of moving through a fully-blocked initial grid cell-by-cell and laying down "observation matrices" at random, while respecting the anti-plaza and anti-looping constraints. You have to restart the process from a wall cell in a "hunt-and-kill" fashion every time it reaches a dead end to complete the maze but you get mazes that look like this (for a 40 × 40 maze):
Oh and you randomly place the S[tart] and E[nd] tiles of course. And you know generated mazes are always solvable because you solve them to generate them (like with DFS etc).But note that in the maps you get this way there are blocked-out regions, "clumps" of wall tiles. There may be a better set of constraints that gets rid of those, but the result was good enough for my needs and I didn't bother.
And of course you can use the same technique to solve a maze and even do a bit of SLAM (Simultaneous Localisation and Mapping) by placing observation matrices in an expanding grid as the agent moves in an initially unseen map. OK, TMI, I'm stopping here.