Forty-Year-Old Arcade Game Reveals Secrets of Robot Path Planning

What’s to be gained from reverse engineering a four-decade-old video game? As it turns out, quite a lot, and as you’ll learn from [Norbert]’s recent talk at the ViennaJS meetup, it’s not just about bringing a classic back to life.

The game in question is Kee Game’s Sprint 2, a monochrome 2D car race that allowed two players to compete head to head. The glorious Harvest Gold and Burnt Orange color scheme just screams 1970s, and it might be hard to see why this game was once a popular quarter-eater. But it was quite engaging for the day, and [Norbert] was interested in reverse engineering it. That he did, using JavaScript to build a faithful browser-based emulation of the game. And he took it further, creating a 3D first-person version of the game.

Continue reading “Forty-Year-Old Arcade Game Reveals Secrets of Robot Path Planning”

Anti-Cogging Algorithm Brings Out the Best in your Hobby Brushless Motors

Cheap, brushless motors may be the workhorses behind our RC planes and quadcopters these days, but we’ve never seen them  in any application that requires low-speed precision. Why? Sadly, cheap brushless motors simply aren’t mechanically well-constructed enough to offer precise position control because they exhibit cogging torque, an unexpected motor characteristic that causes slight variations in the output torque that depend rotor position. Undaunted, [Matthew Piccoli] and the folks at UPenn’s ModLab have developed two approaches to compensate and minimize torque-ripple, essentially giving a cheap BLDC Motor comparable performance to it’s pricier cousins. What’s more, they’ve proven their algorithm works in hardware by building a doodling direct-drive robotic arm from brushless motors that can trace trajectories.

Cogging torque is a function of position. [Matthew’s] algorithm works by measuring the applied voltage (or current) needed to servo the rotor to each measurable encoder position in a full revolution. Cogging torque is directional, so this “motor fingerprint” needs to be taken in both directions. With these measured voltages (or currents) logged for all measurable positions, compensating for the cogging torque is just a matter of subtracting off that measured value at any given position while driving the motor. [Matthew] has graciously taken the trouble of detailing the subtleties in his paper (PDF), where he’s actually developed an additional acceleration-based method.

Hobby BLDC motors abound these days, and you might even have a few spares tucked away on the shelf. This algorithm, when applied on the motor controller electronics, can give us the chance to revisit those projects that mandate precise motor control with high torque–something we could only dream about if we could afford a few Maxon motors. If you’re new to BLDC Motor Control theory, check out a few projects of the past to get yourself up-and-running.

Continue reading “Anti-Cogging Algorithm Brings Out the Best in your Hobby Brushless Motors”

Sort Faster with FPGAs

Sorting. It’s a classic problem that’s been studied for decades, and it’s a great first step towards “thinking algorithmically.” Over the years, a handful of sorting algorithms have emerged, each characterizable by it’s asymptotic order, a measure of how much longer an algorithm takes as the problem size gets bigger. While all sorting algorithms take longer to complete the more elements that must be sorted, some are slower than others.

For a sorter like bubble sort, the time grows quadradically longer for a linear increase in the number of inputs; it’s of order O(N²).With a faster sorter like merge-sort, which is O(N*log(N)), the time required grows far less quickly as the problem size gets bigger. Since sorting is a bit old-hat among many folks here, and since O(N*log(N)) seems to be the generally-accepted baseline for top speed with a single core, I thought I’d pop the question: can we go faster?

In short — yes, we can! In fact, I’ll claim that we can sort in linear time, i.e a running time of O(N). There’s a catch, though: to achieve linear time, we’ll need to build some custom hardware to help us out. In this post, I’ll unfold the problem of sorting in parallel, and then I”ll take us through a linear-time solution that we can synthesize at home on an FPGA.

Need to cut to the chase? Check out the full solution implemented in SystemVerilog on GitHub. I’ve wrapped it inside an SPI communication layer so that we can play with it using an everyday microcontroller.

To understand how it works, join us as we embark on an adventure in designing algorithms for hardware. If you’re used to thinking of programming in a stepwise fashion for a CPU, it’s time to get out your thinking cap!

Continue reading “Sort Faster with FPGAs”

Electronic Glove Detects Sign Language

