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:
Vector2 with an x coordinate lesser or equal than the place where you need to check (I will call it
Vector2 with an x coordinate with the greater or equal than the place where you need to check (I will call it
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
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
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.
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;
// The player is before the ground starts
// let's say you can fall forever
if (A == null)
// The player is after the ground ends
// let's say you can fall forever
if (A.x == B.x)
return A.y > B.y ? A.y : B.y;
Vector2 solution = getSolution(A, B); // the code implemented below
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.
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.
Start with the difference:
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 = 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
delta.x = X - A.x
delta.y = slope * delta.X
delta.x is how far from
X horizontally. We multiply it by the
slope to get how much had the segment advanced vertically at that point (
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
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|) and scale it to
(diff · tmp) / |diff|... that last part is how much we have to advance in the diagonal from
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
solution.x = delta.x + A.x
solution.y = delta.y + A.y
delta.x + A.x sould be equal to
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
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.