Thursday, January 17, 2013

Cheating in Angry Birds

Please allow me to indulge in shameless self-marketing for the entire duration of this post.

Many moons ago, I developed a small library that processes a screenshot from Angry Birds, a popular time-waster computer game, and detects several important parameters like the scale (amount of zoom) of the level, position of the slingshot, and the kind of bird that is currently loaded.  At the time, I had just started doing serious work with OpenCV, and took this as an opportunity to put my newly-acquired OpenCV skillz to the test.  It was a very challenging and interesting side-project.  I consider the fact that I completed it without ever playing a single game of Angry Birds an important lifetime achievement.

I'm happy to report that the library I developed is now part of a real iPad app in the iTunes Store.  Here's a short instructional video to demonstrate how the app works:

Impress friends and relatives!  If you've dreamed of achieving astronomical scores in Angry Birds, then this app is definitely for you!  Once the app processes the screenshot (courtesy of yours truly), you select a target, and the app automatically calculates the required trajectories for you using some in-game physics.  The app is also clever enough to handle each type of bird individually (e.g. the bird splitting in mid-air as shown in the video).  The end result is your ability to hit the targets you picked with deadly accuracy.

In other news, at the end of 2012, an Australian university hosted an artificial intelligence (AI) competition that pitted computers against human players in a game of Angry Birds.  The AI challengers had access to a computer vision component that performed a similar task to the library that I developed (and a lot more, since they also detected other in-game sprites) and an in-game physics component to calculate trajectories.  It seems that the goal for the challengers was to identify the targets that would maximize the score for the game, and utilize the provided computer vision and physics components to hit those targets.  I wasn't able to find the results of the competition anywhere, but a reliable source in Australia with access to local TV reports that the human players tended to win.

Sunday, January 6, 2013

Why Linux rocks

... or how to share your internet connection.

I'm out of town for a conference.  I brought my laptop and tablet PC with me.  Unfortunately, the hotel room doesn't have wireless -- it only has a LAN port.  How can I access the internet through my tablet?  Well, since the laptop has a functioning wireless card, it's not that difficult.  You need to run hostapd, a daemon that implements a wireless Access Point (AP) in software, and bridge-utils to bring the LAN and wireless interfaces.  On Ubuntu, these are available directly through apt-get.  From there, it's relatively straight forward:

  1. Configure the AP (edit /etc/hostapd/hostapd.conf to specify SSID, access keys, etc.)
  2. Configure the bridge (edit /etc/network/interfaces to specify the interfaces you want to bridge, the gateway and DNS servers)
  3. Restart networking services
  4. Connect to the created wireless AP and enjoy your bridged connection
For parts 1 and 2, I used the settings from the original post directly.  I had to change eth1 to eth0 since that's what the LAN interface is called on my system.  The IP addresses for the laptop, gateway and DNS server were also obviously different, but readily available through netstat -nr.  If you skip step 2, then you won't be get an IP address at step 4 unless DHCP is running on the laptop.  If step 2 is performed correctly, then whatever is performing DHCP on the remote side of the LAN connection will perform the IP address allocation and everything will work alright.

It's amazing what you can do just by editing a couple of configuration files.  Of course, it would be great if all this would all be done through a GUI.  There's already nm-applet, which seems to allow one to create an AP, but I couldn't get that going, so I gave up and headed for the command-line option.

Friday, January 4, 2013

This Week's Coding Practice: Linked Lists

Linked lists are elementary data structures that any programmer worth their salt should know back to front.  In contrast to the contiguous array, linked lists naturally grow or contract as the data stored in them increases or decreases, respectively.  Furthermore, the memory occupied by the data does not need to be allocated contiguously.  However, this flexibility comes at a price.  Accessing random elements in constant time is no longer possible -- with a linked list, accessing the nth element takes O(n) time.

There are many ways to skin a cat, and there are also many ways to implement linked lists.  Some important decisions to make along the way include determining the degree of abstraction; picking between singly and doubly-linked lists; and picking between sentinel nodes and sentinel values.  I'll discuss each decision briefly below.

At a high-level, a linked list can be defined recursively: a linked list is a node followed by a linked list.  You have at most two entities to worry about -- the Node, which contains the data you want to store and a pointer to the rest of the linked list, and the List itself.  Ideally, you want to model the list as a "black box" and abstract away the fact that it consists of a chain of Nodes.  This requires defining and implementing the List and Node explicitly as separate data types (as separate structs, for example).  Frameworks, like the C++ STL's vector or Python's list(), do this for you.  Home-brew implementations of the linked list often avoid defining an explicit data type for the list itself, and model the list implicitly as a chain of nodes (see how I implemented Bins in a hash table a few weeks ago).  This saves the developer the effort of having to define separate List and Node data types, at the expense of reduced abstraction.  If the particular linked list implementation is only used internally (as opposed to being part of a framework), then the loss of abstraction is not a big deal.

List linking comes in two flavors: single and double.  A node of singly-linked lists contains a pointer to the next node only.  A node of a doubly-linked list contains pointers to both the previous and the next nodes.  Singly-linked lists are the simplest and most flexible -- so flexible, in fact, that they can be "abused" by chaining lists together in a tree-like structure.  Again, this flexibility comes at a price.  Updating (inserting and removing elements) singly-linked lists can be a pain in the ass, since such operations require access to the node that is before the update location.  Since singly-linked lists can only be traversed in one direction (from the head to the tail), locating this previous node requires a full traversal from the head of the list -- which can cost O(n).  Doubly-linked lists allow the previous node to be determined directly, at the expense of increased storage overhead, due to the extra pointer in each node, and reduced flexibility -- abusing the list as a tree is no longer possible.

All good things come to an end, and linked lists are no exception (OK, with the exception of circular lists...).  Primarily, there are two ways of indicating the end of a list: sentinel values and sentinel nodes.  Sentinel values are special values like NULL that indicate that the previous or next node doesn't exist.  It's a simple idea, but requires additional conditional code to handle search and retrieval operations near the head and tail of the list.  Sentinel nodes simplify the code by removing such conditionals, at the expense of adding nodes that do not hold any real data.

How one goes about making the above-mentioned three decisions depends on the application -- what will you be using the linked list for?  This week, the tasks were to implement a simple singly-linked list and:
  1. Write a function to remove a list's 3rd from last element. Challenge: can you do it in a single list traversal?
  2. Write a function to remove all duplicates from a linked list. Challenge: can you do it without storing any extra data?
  3. Write a function to detect a loop in a linked list.
For the abstraction level, I decided to roll with abstracting away the Node and exposing only the top-level List.  This looks a bit awkward at first, since all the List is is just a pointer to the first Node.  However, it does simplify the representation of border cases, such as empty lists.  I also decided not to use sentinels this time, as they would be more trouble than they are worth in some cases.  Specifically, removing duplicates from a list without storing any extra data requires pre-sorting the list with an algorithm such as merge-sort.  If we're using sentinels, then the divide step of merge-sort would require us to create additional sentinel nodes, and the merge step would require us to delete those additional sentinel nodes.

Finally, here's the code for this week: