Linux scripters usually know about sed — the stream editor. It has a simple job: transform text as it whizzes from input to output. So if you wanted to solve a maze, this wouldn’t be the tool you’d think to use, right? Well, if you were [xsot], you’d disagree.
You build a maze using spaces for empty space and # for walls. There’s an S to mark the start position and an E to mark the end. Of course, the maze can also contain newlines. The sed script does an amazing job of solving the problem.
We can tell that [Jon Howell] is our kind of guy. After updating his vintage 1985 Hewlett-Packard plotter with WiFi and the ability to load SVG files, he obviously needed to find a bunch of stuff to run off with it. Gotta justify those hacks somehow. So he doubled down and decided support a hack with another hack by writing a maze generator to keep his plotter well fed. He was kind enough to unleash his creation on an unsuspecting Internet as an open source project, and now we all can benefit from a couple of reams worth of mazes.
The generator itself is written in Java, and should work on whatever operating system your box happens to be running thanks to the *nix and Windows wrapper scripts [Jon] provides. To create a basic maze, one simply needs to provide the script with the desired dimensions and the paper size. You can define the type of paper with either standard sizes (such as --paper a4) or in the case of a plotter with explicit dimensions (--paper 36x48in).
If you aren’t a big fan of right angles, there’s support for changing the internal geometry of the maze to use a hexagonal or triangle grid. You can even pass the program a black and white PNG “mask” which it will use as the boundaries for the maze itself, allowing for personalized puzzles of whatever shape catches your fancy. [Jon] even ran the Wrencher though his software, leading to the creation of a maze which we can neither confirm nor deny will be making an appearance on our Christmas cards this year.
It’s built around an 8-pin PIC16F18313 microcontroller, uses a joystick for input, and nine WS2812 LEDs to display the player and the surrounding maze walls. His inspiration was [David Johnson-Davies’] minimalist secret maze game built around the 8-pin ATTiny85. In that one, [David] cleverly used charlieplexing to get four pins to control four LEDs and four pushbuttons. [Vegipete’s] use of the WS2812 LEDs allowed him to control the LEDs with just one pin, and also get color while using three pins for the joystick and its button. He may use another pin in the future for sound and vibration.
He goes into some detail on the WS2812 protocol, how communication is done with the LEDs using just one pin and different pulse-lengths to represent 0 and 1. We’ll leave you to see his post for more depth but basically, he introduces a module on the PIC called the Configurable Logic Cell (CLC) which makes this easy and frees up processor cycles for the user’s code to do other things.
His source code is available on request but he does detail a neat software trick he uses for rotating the view. It may be confusing for some but as you move through the maze, your viewpoint rotates so that up is always the direction you’re facing. Luckily, the walls surrounding the user can be represented using 8-bits, four for east, west, north, and south, and four more for the corners. The maze is stored as a bitmap and from it, 8-bit values are extracted for the current position, each bit representing a wall around the position. To rotate the walls to match the user’s current orientation, the bits are simply shifted as needed. Then they’re shifted out to set each LED. Check it out in the video below.
It works very well despite the minimal interface and part count.
[David Johnson-Davies] created a minimal Secret Maze Game using a single ATTiny85 and a few common components. This simple game uses four buttons, four LEDs, and a small speaker. The player moves in the four cardinal directions using buttons, and the LEDs show walls and corridors. If an LED is lit, it means the path in that direction is blocked by a wall, and attempting to move in that direction will make a beep. When the player reaches the exit, a short victory tune chirps from the speaker.
Since the ATTiny85 has only five I/O lines, [David] had to get a bit clever to read four buttons, display output on four LEDs, and drive a little speaker. The solution was to dedicate one pin to the speaker and the other four to charlieplexing, which is a method of driving more LEDs than you have pins. It takes advantage of the fact that most microcontroller pins can easily switch state between output high, output low, or low-impedance high-impedance input.
As for the buttons, [David] charlieplexed them as well. Instead of putting an LED in a charlieplexed “cell”, the cell contains a diode and an SPST switch in series with the diode. To read the state of the switch, one I/O line is first driven low and the other I/O line is made an input with a pullup. A closed switch reads low on the input, and an open switch reads high. With charlieplexing, four pins is sufficient for up to twelve LEDs (or buttons) in any combination, which is more than enough for the Secret Maze.
What if we told you that you are likely to have more computers than you think? And we are not talking about things that are computers while not looking like one, like most modern cars or certain lightbulbs. We are talking about the powerful machines hiding in your desktop computer called ‘graphics card’. In the ordinary gaming rig graphics cards that are much more powerful than the machine they’re built into are a common occurrence. In his tutorial [Viktor Chlumský] demonstrates how to harness your GPU’s power to solve a maze.
Software that runs on a GPU is called a shader. In this example a shader is shown that finds the way through a maze. We also get to catch a glimpse at the limitations that make this field of software special: [Viktor]’s solution has to work with only four variables, because all information is stored in the red, green, blue and alpha channels of an image. The alpha channel represents the boundaries of the maze. Red and green channels are used to broadcast waves from the beginning and end points of the maze. Where these two waves meet is the shortest solution, a value which is captured through the blue channel.
Despite having tons of cores and large memory, programming shaders feels a lot like working on microcontrollers. See for yourself in the maze solving walk through below.
[Jason Carlson]’s favorite game as kid was 1983’s Treasure of Tarmin by Intellivision, a maze game that eventually came to be called Minotaur. As an adult there was only one thing he could do: remake it on a beautiful Arduino-based handheld.
[Jason] built the handheld out of a small-footprint Arduino Mega clone, a 1.8” LCD from Adafruit, a 5 V booster, a 1” speaker and vibe motor for haptic feedback. There are some nice touches, like the joystick with a custom Sugru top and a surprisingly elegant 2 x AA battery holder — harvested from a Yamaha guitar.
The maze maps are all the same as the original game, which [Jason] found online, but he stored the maps as bytes in an array to speed up the game—there was a flicker in the refresh already. However he added a progress map so players could see every area that was explored. In addition to Minotaur [Jason] also added remakes of Tetris, Simon and Snake, simpler games he wrote to test out the hardware.
Dr. Claude E. Shannon was born 100 years ago tomorrow. He contributed greatly to the fields of engineering, communications, and computer science but is not a well known figure, even to those in the field. However, his work touches us all many times each day. The network which delivered this article to your computer or smartphone was designed upon important theories developed by Dr. Shannon.
Shannon was born and raised in Michigan. He graduated from the University of Michigan with degrees in Mathematics and Electrical Engineering. He continued his graduate studies at Massachusetts Institute of Technology (MIT) where he obtained his MS and PhD. He worked for Bell Laboratories on fire-control systems and cryptography during World War II and in 1956 he returned to MIT as a professor.
Shannon’s first impactful contribution was his masters thesis which took the Boolean Algebra work of George Boole and applied it to switching circuits (then made up of relays). Before his work there was no formal basis for the analysis of switching systems, like telephone networks or elevator control systems. Shannon’s thesis developed the use of symbolic notation to represent networks and applied simplifying rules to optimize the system. These same rules later translated to vacuum tube and transistor logic aiding in the development of today’s computer systems. The thesis — A Symbolic Analysis of Relay and Switching Circuits — was completed in 1937 and subsequently published in 1938 in the Transactions of the American Institute of Electrical Engineers.
Shannon’s doctoral work continued in the same vein of applying mathematics someplace new, this time to genetics. Vannevar Bush, his advisor, commented, “It occurred to me that, just as a special algebra had worked well in his hands on the theory of relays, another special algebra might conceivably handle some of the aspects of Mendelian heredity”. Shannon’s work again is revolutionary, providing a mathematical basis for population genetics. Unfortunately, it was a step further than geneticists of time could take. His work languished, although interest increased over time.