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) 
Answer
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
Vector2with an x coordinate lesser or equal than the place where you need to check (I will call itA).The first
Vector2with an x coordinate with the greater or equal than the place where you need to check (I will call itB).
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
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 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.
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:
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.
No comments:
Post a Comment