Game::Collisions v0.1 – Fast 2D collision detection

Some years ago, I wrote a little top-down shooter in Perl. It was not a good game, and was never released, but I learned a lot making it. One problem I encountered was collision detection. Checking every object for collisions against every other object is not feasible past a small size. Especially in pure Perl, since this is a straight numeric problem, but it’s still a struggle for C to do it.

We have faster processors now, so the number of objects you can throw in there has increased a lot. Still, it’d be better to have a faster algorithm than brute force. The typical choice is to use a binary partition tree to split up Axis Aligned Bounding Boxes. This lets you do very fast collision detection even with gigantic lists of objects. I won’t go into detail here, as there’s an excellent blog post that already goes into it:

https://www.azurefromthetrenches.com/introductory-guide-to-aabb-tree-collision-detection/

Most likely, you would use this to quickly prune the list of possible collisions (“broad phase”), and then use more expensive techniques to get pixel-perfect (“narrow phase”).

This is what’s implemented in Game::Collisions v0.1. Here’s some benchmarks comparing the tree-based technique to brute force (running on a modest laptop CPU, an Intel i7-6500U):

This creates a tree of 1000 leaf objects and then gets all the collisions for a specific AABB. As the number of AABBs increases, we would expect brute force to go up linearly, but the tree method to go up logarithmically, so these numbers will get further apart as the tree grows.

“Programming the Raspberry Pi with Perl” is now released

The eBook was released on Monday, and coupon codes to backers were sent out on Tuesday. After a glitch with the first batch of coupons, the second batch was sent out and seems to be all good.

The book assumes you have some knowledge of Perl, but little knowledge of electronics or the Raspberry Pi. It goes through the tools you’ll need, walks through the basic setup of the RPi, and then gets into programming. Starting out with blinking an LED, it later gets into facial recognition and controlling a garage door over the web.

I had hoped that we were releasing on time, and completely forgot that we originally promised a date in August, not September. Oops. Well, a month late still isn’t bad for a crowdfunded project.

Expecting to get some of the coupon codes caught in spam filters. That’s just the nature of sending out a lot of emails that say “here’s your free coupon code!”. Spammers ruin the Internet. Backers, if you don’t see your code at this point, check your spam filter, and then message the campaign directly if you still don’t see it.

This is the first time I’ve done a crowdfunded campaign that worked out. It’s a modest start–not about to retire on that money–but it’s good to have a track record. I tend to be picky about projects I back, and an established track record from the campaign members is one of the things I look at. I expect a lot of other people do the same. I’ll likely have other projects in the future, and this is a good stepping stone.

Sous Vide and Thermocouples

A while back, I built a DIY sous vide cooker. It’s gone through a major revision since the original. My current one uses power outlets to connect the teacup heaters, rather than hard wiring them in. I’m in the midst of making another big change to it, which is to use an ESP8266 with custom programming, rather than an off the shelf PID controller, and also to use a different temperature probe.

Which brings me to this post. The original instructions used a k-type thermocouple, probably because it’s cheap and easily available. After some research, I think the accuracy range of the k-type thermocouple is unacceptable for sous vide.

The accuracy of a k-type thermocouple, for the temperature range we care about for sous vide, is ±2.2C. Now, the FDA recommends that food never be stored between 5C and 54.5C for more than four hours. That means if you’re cooking beef at a medium-rare temperature of 56.5C, a k-type thermocouple could be below the safe temperature.

It’s also worth mentioning that the k-type thermocouple’s temperature range is far beyond what we need for sous vide. We want something that will be accurate inside 50C and 100C. The tighter range of the t-type thermocouple is still more than we need, and its accuracy (for what we care about) would be ±1.0C.

We may be able to do better still. Resistance Temperature Detectors (RTD) probes are more accurate still. A probe with Class-A accuracy would be ±0.35 or less. It may also be cheaper, as you avoid the need for an amplifier chip, which you need with a thermocouple to convert its microvolts into something readable on normal electronics. RTDs just need something that can read resistance.

Which would be no problem on an Arduino with two ADC channels. You need the second one to read a resistor with a known value and then do some math to compare. Unfortunately, the ESP8266 (needed for some of the wireless features I want) only has one ADC channel. There’s some ways to fix that, but they involve some extra hardware. Might end up being a wash in terms of price and complexity. Still, I think it’s worth it for the extra accuracy.

Edit: doing it with a single ADC is possible with a voltage divider, which just needs a resistor with a known value. Cheap and easy.

Device::WebIO::RaspberryPi 0.900, now with AnyEvent and RPi::WiringPi backend

Device::WebIO::RaspberryPi 0.900 has been released. The big changes are to change the backend from HiPi to RPi::WiringPi, as well as put in a new input event system based on AnyEvent. There’s also some slight updates to interrupt handling in Device::WebIO in version 0.022 to support this.

