Gotta graph’em all: Pokémon and graph databases

Inspired by the Pokémon Go hype that’s been around these days, at Sparsity felt like sharing with you an application of graph technologies to catch’em all. We will show you how to use a graph database like Sparksee in conjunction with a document-oriented NoSQL database like MongoDB to find the best Pokémon for a battle depending on your opponent.

Remember that you can download Sparksee for free and use it in your own project.

Let’s start with a little Pokémon background, although odds are that if you are reading this, you won’t need it at all.

All Pokémon creatures and their moves are assigned to a certain type [1]. From generation 1 to 6, the latter being the most recent Pokémon generation in production, there are 18 of those types. Each type has strengths and weaknesses when facing other Pokémon in battle. These can be grouped into 5 different relationships that define how effective will a creature’s defence or attack be.

→ Receives 1/2 damage from opponent
→ Receives 2x damage from opponent
→ Inflicts 1/2 damage to opponent
→ Inflicts 2x damage to opponent
→ Inflicts no damage to opponent

As we are conceiving the graph as a whole, we should simplify the relationships as they are different sides of the same coin. To match the visualisation of the edge direction with the meaning of its label, we will use the “inflicts” relationship.

 

Strengths and weaknesses graph:

pokemon-graph

To create the graphical representation of the graph we used a table by Sheri-B.

We created two subgraphs to simplify its visualisation –one of them highlighting the positive relationship types (edges called inflictsx2) and the other one the negative relationship types (inflictshalf and nodamage edges).

 

Inflicts x2 subgraph:

pokemon-graph-2x

 

Inflicts 1/2 and No damage subgraph:

pokemon-graph-half-and-null

With the graph, finding the best type match for a Pokémon battle is as simple as a neighbours query. You could use a key-value or document nosql databse like MongoDB to store a list of all gen 6 Pokémon and its types [2]. This way we could find first the type of creature we are facing and then traverse the graph, for the type with the greater strengths against the opponent. Here’s how we would code it:

If T1 is your opponent’s Pokémon type


function Objects Catchemall (T1) {
//We are getting all types that inflict a X2 damage to T1
A = neighbors (T1, edge Inflictsx2, ingoing) ;
//We are getting all types to whom T1 does not inflict any damage at all
B = neighbors (T1, edge nodamage, outgoing);
AB = intersection (A,B);
if (AB != null) return AB;
else if (B != null) { return B; }
else {
    //We are getting all the types to whom T1 inflicts half damage
    C = neigbors (T1, edge Inflictshalf, outgoing);
    CA = intersection (C, A);
    if (CA != null) return CA;
    else if (A != null) { return A; }
    else return C;
}

*Call Catchemall for every type of your Pokémon rival (Pokémons can have more than 1 type)
* This is a pseudo-code check your language of preference at the Sparksee reference guide for the exact neighbors and interseaction operation signature.

 

Example: How to fight Pikachu

To better understand the process, let’s have a look to an example where the Pokémon we have to fight is Pikachu.

Step 1:

mongodb

Which type is Pikachu? Answer → Electric.

Step 2:

sparksee-logo

 Call the Sparksee Catchemall function with T1 == Electric.


Objects result = Catchemall (T1);

Answer → The function returns the Object type Ground because this type inflicts 2x damage to Electric and Electric attacks have no effect on Ground. Thus, this is the best option possible, our algorithm would stop at the first return.

Step 3:

mongodb

Which Pokémons are of type Ground?
Answer → list of Ground Pokémon. If you have one of them, Lucky! Chances are that you will be the winner.

pokemon-graph-electric-super-reduced

Graphical representation of the example.

 

Notes to the article:

 

[1] There are more variables to be taken into consideration in a battle, such as the level, the secondary type or the attacks your Pokémon learnt, but for simplicity we are considering only the type of Pokémon.

 

[2] Optionally you can represent Pokémons as a new type of node and add a belong edge to relate them to the type of Pokémon.

 


Download Sparksee 5.2

This entry was posted in News, Sparksee, Use Case and tagged , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *