Perl SDL GUI Layout Engine

As it turns out, SDLx::App only supports having one window at a time. It’s effectively a singleton. This was a problem for UAV::Pilot, because I wanted to draw the navigation output and video in seperate windows.

The fix I have now is to implement a simple layout engine, where you can specify if you want the widget to be placed at the top or bottom of the window. I didn’t want to add complications like left or right. That’s good enough for now; the video always goes on top, the nav on bottom. If you were watching the AR.Drones 720p video stream on a 720p monitor, it might be an issue, but I’m not going to worry about it for now.

Where it could be an issue is when UAV::Pilot starts implementing other types of UAVs. I’m contemplating a rover, which makes the current nav output of roll/pitch/yaw rather pointless. But it’ll still need the battery output, and maybe add throttle and steering.

That all leads into breaking the current nav output into individual widgets with a complicated layout engine, like the sort you might see in Gtk+ or KDE.

As far as I can tell, Perl has nothing like this for SDL. There’s SDLx::GUI and SDLx::Widget. Both of these are limited, and look like the respective authors have left them by the wayside. Which I totally understand. I left Gopher::Server like that.

I’m tempted to write my own, but that seems like a full project in itself. Intergrating with Gtk2 might work, but I’m not sure how well that will go with SDL. Even making Perl bindings for a C layout library seems like a full project.

For now, I can ignore the issue. Implementing just a rover won’t introduce too much redundancy.

Any takers on this one? :)

Underappreciated Perl Code — Test::More::subtest()

Consider a long test that you can break into logical subsections. You could make a flat output with the standard series of TAP ok messages, but Test::More gives a more sophisticated alternative:

use Test::More tests => 3;
 
pass("First test");
 
subtest 'An example subtest' => sub {
    plan tests => 2;
 
    pass("This is a subtest");
    pass("So is this");
};
 
pass("Third test");

This works into the TAP:

1..3
ok 1 - First test
    1..2
    ok 1 - This is a subtest
    ok 2 - So is this
ok 2 - An example subtest
ok 3 - Third test

Notice that the subtest has it’s own test count (“1..2“).

Now, what if we decide that we could speed up this test by fork()ing off and running in parallel, or by using some kind of event interface where we can’t predict what order the callbacks are going to run. This would make the TAP output of each process or event get mixed up with the others.

TAP is actually a defined protocol with lots of features that should see more use. One of the proposals for a new version of the protocol is Test Groups, which looks like this:

1..3
ok 1
1..2 2 a block
1..3 2.1 another block
ok 2.1.1
ok 2.1.2
ok 2.1.3
ok 2.1 # end of another block
ok 2.2
ok 2 # end of a block
1..3 3 a third block
ok 3.1
ok 3.2
not ok 3 # end of a third block, planned for 3 but only ran 2 tests

Which isn’t the prettiest solution, I’ll admit, but it does solve the interleaving problem. The parser can take the test numbers in any order and put them back together.

The other proposal along these lines is Test Blocks, which are similar to what Test::More::subtest() does:

TAP version 14
1..4
begin 1 Object creation
  1..2
  ok 1 Object created OK
  ok 2 Object isa Flunge::Twizzler
end 1 Object creation
ok 2 Clone OK
begin 3 Methods
  1..4
  ok 1 has twizzle method
  ok 2 has burnish method
  ok 3 has spangle method
  not ok 4 has frob method
end 3 Methods
ok 4 Resources released

But this doesn’t solve the interleaving problem.

I had mentioned these in a Lighting Talk at YAPC::NA 2012, and immediately got myself warnocked. So this is me standing up and asking to get this moving again :)

In Which I Rant About Monopoly

It happens to all of us. We’re sitting around the house with friends, when suddenly, one of the dimmer house guests says “Let’s play Monopoly!”

If things were just in the world, it would be legal to shoot them dead with malaria. Instead, everybody meekly decides that, yeah, Monopoly sounds good, let’s do it.

And you start setting up the board, and somebody insists on being the car, because reasons. And then somebody else gets the bright idea of putting a $100 in the middle. This person should be shot dead with rabies.

Yes, I know what you’re thinking. The $100 in the middle is for Free Parking. When you can find me an official rulebook that tells you to do that, I’ll take the rabies needle out of your arm.

There is no benefit from Free Parking. It’s just Free Parking. That’s it. This universal house rule should die, and Monopoly should die with it.

It’s not that it’s a terrible game, provided you can get people to stop using the house rules they grew up with. Everybody complains about how long Monopoly takes, but then they add these rules that makes it take longer. The logic is simple:

  1. In Monopoly, the last one standing wins
  2. This means people have to drop out of the game for it to end
  3. When you can get a big wad of cash on Free Parking or by some other unofficial house rule, it tends to keep people in the game who should have dropped out
  4. If people are staying in the game, it takes longer. QED.

You can have your money on Free Parking, or you can have a game that doesn’t take all night and into the next day to finish. You cannot have both.

