# Creating straight lines between two Vectors? (and slopes?) (interpolation??) libgdx java

I am trying to make a game with very basic physics (just gravity at this stage). Without using box2d How is the best way to create the solid ground. I will be wanting to make ramps soon, but at this moment i am even stuck trying to make flat ground.

The approach i've been researching involves 'interpolation' between 2 or more vector2's , this sounds perfect for me as I only need very basic levels (think Excitebike for NES) so I want to be able to provide my level-creator class with just a bunch of height values and i want it to create invisible straight lines joining up those height points.

As i said ive seen about "interpolation" in the vector2 or the libgdx.math classes but I'm very confused on how to go about using those commands.

As usual any help is much appreciated, thanks for reading

(EDIT: I am thinking I could use Rectangles between the straight parts but is this going to work when i start introducing sloped ground?)

for example i have the green dots saved as vector2 and i need a method that makes the lines between (straight lines is fine no need for curves etc)

• So, the question is how to do interpolation with libgdx.math or is it something else? Feb 28, 2017 at 21:37
• The question is if I have a list/array of Vector2 that designate dots of the layout of a course (such as in ExciteBike) then I want imaginary line between them all for my player to land on, how in libgdx is this best achieved? Feb 28, 2017 at 21:39
• I was writing an answer explaining how to get the height of the ground at an arbitrary X. I understood you needed this since you talk about gravity and because you said "imaginary". Yet, your edit suggest that what you need to draw the lines. Edit: I'm not familiar with libgdx, I'm going for a general solution. Feb 28, 2017 at 22:21
• ok thanks, im not 100% sure what you mean, and im also not sure exactly what I should be researching. The link between the gravity I need and the lines in my diagram are that I want the lines to act like ground (therefore obviously stop my player moving below the line) I DON'T actually need to worry about drawing (rendering) the lines to the screen. hope that helps clarify my question and thanks for your time in trying to help Feb 28, 2017 at 22:30

## Introduction

I am not familiar with libgdx, yet I can explain a general solution.

We start by the fact that you have a list or array with Vector2 that represent the terrain. You want to sort this list by the x coordinate, for ease of searching.

If the list is too large, you may want to move to a hierarchical structure. That is beyond the scope of this post.

Now, if you need to find the height of the ground on a position X, you will search on your data structure for:

• The last Vector2 with an x coordinate lesser or equal than the place where you need to check (I will call it A).

• The first Vector2 with an x coordinate with the greater or equal than the place where you need to check (I will call it B).

If both Vector2 are have the same x coordinate (that is a vertical cliff) then the height of the terrain is the bigger lower of the y coordinates among the two Vector2. Lower because the coordinate system starts at the upper left corner.

Otherwise, you need a linear interpolation between the two points.

The idea here is that you have a game object in some location on the map, this game object is falling due to gravity... and you need to know if it is about to thit the ground.

So, let's say that the position of this entity is (X, Y), we will need this X to find the segement A, B of the ground to compare with.

Once we have found A and B we can find the height of the ground just below the entity

Let's say that the player is falling, and we compute that the next position of the player will be (X, Y). We can then use the method below to find if that is below the ground by comparing Y to the height we find.

If it is below the ground, we may want to set Y to the height of the ground to make the entity stick to it. Or we may compute a bounce, something like this:

float height = getGroundHeight(X);
Y = height - (Y - height)


Note: bouncing also requires to reflect the direction of the speed. And this is diregarding the angle. That's another topic.

## Finding the vectors

<rant>
Java is a disgrace!
I was hoping you could easily do a binary search to find the the vectors on a list...
But no, you can't, even if you write a custom Comparator, because the method for binary search only takes values of the same type of the collection.
Which means you either use the inneficient solution of creating an object just to search, or you iterate yourself, which is error prone.
Thank you for reminding me why I don't use Java.
</rant>


I would like to tell you that you should be using an ArrayList<Vector2> sorted by the x coordinated of the vectors, and you should be using a binary search because it is more efficient. In fact, I would like to tell you that if you can put your vectors in a tree (an AVL for example) you could get a better performance.

But I don't have the patience to do any of that on Java. So you get an array and a for loop:

Vector2[] vectors = getVectors(); // load your vectors or whatever
// ...
public float getGroundHeight(float X)
{
int length = vectors.size();
Vector2 A = null; Vector2 B = null;
for (int index = 0; index < length; index++)
{
Vector2 current = vectors.get(index);
if (current.x > X)
{
if (index > 0)
{
A = vectors.get(index - 1);
B = current;
break;
}
else
{
// The player is before the ground starts
// let's say you can fall forever
return Float.POSITIVE_INFINITY;
}
}
}
if (A == null)
{
// The player is after the ground ends
// let's say you can fall forever
return Float.POSITIVE_INFINITY;
}
if (A.x == B.x)
{
return A.y > B.y ? A.y : B.y;
}
Vector2 solution = getSolution(A, B); // the code implemented below
return solution.y;
}


I hope this code is self explanatory. It may need some tweaking for what you want to do (in particular, those Float.POSITIVE_INFINITY) and it is the naive approach, so it isn't very efficient... but should get the idea accross.

getSolution is what we will be implementing the rest of the post.

## Using slope

When using the slope, we are taking advantage of the orientation of the segment. We know that the segment is not vertical. If it were, we would get a division by zero when we reach the computation of the slope slope = diff.y / diff.x.

Futhermore, this approach will only work on 2D. Once we go to higher dimensions it is no longer effective.

So, you can consider the slope method an optimization for the case where we know that we are working on 2D and the segment is not vertical.

This approach comes from linear algebra.

diff = B - A

=>

diff.x = B.x - A.x
diff.y = B.y - A.y


This vector represents how much does the segment advance in x and y from the point A to the point B.

By using it, it is easy to get the slope:

slope = diff.y / diff.x


This is how much does the segment advance in y for each pixel it advances in x. We will use it to find how much the segment has advanced when we are at the position X:

delta.x = X - A.x
delta.y = slope * delta.X


Here, delta.x is how far from A is X horizontally. We multiply it by the slope to get how much had the segment advanced vertically at that point (delta.y).

The only thing missing is to add the start of the segment to it:

solution.x = X
solution.y = delta.y + A.y


Here the vector solution is the point on the ground at the coordinate X.

## Using vector projection

The advantage of the vector projection approach is that it will work in any situation, no matter what. It will continue to be useful even on 4D and beyond, no need to worry about.

This approach comes from analytical geometry.

Again, we start with the difference, the same way as above. Then we built a temporal vector to project onto the segment:

tmp.x = X - A.x
tmp.y = 0


Then the projection is:

delta = diff * (diff · tmp) / |diff|^2


Where "*" denotes scalar product, "·" denotes dot product, and "||" denote the norm of the vector.

We can understand this as using the director vector for diff (diff / |diff|) and scale it to (diff · tmp) / |diff|... that last part is how much we have to advance in the diagonal from A to B to get to the solution.

Let's break that formula down:

delta.x = diff.x * (diff.x * tmp.x + diff.y * tmp.y) / (diff.x * diff.x + diff.y * diff.y)
delta.y = diff.y * (diff.x * tmp.x + diff.y * tmp.y) / (diff.x * diff.x + diff.y * diff.y)


We end by adding delta to A:

solution.x = delta.x + A.x
solution.y = delta.y + A.y


Note: delta.x + A.x sould be equal to X.

## Using interpolation function

The interpolations are based on the same principles as the vector projection, but they provide additional flexibility by abstracting the "easing" of the values.

Here the challenge is to figure out how much do you have to advance in the diagonal from A to B. We already saw the formula for that:

alpha = (diff · tmp) / |diff|;


Another approach to get it is with trigonometry, but I'll not go into that.

This value alpha is what you would feed into the interpolation function.

In practice this solution will probably be more expensive because the implementation will add an additional step to support the easing the values (a task delegated to the Interpolation class). I would not use it unless I need it. It is here for sake of completness (and also because I'm learning a bit of Libgdx by doing so).

Addendum: what the above gives you is the point on the ground. You still need to check if the player (or whatever object) is about to go below it (here below, means a greater value, because the coordinate system starts at the upper left corner), and have stick to the ground, bounce, or whatever.

• amazing reply thank u. I'm going to try put it into practice now and will get back to u asap. thanks again! Feb 28, 2017 at 22:32
• BTW, i know that LibGDX has basic linear interpolation method within Vector2 class (of libgdx) and also it has it's own Interpolation class too for more complex tasks. I just find reading the official documentation very hard without examples to follow sadly. I beleive much of what u are teaching me here is probably already done for us within libgdx math classes but i don't know how to harness it. Your method is going to teach me the full way anyway so i will push on at trying to implement it this way Feb 28, 2017 at 22:46
• ha just seen your edit. thanks so much again. i still haven't got round to trrying to code yet (been reading this detailled answer by you) but will do soon. you're a real hero man Feb 28, 2017 at 22:50
• im being thick (as usual!) but in your libgdx example code snippets, am i correct in saying those 4 things all acheive the same end? What is the difference, in RESULT between "Using slope" and "Using Vector Projection" Feb 28, 2017 at 22:53
• so yeah, im still having major trouble actually implementing this as a track for my game. (ie. how exactly do i turn my list of Vector2s into the platform / and how do i check the NEXT and LAST points passed) I'm thinking I could create Rectangles between each point and that way, id know that when i reach a certain rectangle that would be pointA and pointB at other corner of rectangle. Im totally confused :S although I full understand your theory explained above I cant find how to put this into my game Feb 28, 2017 at 23:08