# Heightmap + Collision detection.

This topic is 3832 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello all, I've been writing a terrain engine. All is well so far and the thing works beautifully. The only problem is collision detection with hills that are too steep. I got to think, now I could either calculate the degrees the hill is or look at the pixels in the heightmap and check the difference. If the difference would for example be 10 pixels in height, then the hill would most likely be too steep. So, after having figured that out I stumbled upon a problem. How do I figure out what tile I need to check in order to allow/disallow my entity to move. I have a 360 degrees movement system, and I have absolutely no experience on how to do collision detection with that in a tile based map. Does anyone know how to handle this ? Here's my current move entity function.
/// MoveEntity. Moves an entity from it's current position to an other position.
int EntityManager::MoveEntity(BaseEntity *entity, float speed)
{
Vector cp, cr, tp, np, op, ha, hb, hc, hd, deg;
HeightObject *object = NULL;
frametime_t *timer = engine->GetTimer();
curframe = timer->curtime * 0.001f;
lastframe = timer->lasttime * 0.001f;

if (!entity)
return 1;

// Retrieve entities current position and rotation.
cp = entity->GetPosition();
cr = entity->GetRotation();

// Negative speed or positive speed.
if ((cr.GetZ() > 90) && (cr.GetZ() < 270))
speed = -speed;

// Retrieve vertice position in the map.
if (entities.at(0) != NULL)
object = ((HeightObject*)(entities[0]->GetModel()));

// Get the object's plane position.
ha = object->GetVertice(Vector(fabs(cp.GetZ() / 20.0f), fabs(cp.GetX() / 20.0f), 0, 0));
hb = object->GetVertice(Vector(fabs(cp.GetZ() / 20.0f) + 1, fabs(cp.GetX() / 20.0f), 0, 0));
hc = object->GetVertice(Vector(fabs(cp.GetZ() / 20.0f) + 1, fabs(cp.GetX() / 20.0f) + 1, 0, 0));

hd = object->GetVertice(Vector(fabs(cp.GetZ() / 20.0f), fabs(cp.GetX() / 20.0f) + 1, 0, 0));
// Calculate new position, check if a hill is steeper than 65 degrees.
tp = cp;

tp.SetX( tp.GetX() + ( (sin(cr.GetZ() * ANG2RAD) * RAD2ANG) * (speed * (curframe - lastframe))));
tp.SetZ( tp.GetZ() + ( (cos(cr.GetZ() * ANG2RAD) * RAD2ANG) * (speed * (curframe - lastframe))));

cp.SetX( cp.GetX() + ( (sin(cr.GetZ() * ANG2RAD) * RAD2ANG) * (speed * (curframe - lastframe))));
cp.SetZ( cp.GetZ() + ( (cos(cr.GetZ() * ANG2RAD) * RAD2ANG) * (speed * (curframe - lastframe))));

// Perform a bilinear interpolation.
float tx = cp.GetX() / 20.0f - float(cp.GetX() / 20.0f);
float ty = cp.GetZ() / 20.0f - float(cp.GetZ() / 20.0f);

float xy = tx * ty;
float h = ha.GetY() * (1.0f - ty - tx + xy)
+ hb.GetY() * (tx - xy)
+ hc.GetY() * xy
+ hd.GetY() * (ty - xy);

np.SetY(h);

// Adjust the Y value so the object is always on top of the terrain.
cp.SetY(np.GetY() + entity->GetModel()->GetBoundingBox().GetMax().GetY());

// Set the new position.
entity->SetPosition(cp);

return 0;
}


Thanks a lot.

##### Share on other sites

1)You must get yours coordinates
2)if you use an heightmap for terrain, you must have a 'gap value' that identify the distance between 2 consecutives vertices. If you divide your position by this gap values, you get the vertice where you are.
3)with a very easy offset you can get from your heightmapbuffer the 4 vertices's heigh of the square where you are..
4)with these datas and your position in this square, you can calculate the exact heigh where you must be.

ok... my english is poor... so I post an example....

you have a heightmap of 256x256 --> byte* heightmapbuffer[256*256]
distances between vertices 10 --> int gap =10
so the world is 2560x2560 unit...

you are in position 1302,803
1302/10 = 130,2
803/10 = 80,3

this mean that on X axis you are between 130th and 131th vertice,
on Z axis you are between 80th and 81th vertices.

now you get the square's vertices where you are:
heightmapbuffer[(256*79)+130]
heightmapbuffer[(256*79)+131]
heightmapbuffer[(256*80)+130]
heightmapbuffer[(256*80)+130]

now you have this
 _____                                   _____                _____|     |                                 |\    |              |    /||     |                                 |  \  |              |  /  ||_____| and it is divide or in this way |____\|   or in this |/____|

with some operation you can know in which triangle you are, e then calculate your real high....

probably is more easy do it, that read it....

bye

##### Share on other sites
Hmmm, that's an idea yes. But my main point was, I still don't know what square to check for the height, and how to make it so I can stop my player/entity from walking into that part of the terrain.

##### Share on other sites
Assuming you use the y coordinate for the height, then use the x and z coordinates of the player's position to find the tile that it sits on. You do this by dividing the x and z coordinate by the size of the tile. So, if each tile represents 10 units in world space, and the player's position is at (15, 11), then the entity is sitting on (1, 1) in tile space.

##### Share on other sites
you can calculate the square where you are, the square to check for the height.

Like strtok has rewrite, dividing your position by vertices's distance, you get the vertices of the square where you are.

easy and speed....

##### Share on other sites
The problem is not with finding the tile I am standing on. The problem is finding out what tiles to test for how steep a hill is. and also how to make it so that if it is too steep, X or Z won't be added.

##### Share on other sites
This is really better for Math & Physics, I think.

##### Share on other sites
Quote:
 The problem is finding out what tiles to test for how steep a hill is. and also how to make it so that if it is too steep, X or Z won't be added.

it is not a problema, because with trigonometry and the 3 triangle vertices coordinates, you can calculate the tile slope...
if the slope is too much, you don't add X or Z.... you don't need of another tile... and otherwise you know your direction, so you can know which will be the next tile.

##### Share on other sites
Well in that case, if I need to calculate it on the tile that I am standing on. How would I go about calculating how steep it is ? And I still need to know wether I should add X or Z or if I should not add them. I hope you understand me. Thx a lot already :)

##### Share on other sites
ok... you follow above istructions, and you'll know in which tile you stay.

for example you are in this square.
A_____B _ _|\    |  | | \   |  | Z|  \  |  |   <---- this is a square! not a rectangle!!  :)|   \ |  | |____\| _|_C     D  |__x__||     |

A B C and D are 3 vector(x,y,z), of course..

You are in ABD or in ACD??

1)check position inside tile
float coefX = B.x - position.x;
float coefZ = B.z - position.z;

if (coefX >= coefZ) <---- you are in ABD
D3DXPlaneFromPoints(Plane, A,B,D);
else <---- you are in ACD
D3DXPlaneFromPoints(Plane, A,&v3,&v4);

now you have a plane!!
height = (-position.x * Plane.a - position.z * Plane.c - Plane.d) / Plane.b;

now, you calculate the slope.

ok... maybe there are some errors, but the juice there is...

in this forum there is people with mathematical skill better than mine.

##### Share on other sites
Hmm okay, thx, it's getting a bit more clear now :) Just that I am using OpenGL so no d3dx for me ;) Still though, I was planning to calculate the height and wether it should be blocked by checking the tiles around it. So I have no idea how to go about doing that now.

[Edited by - PinguinDude on June 11, 2007 12:03:14 AM]

Anyone ?

##### Share on other sites
Last Bump. Anyone please ? :)

##### Share on other sites
just replace the d3dx calls with your own planeEquation functions. google for planeEquation.

here:

vec3 AB = p1-3p0;vec AC = p2-p0;	planeEquation.Pn = AB.crossProduct(AC);planeEquation.Pn.normalize();	planeEquation.D = -planeEquation.Pn.dot(p0);

##### Share on other sites
Yes, but I still didn't quite understand what to do after I did calculate the plane heights... :\ I'm sorry but this is all very new to me.

##### Share on other sites

#1. You need a function that takes the X and Z coordinates of your heightmap as integers and returns a Y value as a float.

#2. You need a second function that takes floats and takes X,Z, and scaling information and returns your Y. It should lerp to get the proper height, eg:
// a < b, 0 < x < 1float lerp(float a, float b, float x) {  return (b-a)*x+a;}float getHeighti(int x, int z) {  return something;}float getHeightf(float x, float z, float scaleXZ, float scaleY) {  x /= scaleXZ;  z /= scaleXZ;  int Xa = (int)floor(x);      // x on one side  int Xb = (int)floor(x+1.0f); // x on the other side  int Za = (int)floor(z);      // z on one side  int Zb = (int)floor(z+1.0f); // z on the other side  float Xd = x-floor(x);  if (Xd < 0.0f)    Xd *= -1.0f;  float Zd = z-floor(z);  if (Zd < 0.0f)    Zd *= -1.0f;  float b = lerp(getHeighti(Xa,Zb),getHeighti(Xb,Zb),Xd);  float a = lerp(getHeighti(Xa,Za),getHeighti(Xb,Za),Xd);  return scaleY*lerp(a,b,Zd);}

Ok, now you have some options. I think the easiest one would be something like this:

  float x,z;   // Coordinates now  float x1,z1; // Where they want to go  float rise = getHeightf(x1,z1)-getHeightf(x,z);  float run;   // How far one step is  if (rise/run < some_threshold)    move_player_to(x1,z1);  else    twist_ankle();

##### Share on other sites
Ok, currently I got this code which somewhat works... but it really depends on hte values of the map.. it is far from what I want :( I'm getting really confused and tired of this.

/// MoveEntity. Moves an entity from it's current position to an other position.int EntityManager::MoveEntity(BaseEntity *entity, float speed){	Vector cp, cr, tp, np, op, ha, hb, hc, hd, he, hf, hg, hh, deg;	HeightObject *object = NULL;	frametime_t *timer = engine->GetTimer();	curframe = timer->curtime * 0.001f;	lastframe = timer->lasttime * 0.001f;	if (!entity)		return 1;	// Retrieve entities current position and rotation.	cp = entity->GetPosition();	cr = entity->GetRotation();	// Negative speed or positive speed.	if ((cr.GetZ() > 90) && (cr.GetZ() < 270))		speed = -speed;	// Retrieve vertice position in the map.	if (entities.at(0) != NULL)		object = ((HeightObject*)(entities[0]->GetModel()));	// Calculate new position, check if a hill is steeper than 65 degrees.	tp.SetX( tp.GetX() + ( (sin(cr.GetZ() * ANG2RAD) * RAD2ANG) * (speed * (curframe - lastframe))));	tp.SetZ( tp.GetZ() + ( (cos(cr.GetZ() * ANG2RAD) * RAD2ANG) * (speed * (curframe - lastframe))));	// Get the object's current plane position.	ha = object->GetVertice(Vector(fabs(cp.GetZ() / 20.0f), fabs(cp.GetX() / 20.0f), 0, 0));	hb = object->GetVertice(Vector(fabs(cp.GetZ() / 20.0f) + 1, fabs(cp.GetX() / 20.0f), 0, 0));	hc = object->GetVertice(Vector(fabs(cp.GetZ() / 20.0f) + 1, fabs(cp.GetX() / 20.0f) + 1, 0, 0));	hd = object->GetVertice(Vector(fabs(cp.GetZ() / 20.0f), fabs(cp.GetX() / 20.0f) + 1, 0, 0));	// Get the object's new plane position.	he = object->GetVertice(Vector(fabs(tp.GetZ() / 20.0f), fabs(tp.GetX() / 20.0f), 0, 0));	hf = object->GetVertice(Vector(fabs(tp.GetZ() / 20.0f) + 1, fabs(tp.GetX() / 20.0f), 0, 0));	hg = object->GetVertice(Vector(fabs(tp.GetZ() / 20.0f) + 1, fabs(tp.GetX() / 20.0f) + 1, 0, 0));	hh = object->GetVertice(Vector(fabs(tp.GetZ() / 20.0f), fabs(tp.GetX() / 20.0f) + 1, 0, 0));	// Perform a bilinear interpolation.	float tx = cp.GetX() / 20.0f - float(cp.GetX() / 20.0f);	float ty = cp.GetZ() / 20.0f - float(cp.GetZ() / 20.0f);	float xy = tx * ty;	float h = ha.GetY() * (1.0f - ty - tx + xy)				+ hb.GetY() * (tx - xy)				+ hc.GetY() * xy				+ hd.GetY() * (ty - xy);	np.SetY(h);	// Adjust the Y value so the object is always on top of the terrain.	cp.SetY(np.GetY() + entity->GetModel()->GetBoundingBox().GetMax().GetY());	float txa = tp.GetX() / 20.0f - float(tp.GetX() / 20.0f);	float tya = tp.GetZ() / 20.0f - float(tp.GetZ() / 20.0f);	float xya = txa * tya;	float haa = he.GetY() * (1.0f - tya - txa + xya)				+ hf.GetY() * (txa - xya)				+ hg.GetY() * xya				+ hh.GetY() * (tya - xya);	std::cout << haa << " " << h << " " << h / haa << std::endl;	if (h / haa <= 0.7)	{	// Update our current position.	cp.SetX( cp.GetX() + ( (sin(cr.GetZ() * ANG2RAD) * RAD2ANG) * (speed * (curframe - lastframe))));	cp.SetZ( cp.GetZ() + ( (cos(cr.GetZ() * ANG2RAD) * RAD2ANG) * (speed * (curframe - lastframe))));	}	// Set the new position.	entity->SetPosition(cp);	return 0;}

##### Share on other sites
I've been trying to find a way to allow me to move many units over a height map, but ray tracing the mesh became way to expensive with as many units as I have, and someone thankfully directed me to this thread.

There were a few different ways I saw people doing the math on this, but I decided to go with Bluechip's plane approach. Everything works out great except the values are somehow, just slightly off near the origin, but as I get further away it becomes more apparent.

This is what I'm trying to use now:

//tempPtr is a pointer to a single unit that I am working with at the moment.

D3DXVECTOR3 A, B, C, D;A = B = C = D = D3DXVECTOR3(0.0f, 0.0f, 0.0f);A.x = ((int)(tempPtr->m_position.x / 10)) * 10;A.y = this->m_objectManager.m_map.m_heightMap[(int)(tempPtr->m_position.x/10)][(int)(tempPtr->m_position.z/10) + 1];A.z = ((int)(tempPtr->m_position.z / 10)) * 10 + 10;B.x = ((int)(tempPtr->m_position.x / 10)) * 10 + 10;B.y = this->m_objectManager.m_map.m_heightMap[(int)(tempPtr->m_position.x/10) + 1][(int)(tempPtr->m_position.z/10) + 1];B.z = ((int)(tempPtr->m_position.z / 10)) * 10 + 10;C.x = ((int)(tempPtr->m_position.x / 10)) * 10;C.y = this->m_objectManager.m_map.m_heightMap[(int)(tempPtr->m_position.x/10)][(int)(tempPtr->m_position.z/10)];C.z = ((int)(tempPtr->m_position.z / 10)) * 10;D.x = ((int)(tempPtr->m_position.x / 10)) * 10 + 10;D.y = this->m_objectManager.m_map.m_heightMap[(int)(tempPtr->m_position.x/10) + 1][(int)(tempPtr->m_position.z/10)];D.z = ((int)(tempPtr->m_position.z / 10)) * 10;float coefX = B.x - tempPtr->m_position.x;float coefZ = B.z - tempPtr->m_position.z;D3DXPLANE plane;if(coefX >= coefZ){     D3DXPlaneFromPoints(&plane, &A,&B,&D);}else{     D3DXPlaneFromPoints(&plane, &A,&D,&C);}tempPtr->m_targetPosition.y = (-tempPtr->m_position.x * plane.a - tempPtr->m_position.z * plane.c - plane.d) / plane.b;

I've gone through over and over and checked all of the code(all the math adds up) and I understand and know its all correct up to the point involving the final formula for obtaining the height position. Is it just that this formula isn't correct?

Thanks for any help anyone can give me, I've spent most of the day playing with it. ><

[Edited by - WarisSweet on June 21, 2007 10:00:19 AM]

##### Share on other sites
2PinguinDude

You build terrain as triangles based on hights. So, at any moment your model positioned on single triangle. Than you performe moving. Your moving is plane, as a fact. Let's examine Y as hight. So you move your point in ZX plane. Let's assume your speed in ZX constant (does not depend on plane angle). Then your move is
pos_new = pos_old + Vx*dt + Vy*dt. So you have fraction (pos_old, pos_new). Equation for this fraction is:
pos(t) = pos_old + t*(pos_new-pos_old); where t = {0,1};
After we found our fraction, we should find all triangles we intersect. Remember - intersection is flat! Result of intersection gives us list of such data structures:
struct sItersectionData{
double t; // time of intersection
sTringle triangle; // triangle we were intersected
};
Now we should sort this list by minimum t. That gives us information, what triangles we where intersect first. Let us point, that we have still one triangle, we are not intrested in - triangle we are on! We just drop it from list.
Let's itarate intersections list. Iteration element has triangle. We check that triangle to be too stepp. If it is not too steep - continue iteration. If it is steep enough, we found our stop point. It calcucates from pos(t). For reason to have no problems on the edge, lets assume that stop point is pos(t-delta).
Problem solved.
Here is algo. Now you have to implement intersection function and check function for triangle. Check function is quite easy, but you need some optimisation for interseption function for fast work.
Cheers.

##### Share on other sites

This topic is 3832 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.