Posts Tagged ‘pacmanhattan’

Building a Real-Time Location-Based Urban Geofencing Game with Socket.io, Redis, Node.js and Sinatra Synchrony

How we planned, built and tested a truly real-time location-based game with Socket.io, Redis, Node.js, and what we learned along the way.

MapAttack Gameboard on an IPhone 4
Over the past few months, we spent the majority our free time building a real-time game as a test for our location platform, Geoloqi. We built the first prototype of the game at a hackathon over the course of two grueling days. It’s also where Aaron and I met Kyle Drake, who is now part of the Geoloqi team.

We called the game MapAttack! due to its map-based nature. Two teams compete to capture the most points on the gameboard. The gameboard, in this case, is the city streets of the neighborhood the players are in.

MapAttack is a game based on capturing and conquering geofences. For the uninitiated, a geofence is a virtual perimeter for a real-world geographic area. Geofencing is used with GPS tracking devices, notifying a control station when a person or vehicles enters or leaves an area. Traditionally, geofences have been used in heavy industry for tracking fleets of trucks and other moving objects over time.

Instead of tracking trucks, we set each geofence up with a point value that would give players points for entering geofences. The idea was that a virtual map would be set up on top of the real world, and players on red and blue teams would try to capture all of the geofence points in the game before the other team. To capture a point, the phone would have to detect when the player entered the fence, determine the point value of the fence, notify the player that he received the point, turn the geofence the color of the team, and then add the point to the player score and the overall team score.

MapAttack Test Game at the Portland Park Blocks

Why Build a Real-Time Geofencing Game?

The purpose of MapAttack was three-fold. First, we wanted to create a game that allowed people to physically interact with the real world instead of a computer console like a first person shooter or a real-time strategy game. Second, we were inspired by playing a real-life version of Pac-Man called Pacmanhattan, invented by graduate students at the Interactive Telecommunications Program at NYU in 2004. We played it at Portland’s WhereCamp conference in 2008, and we wanted to see if we could make a GPS version of the game, as Pacmanhattan relied entirely on phone calls and physical maps. Finally, we were building the Geoloqi platform at the time and needed a good demo of our streaming socket API.

An Iterative Approach

Taking a game from a static map to real-time, where all of the players could see each other moving on the phone and on the browser was an enormous challenge. In the beginning, the game was full of errors and bugs and required a lot of setup time.

When we tested the game with real players, the web browser tracking player movement was lagging behind the game 10-15 seconds depending on network speed. In addition, all of the players’ phones also had to poll to get updates, which means players would see a delay of 10-15 seconds even for their own position on the map. To make matters worse, some of the slower phones were basically choking on making that many network requests.

We knew that there was a better way to build the game, and that we could make it actually work in real-time. We knew that it wouldn’t be a 16 hour task, but one that was a pretty solid undertaking. We were up to the challenge and began working on it on evenings and weekends for the next few months.

Building a More Advanced PacManhattan

Kyle Drake and Aaron Parecki Working on an Early Iteration of MapAttack!Unlike a real-time GPS-based game played on smartphones, PacManhattan relied on players making phone calls to remote operators updating their location on a physical map and then relaying the newest game state back to them.

Our challenge was whether a game similar to PacManhattan could be run entirely automatically through GPS updates from the phones. When we began thinking about this idea, GPS wasn’t readily available in most smartphones. We had to wait almost 3 years for the technology to exist.

Testing the Game

Playing MapAttack! on the StreetWe tested the game with friends at conferences and around Portland along the way. Each time the experience was better, but it wasn’t good enough yet. Although we were making progress, we still didn’t have a real-time experience, and that was what we were aiming for.

When we brought the game down to Stanford University it was functional but still lagging behind. There was still a lot of work to be done.

This post is about the technical challenges we ran into during game development. While we had gained a lot of experience with location-based technologies from working on the Geoloqi app and platform for the last year, MapAttack! posed new challenges we had to overcome.

