Efficient ORing

To efficiently store a set of options in an integer variable, Listing 1 defines the cardinal directions as constants. The keyword iota with the << operator in line 10 sets the values of the constants North, South, West, and East as powers of two (i.e., to the values 1, 2, 4, and 8).

This allows a variable (such as Options) to be set to more than one of these values by binary ORing. For example, if a cell is to allow transitions to both north and east, the program sets its value to 1 | 8 (i.e., 9). If the program then wants to test whether east is an option, it checks Option & 8, which is always non-zero if an 8 was previously ORed with it.

Randomness

When randomly selecting elements from an array slice, like in line 83 of Listing 2, it is important to take great care to ensure that the pick is truly random, rather than some elements appearing preferentially. The Intn(x) function from Go's standard math/rand package returns equally distributed random values in the form of integers between   (inclusively) and the integer value x (exclusively) for this purpose.

In the code snippet shown in Listing 4, len(slice) returns the number of elements in the array; however, the index of the last element is one less than this. The random generator returns equally distributed index values between 0 and len(slice)-1, inclusively – because the random value lands between   (inclusively) and len(ncells) (exclusively) – which is exactly what the doctor ordered to ensure selection of a random array element.

idx := rand.Intn(len(slice))
randElement := slice[idx]

What happens if the random generator does not output totally random values, but has a bias, as shown in Figure 4? The result is a boring maze that no human would ever tackle – but the computer does a good job anyway, of course.

Figure 4: A broken random number generator with a bias to only generate boring mazes.

To prevent the generator from generating the same maze every time, when the program is run again, main() needs to initialize it to a value that varies from call to call. Line 36 in Listing 1 therefore uses rand.Seed() to set the value to the current time in nanoseconds, which ensures distribution over a relatively wide range.

Journey Without a Destination?

The algorithm for generating the maze only receives the starting point and does not seem to need an endpoint; this is due to the fact that the procedure generates paths along which the explorer can reach all points of the maze. The procedure ensures that no compartmentalized sections are created. This guarantees that the solver later can reach any randomly defined endpoint.

The generator also avoids infinite loops, because it never turns onto paths that it has already taken. If you do want mazes with loops, you will find a wide range of different algorithms that are also easy enough to implement.