A team of Cornell students recently built a prototype electronic glove that can detect sign language and speak the characters out loud. The glove is designed to work with a variety of hand sizes, but currently only fits on the right hand.

The glove uses several different sensors to detect hand motion and position. Perhaps the most obvious are the flex sensors that cover each finger. These sensors can detect how each finger is bent by changing the resistance according to the degree of the bend. The glove also contains an MPU-6050 3-axis accelerometer and gyroscope. This sensor can detect the hand’s orientation as well as rotational movement.

While the more high-tech sensors are used to detect most characters, there are a few letters that are similar enough to trick the system. Specifically, they had trouble with the letters R, U, and V. To get around this, the students strategically placed copper tape in several locations on the fingers. When two pieces of tape come together, it closes a circuit and acts as a momentary switch.

The sensor data is collected by an ATmega1284p microcontroller and is then compiled into a packet. This packet gets sent to a PC which then does the heavy processing. The system uses a machine learning algorithm. The user can train the it by gesturing for each letter of the alphabet multiple times. The system will collect all of this data and store it into a data set that can then be used for detection.

This is a great project to take on. If you need more inspiration there’s a lot to be found, including another Cornell project that speaks the letters you sign, as well as this one which straps all needed parts to your forearm.
Continue reading “Electronic Glove Detects Sign Language”

Morse Decoder’s Lean and Sexy Search Algorithm

Often the Morse Code centered projects that we feature are to help you practice transmitting messages. This one takes a tack and builds an automatic decoder. We think [Nicola Cimmino’s] project is well worth featuring simply based on his explanation of the Digital Signal Processing used on the signal coming in from the microphone. Well done. But he’s really just getting warmed up.

What makes this really stand out is a brilliant algorithm that allows conversion from Morse to ASCII using a lookup table of only 64 bytes. This provides enough room for A-Z and 0-9 without chance of collision but could be expanded to allow for more characters. Below is a concise description of how the algorithm works but make sure you take the time to read [Nicola’s] project description in its entirety.

The algorithm can be decribed as follows. Have an index inside the lookup string inizialied to zero. Have an initial dash jump size of 64. At every received element (dot or dash) halve the initial dash jump and then increase by 1 the index inside the lookup string if a dot was received and by dash jump size if a dash was received. Repeat until a letter separator is reached, at that point the index inside the lookup string will point to the ASCII corresponding to the decoded morse.

Have you heard of this technique before? If so, tell us about it in the comments below. Before you jump all over this one, realize that Magic Morse uses a different technique.

Using Tetris Like MS Paint

Check out Samus looking boss in this pixelated image. Who would have thought of using Tetris as a canvas for these types of graphics? Coming up with the original idea of strategically clearing and leaving Tetris pieces to end up with what is shown above is hard enough. But how in the heck do you implement the algorithm that generated this programmatically?

First off, two thing should not be surprising about this. It wasn’t manually generated during normal gameplay. That would be beyond savant level. The other thing to note is that the order in which pieces occurred was not random, but strategically calculated by the algorithm. The challenge is not only to occupy and clear the correct pixels, but to make sure the correctly colored pieces remain.

You need to see the fast-motion video embedded after the break to fully appreciate the coding masterpiece at work. We’re not going to try to paraphrase how the algorithms functions, but get comfy with the link above which walks through all of the theory (in addition to supplying the code so you can try it yourself).

Continue reading “Using Tetris Like MS Paint”

Dithering in Processing

dithering-experiments

To be honest, we’ve heard of dithering but that’s the extent of our knowledge on the topic. After looking through [Windell’s] post about using Dithering in Processing we can now say we’ve got a base of knowledge on the topic.

Dithering is used to produce an image out of two colors that our eyes can put together into something meaningful. The history of the algorithms goes back to monochrome displays. But now the hobby electronics we work with for fun have comparable computing power and perhaps it’s time to rediscover these techniques. [Windell’s] project implements the Atkinson dithering algorithm in real-time on your webcam. He’s doing this in Processing, which should make it pretty easy to port for your own purposes.

So why might you want to use dithering in your own projects? Because if it can be used to make very cool milled artwork there must be other undiscovered uses lurking around your workshop.