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.

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.

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.

SQL::Functional Cookbook–Updates

Updates are easy, too.

UPDATE takes a table to update, followed by SET and WHERE. In SET, we’re using the op function, which is actually an alias for match. Calling it op is more readable here, since we’re not matching anything. Note that the data there is still handled as placeholders.

The WHERE part works just like it does in SELECT.

Callback Functions Between C and Perl

Everything you ever want to do with xs is documented somewhere in perlxs, perlguts, perlapi, perlxstypemap, and perlcall. Figuring out where it’s documented, and how it relates to everything else, is the hard part.

In my case, the part I wanted was in perlcall, in the section “Strategies for Storing Callback Context Information”. What I wanted to do was to glue together the callbacks for the Perl interface in Games::Chipmunk to the Chipmunk 2D physics library.

From Perl, we want to be able to say things like this:

The C version of cpBodySetVelocityUpdateFunc() does not know what a Perl sub is. It sees an SV, which happens to contain a bunch of things that the Perl interpreter can execute as a Perl sub. What we need to do is hand off a C function to the callback, and then use that to grab our SV and use call_sv() to call it.

If C supported closures, this would be easy. C does not support closures.

Some C libraries with callbacks have a parameter that will pass whatever data you give it directly into the callback later on. Chipmunk has this on a few functions, but not consistently.

One thing the Chipmunk libraries do give us is a pseduo-Object Oriented interface, where we pass the associated datastructure in as the first parameter on every function (Object Oriented languages move this parameter to the left of the function call). This gives us something we can grab on to for getting the SV we need that stores our Perl sub.

The “object” is a pointer, and pointers are just numbers. Numbers can be looked up in a hash. So we’ll make a bunch of global hashes, one for each set of callbacks, and use the address as the lookup key and the SV as the value.

The examples below use Perl’s context macros, which means those global hashes are still thread-safe. You can read about them in perlxs, under the section “Safely Storing Static Data in XS”. Their use won’t be detailed here.

Using cpBodySetVelocityUpdateFunc as an example, we start with the xs declaration:

We’re taking an SV* and assuming it holds a reference to the sub. We store it in the HV* bodyVelocityFuncs, which is initialized elsewhere. Using (char*)&body (C is a true bastion of type safety), we convert the address of the cpBody* into a char pointer, which the hash can use as a key. Lastly, we call the actual cpBodySetVelocityUpdateFunc() in the C library, and pass it our own C function as a callback.

That C function looks like this:

This goes at the top of your xs file, before any PACKAGE declarations, up with #include "EXTERN.h" and such. The perlxs doc doesn’t show this part in its examples very well, but you need to put the dTHX; call here to declare the context for a bunch of Perl macros that come later. Otherwise, you’ll get a bunch of cryptic compiler errors and spend a few hours scratching your head, until you finally come across the section in perlguts entitled “How multiple interpreters and concurrency are supported”. Like I said, everything is documented, you just won’t know where.

Going past the Perl macros, we get to hv_fetch(). This function should have gotten the same cpBody* as we got earlier, so we once again torture the type system and pretend it’s a pointer to a char array for the sake of a hash lookup key. The person who wrote this part of the interface was a two-star C programmer, so we better check that we actually got the SV we wanted by checking perl_func == (SV**) NULL.

Now we’ll need to grow the stack so we can push the subref’s arguments there. In this case, the callback received four arguments, and we want to pass all four to the subref. In this particular case, the last two arguments are easy. They’re double precision floats, which we can pass directly into a Perl SV that contains a number.

The first two are the tricky ones. They’re pointers to complex structs. In my typemap, I made cpBody* into a T_PTROBJ. This means it converts the ‘*’ into ‘Ptr’, collapses any whitespace, and uses the resulting name as the Perl class. You can make an SV contain a pointer to this C object and then carry it around in Perl. The cpVect* comes out the same way (since we take a pointer to the gravity struct).

Finally, we can call call_sv() to call the actual subref.

The good news is that Games::Chipmunk v0.3 has most of the callbacks implemented. There’s some in cpSpatialIndex that aren’t there because they don’t follow the same conventions. Still, this should be good enough to write real physics systems for games in Perl.

Welcome, EEWeb.com Readers

The Wumpus Cave is EEWeb.com‘s site of the day! Here’s a few links to old entries that y’all might be interested in:

Happy reading!