How IPS Works
IPS tackles the coordinate problem in Starbase. Since players have no access to a built-in game coordinate system, we need to program it ourselves.
IPS and other positioning systems utilize 4 developer-placed transmission stations located around the Origin stations. Each transmission station broadcasts on the same channel, and a receiver on board a player ship can listen to that channel to receive a signal. The strength of that signal directly maps to the receiver's distance from the transmitter.
Thus, we can get one distance for each of the 4 transmitter stations. Using those 4 distances, we are able to mathematically deduce our coordinates.
If you are curious how this works with Mono Receiver Mode, check out Mono Receiver Mode.
The core equations that power IPS are as follows:
The idea is that by solving for x, y, and z we are able to get our current coordinates. But actually doing this is tricky. Not only do we need to sort these equations out into something that can be written in YOLOL, but first we need to determine the coordinates of the 4 transmitter stations.
Half the battle is figuring out what the transmitter coordinates are relative to each other. Since we have no coordinate system to start with, we need to define the coordinates ourselves.
First, we need to measure the distances between each transmitter station. This is simple to do. Each fancy transmitter station actually has a physical transmitter module about the size of a small receiver on it. You can fly right up to it. So we take a small ship, slap a receiver on it, and fly to each transmitter and record the distance to all the other transmitters.
The mathematical approach used in IPS is begins with a method known as "Fang's Method". You can read about it in this research paper by Jacek Stefański.
To start, we need to define a coordinate grid. By measuring the distances between each transmitter and then assembling some triangles, we can deduce that the transmitters do not share a common plane. Instead, when you connect the four transmitters together with lines you get an irregular tetrahedron as seen in the below GIF.
Because of this, we can't define a coordinate grid with all 4 transmitters. So, we use 3 transmitters. IPS defines a plane using the West, North, and East transmitters.
- West is assigned the origin point of
[0, 0, 0] - North is placed on the X-axis
[A, 0, 0], where A is the distance from West->North - East gets its coordinates from its distance from West and North
[B, C, 0]. A Triangle Calculator is very useful for this.
Now South is the problem. Since it doesn't lay on the same plane as the other three transmitters, we need to find its coordinates manually using the same kind of math we will eventually use for the player's position. But for South, we only have 3 transmitter stations.
First we assign our variables.
- Transmitter1 = West =
[0, 0, 0] - Transmitter2 = North =
[T2X, 0, 0] - Transmitter3 = East =
[T3X, T3Y, 0] - Transmitter#X/Y/Z = T#X/Y/Z = Coordinates of the respective transmitters
- Transmitter#D = T#D = Distance to the respective transmitter
Following Fang's Method, we take the following three equations:
And simplify them to this after we plug in the coordinate values to their respective variables:
From here, I did everything manually. Fang's Method was crucial for defining the initial coordinates of the transmitter stations, but the mathematical syntax used in the paper was too frustrating for me to try and understand. I may have ended up doing the same thing, or I may have done something different. Either way I struck off on my own to solve the equations.
After flipping variables around, setting equations equal to each other, eliminating a variety of squares and fractions, and plugging in coordinate variables, I ended up with these coordinates:
- South =
[4077.9480364368154955356778616944, 65966.252119351342522984219557446, 71109.554578860361694692488730602] - South =
[4077.9480364368154955356778616944, 65966.252119351342522984219557446, -71109.554578860361694692488730602]
But as you can see, there was an issue with the Z-Coordinate. It involved a square root, which means the resulting value could be positive or negative, which gives us 2 possible coordinates for South. But we can choose between 2 coordinates.
I used an online 3D point plotting utility to get a sense for the orientation of the transmitter stations. I then flew out to dead space in-game, spotted the transmitter stations in the far distance, oriented my in-game perspective to match my 3D graph, and then selected one of the two points.
One South coordinate was very close to the Origin Stations and the second South coordinate was very far from the Origin Stations. Given South is right next to Origin Station 1, I went with that coordinate.
Then by plugging in the distance measurements from each transmitter to South, I am able to calculate what South's coordinates are relative to the others.
- West = T1 =
[0, 0, 0] - North = T2 =
[91923.25, 0, 0] - East = T3 =
[74246.31767, 95459.74094, 0] - South = T4 =
[4077.9480364368154955356778616944, 65966.252119351342522984219557446, 71109.554578860361694692488730602]
Now that we have coordinates for each transmitter station, we can move onto setting up the equations for determining the player's coordinates.
Most of the work for solving the system of equations had been done already by determining South's position. But this time I had a fourth transmitter to consider, which lets us eliminate that double-answer problem we saw with South.
After wrangling the equations around we end up with these:
Note how the equation for y actually uses x, and the equation for z uses y and x. While the instinct may be to substitute x and y out for their equations so you end up with a system of equations that only relies on the transmitter distances, we can actually leave those in there and just calculate the coordinates in order to save sanity.
We then plug in values for the transmitter coordinates and simplify things to try and reduce the number of needed YOLOL variables as much as possible. Then once we YOLOL it, we end up with the following code:
e=91923 f=74246 g=4078 h=95460 i=65966 j=71110 k=5200332997 s=1000000
t=s-:a u=s-:b v=s-:c w=s-:d
x=(t*t-u*u+e*e)/(2*e)
y=(u*u-v*v+x*2*(e-f)+f*f-e*e+h*h)/(2*h)
z=(v*v-w*w+x*2*(f-g)+y*2*(h-i)-k)/(2*j)
From here, various YOLOL tricks allow us reduce it down in size so it's more compact and fits on only 2 functional lines of code and 1 line of setup. But the core logic remains the same. Using this code in-game will actually give you a functional positioning system, but there is a problem.
Because we defined West to be our Origin Point and we put North on the X-axis, our coordinate grid is aligned in a gross way. Draw a line from West to North, and that's your +X-axis. Very bleh. Navigating with this grid alignment would be horrible.
So, we need to define a grid that is perfectly aligned with the belt for ease of use. And even though there is no in-game coordinate system to help us get our grid straight, the SSC comes to the rescue.
For some reason (perhaps this is why, in which case thank you devs), the testing world inside the SSC is rotated and aligned differently than in real-space. In the test world, the SSC building is perfectly aligned with the belt and planet on the game's built in coordinate grid. And so we can define directions based on movement with this.
When spawning in the SCC looking in the standard direction ships are aligned to,
- UP = +X
- DOWN = -X
- LEFT = +Y
- RIGHT = -Y
- FORWARD = -Z
- BACKWARD = +Z
Note that the axis assignment to the directions is a personal choice by me. My instinct is for +X to go inside the belt, for +Y to go to the left of the belt, and for +Z to go above the belt. Though while my math uses these assignments, display of each variable is easily changed for those who prefer to give the axis different labels.
In order to get our coordinate grid to line up with the one in the SSC, we need to rotate it.
Coordinate grid rotations are pretty straight forward. Since we are dealing with a 3D coordinate system, we will need 3 rotations.
But, we need to change the way we think first. Up until this moment, transmitter coordinates have been points in space. But to work with rotations we need to think of them as vectors. Each coordinate represents an arrow with a direction and length from [0, 0, 0] to the coordinate.
Coordinate grid rotations use matrices to easily handle applying the rotation to vectors. I've never been great at matrix syntax and thus opted to use a couple different rotation calculators online to help me. None of these calculators were designed for 3D rotation, but that's alright. When you take 3D grid rotation and do it one step at a time, it becomes 3 2D rotations, which are much easier to handle.
But any rotation requires an angle. To get the angle, we need to take some measurements in the test world with our functioning, mis-aligned system. Since the UP direction is going to be our +X-axis, we measure that first.
I built a crappy little ship in the SSC with 4 receivers and the functioning code, and flew in different directions to take measurements. Note that the most important thing to watch out for when doing this is the ship's center of mass compared to the center of thrust. If they are misaligned then the ship may not fly perfectly straight and your measurements may be skewed.
Test World Start Coords for Up = [58586.077, 84176.746, 33845.84]
Up Coord #1 = [58228.543, 84454.902, 34070.63]
Up Coord #2 = [57981.043, 84647.368, 34226.129]
Up Coord #3 = [57722.089, 84848.814, 34388.89]
Direction Vector from Start to Finish = Finish - Start
Start->#1 = [58228.543, 84454.902, 34070.63] - [58586.077, 84176.746, 33845.84] = [-357.534, 278.156, 224.79]
Start->#2 = [57981.043, 84647.368, 34226.129] - [58586.077, 84176.746, 33845.84] = [-605.034, 470.622, 380.289]
Start->#3 = [57722.089, 84848.814, 34388.89] - [58586.077, 84176.746, 33845.84] = [-863.988, 672.068, 543.05]
Normalized Vectors
[-0.7070089707067077, 0.5500421981011456, 0.44451309952385176]
[-0.7070881178488321, 0.5500041719940583, 0.444434252039744]
[-0.7070822874829227, 0.5500161793729459, 0.44442866824261573]
Averaged Normalized Vector
[-0.70705979201282083333333333333333, 0.5500208498227166, 0.44445867326873716333333333333333]
Now we have a unit vector that represents the direction we want our +X-axis to go.
We then compare the unit vector to a vector along the +X-axis [1, 0, 0] to get the angle between them. In this case it was 142.12 degrees.
Thanks to a couple of online grid-rotation calculators checking each other's work, we successfully rotate the entire coordinate grid around the z-axis by 142.12 degrees, which places our desired UP directional vector perfectly on the XZ-plane.
From here, we perform a second rotation around the Y-axis so the UP vector lines up with the +X-axis perfectly. The same steps were used as in the first rotation above, so I won't display them here.
But, we hit a problem. Our UP vector is now perfectly aligned with the +X-axis, but it contains no further information about the Z- and Y-axis. We can confirm the Y- and Z-axis are 90 degrees from our UP vector, we don't know what the rotation is and we can't use the UP vector to fix them.
So we head back into the SSC to take another selection of measurements, but this time in our rotated space. We fly LEFT to map out the direction we want our +Y-axis to go. It was very satisfying to note that during this activity, the displayed X coordinate never changed since we were flying parallel to the X-axis we had already rotated to match.
With the new LEFT directional measurements, we assemble the LEFT vector and compare it to our +Y-axis [0, 1, 0], and discover that it is a whole whopping 172.88 degrees off. We perform the rotation and end up with a perfectly aligned coordinate grid.
During this whole rotation process, I encountered an issue. After the first 2 rotations I had calculated transmitter station coordinates that were correctly rotated. My first instinct was to plug these correct station coordinates back into the complex equations so the system would spit out the correct numbers.
But our use of Fang's Method stops us from doing this. By altering the coordinates of the transmitter stations we need to re-introduce some variables that we were previously able to eliminate because they were 0. Adding these variables back in requires us to re-solve the system of equations via a completely different method.
I had begun the process when I realized that I didn't need to re-solve the equations. Instead of rotating the transmitters, I could rotate the player's coordinate after it is calculated. This is what allowed me to get the first 2 rotations working inside the SSC so I could take the measurements for LEFT.
But, YOLOL has some limitations when performing rotations. The math wants to use sin and cos on the desired angle, but those functions are only available in professional chips... plus they take a lot of characters. Lucky for us, the rotations we want to perform will never change, which means we can hard code the results of sin and cos.
After assembling the rotation logic and creating constants for it, we end up with the following YOLOL code to rotate a point to the correct orientation:
l=614009 m=789298 n=895789 o=444478 p=123947 q=992288
xa=(l*y-m*x)/s xr=(n*xa+o*z)/s za=(n*z-o*xa)/s ya=((-l)*x-m*y)/s
yr=(p*za-q*ya)/s zr=((-p)*ya-q*za)/s
Where xr, yr, and zr are the correctly rotated coordinates. This adds 2 functional lines to our original coordinate calculations and 1 line of setup.
Now that we have a functioning and aligned positioning system, we want to shift the Origin Point. Lucky for us this is very easy.
All we need to do is take the current, finished coordinate and offset it by an amount equal to the coordinate of the Origin Point. Very simply:
xr-=ox yr-=oy zr-=oz where (ox, oy, oz) are the coordinates of the desired Origin Point.
Desired features in the future may reveal problems with this approach to the coordinate problem. For example, replacing transmitters with new ones will require a player to obtain the coordinates of the new transmitter station in the non-rotated grid space. In addition, I can't even begin to think through what dynamically selecting transmitter stations would look like.
But, adding features such as Mono, Velocity, and perhaps even movement-based orientation shouldn't be difficult. And given the finished code only takes up 10 YOLOL lines, there is plenty of space for improvement.
I believe there is also more to be learned with regards to 3D rotation. I know there are methods to define a rotation matrix that will perform all three required rotations at once, and that may allow me to condense the rotation code even further. But since I've never been great at matrices, it will take some learning to check.