Introduction: Graph Algorithms
A lot of problems in real life are modeled as graphs, and we need to be able to represent those graphs in our code. In this (short) tutorial, we're going to go over graphs, representing those graphs as adjacency lists/matrices, and then we'll look at using Breadth First Search (BFS) and Depth First Search (DFS) to traverse a graph. We'll be writing our code in C++, although the concepts can be extended to any programming language.
This tutorial is supposed to focus on the code, so the drawings are going to be ugly, and the definitions are going to be quick reminders instead of in-depth explanations.
To put it simply, graphs are a set of edges that connect some vertices. To say it "less mathy", there are some points, and some lines that connect those points.
In the graph above, we have four vertices (4, 1, 2, 5) that are connected by some edges. In this case, the edges are bidirectional, meaning 1 is connected to 4 and 4 is connected to 1. Some graphs have directed edges, meaning travel is only allowed in one direction.
Now someone at node 4 can get to node 1, but node 1 can't directly travel to node 4.
Finally, sometimes edges have weights on them.
A reason edges would have weights are to represent distances, as an example. For instance, one road could be 10 miles long, and another is 13.
So how do we represent these graphs in our code? We create what are called adjacency matrices and adjacency lists.
An adjacency matrix is basically a table/spreadsheet, where each row and column represent a vertex. If the vertex 1 and vertex 4 are connected, then cell (1, 4) is a 1. If they aren't connected, then the cell is a 0.
If there's a certain edge weight, then you can represent that edge weight instead of 1 in the cell.
Adjacency matrices take up O(N^2) space. To find if a connection between two vertices exist takes O(1) time, since it's a quick lookup in the table. To add a vertex takes O(N) time, since you need to add a whole row for the new vertex (which also means initialization of the graph takes O(N^2) time).
An adjacency list is another way to represent the edges of a graph. You create a list/array/vector that represents each vertex, and inside of each index for that vertex exists another list/vector/array for all of the vertices that the owner is connected too.
An adjacency list takes up less space than an adjacency list. The actual space it takes up varies based on the graph, but in the worse case, it could take up O(N^2) space if all vertices are connected to each other, which makes it MUCH worse than an adjacency matrix.
To look up a connection takes up O(N) time, as you have to search through a vertex's friend list to see if the friend exists. To add a new vertex is simple, though, and takes O(1) time, since you're just adding it to the end of a list.
Traversing The Graph
So we can represent graphs in our code. (Well, you'll see the coding representations soon.) But how do we traverse through a graph? Specifically, if we're at vertex 1, can we get to vertex 3? What path do we take?
To traverse through a graph, we use BFS and DFS. For the sake of our examples, we're going to traverse through the following graph:
Breadth First Search (BFS)
BFS is a technique for traversing through a graph where we start at a certain vertex, visit all of that vertex's neighbors, then visit the neighbor's neighbors, then visit the neighbor's neighbor's neighbors, etc. (In that order.)
Read through the comments to see what's going on.
Depth First Search (DFS)
Similar to BFS, DFS is a way to traverse a graph. However, instead of using a visiting all of a vertices neighbors before visiting the neighbor's neighbors, DFS just keeps visiting each new node it sees, meaning that it will usually go down a long path, and then come back to visit what it missed. As opposed to a queue, DFS works using recursion.
Read the comments to see how it works.
We went over Graphs, Adjacency Lists, Adjacency Matrices, BFS, and DFS. These data structures and traversal techniques are vital to using graphs.
The next step is to learn about calculating the shortest paths in graphs. See the next blog post to do this.
Then, take a look at maximum flow in this blog post..
Introduction - Debugging?
Debugging is necessary for any program of any size. It's inevitable that our code will return incorrect results, and we'll want to know what values are along the way to see where things are going wrong. For Linux, "gdb" (GNU Debugger) is one tool used for debugging C and C++ code. It can be used for larger programs, but we're going to keep things simple in this tutorial by showing how to use gdp with basic commands, for a simple program.
We'll assume that you're running Ubuntu 16.04 for this gdb installation, but the requirements are very basic. (We'll also assume that you have GCC installed to compile our C++ programs.
Run the following command in your terminal to install gdb and necessary dependencies:
And that's it.
A Basic C++ Program (With Some Bugs)
We're going to create a basic C++ program, and it's going to have a few bugs. We'll need to go through the code (with a debugger) to see why we aren't getting the expected result.
First of all, in your project directory, use the the following commands to create a makefile and our cpp file.
Open "makefile" and add the following code to it:
(If you don't know about makefiles, look at this quick tutorial.)
Notice the extra -g flag for our compile command. This will tell the compiler to leave our code intact in the executable for debugging.
Our C++ program will ask the user for a number, and will calculate the factorial of that number.
Open "main.cpp" and add the following code to it.
Our code is complete.
In your terminal, run "make" to test the code out.
Obviously, the answer our program outputs is wrong. Why is it wrong? Well, we could inspect the code to find out, but we could also use gdb to see what's happening in our code.
Using gdb to Debug The Program
We're going to use gdb to debug our program. Let's go through the commands that we need.
First of all, start gdb. (This still start a gdb shell session.)
Next, we're going to tell gdb that our executable file (named "run") is the one we want to debug.
Now we're going to set a breakpoint at main. (A breakpoint is basically where we tell our code "stop here so we can look at it".)
Next, we start the program (executable) to see what's going on in the code.
We're going to say "next" (or "n") to go through the code line by line (as it's executed, not necessarily as it's written. For example, for loops will be called a lot).
At any time, to see the value of a variable, you can use "p variablename".
This whole process will look something like this.
To quit out of the gdb shell sessions.
And that's it. Use gdb to find out what's going on in your code.
In this tutorial, we had a simple C++ program, with a few bugs. To find out what was going on in our code, we used gdb to go through the code line by line to see what the values of variables were and how the code was executing.
We did a basic tutorial, but gdb can be used for much larger examples. To proceed further, familiarize yourself with all of the gdb commands, and use them as you need to for your own program.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
To watch the youtube video corresponding to this article, please click here.
Multiplayer games often have to store tons of information about the game and their players, such as details about characters and weapon stats in the game, as well as the levels, experience, and money for each player, among many other things. Some of the companies that own these games are nice enough to provide access to their databases, so that fan websites and tools can be created by independent developers and players to further enhance the game and create useful resources.
Hi-Rez Studios, the company that make the games Smite and Paladins, offers such a service: The Smite/Paladins API. Any developer that requests credentials and gets approved gets access to some documentation about the API, a valid API key, and an invite to a secret chat group with other developers.
In this blog post, we'll look at what the API offers, we'll see how to use the API, and we'll take a look at some examples websites that are made using the API.
What Does The API Do?
Basically, Hi-Rez has a database with a bunch of information for their in-game numbers, as well as player information. The API lets us access that information via certain endpoints.
For example, one endpoint that we're given access to is the following:
As the description states, if we supply a player's name to the endpoint, then Hi-Rez's servers will search their database for the match history of that player, format it, and send it back to us.
And the API has endpoints for a bunch of other stuff, not just match history. Of course, it's up to us, as the developers to make the best use of the API and be as creative as possible.
But what about all that other stuff? Response format? Signature? How do we actually use this "endpoint" to get a player's match history? Well...you have to write some code.
Using The API (Low-Level Details)
The Paladins/Smite API works exactly as any other API does: it's a simple GET request to a special URL, that would even work in your browser if you entered it there. For a PC Paladins player, the URL for /getmatchhistory would look something like this:
It's the same as before, but we added a base url in front the endpoint. So what's the deal with the other stuff?
ResponseFormat - JSON or XML.
developerId - It was given to us when we got accepted. Every developer has one.
Timestamp - The time the request was made.
Player - The name of the player that we're stalking.
"Signature" and "session" are a bit tricky...Hi-Rez certainly didn't make this noob friendly.
A signature is when you add the following together:
developerId + method name ("getmatchhistory" in this case) + authenticationKey (given to us when we were accepted) + timestamp
And then you hash that with an MD5 algorithm. Sounds hard? Lol, yeah it is.
Sessions are created with a special endpoint called /createsession. Basically, you open a connection with Hi-Rez's servers for 15 minutes by getting a special authentication token to be able to use other endpoints.
So at least once every 15 minutes, you have to call this endpoint to get a session id variable, which you then use to be able to access the other endpoints.
Using The API (High-Level Details) + Example Code
"Okay, so we know how to use the API, but how to we actually use it??? Give an example!"
Using the API requires a programming language. You can use whatever language you want, but to be honest, NodeJS is the easiest. (WAYYYY easier than C# and Java.)
Conveniently, one of the other developers wrote a NodeJS Wrapper for using some of the endpoints, which you can see here. We're going to be using it. (I'm going to assume you have NodeJS installed. If not, check out the beginning of this blog post.)
On your computer in a folder you want to work in, initiate a node project, and create a file named "config.js" and a file named "index.js" with the following commands in your terminal:
Next, we'll install the Paladins wrapper library to our project.
Open "config.js" and add the following code:
Of course, enter your own credentials with the devId and authKey that you were given.
Next, open "index.js" and add the following code:
To be honest, this code is sort of bad and I wouldn't actually write my code like this, but it's just a simple example...
The code uses the wrapper to create a session, and then calls /GetMatchHistory on player "z1unknown". The results are saved to the file "out.txt".
To run the code:
You can view the results in out.txt. Of course, the results are ugly and you should use a tool to format the JSON to look nicer.
Of course, this was just a demonstration of one endpoint that we didn't actually do anything with. It takes creativity to parse this information and make it useful. Let's look at a few examples of people who actually use the Paladins/Smite API to do nice things.
Websites That Use the API
A few examples of websites that make use of the Paladins API are as follows:
paladins.guru - Shows player match history and generates an ELO for them.
The Better Meta - Analyzes champion/player/win performance for each patch.
hirez-gql-api.now.sh/graphql - Allows for simplified API calls right in the browser. Here's an example, getting some details for a certain Paladins match.
kusqt.com - Shows Paladin player loadouts.
In this post, we saw how to use the Paladins/Smite API, how it works, and we even demonstrated using it in our own code. If you want to use the API, then feel free to request access, and try to program something cool.
Shout out to the active developers who use the API, and HirezAaron, who is the lead developer for the API that everyone pokes when something goes wrong or when we need something.
It's possible that I'll make a blog post for using the API to make a website, which would include the best practices and some architecture drawings, so keep an eye out.
Here's the youtube video for this article, if you want to see a walkthrough/talkthrough of the coding/concepts.