๐ผ๏ธ 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 Scells.
- For each city, find a square with the size is a multiple of
After establishing a grid for each city, assign bonuses ๐ฐ to cells that contains famous places ๐ฏ.
Top comments (0)