Collision detection with heightmap based terrain

Question

I am developing a 2D tank game. The terrain is generated by Midpoint Displacement Algorithm, so the terrain is represented by an array:

index --->  height of terrain
[0]   --->  5
[1]   --->  8
[2]   --->  4
[3]   --->  6
[4]   --->  8
[5]   --->  9
...         ...

The rendered mountain looks like this:

        *
  *     * *
  *     * *
  *   * * *
* *   * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
0 1 2 3 4 5 ...

I want tanks to be able to move smoothly on the terrain (I mean tanks can rotate according to the height when they move), but the surface of the terrain is not flat, it is polygonal. Can anyone give me some help with collision detection in this situation?

Thanks in advance.

Answer 1

You dont really need to do collision detection with the floor, since its expensive to calculate and im guessing the tanks are always touching the ground. All you need to do is to make the tanks height position equal to the one from your height index array. it will give the impression that the tanks are touching the floor but you are not actually calculating collision

Answer 2

Think of your terrain as a bunch of slanted lines. Each line has a 2 points. Each end has a height in y space. Every position between those two points has a height that is just an interpolation of the end points. So if you know the x for your tank (Tx), or for a point on your tank, you just need to calculate the height of the ground at that x. Then check to see if Ty is above Sy.

First determine which terrain line segment the tank (or point on the tank) is over. In my game I pre-sort the terrain segments so it's easier to find the right one quickly. Looks like you have them sorted as well.

Then assuming [1].x is bigger than [0].x, [1].x-[0].x is the x distance of that segment. Call it Dx. [1].y-[0].y is the height change or slant of that segment, Dy.

Tx - [0].x is how far through the x of that line segment your tank is.

So (Tx - [0].x)/Dx is a % through that segment (Px) represented 0-1. And Px is the same as Py. It is also the same % through the slant. Therefore [0].y + Px*Dy is the height of the ground at that Tx.

If your tank is a point you only have one Tx to solve for.

Let's say your tank is a box instead of a point. A cheap way to handle that is to do the above twice. Once for the front bottom of the tank tread and once for the back. This gives you a ground level for each end of the tank. You can easily calculate the angle the tank needs to be here. And yes rotating the tank does change the 2 points, which might require a couple passes. Or over several frames the tank would settle over the ground.

If you're worried that this would allow the tank to straddle peaks in the mountain, since you're only checking the front and back of the tread, then do the detection for 3 points: the front, middle and back. Then when going up over a peak the front of the tank will rise until gravity tips it over. It might straddle the peak a little between any two points. But this might look acceptable. Add more points if it's a problem.

To make the driving up over a peak look like the tank is tipping over it, you'd have to add some simple physics to the game. And that is outside the scope of this question. But the general idea would be to apply downward force (gravity) to probably only the front and rear collision detection points on your tank. Then detect for collisions on all, keep the points from passing through the ground. Then rotate the tank to the new angle. You might have to do 2 or 3 passes on the collision correction to keep it above ground. And you'd have to experiment to make it look good and also be fast enough. But with even 10 points and 5 passes it shouldn't lag.

Collision detection can be cheap. To make it cheap only do the math for a few points on your object. In the image above you see my 3d ship and then the collision detection points for it. I do 2d terrain detection in my game for a 3d space ship with over 700 tris, but I only detect for 20 points around the perimeter. I apply my ship rotation matrix to each point and then check for collisions and it works great and is fast.

Answer 3

If it is all quads it is just lerping between the values using modular arithmetic.

You have dx, dz which is the distance between nodes when scaled.

//Get your indices and normalized distances between.
float offsetX, offsetZ; 
//this is how far the grid is offset...used to map it to indices
int Xindex = (int)((pos.x - offsetX)/dx);
int Zindex = (int)((pos.z - offsetZ)/dz);
float normModX = (pos.x - dx*Xindex)/dx; //should cache 1.0/dx as inverse_dx
float normModZ = (pos.z - dz*Zindex)/dz; //should cache 1.0/dz as inverse_dz

//Get your heights
float Y0 = Height[Xindex][Zindex];
float Y1 = Height[Xindex+1][Zindex];
float Y2 = Height[Xindex][Zindex+1];
float Y3 = Height[Xindex+1][Zindex+1];


 float height;
 //The exact way this is done depends on how your grid mesh is stitched together...
 //Now you are working with 2 triangles and you know the height of all 4 points.
 //Determine which triangle we are on. Then interpolate between the 3 heights.
 if(normModX/normModZ < 1.0f)
 {
   height = InterpolateHeights(normModX,normModZ,Y0,Y1,Y2);
 }
 else
 {
   height = InterpolateHeights(normModX,normModZ,Y1,Y2,Y3); /
 }