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.
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.
« Previous 1 2 3 Next »
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
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.
News
-
Canonical Bumps LTS Support to 12 years
If you're worried that your Ubuntu LTS release won't be supported long enough to last, Canonical has a surprise for you in the form of 12 years of security coverage.
-
Fedora 40 Beta Released Soon
With the official release of Fedora 40 coming in April, it's almost time to download the beta and see what's new.
-
New Pentesting Distribution to Compete with Kali Linux
SnoopGod is now available for your testing needs
-
Juno Computers Launches Another Linux Laptop
If you're looking for a powerhouse laptop that runs Ubuntu, the Juno Computers Neptune 17 v6 should be on your radar.
-
ZorinOS 17.1 Released, Includes Improved Windows App Support
If you need or desire to run Windows applications on Linux, there's one distribution intent on making that easier for you and its new release further improves that feature.
-
Linux Market Share Surpasses 4% for the First Time
Look out Windows and macOS, Linux is on the rise and has even topped ChromeOS to become the fourth most widely used OS around the globe.
-
KDE’s Plasma 6 Officially Available
KDE’s Plasma 6.0 "Megarelease" has happened, and it's brimming with new features, polish, and performance.
-
Latest Version of Tails Unleashed
Tails 6.0 is based on Debian 12 and includes GNOME 43.
-
KDE Announces New Slimbook V with Plenty of Power and KDE’s Plasma 6
If you're a fan of KDE Plasma, you'll be thrilled to hear they've announced a new Slimbook with an AMD CPU and the latest version of KDE Plasma desktop.
-
Monthly Sponsorship Includes Early Access to elementary OS 8
If you want to get a glimpse of what's in the pipeline for elementary OS 8, just set up a monthly sponsorship to help fund its continued existence.