The GPS plugin is a multifaceted Spigot plugin which is designed to take information from a coordinate plane system known as a "graph" containing intersecting lines called "nodes" and "edges", and utilizing it to provide a solution to any given shortest path problem.
In simpler terms, it is a GPS navigation plugin which works with the road network on the server to provide turn by turn directions to a player wanting to get to a destination.
How it Works
Just a forewarning to anyone reading this, this section of the page gets extremely technical.
The GPS plugin has three main parts to it:
The first part is the YAML file which stores the road information that the GPS system uses to navigate. This file is extremely large, storing about 22,000 lines of YAML code. The file is actually generated by a completely separate program you may have heard of: Dynmap! You may know that Dynmap has a roads overlay which allows you to see the roads on the server. The GPS system works off of this roads overlay, but I'll bet you didn't know how literal that is: The GPS program and Dynmap literally use the exact same file to generate the road network!
The second part is the GPS algorithm. Although the actual data explained above is pretty darn important, this is arguably the most important part of the system. Without this, the rest of the stuff is pretty much meaningless. The GPS algorithm is the piece of code written in Python which does the following:
- Parses through the YAML file, interpreting it and assigning distances to the lines that are defined by it.
- Using a pathfinding algorithm along with the data previously generated to find the shortest possible path through a network of roads.
- Interpreting the path generated and assigning human readable directions to it.
This, it can be said, is the meat 'n' potatoes of the program. It is the code which actually accomplishes what the entire system sets out to do.
The third and final part is what I like to call the plugin bridge. You see, the above code is all written in the Python programming language. It works on its own, but what we really want to do is to run the program from Minecraft's chat. But in order to do this, we have to communicate with Spigot. The problem is, Spigot doesn't speak Python, Spigot speaks Java. So, the final piece of the puzzle is a tiny little piece of Java code which executes the Python code and reads the results to Spigot. This is what allows you to see the directions in the chat.
In Depth, Step by Step Developer's Cut
Alrighty, when you execute a /nav command, here is what is actually happening:
- First off Spigot gets wind of the fact that you executed a /nav command. Spigot knows that /nav commands should be handled by the GPS plugin, so it calls upon the code inside of it.
- Within the GPS plugin, checks are performed to make sure that the command is run correctly. Once the plugin is satisfied that it is a valid command, it makes a call directly to the operating system. Specifically, it calls upon the program "python" which starts the python interpreter. It tells python to begin executing the code within the python end of the program. This is where things get confusing.
- The very first thing that has to be done in the python end of the program is it must update a file called "GRAPH.py", a large file containing a large number of python dictionaries which essentially contains the road information. In order to do this, some other things have to happen first.
- First, we've got to go get the new information from Dynmap. The program does this by reading Dynmap's markers.yml file, a YAML file which contains the 22,000 some lines of code I mentioned earlier. It reads through this file, and then for each and every point creates an object called a "node". These nodes group together to create a new object, a "road". It assigns every node a zero-indexed number which is referred to as the "node number", and every road a zero-indexed number called a "road number." The numbers only have significance to the program and do not occur in any particular order.
- By this time, the program has essentially created a big graph with a bunch of roads on it. The trouble is that the program still doesn't know which roads intersect each other. The previous way the program did this is by figuring out what nodes each road had in common with all the other roads. For example, if road A has a node (22, 63, -37), and road B has a node (22, 63, -37), then it can be assumed that because they are the same point, the roads must intersect. There is a problem with this method though: the roads need to both contain the same point, and as a result, that point must be specifically defined to the road when it is created. Because the server's road network is very dynamic, road definitions are changed a lot. However, using this method, when a road is changed, every other road that that road intersects must be redefined as well. This is a lot of work, and it is not conducive to the dynamic environment of the server. So instead of using that method, the program now uses linear algebra. To do this, it first creates what basically amounts to a large list containing all of the edges, or lines that make up the roads. It does this using the coordinates from the nodes. Now, remember back to middle school algebra when you used two equations to determine if two lines intersect? Yeah, the program is doing essentially the same thing, only it has to do it in three dimensions. It does this by performing it in 2D, but once for each possible set of planes: XY, XZ, and YZ. If each set of lines intersects in all three planes, it can be deduced that the lines also intersect in 3D space, and as a result, it can be deduced that two roads intersect at that point. This makes it so that intersections do not have to be specifically defined upon the creation of the roads, rather, they can be created as an afterthought, and the program will automatically determine if an intersection exists or not. This is by far the most complex and computationally intensive part of the program. During this sequence, the program must test and compute approximately 468,000,000 sets of data to determine this for all roads. As a result, this data is stored away and not computed dynamically. Instead, the program simply accesses a data file containing this information when it needs it, and this data file is periodically updated.
- Now that we know which nodes are connected to one another, we need to calculate the distances between them so the pathfinder can know which path will be shortest. This is done pretty easily. The program uses some algebra to calculate the distance between every pair of nodes. More specifically, it uses a version of the distance formula which works in 3D. Using this along with the coordinates of the nodes, it can calculate the distance between them.
- Finally, now that that is done, we now have all the information necessary to write GRAPH.py. The program writes the file and then saves it.
- With the updating process done, we can actually begin navigation now! A call is made to a special function called GPS. The GPS function is given two sets of coordinates, one which is the starting point, and one which is the ending point. In order to find this out, the GPS function makes another call to a function containing the pathfinding algorithm itself.
- The pathfinding algorithm is based off of one of the more famous algorithms in computer science, Dijkstra's Algorithm. Dijkstra's algorithm is a pathfinding algorithm which works by eliminating paths until it finds the path with the shortest distance. (I won't go in to detail. Google it.)
- Dijkstra's algorithm will either return the list of nodes which corresponds to the shortest path, or it will return "false" which means that no path exists between the two specified points. Assuming however that a path exists, the GPS function passes the list of nodes on to the GPS interpreter. The list of nodes is the path, but it's effectively gibberish until the interpreter reads it, and spits out human readable directions. I won't go into detail how the interpreter works either because it's a highly complex and advanced piece of code which is not easy to explain.
- We're in the clear! Now, the python program is complete, and it produces standard output in the form of a series of sentences containing the turn by turn directions the interpreter gave us. Those lines are picked back up by the Java code in the GPS plugin. Java then stuffs them into a function which reads out the results to the player, and the GPS program is complete.
The question can be posed: what type of crazy stuff does the program have to do in order to determine on its own whether or not two roads intersect? Well, it's actually not too advanced. In fact, most of the stranger stuff it does doesn't involve very much higher level math, rather it requires you to make a few logical leaps that may not be immediately apparent. The program creates intersections based on three mathematical and logical truths:
- There is no such thing as a curved line in Minecraft. Rather, curved lines consist of a set of smaller lines with changing slopes to give the illusion of a curve.
- Given a set of two line segments and therefore their points, the line segments can be assumed to intersect if the geometric orientations of both line segments and both points on the other line segment either do not match, (4-way crossing) or are colinear. (3-way crossing)
- If a set of lines intersect on the XY, XZ, and YZ axes, then the lines intersect on all planes in 3D space.
Let's talk about these truths a bit.
The first truth is not entirely necessary in order to calculate intersections, but it helps a lot because curved lines are much more difficult to work with. This reduces the problem to a question of simple lines, and it is also more accurate because, well...it's the truth! There is no such thing as a truly curved line in Minecraft. Instead, we use approximations of curves by creating a series of smaller lines with slopes varying such that they as a whole give the appearance of a curve. By realizing this, we can utilize those individual lines instead of looking at the curve as a whole, which makes the problem much easier to solve.
The second truth is difficult to visualize in your head. In geometry, there is a concept called orientation. That, given three ordered points, you can determine the direction that those points are oriented in. This probably sounds scary because you can't easily visualize it, but here's a picture to help:
Yeah, it really is that simple. Any set of three points can have only one of three orientations: clockwise, counterclockwise, or colinear. Now that's nice and everything, but how does this help us with determining whether or not roads intersect? Well, orientation can be used to determine if lines intersect in 2D, which gets us part of the way there. First, we can realize that if anywhere in determining the orientations of a set of points from lines we discover that any of them are collinear, then they must intersect. There is no way they can't:
That is the first case, but what about lines that do not have a 3-way intersection? What about lines that do not produce collinear points, but intersect anyway? Well, let's take a look:
Hmm! Notice something: that when two lines intersect, their orientations are different between each pair. Correction: they are always different. They have to be. Other than a few special cases which I won't discuss here, it is not possible to have a pair of orientations be the same if lines intersect. Go ahead, try it in your head. It can't be done. As a result of this, we can deduce that if the first pair of orientations is different, and the second pair is different, then the lines must intersect!
Ok, so we can determine if two lines intersect! Great, so we're done, right? Well, not quite...unfortunately, this solution only works in two dimensions. "Well, what's wrong with only using two dimensions?" Only using two out of the three dimensions results in the program being effectively oblivious to height. That, of course, works fine as long as you do not have any roads which cross over one another, but do not intersect. If you have even one road which travels on a bridge over another road, you must pay attention to height. If you don't, the program will assume, (because it is oblivious to height) that because the roads cross over one another, they must intersect, even if they don't! The program can't know any better because by only using two dimensions, you deprive it of the necessary knowledge to know otherwise. During development, I found this out myself the hard way and referred to it as the "IOS Maps" Bug. So, how can we determine if lines intersect in 3D space? That is the job of the third and final truth, which is complicated to explain, but I'll make it simpler. Imagine that you have two lines, just like we talked about before. These lines, of course, are created using the X and Y coordinates from the points. We can determine if those two lines intersect because it is only 2D. However, we can also do the same if we create lines from the X and Z coordinates. Again, because we're still working in two dimensions. We can again do the same thing, but using the Y and Z coordinates this time. What we're essentially trying to do is figure out if all of these sets of lines intersects. Why? Because if they all intersect, then the original lines must intersect in 3D. This is difficult to visualize without the aid of 3D graphing calculators, but if all of these lines share a point, then the original lines we set up must also intersect in 3D space. Using this, we simply have to apply the second truth three times, and we can determine whether or not our 3D lines intersect!
That is it! That is all that the program has to do in order to determine if two roads intersect. Sounds like a lot huh? Well, to be honest, it is. Think about this: The program has to perform these calculations once for every set of points on every line on every road on the server. Bearing in mind that at the time of writing, there are 468 roads on the server. Although the number of lines per road varies, it averages around 25 per road. Larger roads like interstates can have as many as 400 lines! All of this makes this part of the program the most computationally intensive of all.