Creating and solving mazes with Go
Programming Snapshot – Go Mazes
© Photo by Henri Lajarrige Lombard on Unsplash
Mazes fascinated even the ancient Greeks. Mike Schilli uses his Go programming skills to create a maze and then efficiently travel through it.
In Europe, mazes are said to have come into fashion during the 15th century, mostly on manorial estates where guests were politely invited to "lose themselves" in gardens segregated by high hedges. However, winding paths (some of which even lead you in circles), where you need to make it from a starting point to an endpoint, can also be drawn on paper or simulated on computers. Algorithms usually represent a maze's path system internally as a graph along the edges of which the virtual explorer traverses from one node to the next, discarding dead ends, breaking out of endless loops, and eventually arriving at the destination node.
Computational handling of mazes is divided into two tasks: creating mazes and traversing them as effectively as possible by using a solver. You wouldn't think it possible, but on Amazon you can actually find a book entitled Mazes for Programmers [1]. The Kindle version of this book is a total failure due to font problems, but the paper edition shows some useful methods for creating and solving mazes.
From Cell to Cell
A maze consists of a matrix of MxN cells. In Figure 1, red arrows show the directions in which a traveler advances from cell to cell. These options then define the walls that are drawn to separate a cell from its neighbors.
[...]
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
US / Canada
UK / Australia
Direct Download
Read full article as PDF:
Price $2.95
News
-
KDE Plasma 5.22 Released with Better Stability and Usability Across the Board
The KDE Plasma desktop development has kicked into high gear and the latest release reflects newfound popularity and drive behind the open-source environment.
-
Nvidia and Valve Collaborate to Bring DLSS to Linux
Both powerhouses in the gaming industry are trying to make the experience on Linux much improved, by way of DLSS.
-
Kali Linux 2021.2 Official Release Now Available
The latest iteration of security fan-favorite Kali Linux has been released with new tools, themes, and plenty of improvements.
-
Entroware Unleashes a Beast of a Linux Laptop
If you're looking for a portable workhorse, look no further than the Entroware Proteus laptop.
-
System76 Unveils its “Launch” Keyboard
The open-source darling, System76, is about to launch the Launch keyboard and you can pre-order yours now.
-
Armbian 21.05 Now Available
The Armbian developers have released the latest update to the Debian-based Linux distribution geared for ARM and embedded devices.
-
StarLabs has Released Another Linux Laptop
A new 14" Linux laptop has been released by the company that created the 11" Star Lite and can be purchased with your choice of Linux distribution.
-
Ubuntu 21.04 Adds Support for Active Directory and Other Major Changes
In a bid to help make Linux more viable for the business desktop, Canonical adds support for Active Directory and a few other notable changes.
-
GNOME 40 Available on openSUSE
The rolling release edition of openSUSE, Tumbleweed, now offers the latest version of the GNOME desktop.
-
Apple M1 Hardware Support to be Merged into Linux Kernel 5.13
Linux users will be able to install their favorite distribution on Apple’s M1-based hardware.