This is a screenshot from the Atari 5200 version of the classic game Berserk. But the write-up we’re featuring actually looks at the original coin-op version. The maze for each level was established on the fly using a seed number fed into a rudimentary algorithm . Here’s a close look at how the maze building code actually worked.
Recently we saw a talk by Pitfall creator [David Crane] as part of our Retrotechtacular series. That is a real gem of programming history, and one of our favorite take-aways was that the levels were not hardcoded, but built using a random number generator algorithm with a hardcoded seed (so that the game was the same each time you played it). This uses a similar method but with a somewhat random seed.
The maze building was reverse engineered by observing the game in a MAME emulator, and by digging through disassembled code. Each time the code is “cold started” the seed starts out at zero, but from there the room number is used as the next seed. This is fed through a very simple algorithm. It generates directions for the walls, which use s few bit-wise operations to add the pillars inside the rooms.
It’s a great thing to study if you’re writing games for your embedded projects. By generating the room programmatically you don’t use up as much program memory. Of course these days even simple hobby controllers have way more storage to work with than [Alan McNeil] had when he designed Berserk.
[Wardy] built himself a high quality entropy source with parts he had lying around. It’s based on the hourglass entropy project we saw in a links post earlier this month. Just like that project, he is bouncing a laser off of the falling sand and reading the result. But he brings a few innovations to the party, and has test results to back up his work.
The first change is an obvious one; motorize the hourglass so that you don’t need to flip it by hand. We thought this might mess with the laser alignment but the clip after the break proved us wrong. He changed up the sensor, using an LED connected to the base of an NPN transistor. The next change was to mount the light sensor at an angle to the laser rather than straight on. This picks up reflections of the laser and not the direct beam itself, resulting in a wider range of readings.
He used an Ethernet shield to get the system on the network. It’s pushing 420k random numbers per second and was tested with the DieHarder suite. It didn’t get a very high score, but it did pass the test.
Continue reading “Improved hourglass entropy”
[Lambgx02] got tired of his Android device getting bogged down and decided to dig down to the cause of the issue. His investigation led him to believe that entropy is causing the slowdown. He believes that his workaround reduces 90% of the lag on the average Android device.
So how is it possible that entropy is causing the problem? It seems there is a bottleneck when an app requests a random number from the Linux kernel running at the lowest level of the device. Android is set up to use /dev/random for all random number requests, but [Lambgx02] says that location has a very shallow pool of numbers available. When they run out the kernel has to reload with a new seed and this is blocking the app that requested the data from continuing.
His solution was to write his own app that seeds /dev/random once every second using a number from /dev/urandom. He mentions that this might cause a security vulnerability as seeding the random data in this way is not quite as random. There may also be issues with battery life, so make sure to monitor performance if you give it a try.
Most toolchains for embedded system include support for random number generation. But if you’ve read the manual you’ll know that this is really just pseudo random number generation (PRNG). When calling this function the same numbers will always return in the same order unless a different random number seed is supplied in advance. [Gardner] put together a simple and cheap solution for deriving better random number seeds. He reads a voltage from a 555 timer using the ADC on the microcontroller. At first glance it may not seem like a great source of randomness, but he performed some testing and the results look quite promising.
The project is aimed at Arduino-based circuits, but any chip with an ADC will work. The 555 timer is used as a free running oscillator. We know that this not be very stable when compared to even the worst of crystal oscillators, but that’s what makes it work so well as a random seed source. Add to this the low parts count and small size of the additional circuitry and you’ve got a winning combination. So keep this in mind when you need a random number but don’t necessarily need rock solid entropy.
[via Reddit and Freetronics]
Even though rand() may be a good enough random number generator for making a video game, the patterns of random bits it spits out may not be sufficient for applications requiring truly random data. [Giorgio] built his own random number generator, and after many statistical tests it ended up being random enough for a few very complex calculations.
Previously, we saw [Giorgio] generate random numbers with a Chua circuit, but for all the complexity of building an electronic strange attractor there’s actually a much simpler source of random data: a white noise generator.
[Giorgio]’s random number generator for this project is just a pair of resistors, with an op-amp buffer, amplifier, and current switch to turn analog data into a digital output of random 1s and 0s. [Giorgio] sampled this data by plugging the digital out into one of the GPIO pins of a Raspberry Pi and recording the data with s small script.
To verify his sequence of bits was actually random, [Giorgio] performed a few tests on the data, some more reliable in determining randomness than others.
Because every project needs a few awesome visualizations, [Giorgio] plotted each sequence of bits as either a black or white pixel in a bitmap. The resulting image certainly looks like television static, so there are no obvious problems with the data.
[Giorgio] also performed an interesting Monte Carlo simulation with his megabytes of random data: By plotting points on a plane (with a range from 0,0 to 1,1), [Giorgio] can approximate the value of π by testing if a point is inside a circle with a radius of 1. The best approximation of pi using 10,000 points of random data came out to be 3.1436
Of course [Giorgio] put his random data through a few proper statistical tests such as rngtest and dieharder, passing all the tests of randomness with flying colors. An interesting build that shows a small glimpse of how hard generating really random numbers actually is.
Your brain can’t generate random numbers, and computers can’t either. Most of the ‘random’ numbers we come across in our lives are actually pseudorandom numbers; random enough for their purpose, but ordered enough to throw statistical analyses for a loop. [Giorgio] thought generating random sequences would make for an excellent project, so he whipped up a random sequence generator out of a few Opamps, resistors, and a handful of caps.
[Giorgio] used a Chua Circuit – a circuit that models nonlinear equations – to create a chaotic system. When pairs of points from these systems of equations are plotted on a graph, a fabulous and chaotic ‘double scroll’ pattern (seen above) can be found. After taking oscilloscope probes to different points on his Chua circuit, [Giorgio] watched chaos magically appear on his ‘oscope screen.
The double scroll pattern isn’t exactly random, but since the Z signal of his circuit chaotically varies between positive and negative, the only thing needed to create a random sequence of 1s and 0s is sending the Z signal through a comparator.
After calibrating and sampling his circuit [Giorgio] captured thousands of samples at a rate of 5 samples per second. From a cursory glance, it looks like [Giorgio]’s circuit is at least as good as flipping a coin, but proper tests for randomness require many more samples.
A very, very cool piece of work that is much, much more elegant than getting random bits from a Geiger counter.
[Zach] sent in a project he’s been working on that brings hardware random number generators to common hardware you might have lying around. It’s called Whirlyfly and it turns an FPGA dev board into a hardware random number capable of outputting random bits over a USB connection at 3 Mbps.
Previously, the whirlygig ran on a custom CPLD that interfaced to a *nix box and provided high quality random numbers via /dev/hw_random. [Zach]’s efforts takes the core of the whirlygig and ports it to the very popular and inexpensive Papilio One FPGA dev board.
As for what [Zach] can do with his random number generator, it’s extremely easy to write a Monte Carlo experiment to approximate the value of π with a better accuracy than [Ptolemy] was able to muster 1900 years ago. There’s also the aspect of encryption, and – why you would do this we have no idea – making an uncompressable file is also possible.