How the maze for maze-mapping problem is generated? It seems there are multiple ways to approach the task - let's here try the specific way implemented in that problem - just as an exercise.
In the process we'll use random sequence generated with linear congruential generator, using
parameters A = 445, C = 700001 and M = 2097169. The input data will consist of the maze size N (so it is N*N cells) and X0 - the
seed for the generator. Wherever we need to generate value from 0 to K-1 (i.e. one of K values) - let's describe it with rnd(K).
So the flow is like this. We start with N*N square where every cell has all its walls in place (i.e. all cells are separated).
Pick the initial cell by generating random numbers for column and row:
col = rnd(N)
row = rnd(N)
Now the future "maze" consists of this single cell. Put it into some array (let's call it cells).
On every step pick random cell from cells array (i.e. with rnd(length(cells)) if array uses 0-based indices).
For this randomly chosen cell, collect all of its 4 neighbours which are not yet included in the maze. Let's call this small array neighbors.
Neighbors are to be collected in the north-east-south-west order (above, right, below, left).
Pick randomly one from these collected neighbors (i.e. with rnd(length(neighbors))) and connect it to the current "chosen" cell, by "breaking"
the wall between them. If there were no suitable neighbors at all, remove the "chosen" cell from cells array.
Continue in this manner until the end.
Please, "pretty-print" your generated maze. As each wall is shared by two cells, it is enough to print two walls for every cell. Firstly
print underscore _ if the cell has "south" (below) wall, then print "pipe" | if cell has east wall. Thus every cell is described by
two consequtive characters (if there is no wall in either place - print space).
Also, of course, print the left and top borders of the maze in the same way.
Let's see an example with 3x3 grid, using 0 seed for randomizer:
Firstly we generate column and row for the initial cell. We got two random values (700001, 1819434) which by modulo 3 give (2, 0).
Next random number 840897 picks random cell, though we have one only. Looking around we find two neighbors (2, 1) and (1, 0) for it
(in this particular order). Another random number 1603084 means we pick the first of them (index 0) and add it to the maze, breaking the
wall below (2, 0).
Next random number 1034921 picks the second (index 1) of two cells, it's our newly added one. We find two neighbors again (2, 2) and
(1, 1) because the neighbor above is already in the maze (in other words - we came from there). Next random 1959835 means that now we
pick the latter of two and add it to the maze, breaking the wall on the left of (2, 1).
And so on, we should end with maze like this:
_ _ _
| _ |
|_|_ |
|_ _ _|
Another example, with size 5 and seed 1:
_ _ _ _ _
| | |_ | |
| _|_ | |
| _| |_ |
| | |_ |
|_ _|_ _ _|
That's all. It seems this way of generating mazes produces many "side-rooms" or "short-branches". Feel free to share if you come upon some simple way of building mazes with fewer and longer branches :)