In early September 2011, we had our final test of the game and we finally achieved our goals of a truly real-time game. It took a lot to get there, and we’d like to share it with you.

Technical Challenges

Map Attack Loading Errors on iPhoneHere is an overview of the problems we had to focus on in order to build the game.

  • Handling the detection of users entering and leaving 200+ geofences concurrently.
  • Handling the volume of location-updates from all the phones in a given game (20 or more users per game).
  • The gameboard itself. We made our own in-house game editor that allowed us to quickly draw geofences on the map and assign them point values. Before we made the game editor, we had to hand code latitude and longitude markers into the database. It was extremely tedious and inefficient.
  • Changing the geofence state based on player movements.
  • Allowing each phone and web browser watching the game to be able to see the movements of players and the geofences changing color in real time. Every phone in the game sends its location to the server, which broadcasts that data to every other phone and browser watching the game.
  • Handling errors and differences in GPS technology on different smart phone models in order to ensure a fair gameplay experience. See below for a comparison of GPS data tracking on an iPhone 3GS vs. an iPhone 4.

Differences in GPS Hardware

GPS signals are known for reflecting off of tall buildings in urban settings. This causes inaccuracy and inconsistency in location data. It is less-pronounced in newer phones, but it greatly shows in older ones.

GPS Comparison in iPhone 3GS vs. 4
Users with 3GS iPhones would miss more points than players with iPhone 4s. Solving that problem required finding urban settings with buildings less than 5 stories high in which to draw the gameboard.

Pre-Streaming API

Before we finished the Geoloqi streaming API and before we started using Node.js and Socket.io, everything was based on polling for new updates. Phones reported their location at 5 second intervals and the browsers would update the game board in 5 second intervals.

Before the streaming API, every time we wanted to get location data from the phones to the server, the process consisted of opening a new connection, sending a bunch of redundant information headers in the request, and then closing the connection. This had to be done in the same way again and again, every five seconds for every phone for the entirety of the game. This resulted in a ton of redundant information and protocol overhead and resulted in a great drain on battery life of the phones as well.

In the worst case scenario, the browsers were lagging behind the game 10-15 seconds depending on network speed. What was worse was that the phones also had to poll to get updates, which means players would see a delay of 10-15 seconds even for their own position on the map. And some of the slower phones were basically choking on making that many network requests.

MapAttack Server and Phone Architecture Diagram

Enter Socket.io, Node.js, Redis, and Sinatra Synchrony

Socket.io

Socket IO: the cross-browser WebSocket for realtime appsSocket.io is a cross-browser web socket implementation allowing us to do real-time data updates on the browser and also supports older browsers. We can use the latest technology without requiring all of our users to update to the newest browsers, thanks to Socket.io falling back to older technologies in older browsers. This allow us to do instant updates across browsers and the phones in the game.

Node.js

Node JS Node.js is Evented I/O for V8 Google’s Javascript implementation for Chrome, implemented with a reactor pattern, that enables for large amounts of asynchronous data traffic.

We use a Node.js server to stream the location data from the phones to the Redis pub/sub channel. It publishes to Redis, and another Node server subscribes to that redis channel. Our Node.js server receives updates from the phones using a custom protocol similar to Google’s Protocol Buffers, which is essentially a very compact binary JSON.

When a browser wants to start streaming data, it connects to the Socket.io server and that server then subscribes to the Redis pub/sub channel. The Socket.io server sends that data via Websockets to the browser, falling back to Flash or long-polling if Websockets is not available.

In essence, Socket.io allows us to use Websockets, which are completely new, but also allows this to work on older browsers thanks to the fallback tricks.

Redis

Redis: an open source, advanced key-value store. Redis is an open source, advanced key-value store that has support for message queues using something called publish/subscribe, or pub/sub (not to be confused with PubSubHubbub).