It works by having a condvar with a subref. You can get the pin number and its value out of $cv->recv:

This is one part of a series of updates to support an upcoming Device::WebIO::MQTT. The original versions of the Device::WebIO family were meant to an HTTP interface (like the one in Device::WebIO::Dancer). Where HTTP pulls data, MQTT is push. The new AnyEvent system should integrate easily with AnyEvent::MQTT.

MQTT is also part of our stretch goals for the Raspberry Pi Perl eBook. Don’t worry though–I’ll be working on Device::WebIO::MQTT regardless of the funding level on the book.

Perl Raspberry Pi ebook sample chapter 1

The Perl Raspberry Pi ebook campaign is going great so far. As promised, here’s another sample chapter, where we cover the lineup of Raspberry Pi models, as well as some tools you’ll want/need.


Let’s Get Down to Basics

The Raspberry Pi has expanded into a range of devices, which may seem
overwhelming at first. There’s also the matter of which tools you’ll need once
you do end up requiring one.

Raspberry Pi Models

Model A and B(+)

The initial offerings were the Pi Model A and B in 2012. These were both
based on the Broadcom BCM2835 System on a Chip. The Model A had 256MB of
RAM for $25, while the Model B had 512MB for $35.

These models also standardized the layout for most future Pi’s, including the
location of the pin header and HDMI port. These models also include a composite
video connector.

In 2014, the A+ and B+ models were released, with prices reduced to $20 and
$25, respectively. They expanded the pin header, which has been used on other
Pi releases ever since. The separate composite video connector was also removed,
with its functionality still accessible through a 3.5mm connector. The A+ also
shrunk its form factor.

Compute Module

Released in 2014, the Compute Module was designed for industrial use. Instead of
external ports, it uses the same connector as DDR2 SODIMM RAM (but don’t try
plugging it into your laptop). These require a special development kit for
programming.

Zero and Zero W

The Raspberry Pi Foundation made headlines in 2015 when they included an
entire computer bundled with a magazine. The Pi Zero had an MSRP of $5, or
free if you bought the December issue of the MagPi magazine. It introduced a
smaller form factor that’s not much bigger than a stick of gum, and used the
same BCM2835 used in the original Model A and B. In 2017, the Pi Zero W was
released for $10 that included onboard WiFi and Bluetooth, just like the B3/B3+
(see below).

B2 and B3

In early 2015, the Pi B2 was introduced with a new BCM2836 SoC. This upgraded
the CPU from single to quad core, and from 700MHz to 900MHz. It also bumped the
memory to 1GB of RAM. This would be followed in 2016 by the B3, which has a
BMC2837, bringing the clockrate to 1.2GHz. It also gave you built-in
WiFi and Bluetooth, which means you no longer needed a separate dongle to
connect your Pi to the Internet.

Both the B2 and B3 had an MSRP of $35.

B3+

While we wait for the next big iteration, the B3+ was released. It pushed
the clockrate further to 1.4GHz, and now includes dual-band 802.11ac
WiFi. It’s also the first Pi to have gigabit Ethernet. Following tradition,
it’s priced at $35.

The Future?

The Raspberry Pi Foundation isn’t sitting still with the B3+ at the top of the
model lineup, and are hard at work on the next major revision. Hoped-for
improvements are support for USB3, a faster CPU, and breaking the 1GB RAM
limit. We’ll have to wait and see.

Which Model Should You Buy?

The hardware projects in this book can be easily done on any of the more
recent models–Zero (W), Pi2, or Pi3. The Compute Module requires an
extra development kit, which you will probably want to avoid until you have
a specific need and experience working with the more mainstream boards.

If you need to fit the project in a small space, run off of low power, or want
the cheapest option available, the Zero or Zero W are your best options. If
you want speed and don’t need to worry about power usage, the Pi3 is the best
option. If you find a Pi2 for cheap, that’s a perfectly good option, as well.

The Tools You Need

Power Supply

When the Raspberry Pi was first released, many people saw that it used a
micro USB power port, and tried to use their leftover cellphone chargers to
power it.

This did not work.

Cellphone chargers are meant for charging cellphone batteries. Under load,
their voltage may sag below the level needed to keep the Pi running. A
charger rated for 500mA may not be enough when you add a WiFi dongle, a
monitor, a keyboard, and a mouse. It might boot up, but you’ll likely run
into strange problems with no obvious fix due to undervoltage/undercurrent.

The CanaKit micro USB power adapter is the standard way to power the Pi.
It’s rated for 2500mA, which is plenty to run even the Pi3.

WiFi Dongle

