๐Ÿ–ผ๏ธ 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 ๐Ÿฏ.

Loading comments

netcell

Software engineer with 4+ years of work experience in designing and developing cross-platform games and apps on web technology.