   Walking on a terrain in a FPS?
  Hello, I am new to gamedev.net. I have previous experience in OpenGL and am currently programming a Quake style first person shooter in C. I have an OBJ model loader sorted out and the basic camera movement system. I keep running into problems keeping the camera above the terrain (The terrain is stored as an OBJ mesh, but could change). I have tried many times but none have been successful. What is the way that professional games do it? (e.g. Quake, Call of Duty, Battlefield 1942)What is the real name for this topic? I have tried googling things like 'finding height of player on terrain' but with limited results.What is the way that you think I should do it?P.S. I am working on a mac so I can't load heightmaps using glaux.h
  I'd suppose the easiest and straightforward way would be to link the camera to a player which has a bounding box, checked for collisions each frame. In a graph that would equal the camera being a child of player, which has a bounding box or something equivalent to that which does the same trick. Keeping the camera over the terrain is then "just" a question of doing collision detection and response between the bounds and terrain.   ;  You can stick an object on a terrain by using ray tracing. In short you send an line above the player right down and detect where the line intersect with the terrain.You can do this physics yourself or use a third party libraries, such as ODE, Bullet or Newton to name a few of the most popular.If you have an OBJ mesh you use the same vertexes/faces as opengl to build the physics object.   ;  Yes, I did think of both of these methods, but I have had problems with them. I used to use this code:float getFloor(Mesh * mesh , float  x, float y, float z ){vec3D player;int cellx = 0;int celly = 0;int cell;float closest_dist = 2000;int closest_point;int indexref;int cv = 0;cell =  (CELL_SIZE *  (int) (z/CELL_SIZE)) + (int) (x/CELL_SIZE);if (cell < 0)cell = -cell;printf("cell = %i\n", cell);printf("celly = %i\n", celly);player.x = x;player.y = z;while (cv <= grid_list[cell].size) // cycles through all cells{vec3D p1;vec3D p2;vec3D p3;float p1y;float p2y;float p3y;if (sizeof(grid_list[cell].arr[cv]) == 0){return y;printf("No triangles in cell...\n");}printf("grid_list[%i].arr[%i] = %i\n",cell,cv,indexref);indexref = grid_list[cell].arr[cv];p1.x = mesh->verts[indexref];    // p1.y = mesh->verts[indexref+1];  //p1.y = mesh->verts[indexref+2];  //p2.x = mesh->verts[indexref+3];  //p2.y = mesh->verts[indexref+4];  //GET FIRST TRIANGLE ACCORDING TO indexref WHICH IS ONE OF THE TRIANGLES THAT OCCUPY THIS CELLp2y = mesh->verts[indexref+5];  //p3.x = mesh->verts[indexref+6];  //p3.y = mesh->verts[indexref+7];  //p3.y = mesh->verts[indexref+8];  //printf("Getting triangle of index %i with points (%f,%f,%f)(%f,%f,%f)(%f,%f,%f)\n",indexref,p1.x,p1.y,p1.z,p2.x,p2.y,p2.z,p3.x,p3.y,p3.z);if (pointInTriangle(p1, p2, p3, player) == 1){// player is inside this triangleprintf("Player inside triangle...\n");return (p1.y + p2.y + p3.y)/3;}else{cv++;}}printf("There was no triangle...\n");// there was no triangle :(return y;// printf("\n\n --BEGINNING NEW GETFLOOR SESSION-- \n\n");}int pointInTriangle(vec3D A, vec3D B, vec3D C, vec3D P){/* p1 / /   /____ p2    p3  */vec2D point;vec3D AB;vec3D BC;vec3D AC;vec3D AP;vec3D BP;vec3D CP;vec3D cp1;vec3D cp2;vec3D cp3;AP.x = P.x - A.x;AP.y = P.y - A.y;BP.x = P.x - C.x;BP.y = P.y - C.y;AP.x = P.x - A.x;AP.y = P.y - A.y;AB.x = B.x - A.x;AB.y = B.y - A.y;BC.x = B.x - C.x;BC.y = B.y - C.y;AC.x = C.x - A.x;AC.y = C.y - A.y;cp1 = crossprodVec3D(AP, AB);cp2 = crossprodVec3D(BP, BC);cp3 = crossprodVec3D(CP, AC);if ( (cp1.x < 0 && cp2.x < 0 && cp3.x < 0) && (cp1.y < 0 && cp2.y < 0 && cp3.y < 0) )return 1;else if( (cp1.x > 0 && cp2.x > 0 && cp3.x > 0) && (cp1.y > 0 && cp2.y > 0 && cp3.y > 0) )return 1;elsereturn 0;}/* 13 14 15 16 9  10 11 12 5  6  7  8 1  2  3  4^^ playerpos positions^^  */int hash_func( x,  y,  n){return (x*2185031351ul ^ y*4232417593ul) % n;}int getCell(float x, int width){return ((int)(x/width))*width;}void setupLvl(Mesh * mesh){float x1; // x of first point of trianglefloat y1; // y of first point of trianglefloat z1; // z of first point of trianglefloat x2; // x of second point of trianglefloat y2; // y of second point of trianglefloat z2; // z of second point of trianglefloat x3; // x of third point of trianglefloat y3; // y of third point of trianglefloat z3; // z of third point of triangleint cell1x; // cell that the first point belongs inint cell2x; // cell that the second point belongs inint cell3x; // cell that the third point belongs inint cell1z; // cell that the first point belongs inint cell2z; // cell that the second point belongs inint cell3z; // cell that the third point belongs inint csizetemp=0; // size of temporary arrayint x; // used for 'for' while loopsint y; // dittoint xcomy;int cellhash;int counterx = 0;int countery = 0;int occupiedCells[CELL_WIDTH][CELL_WIDTH] [256]; // first two dimensions are the cell, second is the actual list of triangles for that cellint occupiedCellCount[CELL_WIDTH][CELL_WIDTH]; // this is the number of cells a triangle occupies in the cell denoted by the first dimensionint vhash;int indexref = 0; // triange index number// formula is (int)(x/cellsize) *cellsize 10*while (mesh->verts[indexref] != '\0'){x1 = mesh->verts[indexref];    // y1 = mesh->verts[indexref+1];  //z1 = mesh->verts[indexref+2];  //x2 = mesh->verts[indexref+3];  //y2 = mesh->verts[indexref+4];  //GET FIRST TRIANGLEz2 = mesh->verts[indexref+5];  //x3 = mesh->verts[indexref+6];  //y3 = mesh->verts[indexref+7];  //z3 = mesh->verts[indexref+8];  //printf("Getting triangle of index %i with points (%f,%f,%f)(%f,%f,%f)(%f,%f,%f)\n",indexref,x1,y1,z1,x2,y2,z2,x3,y3,z3);//x = 0;// WE NOW HAVE TO SORT A LIST OF ALL THE CELLS THE TRIANGLE OCCUPIEScell1x = getCell(x1,CELL_WIDTH);cell1z = getCell(z1, CELL_WIDTH);cell2x = getCell(x2,CELL_WIDTH);cell2z = getCell(z2, CELL_WIDTH);cell3x = getCell(x3,CELL_WIDTH);cell3z = getCell(z3, CELL_WIDTH);if (cell1x < 0)cell1x = -cell1x;if (cell1z < 0)cell1z = -cell1z;if (cell2x < 0)cell2x = -cell2x;if (cell2z < 0)cell2z = -cell2z;if (cell3x < 0)cell3x = -cell3x;if (cell3z < 0)cell3z = -cell3z;if (occupiedCells[cell1x][cell1z][(occupiedCellCount[cell1x][cell1z])] == '\0')return 2;occupiedCellCount[cell1x][cell1z]++;occupiedCells[cell1x][cell1z][(occupiedCellCount[cell1x][cell1z])] = indexref; // adds this triangle to the occupied cell list of this grid cell. if (cell1x != cell2x && cell1z != cell2z) // if the next point is in the same triangle there's no point in adding it...occupiedCells[cell2x][cell2z][occupiedCellCount[cell2x][cell2z]] = indexref; // adds this triangle to the occupied cell list of this grid cell.if (cell3x != cell2x && cell3z != cell2z && cell1x != cell3x && cell1z != cell3z)occupiedCells[cell3x][cell3z][occupiedCellCount[cell3x][cell3z]] = indexref; // adds this triangle to the occupied cell list of this grid cell.while (x < CELL_GRID) // loop through all cells  { cell1x = ((int)(x1/CELL_WIDTH))*CELL_WIDTH;  // pick cell that first point is in cell1y = ((int)(y1/CELL_WIDTH))*CELL_WIDTH;  if (cell1 < 0) cell1 = -cell1; if (cell1 == x) // the first point is inside the cell we are checking... { NSBeep(); occupiedCells[x][occupiedCellCount[x]] = indexref; //  ... so add it to the list of cells occupied by this triangle! occupiedCellCount[x]++; // increment the count (number of cells that the triangle occupies) }  cell2 = (CELL_SIZE *  (int) (z2/CELL_SIZE)) + (int) (x2/CELL_SIZE); if (cell2 < 0) cell2 = -cell2; if (cell2 == x && cell1 != x) // the second point is inside the cell we are checking... { occupiedCells[x][occupiedCellCount[x]] = indexref; //  ... so add it to the list of cells occupied by this triangle! occupiedCellCount[x]++; // increment the count (number of cells that the triangle occupies) }  cell3 = (CELL_SIZE *  (int) (z3/CELL_SIZE)) + (int) (x3/CELL_SIZE); if (cell3 < 0) cell3 = -cell3; if (cell3 == x && cell2 != x) // the third point is inside the cell we are checking... { occupiedCells[x][occupiedCellCount[x]] = indexref; //  ... so add it to the list of cells occupied by this triangle! occupiedCellCount[x]++; // increment the count (number of cells that the triangle occupies) }   x++; }// now we are finished with this point and have sorted the triangle into occupied cellsy = 0;x = 0;while(x < CELL_WIDTH) // loops through cell's x values{while (y < CELL_WIDTH){xcomy = (y * CELL_WIDTH) + x;grid_list[xcomy].arr =  occupiedCells[x]; // resizes the grid_list array for this cell to the number of triangles that are in the cell.grid_list[xcomy].size = occupiedCellCount[x]; // not releated to above!!!// now copy array from occupiedCells[x] to grid_list[x].arr grid_list[xcomy].arr = (int *)calloc(occupiedCellCount[x][y], sizeof(int));memcpy(grid_list[xcomy].arr, occupiedCells[x][y], occupiedCellCount[x][y]);y++;}y = 0;x++;}// now we're finished with occupiedCells!!!!! (this is deleted anyway at the end of the functionx = 0;indexref += 9;}// at this point we have a nice list (occupiedcells[]) of cells that the triangle occupies!!!!! And, the list doesn't contain any duplicates!}I think the problem is with the point in triangle function but I can't find another way of doing this? Please feel free to use this code.   ;  im working on an fps game as well. well not just a shooter due to sword play, but you get the point,  my approach was to set the camera to the players coordinates, with the y a few units above the player, and for collision, all i did was:if (player.y <= obj.y){player.y = obj.y;}if your using some other other floor effect like me such as tiling, i did this:if (player.y <= obj.y && player.x <= obj.x + obj.length/2 && player.x >= obj.x - obj.length/2 && player.z <= obj.z + obj.width/2 && player.z >= obj.z - obj.width/2){player.y = 0bj.y;}if you are using a height map, then average the y of the vertices surrounding the player or use another method and convert the vertices to quads and do the like.please note that there is more to my code.  i have a boolean jump status so if the player touches the ground, i set it to false to enable jumping again.   ;  I've always used something like:xCell = floor(pos.x/cellSize);zCell = floor(pos.z/cellSize);this gives you the position in the grid, then to get the height at the specific part of the cell you're in, use something like (psudocode)xHeight = heightOfLeftSideOfCell + ( (heightOfRightSideOfCell - heightOfLeftSideOfCell) * percentThroughCell);do the same for the zHeight using heightOfBackSideOfCell, and heightOfFrontSideOfCell, then take the average of xHeight and zHeight, or the min.   ;  Good idea but How would I find the height of the left cell?   ;  Well the data for the model has to be stored somewhere, right?  There's a fair chance that it's simply a square grid.  Are you loading the .obj yourself? or using a model loader of some sort?Looking at the code you posted, it looks like you're trying to pinpoint an exact coordinate, when a much simpler task would be to pinpoint the grid cell you're in, and iterpolate to get the height.for instance, say you use a linear list of triangles to represent a 2D terrain grid, with 2 triangles per quad.now say you want to find the cell at (25x, 34z) (completely arbitrary by the way).  Assuming you're going left to right, far to near, the triangles that make this cell will be found at triangleList [ (trisPerQuad * gridWidth * 34) + (trisPerQuad *  25)] andtriangleList [ (trisPerQuad * gridWidth * 34) + (trisPerQuad *  25) + 1].  you then get the heights from these triangles, depending on how they're ordered and wound, and you interpolate and average between them.EDIT: Keep in mind that's all untested, ballpark stuff, but it gives you a rough idea how to go about that.   ;  One of the easier ways to accomplish this is by casting a ray down from the camera position towards the ground and get the distance to the ground from that position. If that distance is smaller than the wanted distance you move the player up, if it's bigger than you move the player down. So what you'd have to do is something like this:for every triangle in the map{   //project camera position in the 0,-1,0 direction on the triangle plane   if the point lies in the triangle   {   //check if this is the smallest or the first distance you've found and if so store it   }}//move camera in y direction by 'wanted distance from ground' - 'distance found'this will put your camera on the 'ground', you could put a cap on the maximum distance you can go down to simulate gravity.A link you will find interesting is this one. It's more advanced and harder to implement but that's kinda how it's done in most FPS games. It also contains some code to project a point on a plane.   ;Quote:Original post by mikenovemberoscarYes, I did think of both of these methods, but I have had problems with them. I used to use this code:*** Source Snippet Removed ***I think the problem is with the point in triangle function but I can't find another way of doing this? Please feel free to use this code.First problem is that you appear to be assigning p1.x, p1.y, and p1.y (the last one should be p2.z, right?).  Same for p2 and p3.  Once you fix this, though, you have another problem.Your getFloor function returns the average heights of the triangle vertices regardless of *where* the point is inside the triangle.  When the point is near the vertex of maximum height, your getFloor function will underestimate the height.You should compute the barycentric coordinates of the point P relative to the triangle vertices V0, V1, and V2.  That is, (P.x,P.y) = b0*(V0.x,V0.y) + b1*(V1.x,V1.y) + b2*(V2.x,V2.y) where b0 + b1 + b2 = 1.  P is inside the triangle when b0 >= 0 and b1 >= 0 and b2 >= 0.  The height at P is P.z = b0*V0.z + b1*V1.z + b2*V2.z.