Most of the Pi lineup doesn’t have built-in WiFi. If you buy the Pi3 or the
Zero W, you won’t need one. If you can use wired ethernet and have a Pi
with a wired port (not the A(+), Zero (W), or Compute Module), then you can
also skip a WiFi dongle.

Otherwise, there are a number of cheap USB dongles that will work with the Pi.
Edimax sells a small nub adapter. If you need more signal, the EDUP adapter
has an external antenna, and works well with the Pi.

SD Card

The main storage system on the Pi is an SD card (the Pi3 requires
a micro SD card). If you take a quick look at SD card speed classes,
you may be tempted to buy the first Class 10 or U3 card you can find.

Before you do that, note that the speed classes on SD cards refers to
the sequential writing speed. This is good if you were putting your
SD card in a camera, since streaming 60 frames of 4k video every second
takes a lot of sequential writing. Running an operating system off that
SD card does a lot of random access, not sequential. In practice,
you’ll often find that a quality Class 4 card works better than a cheap
Class 10.

Recently, the A1 and A2 performance classes were released. These specify
a minimum number of random IO operations per second, which is exactly
what we want for the Pi. These are worth looking into.

You should look at benchmarks to compare SD cards on the Pi. The Pi’s own
SD card access rate is admittedly limited, so you may see the Pi hit a
bottleneck before the SD card itself is maxed out.

As for size, at least 8GB will do. You can get away with 4GB, but you’ll
find yourself limited at that size.

USB Micro to USB A adapter, and hub (for the Zero and Zero W)

The Zero and Zero W have only one USB port for connecting external
devices, and it’s a micro port. To connect anything, you’ll need a
male micro to female USB A adapter. If you need to connect more than
one device, then you’ll also need a hub, preferably a powered one so
that you’re not drawing too much from the Pi itself.

Soldering Iron

When I was young, I bought a $15 Radio Shack stick soldering iron that
plugged directly into the wall. I was always frustrated at getting bad
solder joints that would never form into the nice little volcano-shaped
mounds you usually see on PCBs. I dreaded soldering pins that were close
together, because it was always a struggle to keep the solder from spilling
over and bridging the connections together. I thought I was bad at
soldering.

I eventually bought a nice soldering iron with a good temperature control
unit. Turned out, I was pretty good at soldering, I just had the wrong
tool from the start.

Where that old stick iron simply heated the element up with power right
from the socket, a temperature controlled iron measures the heat of the tip
and supplies power to keep it near a setting. They heat up much faster,
as well.

The one that I bought is the Kendal 937D, and I still use it as my main
iron. The Hakko FX-888D is one of the more popular models out there,
though I’m not a fan. It’s more expensive than the Kendal, and setting
the temperature is more cumbersome.

Solder

Be sure to get solder meant for electronics. Plumbing solder can damage
electronics components. Other than that, something around 0.8mm
thickness will do fine.

Solder Sucker and Wick

Even with a good iron, I sometimes make mistakes. The Solder Sucker uses a
plunger or a squeeze bottle to suck the molten solder away. The wick uses
capillary action to do the same. I tend to prefer the sucker method, but
this is personal opinion. Either option is cheap, so it doesn’t hurt to have
both around.

Solderless Breadboard

Not everything has to be soldered together. A solderless breadboard has
pins connected in rows, which is nice for prototyping before laying
everything down on a circuit board and making it permanent. Buy a
few different sizes.

Jumper Wires

These connect the Pi and other devices together using either the pin
headers or a solderless breadboard. You’ll need male-to-male,
male-to-female, and female-to-female connectors. These are often
available in a variety pack, in a flat strip where the individual
wires can be pulled apart, and often you find these wire variety
packs bundled with a breadboard (mentioned above).

Resistors, LEDs, Switches, and Capacitors

These four components are the bread and butter of electronics. You’ll want
a variety of all these. 100 Ohm resistors are especially needed, since
this is a good value for protecting LEDs from pulling too much current.
Other than that, assortment packs are readily available for all of these.

Breakout Boards

Modern electronics manufacturing has moved towards surface mount
components, which can’t be plugged into a breadboard directly. They need
a specific footprint on a PCB.

Fortunately, two of the major hobbyist electronics suppliers, Sparkfun
and Adafruit, sell breakout boards for many common components. These
are a small PCB with a pin header that can be plugged into a breadboard,
and from there into a Pi using jumper wires.

We’re going to be using the TMP102 temperature sensor chip in this book.
It’s available in a breakout board from both Sparkfun and Adafruit. The
chapter on GPS was tested using the Adafruit Ultimate GPS Breakout, though
any GPS unit that puts out NEMA over a serial connection should work.

Pi Camera

The chapter on taking pictures will be using the Pi camera. It uses a
special connector on the Pi, and is generally higher quality than any
USB webcam you could buy for the same price.

Perl Raspberry Pi ebook sample chapter: intro

