Note 12/29/2017: This article was written several years ago and is in draft form; it was never published due to concerns over IP protection. Since those concerns are no longer relevant and the topic no longer fresh in my mind, I’m publishing it as-is for archival purposes.
Recently I’ve been tasked here at The Tap Lab with investigating how to incorporate Apple’s iBeacon technology into our games. Our game Tiny Tycoons is a location-based empire builder involving real world shops and other businesses, so it seemed only natural that a protocol designed primarily to enable retail outlets to detect when their customers are in close proximity might yield some interesting gameplay options. While experimenting I found myself using bit shifting, a low-level operation most programmers are familiar with but rarely if ever use unless doing systems programming. It’s not a particularly difficult concept to grasp, but having never actually done it before I found myself revisiting some basic principles.
iBeacon is a protocol developed by Apple that defines a simple way for devices called “beacons” to broadcast their location and identity over Bluetooth Low-Energy (BLE). BLE has been included in most iOS devices for a couple of years now (as well as many non-Apple products), but only recently with the release of iOS 7 has Apple enabled iBeacon functionality. BLE is a version of Bluetooth that uses very little energy, allowing devices to broadcast/listen for signal for years on a single battery. The strength of the signal can be used to determine how close the beacon is to listening device, such as a smartphone, within more granular range than GPS (under 150ft).
The canonical use case is that retailers would place beacons throughout their store next to certain products. When customers running the store’s app on their phone come within a certain proximity of the beacon/product, the app would display information related to that product or special deals. Another popular example is museum exhibits.
BLE allows for all sorts of other communication between devices, but iBeacon is just a simple abstraction built on top of it. Beacons simply broadcast a UUID and a 16-bit major and 16-bit minor value, and applications listen for a particular UUID and interpret the major/minor values in whatever way they see fit. For example, the Museum in Science might have an app that listens for their particular UUID, with the major value representing which section the visitor is in and the minor which exhibit they are looking at. The museum’s app has a database mapping these values to information about the exhibits, or perhaps they make a call to a remote API that sends the information down. Beacons are placed throughout the museum and set to broadcast the museum’s UUID and the major/minor values corresponding to each particular exhibit. Visitors are encouraged to download the app to their phone at the front desk.
As you can see, the “official” use cases are quite narrow. We wanted to see how this technology could benefit mobile gaming. The most obvious way to integrate this functionality into Tiny Tycoons was to alert the user when they walked by a business that was (virtually) owned by someone within the game. We’d tell them who owned the property and how much it was worth, and encourage them to make an offer on it in-game. If they were physically visiting a place in real life, there’s a good chance they have some interest in the location. At the very least, it would be a great way to bridge the virtual and real world in a way we hoped would excite players.
We ran into a few problems with this. The first we were prepared for: iBeacon would only work for businesses that actually had beacons installed at their location, which at the time (and still is, as far as I know) just Apple Stores. Being a new technology, no one had rolled it out yet, though there was plenty of buzz and we were sure many chains were actively looking into it. Even Apple’s rollout was a bit shaky, as evidenced by our exploratory trip to the Apple Store. But that was fine; we would implement support for it in our game, generate some positive press, and as more businesses adopted iBeacon our integration would pay off more and more.
The problem we did not foresee was not aligning with Apple’s vision for iBeacon, particularly with regard to third-party apps. In order for our game to detect beacons, we would have to listen for one or more specific UUID’s. What should we listen for? We wanted a solution that we could get up and running with at least one business right away, but that was scalable to potentially all businesses once the technology took off. Ideally, adding a business would not even require an explicit partnership, but would happen automatically when said businesses rolled out beacons in their store. Unfortunately, Apple had not said much about how it intended the technology to be used outside of the aforementioned use cases, so choosing an approach that satisfied the above conditions proved difficult.
We thought about defining a Tiny Tycoons/Tap Lab UUID and listening for that, but that would require getting each business to set their beacons to broadcast our UUID. Even if beacon technology reached the point where it was possible to programmatically add unlimited UUIDs to a single beacon, it seemed unlikely we would be able to convince large companies like Best Buy or Starbucks to broadcast ours. Reaching the millions of small businesses across the world would be impossible. The best case scenario would be if eventually a centralized broker evolved (perhaps even Apple) that one could register their UUID with, and could then push said UUID through an API to the beacons of all member businesses. I doubt, however, that this was Apple’s intent, or if it is even possible or practical to broadcast that many different UUIDs on a single beacon. Regardless, such a service did not currently exist.
The second option would be to program our game to listen for a list of known UUIDs for certain businesses. The server could send down an updated list on each startup, and businesses could be added to the database as they adopted the iBeacon technology. Our research though seemed to indicate that Apple didn’t intend for these UUIDs to be publicly published and utilized by applications other than the first party. We also had severe doubts, again, about whether it was possible/practical for a single iOS device to listen for tens, hundreds, or even thousands of different UUIDs at the same time. It seemed unlikely that this was an approach Apple had in mind, and it was highly unlikely to scale.
The third option would be to petition Apple to define, or define ourselves, a universal UUID that businesses could broadcast that would allow third-party developers like us to build presence apps not tied to one particular business. If a business wanted to participate in the third-party iBeacon app ecosystem, they would simply broadcast the standardized UUID from their store and would instantly be recognizable by any past, present, or future app also listening for that UUID, games included. I still believe this is a pretty sweet idea, but I’m also skeptical this is part of Apple’s vision. Regardless, it is not immediately doable, and a small game company like ours does not have the clout to establish a global standard for retail technology.
In the end we went with the first option, but it was strictly for demonstration purposes; it required us to bring our own beacon into a business before it could be detected in game. But no long-term practical solution presented itself, and we were forced to move on. But we continued to look for ways to integrate iBeacon into our games.
Another important detail about Apple’s iBeacon tech is that any iOS device with BLE can itself act as a beacon, in addition to detecting them. Apple seems to have intended beacons to be static devices tied to a particular spatial region, and most commercial beacons so far appear to be simple, cheap custom pieces of hardware that can be discretely affixed to various surfaces. The ability of devices to also be beacons however enables all sorts interesting use cases that we perhaps unintended, as having a user’s device both broadcast and listen for other devices enables a sort of “who’s nearby” functionality for an app. The same thing could be accomplished with GPS, though with a bit less granularity and a lot less of the “neato” factor.
We decided to try implementing a feature that alerted players of Tiny Tycoons when other players were nearby, and brought up that nearby player’s (in-game) info in order to encourage friending, gifting, or bartering over properties. While the physical proximity mattered very little from a gameplay perspective–as all of these things could be done with someone half way around the world–the we thought the idea that there were other players nearby would excite our users, and might even lead to some (hopefully positive) real-world interaction.
Because this feature did not involve outside businesses, we didn’t have to worry about multiple UUIDs and could just use our own. On the surface, implementing the feature seemed trivial: we have each player’s phone both broadcast and listen for our UUID, and when detected we send a local notification that, when swiped, takes the player to the nearby player’s info screen in the game. Simple enough. The slightly tricky part is identifying the player who is nearby. Everyone is broadcasting the same UUID, how do we differentiate them once detected?
Going back to the museum example, each beacon is capable of broadcasting two 16-bit integers, known as the major and minor values. That is the extent of the communication allowed before you need to break out of the iBeacon protocol and start using full-on BLE. This is not a lot of information, but enough to store an ID number for a particular store department or museum exhibit that can then be looked up in a database containing more details information.
Like most games backed by a server, Tiny Tycoons stores players in a database table keyed by an integer ID column. Seems obvious that we would have each player’s device broadcast their player ID inside either the major or minor value, and then have other players’ devices make a call to the server with that ID to look up a nearby player’s info once detected. I’m sure you see where this is going. At the time of this writing, there are currently 400,000+ player rows in the database. A 16-bit unsigned integer (short) can store values ranging from 0 to 2^16=65,535. Oops. Neither the major not the minor value alone is big enough to hold an ID for a game with more than that many players.
However, the major and minor values together contain enough bits to hold values ranging from 0 to 2^32=4.3 billion. If we ever have more players than that, I’ll probably be too busy on my yacht to care about overflow. So there’s theoretically enough bits of information available in the iBeacon protocol to broadcast a player ID. But there’s still the minor problem that the major/minor values are treated as two 16-bit integers rather than one 32-bit integer. I needed to figure out a way to split a player ID into two shorts when broadcasting, then combining them back into an integer when picking up that broadcast on another device. This is where bit-shifting comes in.
Like many programmers, I had never actually used bit-shifting in any of my code. I was aware of it’s existence and had a general idea of what it did and what it was for. Every language I had ever learned about had the << and >> operators. I had used basic bitwise OR operations for setting flags in the Windows API, and I knew there existed a fast way to swap variables without using a temp via XOR operations that I might be asked during a tech interview some day. But being a practical person, I had never been presented with a problem that require bit shifting to get the job done. So I had to brush up a bit on my binary.
As a refresher, the number 6 stored in a 16-bit integer would look something like this: 00000000 00000110, with each digit starting from the right representing a power of 2. If you shift each digit to the left one (6 << 1), you get 12 (00000000 00001100). If you shift it the other way, you get 3 (6 >> 1). Any digits that fall off the end are lost, and any new digits introduced on the other side are set to 0 (there’s no “wrap-around”). So 6 >> 2 is 1 (00000000 00000001). That’s really all there is to it.
How does this apply to the problem at hand? Take a 32-bit player ID, say 127,721 (00000000 00000001 11110010 11101001). We need to somehow turn this into two 16-bit shorts in a reversible way. The most obvious solution is to chop the integer in half, and store the first two bytes (00000000 00000001 = 1) in the major value, and the last two bytes (11110010 11101001 = 62,185) in the minor. How do we do that though? This depends on your language, but one way available in Objective-C and most other languages is, of course, bit shifting!
Let’s start with the major value, the first two bytes. We essentially need to chop off the last two bytes and then replace the first two bytes with 0, so that we end up with the integer 00000000 00000000 00000000 00000001, which can be safely cast to a 16-bit short (if you try to cast something without 0’s in the first two bytes, you’re going to get weird results). What we’re essentially doing here is shifting the entire integer 16 places to the right, which has the effect of dropping the original right-most 2 bytes off the edge and padding the new left-most 2 bytes with 0’s as described above. So we are left with:
uint32_t playerId = … ; uint16_t major = playerId >> 16;
Simple! Now how about the major value? In this case, we just want to chop off the 2 left-most bytes, meaning we want to 0 them out and then cast to a 16 bit short as before. We know that a good way to get rid of bits is to shift them off the end of the integer, so we could start by shifting the player ID 16 bits to the left, which would give us 11110010 11101001 00000000 00000000. At this point the relevant bytes are in the wrong spot on the left, so we shift them back 16 places to the right. The original 2 left-most bytes are now replaced with 0’s, just like we wanted.
uint16_t minor = (playerId << 16) >> 16;
We are now left with two 16-bit values that can be broadcast over a beacon. The real question though is whether this process can be reversed by a device that detects said beacon. Given two 16 bit shorts, how can they be combined back into a 32 bit player ID? The answer, again, is bit shifting. Let’s start by extracting both values from the beacon into 32-bit unsigned integers.
uint32_t major = [[beacon major] intValue]; uint32_t minor = [[beacon minor] intValue]; // Major: 00000000 00000000 00000000 00000001 // Minor: 00000000 00000000 11110010 11101001
The cast to 32-bit pads each value with 2 bytes worth of 0’s on the left. You might have noticed that, if we shift the right-most two bytes of the major value back to their original position on the left (reversing our original operation), we can simply add the two values together to get our original 32-bit player ID:
// Major: 00000000 00000001 00000000 00000000 // Minor: 00000000 00000000 11110010 11101001 // + : 00000000 00000001 11110010 11101001 (127,721)
That’s exactly what we do:
uint32_t playerId32 = (major << 16) + minor; NSNumber *playerId = [NSNumber numberWithUnsignedInt:playerId32];
And there you have it. Many of you might be rolling your eyes thinking, “this is elementary stuff”. Indeed it is, and perhaps I’m just a bit slow, but I did have to dedicate a bit of time to working this all out, and I suspect I’m not the only one who isn’t regularly shifting bits around at their current coding gig. You may also have noticed that you can avoid doing any bit shifting at all, and instead just use division and multiplication (x << y = x * 2^y and x >> y = x / 2^y). This may be true, but to even arrive at that solution you need to understand what’s going on at the binary level. Plus you may (depending, I imagine, on the language implementation) open yourself up to some wrap-around issues that bit-shifting avoids.
As for the feature itself, the fact that this little exercise is necessary in the first place indicates that this is probably not what Apple had in mind for iBeacon. Given the limited bandwidth provided by two 16-bit integers, it seems clear the intent was for a small number of beacons to exist within any given domain. Even with this trick, a limit of 4.3 billion puts an absolute restriction on the features iBeacon can support (app developers can always resort, of course, to the underlying Bluetooth protocol). If you think 4.3 billion is sufficient, consider the fact that the very reason we are running out of IPv4 addresses and being forced to adopt IPv6 is that the traditional 32-bits of an IPv4 address only allows for 4.3 billion of them. And it’s just not enough for all the devices of our rapidly evolving world.
We will continue to experiment with iBeacon and see if it can unlock any interesting gameplay concepts. I’m very curious to see if it takes off as a technology standard and how it is used by other developers. Will they stick to the narrowly defined retail use cases, or will someone come up with a killer app that uses the technology in a way that Apple did not intend? Will Apple remain quiet about their plans for the technology, or will they step in and provide guidance/interference? Will a 3rd party app ecosystem evolve around iBeacon, and will Apple support it? All of these things remain to be seen, and I can’t wait to find out.