The most genius thing in recent Monopoly variants is the electronic banker. This might seem like a cheap gimmick, but it isn’t to me. The reason is that without physical pieces of cash, there’s nothing to stuff into the center. If you wanted to follow the Free Parking house rule, you’d have to keep track of it separately, and people tend not to want to bother.

But still, don’t play Monopoly. Like I said, it’s not a terrible game, but there are million better ones.

UAV/FOSS — ArduPilot

ArduPilot is a FOSS autopilot based around Arduino. It has different firmware builds to support helicopters, multicopters, planes, cars, and boats.

Since I’ve been mostly focusing on multicopters, I’ll stick with that. A basic, fully assembled quadcopter kit will run you about $600. This does not include a telemetry module for controlling from a computer, or an RC radio for controlling manually. The US-band telemetry module will run another $85. A cheap 2.4GHz RC radio can go for $50-75, though if you’re serious, you’ll probably want to run at least $150-250. Then there’s the battery, which goes for about $70.

That also doesn’t come with on-board video, which is another $190, and uses a secondary radio on 5.8GHz. The standard OSD module sold on 3D Robotics does not have HD resolution.

If you’re looking for something to play around with, the AR.Drone will cost about a third the price.

I don’t mean to be all negative about the ArduPilot. Clearly, ArduPilot does something much more serious than the AR.Drone. This is a platform you can hack. Change out motors, platforms, hexcopters, octocopters, camera gimbals, everything. It’s also designed with a GPS module that can be used to instruct the UAV to fly to a spot and fly back.

ArduPilot has a documented control protocol. At least, I think that doc is still relevant. The wiki page there says they’ve moved, but I couldn’t find anything more up to date on the protocol description. In any case, I’d love to implement this in UAV::Pilot someday.

The impression I’ve been getting is that if you just want to mess around (nothing wrong with that), buy the AR.Drone. If you want to get serious, buy the ArduPilot. Somehow, though, I think there should be a platform that starts as cheap as the AR.Drone but lets you work your way up.

Underappreciated Perl Modules–Tree::Trie

Before the Perl community settled on the term “hashes”, many called them “associative arrays”. This was a common term for an array that looked up elements by a string among dynamic languages in the old days, such as Tcl.

Although the hash algorithm is the popular choice in modern times, it wasn’t always this way. Binary search trees were also popular, but have the disadvantage that they have a worst-case time of O(n), and an average time of O(log(n)) (where n is the number of elements). Hashes lookup keys in constant time; they stay the same speed no matter how many elements you have.

There’s a caveat to hashes though: they have large constant factors, so a binary search tree tends to be faster for a small number of elements. They also don’t come back in any obvious order unless you make them that way by alternative means.

Hashes also have a problem where the value a string hashes to may collide with another string’s hash. When that happens, the value is appended to the list. On lookup, we then have to walk that list. This means that while hashes are generally close to constant time, they actually have a worst-case time of O(n), just like binary search trees. Since hashes are used so much on Perl, it tends to be very careful about colliding hash values, but it’s still a weakness in the algorithm.

This is where the trie comes in (usually pronounced “try”). A trie will lookup keys in O(m) time, where m is the length of the lookup string. Note that hashes actually have this limitation, too. It takes at least O(m) time to hash the string so we can look it up.

Oh, and you can get back the keys in sorted order by doing a pre-order traversal.

Oh, and you can get back a list of keys that match a prefix with practically no additional overhead.

All else being equal, a trie will be on par or better than the speed of hashes. However, in Perl, not all is equal. Perl’s hash implementation is handled by the language internally at the C level. Any trie library you use will go through subroutine/method lookups, which will be substantially slower. If we were rewritting Perl from scratch, maybe you could argue for replacing hashes with tries. But if you were rewritting Perl from scratch, that’s probably pretty low on the list of changes.

But never mind that. Sorted returns and prefix matching are still pretty cool if you need that sort of thing.

Tree::Trie looks like a good place to start experimenting with tries. To get behavior equivalent to hashes, you need to use the methods marked *_data. The other methods only store keys without a value.

Some example code

my $trie = Tree::Trie->new;
$trie->add_data( foo => 1 );
$trie->add_data( bar => 2 );
$trie->add_data( qux => 3 );
$trie->add_data( quuux => 4 );

say $trie->lookup_data( 'bar' ); # Prints "2"

my @qu  = $trie->lookup( 'qu' );
# Prints:
# qux: 3
# quux: 4
say "$_: " . $trie->lookup_data( $_ ) for @qu;

$trie->delete_data( 'qu' ); # Deletes 'qux' AND 'quux'

That’s all I have to say on tries. If you have suggestions for future underappreciated Perl modules, feel free to leave a comment below.

Perl Modules: AnyEvent::ReadLine::Gnu

REPLs (Read-Eval–Print Loop) can be handy little things. In UAV::Pilot, the uav shell takes arbitrary Perl expressions and eval()‘s them.

Before integrating with AnyEvent, handling the prompt was done by Term::ReadLine::Gnu. When AnyEvent was integrated, I wanted the shell to use AnyEvent’s non-blocking I/O, so it was migrated to AnyEvent::ReadLine::Gnu.

This also handles command history. Hit the ‘Up’ arrow to get your previous command. No code is necessary; AnyEvent::ReadLine::Gnu does it for you.

ReadLine also has options for tab-completion. I would like to add this to the uav shell eventually.

Using the AnyEvent version is quite simple. You pass a callback that takes input. In the uav callback, we only run the code when it ends with a semicolon (ignoring trailing whitespace). If it doesn’t, we save it in a buffer and wait for more input.

Here’s how this is implemented in UAV::Pilot:

    my $readline; $readline = AnyEvent::ReadLine::Gnu->new(
        prompt => 'uav> ',
        on_line => sub {
            my ($line) = @_;
            add_cmd( $line );
            if( $line =~ /; \s* \z/x ) {
                my $cmd = full_cmd;
                $readline->hide;
                my $do_continue = run_cmd( $cmd, $repl );
                $readline->show;
 
                $cv->send( $do_continue ) unless $do_continue;
            }
        },
    );

The add_cmd() method adds the input to the buffer. If that did end with a semicolon, then we call full_cmd() to get back the text of the code. It also clears the buffer. run_cmd() then eval()‘s the code. If we’re meant to exit the program, it returns false, which we handle with the $cv->send.

The $readline->hide and $readline->show calls stop ReadLine from outputting the prompt when we might have other output going.

UAV Basics — Legality

IANAL. I don’t even play one on TV. None of this is legal advice, and it only covers US regulations.

That said, FAA regulations on UAVs are pretty simple. UAVs are basically model aircraft, and the rules are:

  • Below 400 feet
  • Away from populated areas and full sized aircraft
  • Not for commercial use

That last one is what’s giving everyone fits right now. As a private citizen, your options for flying UAVs commercially are limited. There is a process to get either an experimental aircraft certificate, or a wavier certificate. Experimental certificates are only granted for “R&D, market survey and crew training”, while waivers are usually only granted to government agencies. That includes local government agencies, so you could feasibly get a contract to survey land for a local town.

Some people have tried to skirt around things by taking aerial photographs on a hobbyist basis, but then claiming they charge a client for post-processing. I doubt the FAA or courts will agree with this reasoning; they’re really just hoping that they’re too small for the FAA to bother.

Short of government contracts, commercial use of UAVs is limited to selling them for now. The FAA is set to introduce new rules for commercial UAVs in 2015. Mark your calendars.

UAVs and FOSS — AR.Drone

This is the first in a series of articles about the state of FOSS software in terms of UAVs. We start with the place where I have the most experience, the Parrot AR.Drone.

On the client side, Parrot has released a complete SDK for controlling the AR.Drone. It includes support for the control protocol, the navigation protocol, and the video streams (which is handled by ffmpeg).

However, many people choose to make a clean implementation based on the SDK docs. This includes my own UAV::Pilot, and also NodeCopter, an implementation for Node.js. Both of these are under a BSD-style license. The parts of UAV::Pilot that interface to ffmpeg are LGPL.

Control is done over WiFi. It will create its own ad-hoc network by default. With some trickery, you can connect it to an open access point, though it doesn’t seem to support WPA authentication.

The on-board electronics for the AR.Drone has a Linux system with Busybox, which you can telnet into. This seems to be mostly useful for debugging the commands sent over the network, or configuring it to connect to an open access point. Hacking it to control external devices via USB seems like it should be possible, though I haven’t been able to find anybody who actually accomplished this. Just a lot of people talking about it. C’est la vie.

Version 2.0 of the AR.Drone includes front and bottom cameras, which can stream 720p video. They’re on par with cheap webcam quality.

As I’ve complained about before the AR.Drone’s SDK doc is rather poorly documented. The control protocol is mostly fine, but there are a lot of missing details about the nav data and video protocols. The information you need is spread out on the dev fourms, and it just shouldn’t be that way. I’m also dealing with the multiconfig options, which requires getting the ACK bit off the nav data stream, which seems all backwards to me even if it was well-documented. The config should have been handled over a TCP stream, especially when multiconfig was implemented.

It is relatively cheap, though, at $300. A basic ArduPilot setup will be around $700 if you include the telemetry module and a cheap 6-channel radio. That setup wouldn’t even have a camera.

All things said, I think the AR.Drone is a good way to get started considering what’s out there right now. But it could definitely be improved.

Underappreciated Perl Modules: File::HomeDir

Problem: your module needs to save a config file. Where should it go?

Obviously, the user’s homedir, but the exact conventions differ between platforms. On Unixy things, it’s usually a dot file. Windows has a more complex layout for User directories, which Microsoft seems to change with every new version.

Instead of guessing, ask File::HomeDir where it should go. UAV::Pilot needed this for the joystick config, so it does something like this:

use File::HomeDir;
use File::Spec;
my $dir = File::HomeDir->my_dist_config( 'UAV-Pilot', {
    create => 1,
});

my $file = File::Spec->catfile( $dir, 'sdl_joystick.yml' );

File::HomeDir also has functions for my_music, my_pictures, etc., and also for getting the homedir of another user. It should always Do the Right Thing on any platform you throw at it.