I explored the test site and tried different maze sizes with values in the 50s, 70s, 110s, 150 (including odd numbers). Curiously, I found the maze could be visually divided into four Cartesian-like quadrants. Consistently the middle divider had only one gap, and other major quadrants also consistently have only one gap. So, when I wondered if BFS solution might be different if I ran it multiple times, I couldn't tell. Because of the curious constraint I just mentioned, all paths had to traverse these major divisions through the same gap. In other words, if there was variance, it would be constrained to a very small movement in a corner.
I imagine if I dived into the code I would realize if my hypothesis that multiple runs of the BFS would always result in the same solution, was plausible or not. And it might also be the case if I understood BFS more, I would also know if it would always result in the same solution.
But how much fun if I could see it visually with a few clicks in the GUI.
Thanks so much for the compliment. This is probably a bi-product of the maze generation algorithm I used. Essentially, at every step, the algorithm bisects the maze horizontally or vertically - then, it chooses a random cell along this bisection to leave open (that way the 2 resulting regions are still connected). Then, the same algorithm is performed on the 2 new regions. Recursion continues until it no longer makes sense to continue bisecting.
You’ll have fun if you implement all the generation algorithms in that article. If you want to get rid of the visible bisect structure, you can use your solver with only slight modifications to generate your maze.
I can confirm that that's exactly what happened, different generation algorithms have a different "texture" to them in precisely this way and those textures do sometimes have a byproduct of making the maze easier or harder to solve.
The algorithm with the least helpful "texture" is probably Wilson's algorithm, which basically says: choose a point at random out in the unsolved territory and begin a random walk: when you reach the solved territory (the maze as it is already known), add those points back to the maze; when you self-intersect you should delete the random walk back to where you self-intersected. (For the very first walk, furthermore, there is only one "solved" point in the maze so you may wish to speed up maze generation by doing a different random walk that just "busts down walls" into the as-yet-unknown area; this is called Aldous-Broder and it has the opposite problem where it tries to randomly walk into unsolved space so it takes forever when the unsolved space becomes rare.) So one would start from,
function* randomWalkPoints({ x, y }, height, width) {
const incr = [{dx: -1, dy: 0}, {dx: 1, dy: 0}, {dx: 0, dy: -1}, {dx: 0, dy: 1}];
while (true) {
const { dx, dy } = incr[Math.floor(4 * Math.random())];
const new_x = x + dx, new_y = y + dy;
if (new_x >= 0 && new_x < width && new_y >= 0 && new_y < width) {
x = new_x;
y = new_y;
yield { x, y };
}
}
}
Now, the algorithm might get a bit weird because it looks like you are using block mazes rather than conventional thin-walled mazes; every n-by-m thin-walled maze has an embedding as a block maze of size (2n+1)-by-(2m+1) simply by making (0, y) and (x, 0) all walls, every (odd, odd) point is empty space representing one of the squares of the original maze, every (even, even) point is a block, and (odd, even) and (even, odd) points are blocks if and only if there is a vertical/horizontal wall between the corresponding squares in the original maze. So all of the resources you will find are talking about mazes that look like,
X X X X X X X X X X X
X . . . . . X . . . X
X . X X X . X . X X X
X . X . . . . . . . X
X . X . X X X . X X X
X . X . . . X . . . X
X . X X X X X . X . X
X . . . . . X . X . X
X X X X X . X X X . X
X . . . . . . . X . X
X X X X X X X X X X X
So I'm not 100% sure whether you would want to just restrict yourself to block mazes of this type, or whether you would want to just try something like "I modify Wilson's to keep track of walls I have already placed, too, and then when I intersect with myself on a path that already hit a block wall, I discard back to the open-space which placed that block" to get a slightly more general vision of the problem... I am not sure how you'd want to handle that.
Yeah, currently it seems large mazes are generated in 7x7 or similar blocks which are then combined to fill the area. A good example of this visually is a 29x29 or a 49x49 maze.
I imagine if I dived into the code I would realize if my hypothesis that multiple runs of the BFS would always result in the same solution, was plausible or not. And it might also be the case if I understood BFS more, I would also know if it would always result in the same solution.
But how much fun if I could see it visually with a few clicks in the GUI.
Thanks and Good luck.