Geolocation in Mobile Game

🖼️ Overview

The general problem is as follow:

Provides the game a context of player being inside a certain area in a set of predefined records, allowing the game to affect player’s process accordingly.

🗒️ Here, a location is understand as a set of two value (latitude, longitude) which refers to a position on the surface of the Earth.

🛒 What’s on the market?

🎮 Geolocation Games

🔴 🌐 Geocaching

Launched in 2000 and is still kicking well, the game allows players to go find real boxes 📦 hidden around the world. While being more of an outdoor game ⚽ than a video game 🎮 , this is probably one of the longest running geolocation mobile game ever.

🔴 🏙️ Ingress

Before the widely successful Pokemon Go 👎 , Niantic created Ingress with a futuristic theme 🚀 and so many more features: location capturing, structure building, PvP actions, etc.

🔴 📈 Landlord

Landlord allows player to buy venues 🏯 that they visits and earn rent 💵 as people check in 📍 at those location in real time.

🔴🕵️‍♀️ Revenge of the Gang

In this game, the players create gangs 👨‍👦‍👦 to fight each other for territories 🗺️ . The aim of the game is to try to conquer as many cells as possible on a grid map (see more at Grid section).

⚙️ Location as a Services

🔴 🏖️ Google Places API

This service is discussed below 👇 in Marker section.

🔴 🔪 Motive.io 🌟

A location backend with Vuforia AR integration for Unity.

The service provides quite a complete backend solution for location-based game 👍 development with places matching, user location tracking, narrative designs and quest management.

They also promote AR integration with Vuforia but I believe with ARKit and ARCore insight, the modern AR approach implementation is in due.

Sadly, Motive.io is currently still in closed beta.

🔴 ⛓️ Backendless.com 🌟

The geolocation feature of this service seems to cover most 👍 of the backend features you need. However, there are no 🚫 Backendless SDK for game engines right now (though about one year ago, it is said to be under development).

🔴 🗺️ Mapbox

🌟 Mapbox is a toolbox of geo-related tools. It even has mobile SDKs and Unity SDK for displaying maps. Mapbox analysis tool Turf.js allows complicated geo calculation and estimation.

🤖 Technical Patterns

🏁 Grid - Area-based method

Grid map is really popular in games. A grid split the map into multiple consecutive regions called cells with identical shapes (square or hexagon in most cases).

🌟 By using grid method in geolocation, the game can find out which cell player is currently in and affect the player’s process accordingly.

Considering the world map 🗺️ as a 2D plane , latitude and longitude are the coordinates, this problem is similar to checking if a point is within a polygon. ☝️ However, there are cases where the area overlaps where the map wrap around, but these cases can be solved with relatively simple algorithms.

📌 Markers - Distance-based method

🌟 In this method, given a database of locations, the game need to figure out which of those locations are within a certain radius around and nearest to player’s current location.

🔴 🏖️ Google Places API - The third-party way

🌟 With this method, the database doesn’t save the location but ID of the places available on Google Places API.

🌟 Google Places has a very good 🛢️ location database of real-life places. The nearby search-request API 🔎 allows searching places near player’s current location within a radius 👉 which is the problem we are looking into.

- Notice 1: It was possible to add places that doesn’t exist on Google Places. However, that API has been deprecated ⛔ since June 2017. Therefore, if we use Google Places API, our markers will be limited to what exists on Google Places only. On the bright side 🔅, its database is really huge so this may not be that big of a problem.

Notice 2 The Google Places API for iOS enforces a default ⚠️ limit of 1,000 requests per 24 hour period. However, it is possible to request an increase by following a simple review process.

With this method, the database structures and operations would be much simple , delicate the most notable features to the Google’s service. The game backend only needs to map places to desired behaviours.

🔴 ⚗️ Formulas for Spherical distance - The first-party way

There are three formulas for this including: Haversine formula, Spherical Law of Cosines and Equirectangular approximation. These are listed in the document that is referred by Google Maps 🗺️ team.

👉 According to the document:

• Spherical Law of Cosines - provided the 👍 best accuracy for small distances and the 👎 worst performance overall.
• Haversine formula - is the most popular in the past ⏳ since it avoids large round-off errors in computations in the era where computers 🖥️ did not exist or were very primitive.
• Equirectangular approximation - has the 👍 **best performance while provides the 👎 worst accuracy.

🌟 With the current technology, Spherical Law of Cosines became widely used for spherical distance calculation. The Google Maps 🗺️ documentation, regarding this matter, also gave the example SQL query based on Spherical Law of Cosines . 👍

🔴 🔬 Optimization

For whichever formula selected, the problem with these techniques is that the formula requires a lot of trigonometric operations, which are very CPU-intensive 🤖. It is important to ✂️ trim down the records to a small subset prior to use the formula.

🌟 A method for trimming process would be using a square with player’s location at center and only select locations in the database that lies within this square. The calculation, as mentioned in Grid section 👆, is relatively simple.

---

🚚 Distribution

There are 2 ways to distribute bonuses 💰 to real-life locations 📍 where players can visit:

• ✋ Manually: By creating location manually, we can establish partnerships 🤝 by putting special bonuses 💰 at partner’s location 📍 .
• 🤖 Automatically** : Even with partnerships, we still need to populate 🌧️ the map with many regular bonus places to keep players interests inside the geo-game-loop**.

📁 General Distribution

🌟 For seeding 🌱 , in the beginning, we would be distributing bonuses around famous places 🏯 in selective (or all) cities 🏙️ around the world (or in selected countries).

🌟 Using Text Search Requests in Google Places API, we can search for point of interest places (tourist attraction) by querying:

${cityName}+point+of+interest

    # Example requesting famous places in New York City
    https://maps.googleapis.com/maps/api/place/textsearch/json?query=new+york+city+point+of+interest

The response returns 20 places object along with a next_page_token string which can be used to fetch more places.

📌 Markers Distribution

Markers distribution pretty simple: For each famous, we only need to directly assign bonuses 💰 to its location 📍.

🏁 Grid Distribution

Note: I will only cover square grid only. Hexagon grid is more complicated and other than game visual requirement, there is actually no perk over square grid.

Note: Here I use the term subgrid which means a set of cells in the grid that forms a square.

First we decide the size S of a square grid cell S x S and put this grid over the world map 🗺️. There are two options:

• The grid cover the whole map 🗺️
  • For each city, we find the smallest subgrid that fully cover that city.
• A custom grid for each city 🏙️
  • For each city, find a square with the size is a multiple of S
  • Divide the square into a grid of S x S cells.

After establishing a grid for each city, assign bonuses 💰 to cells that contains famous places 🏯.