With the campaign for the Perl Raspberry Pi ebook underway, we’re releasing a few sample chapters. First one for today is a short intro chapter. Tomorrow, we’ll be releasing one with more meat, covering the basics of the Raspberry Pi range and some other tools you might need to get started. For now, here’s the intro:


Introduction

Welcome! If you’re reading this, you’ve probably been using Perl for a while
and heard about the wonderful Raspberry Pi. If you haven’t programmed Perl
before, I suggest starting with Learning Perl by Randal L. Schwartz, brian d
foy, and Tom Phoenix. With that said, we try to keep the examples in this book
as simple and concise as possible, sticking to the most basic of expressions
wherever possible. Even without previous Perl experience, you
should be able to grasp the concepts we’ve presented within if you’ve done
any programming in other languages.

No previous electronics experience is necessary. We’ll be covering some of the
basics where appropriate. Most of the projects can be completed without any
soldering. In others, minimal soldering skills may be necessary. However,
being able to solder is a valuable skill to have if you are to grow further
in the field of electronics.

About the Raspberry Pi

In 2012, the Raspberry Pi Foundation was started by employees of Broadcom,
intending to use one of Broadcom’s inexpensive System on a Chip (SoC) fabs
to create a low-cost computer for education. Hobbyists quickly grabbed them
up and started hacking away. Today, the line has expanded to several models,
ranging from the $5 Pi Zero, to the $35 Pi3 (most recently, the Pi3B+).

About Perl

Perl was released by Larry Wall in 1987 inspired by a combination of several
other programming languages. A major revision to Perl 5 was done in 1994. Work
on Perl 6 began in 2000 as a completely separate language from Perl 5 (often
referred to as its “sister” language). Since then, work on Perl 5 has
continued. We’ll be using Perl 5 in this book. We recommend ensuring the most
recent version of Perl is installed before attempting the projects outlined in
this book, that version being 5.26 at the time of writing.

The language was important for the early web, being used in many of the first
CGIs, a simple way to write server applications. Since then, it has evolved
with the rest of the web and is still used by several large companies today.

It also continues as popular language for managing systems, and is installed
by default on the Raspberry Pi.

New Perl Raspberry Pi ebook campaign!

The Perl Raspberry Pi ebook campaign is now live! Steve Bertrand, the author of the excellent RPi::WiringPi module (among other RPi modules), has agreed to help.

The aim is to not just hand you a bunch of prebuilt modules that connect to temperature sensors and accelerometers and such. In CPAN tradition, there are quite a few modules already. But there will always be more, and it’s important that people know how to implement new hardware themselves. It’s admittedly not the easiest skill to learn (or to teach, for that matter), but I’m hoping we can get some new people hacking away, helping CPAN expand into whole new areas.

New Device::WebIO release

Device::WebIO was originally based on a Python project, WebIOPi. It duplicated the REST API (with some slight corrections), which means it was built around the pull-style system of HTTP.

I wanted to expand it to MQTT, which means doing more push-style. It’s not a difficult addition, but it does need to be able to track input pins using async interrupts.

So version 0.020 is released, with the Device::WebIO::Device::DigitalInputAnyEvent. This sets up the basics of putting an async loop together with the hardware portion. Next step is to integrate this into Device::WebIO::RaspberryPi, and then write Device::WebIO::MQTT to take advantage of all this.

What would you like to see from an ebook on programming the Raspberry Pi in Perl?

I guess the title says it all.

We’re well past the time when Perl should have an ebook about programming on the Raspberry Pi, so let’s fix that. I’d like to get a feel for what people will want to get out of this.

It will probably be based around Steve Bertrand’s series of RPi::* modules. We’ll expand from there into web projects (Device::WebIO::Dancer), capturing from the camera (GStreamer1), and interfacing with Arduino (Device::Firmata).

For i2c/SPI examples, we’ll show how to interface directly with some low-cost sensors. Tentatively, these will be an accelerometer for SPI (ADXL345) and a temperature sensor for i2c (MPL115A2). Both are available with breakout boards from Adafruit and Sparkfun.

Then there will be real project examples, such as a garage door opener and a temperature logger.

Here’s my chapter outline so far:

  • Introduction
  • RPi Models, Basic Setup, and Tools/Hardware You Need
  • GPIO [blink an LED, read from a switch, pullups/pulldowns]
  • SPI [ADXL345 accelerometer?]
  • i2c [MPL115A2 temperature sensor?]
  • Camera [GStreamer1]
  • Serial [GPS]
  • Expanding with Firmata
  • Interfacing from the Web [Device::WebIO]
  • PWM and Analog Input
  • Asynchronous code
  • Build Project: Garage Door Opener
  • Build Project: Temperature Logger

And there’s even a start on a cover:

ProgrammingThe Raspberry Pi