Creating and solving mazes with Go

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.

Listing 4

Random Selection

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.

Buy this article as PDF

Express-Checkout as PDF
Price $2.95
(incl. VAT)

Buy Linux Magazine

SINGLE ISSUES
 
SUBSCRIPTIONS
 
TABLET & SMARTPHONE APPS
Get it on Google Play

US / Canada

Get it on Google Play

UK / Australia

Related content

  • Free Software Projects

    Python inventor Guido van Rossum is known to have a good sense of humor and probably had a good laugh when he heard about the Guido van Robot project. If you are learning how to program, or would like to teach others, this software gives you a light-hearted introduction.

  • Gifts for Gamers: Some End-of-Year Recommendations, Part 3

    In part 3 of our gamers recommandations we present more strategy games, puzzles, card games, language skill training and more. To be continued.

  • Top Coder

    Springtime is application time! Mike Schilli, who has experience with job application procedures at companies in Silicon Valley, digs up a question asked at the Google Engineering interview and explains a possible solution in Go.

  • Treasure Hunt

    A geolocation guessing game based on the popular Wordle evaluates a player's guesses based on the distance from and direction to the target location. Mike Schilli turns this concept into a desktop game in Go using the photos from his private collection.

  • Firefox Phone Apps

    Cooking up an app for the Firefox OS is in no way difficult. All you need is a good measure of HTML and a dash of CSS. A few drops of JavaScript will bring it all to life.

comments powered by Disqus
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters

Support Our Work

Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.

Learn More

News