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
-
So Long Neofetch and Thanks for the Info
Today is a day that every Linux user who enjoys bragging about their system(s) will mourn, as Neofetch has come to an end.
-
Ubuntu 24.04 Comes with a “Flaw"
If you're thinking you might want to upgrade from your current Ubuntu release to the latest, there's something you might want to consider before doing so.
-
Canonical Releases Ubuntu 24.04
After a brief pause because of the XZ vulnerability, Ubuntu 24.04 is now available for install.
-
Linux Servers Targeted by Akira Ransomware
A group of bad actors who have already extorted $42 million have their sights set on the Linux platform.
-
TUXEDO Computers Unveils Linux Laptop Featuring AMD Ryzen CPU
This latest release is the first laptop to include the new CPU from Ryzen and Linux preinstalled.
-
XZ Gets the All-Clear
The back door xz vulnerability has been officially reverted for Fedora 40 and versions 38 and 39 were never affected.
-
Canonical Collaborates with Qualcomm on New Venture
This new joint effort is geared toward bringing Ubuntu and Ubuntu Core to Qualcomm-powered devices.
-
Kodi 21.0 Open-Source Entertainment Hub Released
After a year of development, the award-winning Kodi cross-platform, media center software is now available with many new additions and improvements.
-
Linux Usage Increases in Two Key Areas
If market share is your thing, you'll be happy to know that Linux is on the rise in two areas that, if they keep climbing, could have serious meaning for Linux's future.
-
Vulnerability Discovered in xz Libraries
An urgent alert for Fedora 40 has been posted and users should pay attention.