From the higher level what this lets us do is handle the difficulty of sending data to all of the phones in the game and the browser in real-time. Every phone in the game sends its location to the server, which broadcasts that data to every other phone and browser watching the game.

One of the interesting things about the publish/subscribe system is that with a traditional system you have to maintain connections and iterate through each in order to pass data through them. The alternative would be that if you had 10,000 users you’d have to iterate through an array of 10,000 connections, which would be very slow and prone to locking up on socket problems.

Pubsub Action

Using Redis pub/sub is like starting a radio station. Once it is turned on, people (in this case, browsers) can just listen in. This allows us to do real-time data updates to clients (browsers and phones) at a massive scale.

Sinatra Synchrony

Sinatra Synchrony for Ruby by Kyle DrakeSinatra::Synchrony is a small extension for Sinatra that dramatically improves the concurrency of Sinatra web applications. Powered by EventMachine and EM-Synchrony, it increases the number of clients your application can serve per process when you have a lot of traffic and slow IO calls (like HTTP calls to external APIs). Because it uses Fibers internally to handle blocking IO, no callback gymnastics are required! This means we can just develop as if we were writing a normal Sinatra web application.

Sinatra::Synchrony allows us to do asynchronous programming (ala Node.js), except that it wraps the callbacks in Fibers (which are basically co-routines in Ruby). This allows you to do synchronous programming while taking advantage of asynchronous code. Aside from being easier to program this way, it also allows us to switch to a different concurrency/parallelism strategy if we need to. Kyle Drake developed Sinatra Synchrony specifically for MapAttack. Drake’s work became popular after he made a presentation on Sinatra::Synchrony at PDX Ruby.

The MapAttack Game Server

Finally, there is the MapAttack Game Server. In this case the Game Server is a simple database that takes care of storing the player point data that is displayed on the map and on the phones as players grab points in real-time.

International Testing

MapAttack! International Game Test in Sweden
We felt good enough about the game last week to take it on its first international test in Sweden. It passed with flying colors, although there were issues with not having enough time during the coffee break to finish the game.

Augmented Event and MapAttack in Sweden
Thanks to Michaela of Augmented Event Sweden who helped us run the game remotely, and Sony Ericsson who donated 10 Android phones for players to use for the game. We learned that the game runs better as part of a conference session or longer break time session. While the technology is solid, we’re still learning about the human element of the game. It takes about 10 minutes to download and get into groups before heading out the door to grab points at the same time. The game isn’t as fun when there’s only 20 minutes available to both set up and play it!

What We Learned

We learned that, while difficult, it is completely possible to create a truly real-time gaming experience with geofences and location-based technology. We didn’t know if it was possible when we started, and didn’t think too much as to how difficult it might be.
MapAttack Game at Stanford University
The whole thing was a very iterative process fueled by feedback and help and struggles, but also this lingering feeling that we were doing something that was important in some way. We keep going because playing the game felt awesome and exciting. It felt almost like being a kid again. We knew that as long as we had fun playing the game, we knew we were moving in the right direction.

Source Code

We made the source code for MapAttack available for download. You can download or fork the source code for MapAttack here. If you build anything interesting with it, please let us know!

Upcoming Games

We’ll be bringing MapAttack! to WhereCamp Portland on October 7-9, 2011. We’ll give an overview of the technology there as well. If you plan to be in the area, please join us!

Host Your Own Game

Get in touch if you’d like to host your own game. We’re working on making the game freely accessible to more than just us, and if you’re interested it will likely motivate us to work on that aspect of the technology.

Feedback

Have you tried to make your own real-time location-based game? If so, how did it go? What did you struggle with? What did you learn? I’d love to hear your thoughts. We have a great respect for game makers, as what looks like something very simple is often very difficult and invisible under the surface.

Cheers, and thanks for reading! You can follow @geoloqi on Twitter, or contact us at @playmapattack or http://mapattack.org if you’d like to schedule a game!